08 信号量与管程 | 《操作系统》笔记
这一系列是操作系统 (清华大学向勇、陈渝)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。
信号量
- 抽象数据类型
- 一个整型(sem)，两个原子操作
- P(): sem 减 1，如果 sem<0，等待，否则继续
- V(): sem 加 1，如果 sem<=0，唤醒一个等待的 P
- 信号量类似铁路
- 初始化 2 个资源控制信号灯
信号量使用
- 信号量是有符号整数
- 信号量是被保护的变量
- 初始化完成后，唯一改变一个信号量的值的办法是通过 P() 和 V()
- 操作必须是原子
- P() 能够阻塞，V() 不会阻塞
- 我们假定信号量是“公平的”
- 在实践中，FIFO 经常被使用
- 两种类型信号量
- 二进制信号量：可以是 0 或 1
- 一般/计数信号量：可取任何非负值
- 两者相互表现（给定一个可以实现另一个）
- 信号量可以用在 2 个方面
- 互斥
- 条件同步（调度约束：一个线程等待另一个线程的事情发生）
- 调度约束：一个线程等待另一个线程处理事情
- 比如生产东西或消费东西
- 互斥（锁机制）是不够的
- 例子：有界缓冲区的生产者——消费者问题
- 一个或多个生产者产生数据将数据放在一个缓冲区里
- 单个消费者每次从缓冲区取出数据
- 在任何一个时间只有一个生产者或消费者可以访问该缓冲区
- 正确性要求
- 在任何一个时间只能有一个线程操作缓冲区（互斥）
- 当缓冲区为空，消费者必须等待生产者（调度/同步约束）
- 当缓存区满，生产者必须等待消费者（调度/同步约束）
- 每个约束用一个单独的信号量
- 二进制信号量互斥
- 一般信号量 full Buffers
- 一般信号量 empty Buffers
信号量的实现
- 信号量的双用途
- 互斥和条件同步
- 但等待条件是独立的互斥
- 读/开发代码比较困难
- 程序员必须非常精通信号量
- 容易出错
- 使用的信号量已经被另一个线程占用
- 忘记释放信号量
- 不能够处理死锁问题
管程（monitor）
- 什么是管程？
- 一个锁：指定临界区
- 零个或者多个条件变量：等待/通知线程，用于管理并发访问共享数据（线程挂在条件变量上）
- 一般方法
- 收集在对象/模块中的相关共享数据
- 定义方法来访问共享数据
- Lock
- Lock::Acquire() 等待直到锁可用，然后抢占锁
- Lock::Release() 释放锁，唤醒等待者
- 条件变量
- 允许等待状态进入临界区
- 令允许处于等待（睡眠）的线程进入临界区
- 某个时刻原子释放锁进入睡眠
- Wait() operation
- Signal() operation or broadcast() operation
- 实现
- 需要维持每个条件队列
- 线程等待的条件等待 signal()
- 使用管程解决生产者消费者问题
- 线程获得 lock 才可以进入管程，如果需要的资源得不到满足，就挂在条件变量上并释放 lock
经典同步问题
- 读者写者问题
- 动机
- 共享数据的访问
- 两种类型使用者
- 读者：不需要修改数据
- 写者：读取和修改数据
- 问题的约束
- 允许同一时间有多个读者，但在任何时候只有一个写者
- 当没有写者时读者才能访问数据
- 当没有读者和写者时写者才能访问数据
- 在任何时候只能有一个线程可以操作共享变量
- 读者优先与写者优先
- 基于读者优先策略的方法：只要有一个读者处于活动状态，后来的读者都会被接纳，如果读者源源不断地岀现的话，那么写者就始终处于阻塞状态
- 基于写者优先策略的方法：一旦写者就绪，那么写者会尽可能快地执行写操作，如果写者源源不断地岀现的话，那么读者就始终处于阻塞状态
- 共享数据
- 数据集
- 信号量 CountMutex 初始化为 1
- 信号量 WriteMutex 初始化为 1
- 整数 Count 初始化为 0
- 实现
- 读者优先
- 写者优先
- 读者优先
- 动机
- 哲学家就餐问题
- 方案一
- 方案二
- 方案三
- 方案四
- 缺点：它把就餐（而不是叉子）看成是必须互斥访问的临界资源，因此会造成（叉子）资源的浪费，从理论上说，如果有五把叉子，应允许两个不相邻的哲学家同时进餐
- 计算机解决方案：状态是资源而不是叉子是资源
08 信号量与管程 | 《操作系统》笔记