（三）进程同步
1. 同步与互斥的基本概念
1.1. 两种形式的制约关系
间接相互制约：源于 OS 中的资源共享；
- 例：两个进程 A, B 同时申请打印机，规定若 A 申请时 B 已在使用，则 A 阻塞，直至 B 使用完毕再将打印机分配给 A；
直接相互制约：源于进程之间的合作关系；
- 例：进程 A 要向 B 输入数据，规定缓冲区空时，B 读取数据会阻塞，直至缓冲区来数据；缓冲区满时，A 写入数据会阻塞，又称为 “同步”；
2. 临界资源（Critical Resource）
在进程间需要采取互斥的方式共享的资源，有软件和硬件两种；
软件：如共享变量；
硬件：如打印机等；
3. 临界区（Critical Section）
每个进程中，访问临界资源的代码段称为临界区；
进程进入临界区的步骤：
检查临界资源是否正在被访问；
若未被访问，则进入临界区，同时置位访问标志；
退出临界区时，复位访问标志；
进入临界区之前执行的代码称为进入区，退出后执行的代码称为退出区
4. 同步机制应该遵循的原则
注意：区分 “应该” 和 “必须”；
四条准则：
空闲让进（应该 + 必须）；
忙则等待（应该 + 必须）；
有限等待（应该 + 必须）；
让权等待（应该）；
- 指进程因为临界资源被占用而不能访问时，应让出 CPU 使用权进行等待；
5. 同步/互斥基本的实现方法
5.1. 开/关中断
实现互斥最简单的方法之一；
内容：
检查互斥锁，此时要关闭 OS 中断，检查完成并上锁后才打开中断；
进程在临界区执行期间，OS 不响应中断，从而不会引发调度和进程切换；
缺点：
滥用关中断功能可能造成严重后果；
关中断时间过长，会影响 OS 效率；
不适用于多 CPU 系统；
5.2 利用 Test-and-Set（TS）指令
TS 是硬件指令，以下用 C 语言来模拟其原理和使用；
代码示意：
规定
lock = true为上锁，lock = false为没上锁；TS 函数的功能：返回当前锁的值，同时如果当前没上锁，则上锁；
使用 lock：
- 此方式没有实现让权（
while语句会一直占用 CPU）；
- 此方式没有实现让权（
5.3. 利用 Swap 指令
Swap 为硬件指令，在 Intel 8086 中又称为 XCHG 指令，用于交换两个字的内容；
代码模拟示意：
- 此方式也没有实现让权；
6. 锁（Lock）
- 整型变量，0 表示空闲，1 表示忙（占用）；
7. 信号量（Semaphore）（⭐）
7.1. 整形信号量
Dijkstra 定义：一个表示资源数量的整形量 S。初始化后，仅能通过两个标准的原子操作来访问：
两个原子操作：
wait(S)和signal(S)；也称为 P, V 操作；
wait和singal操作的代码模拟示意：
两个操作都是原子操作，执行中不可被打断；
wait：等待并索取信号量S = S - 1使资源可用量减 1；signal：释放信号量，释放 1 单位资源，即S = S + 1；
缺点：
while (S <= 0) {}会占用 CPU，没有实现让权等待；
7.2. 记录型信号量
解决进程等待时会一直进行判断，占用 CPU 的问题（即 “忙等”）；
定义信号量结构体，除表示资源数目的整数
value外，加入一个链表存储所有正在等待的进程；代码模拟示意：
更改相应的
wait和signal操作：
性质：
value的初始值表示 OS 某类资源的数目，因而又称为资源信号量；value > 0时，表示有空闲资源；value <= 0时，表示资源已经分配完了，其绝对值为正在等待的进程数；value初值为 1，表示同时只允许一个进程访问，此时信号量转为互斥信号量；
7.3. AND 型信号量
将进程所需的若干临界资源，按照原子操作的方式：要么全部分配给进程，要么一个也不分配；
在
wait中，增加 “与” 逻辑，称为 AND 同步、swait，对应的ssignal；代码示意（仅要求理解）
7.4. 信号量的应用
实现进程的互斥
设置一初值为 1 的互斥信号量 mutex；
将进程的临界区 CS 置于
wait(mutex)和signal(mutex)操作之间即可；
实现前趋关系（同步关系）
案例：两个并发进程
， 里有语句 ， 有语句 ，现希望先执行 ，再执行 ； 方案：定义一个初值为 0 的共享信号量
S，在后插入 signal(S)，之前插入 wait(S)即可；- 初值为 0 的作用：使得
即使先执行也一定会阻塞；
- 初值为 0 的作用：使得
8. 条件变量（Condition Variables）
8.1. 管程
定义：管程 = 一个数据结构 + 能被并发进程所执行的一组操作；
类似于 OOP 中类（Class）的概念，封装了共享资源和对这些资源的操作和同步机制；
共享资源
成员变量； 同步机制
私有方法，对外不可见； 资源操作
公共方法，给进程提供的资源操作接口；
组成部分：(1) 名称；(2) 共享数据的结构说明；(3) 一组操作共享数据的方法；(4) 设置共享数据初值的语句；
- 对应类的概念：类名，成员变量，成员方法，构造函数；
8.2. 条件变量
管程内部，用于管理进程的阻塞与唤醒的变量，形式为
condition x；其操作（成员方法）仅有
wait和signal，类似于信号量的两个方法**（不等同！）**；x.wait：正在调用管程的进程因 x 条件需要被阻塞或挂起，则调用x.wait将自己插入到 x 条件的等待队列上，并释放管程，直到 x 条件变化。此时其它进程可以使用该管程；x.signal：正在调用管程的进程发现 x 条件发生了变化，则调用x.signal，重新启动一个因 x 条件而阻塞或挂起的进程，若没有，则不起任何作用（与信号量的signal不同，没有S = S + 1的操作）；
条件变量
x可以理解为 “被阻塞的某个原因”，x的阻塞队列上的进程都是因为此原因而阻塞；- 例：因为共享数据被占用而调用进程需要等待，此条件变量为
condition nonbusy；
- 例：因为共享数据被占用而调用进程需要等待，此条件变量为
9. 经典同步问题
- 具有代表性的 3 个问题：(1) 生产者—消费者问题，(2) 读者—写者问题，(3) 哲学家进餐问题；
9.1. 生产者—消费者问题
描述： 有一群生产者进程在生产产品，并将这些产品提供给消费者进程进行消费。两者之间有一个具有 n 个缓冲区的缓冲池，生产者可向一个缓冲区放入一个产品，消费者可从一个缓冲区取走一个产品。规定生产者和消费者之间必须保持同步，即缓冲区为空时，不允许消费者取用，缓冲区已满时，不允许生产者再放入；
利用记录型信号量解决
利用 1 个互斥信号量 mutex实现对缓冲池的互斥访问；
利用 2 个信号量 empty 和 full 表示缓冲池中空缓冲区和满缓冲区的数量；
empty 信号量约束生产者放入产品的行为，此时生产者 wait，消费者 wakeup；
full 信号量约束消费者取走产品的行为，消费者 wait，生产者 wakeup；
伪代码示意（实际上外层都有个
while(true)反复执行）
9.2. 哲学家进餐问题
描述：5 个哲学家坐在桌子边，桌上有 5 个碗和 5 根筷子。哲学家交替地思考和进餐：进餐时拿起两边的筷子，只有拿到 2 根筷子才能进餐；进餐完毕后又放下筷子继续思考。
- 注：圆形桌，5 个碗对应 5 个哲学家，5 根筷子放在相邻哲学家中间；
利用记录型信号量解决
每根筷子对应一个互斥信号量；
伪代码示意**（有问题的版本⚠）**：
问题：考虑 5 个哲学家同时开始进餐，则按照代码顺序，每个哲学家都会占用左边的筷子并一直等待右边的筷子，没有人释放筷子，导致死锁。
解决方案：增加一个约束信号量
max_eating = 4，表示同一时刻至多允许 4 位哲学家开始进餐，从而始终能保证有一人能拿到两边的筷子，开始进餐并最终释放筷子；
改进后的伪代码示意：
9.3. 读者—写者问题
描述：一个文件可被多个进程共享，只读取该文件的进程称为读者进程，会写入该文件的进程称为写者进程。为防止多个进程同时操作可能导致的混乱，规定同时只能有以下情况存在：(1) 同时存在多个读者进程；(2) 同时存在一个写者进程。即不允许读者和写者同时存在，也不允许多个写者同时存在；
利用互斥信号量解决；
用 1 个互斥信号量 mutex 约束读者和写者的同时访问；
设置共享变量 ReadCount 表示正在读取的进程数目，约束写者进程；
对于多个读者的情况，只要 ReadCount 不为 0，表示已经有读者，则此时新读者无需操作 mutex；否则需要先锁住 mutex。对于读者进程的释放，同理：仅当 ReadCount 减 1 后变为 0 时，才需要释放 mutex；
对于 ReadCount，也要用一个互斥信号量 rmutex 来保证同步；
伪代码示意：
此算法为读者优先：若写者到来前已经存在读者，则在写者后面到的读者也能先访问文件；
改进方法 1（公平队列）：所有进程按照到来的先后次序排成一队，保证写者后面的读者不会抢占文件；
改进方法 2（写者优先）：在方法 1 的基础上提升写者的次序，适合经常需要更新的文件；