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

进程的并发执行可能导致结果不确定，甚至出现错误（如打印机）。并发执行的多个进程，都是独立地和异步地向前推进，彼此间似乎互不相关，但实际上每个进程在其运行过程中总是存在着某种间接或直接的制约关系，直接制约关系即为同步，间接制约关系即为互斥。同步与互斥问题同样适用于线程，因为它们共享地址空间，又经常协调共同完成任务。

1. 互斥和同步问题⚓

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

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

互斥是一种特殊的同步：逐次使用互斥资源，也是对进程使用资源次序上的一种协调。

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

一般代码的大致划分：

进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志。
临界区(critical section)：进程中访问临界资源的代码片断。
退出区(exit section)：将“正在访问临界区”标志清除。
剩余区(remainder section)：代码中的其余部分。

使用临界区的原则：

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

这样做的目的是保证使用临界资源的进程能够正确和高效地进行协作，避免竞争条件。竞争条件(race condition)：两个或多个进程访问某些共享资源，最终结果取决于进程运行的精确时序。

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

常见方法有：锁变量、轮转法、Peterson 算法、硬件方法——禁止中断、硬件指令方法。

锁变量

设置共享锁变量 lock ，初值为0代表没有进程在临界区，值为1代表有进程在临界区。进程在进入临界区前循环等待 lock 变为0，进入临界区后将 lock 置为1，退出临界区后将 lock 置为0。例如：

C

while (lock == 1); // 等待
lock = 1; // 进入临界区
// 临界区代码
lock = 0; // 退出临界区
// 非临界区代码

问题：共享变量 lock 本身可能成为竞争访问的对象。例如：存在违反条件2的可能，一个进程 P1 检测到 lock 为0后，进入临界区前刚要把 lock 置为1，突然发生中断，CPU 调度另一个进程 P2 执行，P2 也检测到 lock 为0后进入临界区，而 P1 再次运行时会直接进入临界区，导致两个进程同时进入临界区。另外，也会导致忙等待，因为存在 while 循环，违反条件4。

忙等待

忙等待(busy waiting)：连续测试一个变量直到出现某个值为止。忙等待非常浪费CPU时间，所以应该尽量避免，只有等待时间非常短的情况下才使用忙等待。用于忙等待的锁，称为自旋锁(spin lock)。

轮转法

设置整型变量 turn ，记录该轮到哪个进程进入临界区。初值为0表示轮到进程 P0 进入临界区，值为1 表示轮到进程 P1 进入临界区。每个进程在进入临界区前将 turn 置为自己的编号，表示自己要进入临界区。无法进入临界区的进程处于就绪态，等待调度器分配下一个时间片。例如：

C

// 进程 P0
while (turn != 0); // 等待
// 临界区代码
turn = 1; // 退出临界区
// 非临界区代码


// 进程 P1
while (turn != 1); // 等待
// 临界区代码
turn = 0; // 退出临界区
// 非临界区代码

从软件上保证了任何时刻最多只有一个进程位于临界区。但是该算法要求进程严格按照顺序进入临界区，可能违反条件1（进程不在临界区且不需要访问共享资源时，不能妨碍其他进程进入临界区），例如该轮到进程 P1 进入临界区，但是进程 P1 在忙其他工作，进程 P0 想要进入但是没有轮到它，只能一直等待，即“想进的人没有资格，而有资格进的人又不想进”，造成资源浪费。另外，也存在程序代码不对称、忙等待的问题。

Peterson 算法

设置整形变量 turn 和数组 interested ， turn 表示轮到哪个进程进入临界区，数组 interested 表示进程是否想要进入临界区。当进程想进入临界区时，先调用 enter_region 函数，判断是否能安全进入，不能的话等待;当进程从临界区退出后，需调用 leave_region 函数，允许其它进程进入临界区。例如：

C

// 进程 P0
enter_region(0); // 进入临界区
// 临界区代码
leave_region(0); // 退出临界区
// 非临界区代码


// 进程 P1
enter_region(1); // 进入临界区
// 临界区代码
leave_region(1); // 退出临界区
// 非临界区代码


int turn = 0;
int interested[2] = {0, 0};
void enter_region(int i) {
    interested[i] = TRUE; // 表示进程 i 想进入临界区
    turn = i;
    while (turn == i && interested[1 - i] == TRUE); // 等待，直到另一个进程不想进入临界区或轮到自己
}
void leave_region(int i) {
    interested[i] = FALSE; // 退出临界区
}

只有当 turn == other 或 interested[other] == FALSE 时，本进程才能进入临界区。如果 other 已经在临界区中，那么 interested[other] == TRUE 并且 turn == i，因此本进程只能在 while 循环上忙等，无法进入临界区，但同时该进程也在不断检查条件，占用 CPU 资源。

考虑极端情况，两个进程几乎同时希望进入临界区，此时 while 循环中的 interested[other] == TRUE 成立，但是 turn == i 只可能对一个进程成立，turn 的取值为后一个修改 turn 变量的进程号（前一个的进程号被覆盖），因此后一个进程在 while 循环上忙等，前一个进程进入临界区。这是合理的，先要进入临界区的进程进入，后要进入临界区的进程等待。

优点是解决了互斥访问的问题，而且克服了轮转法的缺点，可以正常地工作。缺点是仍然存在忙等待。

硬件方法——禁止中断

进入临界区前执行“关中断”指令，忽略其他进程的中断请求（主要是 I/O 中断）；离开临界区后执行“开中断”指令。这样只有在发生时钟中断或其他中断时才会进行进程切换。因为操作系统主要是靠中断驱动的，只有发生中断时操作系统才能获得控制权，进行进程调度。

优点是实现简单。缺点是把禁止中断的权利交给用户进程，导致系统可靠性较差，且只适用于单 CPU 系统，不适用于多处理器。

硬件指令方法

利用处理机提供的专门的硬件指令，对一个字的内容进行检测和修改。硬件方法的目的是解决共享变量的完整性和正确性，其读写操作由单条指令完成，因此保证读操作与写操作不被打断。

优点是：适用于任意数目的进程；实现简单，容易验证其正确性；可以支持进程中存在多个临界区，只需为每个临界区设立一个布尔变量。缺点是：仍有忙等待，耗费 CPU 时间。

优先级反转问题

忙等待不仅浪费CPU时间，而且可能导致优先级反转问题(priorityinversion problem)。

考虑两个进程 P1,P2，且 P1 的优先级高于 P2.假设调度规则规定，只要 P1 处于就绪态它就可以运行。若某一时刻 P2 处于临界区中，此时 P1 变成就绪态并被调度，从而开始忙等待，但是由于 P1 的优先级高于 P2，使得 P2 不会被调度，也就无法离开临界区，造成死锁。

3. 信号量⚓

以上讨论的锁变量、Peterson 算法等，都有忙等待的缺陷，并且都是基于“多个进程，同一时刻临界区最多允许一个进程进入”的问题，但是无法解决“多个进程，同一时刻临界区最多允许 N 个进程进入”的更复杂问题。信号量(semaphore)是为了解决这个问题而提出的。

信号量 s 包括一个整数值 s.count (计数)，以及一个进程等待队列 s.queue，队列中是阻塞在该信号量上的各个进程的标识。信号量只能通过初始化和两个标准的原语来访问，作为 OS 核心代码执行，不受进程调度的打断。初始化时必须指定一个非负整数表示空闲资源个数。原语其实是一个操作系统提供的函数，是原子操作，执行过程中不会被中断打断。

s.count>0 表示有 count 个资源可用。s.count=0 表示无资源可用。s.count<0 则 count 的绝对值表示 s 等待队列中的进程个数。上述形式的信号量称为资源信号量，如果信号量的取值只有0和1，只用于对临界资源的互斥访问，则称为互斥信号量(mutex semaphore)。

PV 原语：

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

PV 原语的实现示例：

C

P(s) {
    s.count--; // 申请资源
    if (s.count < 0) { // 没有资源可用
        // 阻塞当前进程，将其加入等待队列 s.queue
    }
}

V(s) {
    s.count++; // 释放资源
    if (s.count <= 0) { // 有进程在等待
        // 从等待队列 s.queue 中唤醒一个进程，将其加入就绪队列
    }
}

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

C

P(mutex); // 进入临界区
// 临界区代码
V(mutex); // 退出临界区
// 非临界区代码

进程执行的顺序问题（一个最简单的进程同步问题）：并发执行的进程 P1,P2 中，分别有代码 C1,C2，要求 C1 在 C2 之前完成。解决方法是：为每个前趋关系设置一个互斥信号量 S12，其初值为0。例如：

C

// 进程 P1
// 代码段 C1
V(S12); // C1 完成，唤醒 P2

// 进程 P2
P(S12); // 等待 P1 完成
// 代码段 C2

又例如：进程 P1,P2,P3 中，P1,P2 可以并发执行，而 P3 必须等待 P1,P2 都完成才能执行。可以设置两个互斥信号量 S12,S23，初值均为0。

C

// 进程 P1
// 代码段 C1
V(S13); // C1 完成，唤醒 P3

// 进程 P2
// 代码段 C2
V(S23); // C2 完成，唤醒 P3

// 进程 P3
P(S13); // 等待 P1 完成
P(S23); // 等待 P2 完成
// 代码段 C3

PV 原语使用注意：

必须成对使用 P 和 V 原语，不能重复或遗漏。遗漏 P 原语则不能保证互斥访问，遗漏 V 原语则不能在使用临界资源之后将其释放。
当为互斥操作时，P,V 原语处于同一进程。当为同步操作时，P,V 原语不在同一进程中出现。
PV 原语的次序至关重要。如果 P(S1) 和 P(S2) 两个操作在一起，那么 P 操作的顺序至关重要，一个同步 P 操作与一个互斥 P 操作在一起时必须同步 P 操作在前、互斥 P 操作在后，因为一个进程需要先等待其他进程完成某个操作（同步），然后才能进入临界区访问共享资源（互斥）。2个 V 操作顺序无关紧要。
理解：P 就相当于阻塞，我们通常可以假定进程执行 P 操作时会被阻塞，需要等待。而 V 操作就相当于另外一个进程把阻塞在这个信号量的进程唤醒。

4. 经典 IPC 问题⚓

IPC(Inter-ProcessCommunication)，进程间通信，解决进程间竞争共享资源引起的同步-互斥问题。

示例：生产者-消费者问题，读者-写者问题，哲学家进餐问题，睡眠理发师问题。

5. 管程⚓

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

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

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

管程的特点：

模块化：一个管程是一个基本程序单位，可以单独编译。
抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码。
信息封装：进程可调用管程中实现的某些过程(函数) ，至于这些过程是怎样实现的，在其外部则是不可见的。
引入管程可提高代码的可读性，便于修改和维护，正确性易于保证。

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

管程是用于管理资源的，当进入管程的进程因资源被占用等原因不能继续运行时，应当释放管程的互斥权，即将等待资源的进程加入资源等待队列。资源等待队列可以由多个，每种资源一个队列，资源等待队列由条件变量维护。

条件变量(condition variables)是管程内的一种数据结构，且只有在管程中才能被访问，它对管程内的所有过程是全局的，只能通过 wait 和 signal 两个原语操作来控制。

wait(c)：调用进程阻塞并移入与条件变量 c 相关的等待队列中，并释放管程，直到另一个进程在该条件变量 c 上执行 signal() 唤醒等待进程并将其移出条件变量 c 队列。
signal(c)：如果 c 链为空，则相当于空操作，执行此操作的进程继续；否则唤醒 c 链中的第一个等待者。

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

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

管程的缺点：管程是一个编程语言概念，编译器必须要识别管程并用某种方式对其互斥做出安排。Java, Pascal, Modula-2等语言支持管程，而 C, C++及多数语言不支持管程，也没有信号量，但是支持信号量十分容易，编译器甚至不需知道它们的存在，因为信号量是 OS 机制，系统只需提供相应系统调用即可。

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