第 5 讲互斥和同步 (1) ¶

about 1833 words reading time 9 minutes

1. 互斥和同步问题 ¶

同步：指系统中一些进程需要相互合作，共同完成一项任务，这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步。产生原因为：进程合作。并发进程在一些关键点上可能需要互相等待与互通消息，进程间的相互联系是有意识的安排的。

互斥：指若干个进程同时竞争一个需要互斥使用的资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到该资源被释放。进程间要通过某种中介发生联系，是无意识安排的。产生原因：资源共享。

系统中某些共享资源一次只允许一个进程使用，为临界资源 (critical resource)。硬件：打印机、光盘刻录机，软件：只能互斥访问的变量、表格、队列。并非所有共享资源都是临界资源，如只读数据。

进入区 (entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志。

临界区 (critical section)：进程中访问临界资源的代码片断。

退出区 (exit section)：将“正在访问临界区”标志清除。

剩余区 (remainder section)：代码中的其余部分。

使用临界区的原则：

空闲让进——当无进程在临界区时，任何有权使用临界区的进程可以进入。
忙则等待——不允许两个以上的进程同时进入临界区。
有限等待——任何进入临界区的要求应在有限的时间内得到满足。
让权等待——不能进入临界区的进程应放弃占用 CPU。

2. 临界区互斥问题的算法 ¶

锁变量。轮转法。Peterson 算法。硬件方法——禁止中断。硬件指令方法。

3. 信号量 ¶

每个信号量 s 包括一个整数值s.count ( 计数 )，以及一个进程等待队列 s.queue，队列中是阻塞在该信号量上的各个进程的标识。信号量只能通过初始化和两个标准的原语来访问，作为 OS 核心代码执行，不受进程调度的打断。

s.count>0 表示有 count 个资源可用。s.count=0 表示无资源可用。s.count<0 则 count 绝对值表示 s 等待队列中的进程个数。

PV 原语：P 操作表示申请一个资源，它使信号量减 1，如果信号量小于 0，则进程被阻塞而不能进入临界区。V 操作表示释放一个资源，它使信号量增 1，如果信号量不大于 0，则唤醒一个被阻塞的进程。

为临界资源设置一个互斥信号量 mutex(MUTualExclusion)，初值为 1。在每个进程中将临界区代码置于 P(mutex) 和 V(mutex) 原语之间。

注意：必须成对使用 P 和 V 原语，不能重复或遗漏。当为互斥操作时，P 和 V 原语同处于同一进程。当为同步操作时，P 和 V 原语不在同一进程中出现。

4. 经典 IPC 问题 ¶

IPC(Inter-ProcessCommunication)，进程间通信，解决进程间竞争共享资源引起的同步 - 互斥问题。如：生产者 - 消费者，读者 - 写者，哲学家进餐，睡眠理发师。

5. 管程 ¶

信号量的缺点：用信号量可实现进程间的同步和互斥，但由于信号量的控制分布在整个程序中，其正确性分析很困难

同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁 ( 如 P、V 操作的次序错误、重复或遗漏 )。
易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统中并发执行的各个程序。
不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局。
正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误。

管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。基本思想是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的过程 ( 函数 ) 来间接地访问管程中的共享变量。

典型的处理方法：当一个进程调用管程过程时，该过程将检查在管程中是否有其他活跃进程。如果有，调用进程将被阻塞，直到另一个进程离开管程而将其唤醒；如果没有，则该调用进程可以进入。因为管程是互斥进入的，所以当一个进程试图进入一个已被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。

管程是用于管理资源的，当进入管程的进程因资源被占用等原因不能继续运行时应当释放管程的互斥权，即将等待资源的进程加入资源等待队列。资源等待队列可以由多个，每种资源一个队列。资源等待队列由条件变量维护。条件变量 (condition variables) 是管程内的一种数据结构，且只有在管程中才能被访问，它对管程内的所有过程是全局的，只能通过 wait 和 signal 两个原语操作来控制。

wait(c)：调用进程阻塞并移入与条件变量 c 相关的等待队列中，并释放管程，直到另一个进程在该条件变量 c 上执行 signal() 唤醒等待进程并将其移出条件变量 c 队列。

signal(c)：如果 c 链为空，则相当于空操作，执行此操作的进程继续；否则唤醒 c 链中的第一个等待者。

当一个进入管程的进程执行唤醒操作时 ( 如 P 唤醒 Q)，管程中便存在两个同时处于活动状态的进程。处理方法有两种：P 等待，Q 继续，直到 Q 退出或等待 (Hoare)。或规定唤醒为管程中最后一个可执行的操作 (Hansen) 紧急等待队列。

假设进程 P 唤醒进程 Q，则 P 等待 Q 继续。如果进程 Q 在执行时又唤醒进程 R，则 Q 等待 R 继续，......，于是，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。

第 5 讲 互斥和同步 (1) ¶