2.3.5 经典同步问题
1. 生产者-消费者问题
问题描述：
系统中存在一组生产者进程和一组消费者进程，它们共享一个初始为空、容量为 的缓冲区。生产者每次生产一个产品，并将其放入缓冲区；消费者每次从缓冲区取出一个产品并进行消费。该问题需满足以下约束条件：仅当缓冲区未满时，生产者才能写入产品，否则必须等待；仅当缓冲区非空时，消费者才能读取产品，否则必须等待；缓冲区是临界资源，所有进程必须互斥访问。
问题分析：
关系分析。由于缓冲区是共享的临界资源，生产者与消费者对缓冲区的访问构成互斥关系；同时，消费者必须等待生产者生成产品后才能消费，二者又存在同步关系。思路梳理。使用一个互斥信号量控制对缓冲区的互斥访问；使用两个计数信号量分别跟踪空缓冲区和满缓冲区的数量；并严格控制P和V操作的执行顺序，以避免死锁。信号量设置。互斥信号量mutex，控制对缓冲区的互斥访问，初值为1；计数信号量empty，记录空缓冲区的数量，初值为 ；计数信号量full，记录满缓冲区的数量，初值为0。
生产者-消费者进程的实现如下：
// 互斥访问缓冲区semaphore mutex = 1;// 空缓冲区数量semaphore empty = n;// 满缓冲区数量semaphore full = 0;
// 生产者进程producer() { while (1) { 生产一个产品 P(empty); // 申请一个空缓冲区 (要用什么，P一下) P(mutex); // 进入临界区 (互斥夹紧) 将产品放入缓冲区 V(mutex); // 退出临界区 (互斥夹紧) V(full); // 满缓冲区数加1 (提供什么，V一下) }}
// 消费者进程consumer() { while (1) { P(full); // 申请一个满缓冲区 P(mutex); // 进入临界区 从缓冲区中取出一个产品 V(mutex); // 退出临界区 V(empty); // 空缓冲区数加1 消费产品 }}需特别注意：对 empty 和 full 的P操作必须置于对 mutex 的P操作之前。若顺序颠倒，例如生产者先执行 P(mutex) 再执行 P(empty)，则消费者先执行 P(mutex) 再执行 P(full) 可能导致死锁。试想：当缓冲区已满()，若生产者先获取 mutex，随后因 P(empty) 而阻塞；此时消费者欲取产品，却因 mutex 已被生产者持有而无法进入临界区执行 P(full) 和消费操作。结果，生产者等待消费者释放空位，消费者等待生产者释放 mutex，双方互相阻塞，导致死锁。同理，当缓冲区为空()时，若消费者先获取 mutex 再执行 P(full)，也会因无法继续而阻塞，进而阻止生产者进入临界区放入产品，同样导致死锁。因此，必须先申请资源状态(empty或full)，再申请互斥访问(mutex)，以确保进程不会在持有互斥锁的同时等待资源，从而避免死锁。
下面再看一个较为复杂的生产者-消费者问题。
问题描述：
桌上有一个盘子，最多只能容纳一个水果。爸爸专门向盘中放入苹果，妈妈专门放入橘子；女儿只吃盘中的苹果，儿子只吃盘中的橘子；只有当盘子为空时，爸爸或妈妈才能向其中放入一个水果；只有当盘中有自己所需的水果时，儿子或女儿才能从中取出并食用。
问题分析：
关系分析。爸爸和妈妈在向盘中放入水果时存在互斥关系；爸爸与女儿、妈妈与儿子之间分别构成同步关系（爸爸放苹果后，女儿才能取用；妈妈放橘子后，儿子才能取用）；儿子与女儿各自等待不同的水果，因此他们之间既无互斥也无同步关系。整理思路。可抽象为两个生产者（爸爸、妈妈）和两个消费者（女儿、儿子），共享一个容量为1的缓冲区。由于不同类型的产品（苹果、橘子）需由不同的消费者消费，故不能仅使用一个full信号量来表示满状态，而需为每种产品设置独立的同步信号量。信号量设置。互斥信号量plate，控制对盘子的互斥访问，初值为1；同步信号量apple，表示盘中是否有苹果，初值为0；同步信号量orange，表示盘中是否有橘子，初值为0。
进程的实现如下：
semaphore plate = 1, apple = 0, orange = 0;
dad() { // 爸爸进程 while (1) { 准备一个苹果 P(plate); // 获取对盘子的独占使用权 把苹果放入盘子 V(apple); // 通知女儿：苹果已放入盘中 }}
mom() { // 母亲进程 while (1) { 准备一个橘子 P(plate); // 获取对盘子的独占使用权 把橘子放入盘子 V(orange); // 通知儿子：橘子已放入盘中 }}
son() { // 儿子进程 while (1) { P(orange); // 等待盘中有橘子 从盘子中取出橘子 V(plate); // 释放盘子，允许他人使用 吃掉橘子 }}
daughter() { // 女儿进程 while (1) { P(apple); // 等待盘中有苹果 从盘子中取出苹果 V(plate); // 释放盘子，允许他人使用 吃掉苹果 }}dad() 和 daughter()、mom() 和 son() 必须成对执行。只有当女儿拿走苹果或儿子拿走橘子之后，才会执行 V(plate) 操作，从而释放盘子供下一次使用。
2. 读者-写者问题
问题描述：
系统中存在两组并发进程：读者和写者，它们共享一个文件。多个读者可以同时读取文件，不会导致数据不一致；但若任一写者与其他进程（无论是读者还是其他写者）同时访问文件，则可能破坏数据一致性。因此，需满足以下要求：
- 允许多个读者同时执行读操作；
- 任一时刻只允许一个写者执行写操作；
- 写者在完成写操作前，不允许任何其他读者或写者访问文件；
- 写者开始写操作前，必须等待所有已进入的读者和写者全部退出。
问题分析：
关系分析。读者与写者之间存在互斥关系；写者与写者之间也存在互斥关系；读者与读者之间无互斥关系，可并发读取。整理思路。写者的实现较为直接：它与所有其他进程互斥，只需用一个互斥信号量控制即可。读者的实现则更为复杂：它既要允许其他读者并发读取，又要阻止写者在读期间介入。为此，引入一个计数器count，用于记录当前正在读文件的读者数量。当第一个读者开始读时，应阻塞后续的写者；当最后一个读者结束读时，才允许写者进入；同时，多个读者对count的修改必须互斥。信号量设置。计数信号量count，记录当前读者数量，初值为0；互斥信号量mutex，控制对count的互斥访问，初值为1；互斥信号量rw，控制对文件的互斥访问，初值为1。
进程的实现如下（读者优先）：
int count = 0; // 记录当前的读者数量semaphore mutex = 1; // 控制对count的互斥访问semaphore rw = 1; // 控制读者与写者对文件的互斥访问
writer() { // 写者进程 while (1) { P(rw); // 申请对文件的独占写权限 写文件 V(rw); // 释放文件写权限 }}
reader() { // 读者进程 while (1) { P(mutex); // 互斥访问count if (count == 0) // 若是第一个读者 P(rw); // 阻止写者访问文件 count++; // 读者数量加1 V(mutex); // 释放对count的访问 读文件 P(mutex); // 互斥访问count count--; // 读者数量减1 if (count == 0) // 若是最后一个读者 V(rw); // 允许写者访问文件 V(mutex); // 释放对count的访问 }}上述算法实现的是读者优先策略。只要已有读者在读，后续到来的读者均可立即进入读取，而写者必须等待所有读者全部退出。这种设计可能导致写者长时间等待，甚至出现写者饥饿，即在读者持续到达的情况下，写者可能被无限期推迟。
若需实现写者优先策略：一旦有写者请求写入，就禁止新读者进入，并在当前读者全部退出后立即让写者执行。为此，引入互斥信号量 w，用于控制所有进程进入“准备访问文件”阶段的权限：写者先执行 P(w)，再执行 P(rw)，从而阻止后续读者插队；读者也需先执行 P(w)；若此时有写者持有 w，该读者将被阻塞；读者在更新 count 后立即执行 V(w)，因为只要存在活跃读者()，写者已被 rw 阻塞，提前释放 w 可避免不必要地阻碍其他写者；写者完成写操作后执行 V(w)，释放访问权。这样，w 如同“门卫”：当有写者等待时，新读者无法进入；但已在 count 内的读者仍可完成操作，既保障了写者的优先权，又维持了读者之间的并发读取。
int count = 0; // 记录当前的读者数量semaphore mutex = 1; // 控制对count的互斥访问semaphore rw = 1; // 控制读者与写者对文件的互斥访问semaphore w = 1; // 实现写者优先的关键信号量
writer() { // 写者进程 while (1) { P(w); // 申请写者优先权：阻止新读者进入 P(rw); // 申请对文件的独占写权限 写文件 V(rw); // 释放文件写权限 V(w); // 释放写者优先权，允许其他进程进入 }}
reader() { // 读者进程 while (1) { P(w); // 申请进入权限：若无写者等待，则通过 P(mutex); // 互斥访问count if (count == 0) // 若是第一个读者 P(rw); // 阻止写者访问文件 count++; // 读者数量加1 V(mutex); // 释放对count的访问 V(w); // 立即释放w，允许其他进程竞争 读文件 P(mutex); // 互斥访问count count--; // 读者数量减1 if (count == 0) // 若是最后一个读者 V(rw); // 允许写者访问文件 V(mutex); // 释放对count的访问 }}上述写者优先策略是相对的，并非绝对优先。该算法通过信号量 w 阻止新读者在写者等待时进入，从而避免读者无限插队；然而，若多个进程（包括读者和写者）同时阻塞在 w 上，系统通常按FCFS顺序唤醒，此时先到达的读者仍可能优先于后到的写者获得访问权。因此，该算法本质上是在防止写者饥饿的前提下，对写者给予有限优先，而非严格意义上的写者优先。
读者-写者问题的关键在于使用了受互斥保护的计数器 count。因此，面对复杂的同步互斥问题时，可考虑引入此类计数器来动态判断资源状态，这是一种重要的解题思路。
3. 哲学家进餐问题
问题描述：
一张圆桌旁围坐5名哲学家，每两名相邻哲学家之间放置一根筷子，共5根筷子，每位哲学家面前有一碗米饭。哲学家交替进行思考与进餐：思考时互不影响；饥饿时，必须同时持有左右两根筷子才能开始进餐（筷子需要逐根拿起）；若所需筷子已被他人持有，则必须等待；进餐结束后，立即放下两根筷子，继续思考。
问题分析：
关系分析。每根筷子被其两侧的哲学家共享，因此对同一根筷子的访问必须互斥。整理思路。共有5个并发进程。本题的关键是如何让一名哲学家安全地获取左右两根筷子，避免死锁或饥饿。直观的解决思路有两种：- 尝试同时获取两根筷子，即仅当左右筷子均空闲时才拿起；
- 对哲学家的行为制定规则，破坏死锁产生的必要条件。
信号量设置。定义互斥信号量数组chopstick[5]，控制对5根筷子的互斥访问，初值均为1。哲学家编号为 ，哲学家 左侧筷子的编号为 ，右侧筷子的编号为 。
一个直观的实现如下（存在死锁风险）：
semaphore chopstick[5] = {1, 1, 1, 1, 1}; // 初始化5根筷子的信号量
Pi() { // i号哲学家进程 do { P(chopstick[i]); // 拿起左侧筷子 P(chopstick[(i+1)%5]); // 拿起右侧筷子 进餐 V(chopstick[i]); // 放回左侧筷子 V(chopstick[(i+1)%5]); // 放回右侧筷子 思考 } while (1);}假设5名哲学家同时饥饿，并几乎同时执行完 P(chopstick[i])。此时，每位哲学家各持一根左侧筷子，且均在等待右侧筷子，系统进入循环等待状态，所有进程阻塞，形成死锁。
为防止死锁发生，可对哲学家进程施加一些限制条件：
- 限制最多4名哲学家同时尝试进餐，确保至少有一人能获得两根筷子，这样在其用餐完毕后释放他的两根筷子，从而使更多的哲学家能够进餐；
- 对哲学家编号，规定奇数号哲学家先拿左筷、再拿右筷，偶数号则相反，打破循环等待条件；
- 仅当左右两根筷子均空闲时，才允许哲学家同时拿起。
假设采用第二种方法，当一名哲学家左右两侧的筷子都可用时，才允许他拿起筷子。
semaphore chopstick[5] = {1, 1, 1, 1, 1}; // 初始化5根筷子的信号量semaphore mutex = 1; // 设置取筷子的信号量
Pi() { // i号哲学家的进程 do { P(mutex); // 申请取筷子的信号量 P(chopstick[i]); // 拿起左侧筷子 P(chopstick[(i+1)%5]); // 拿起右侧筷子 V(mutex); // 释放取筷子的信号量 进餐 V(chopstick[i]); // 放回左侧筷子 V(chopstick[(i+1)%5]); // 放回右侧筷子 思考 } while (1);}哲学家进餐问题是经典的进程同步案例，其本质在于预防循环等待。尽管大部分习题和真题通过消费者-生产者模型或读者-写者问题就能求解，但对哲学家进餐问题仍然要熟悉。考研复习的关键在于反复多次和全面，“偷工减料”是要吃亏的。
2.3.6 管程
在信号量机制中，每个访问临界资源的进程都需自行编写PV操作。分散的同步代码不仅增加了编程复杂度，还极易因操作顺序不当而引发死锁。为简化同步控制，操作系统引入了更高层的抽象机制——管程：它将共享资源及其操作封装于一体，自动保证互斥访问，程序员无须显式编写互斥代码；同时，通过条件变量实现灵活的进程同步，有效降低死锁风险。
1. 管程的定义
系统中的各类硬件资源和软件资源，均可通过数据结构进行抽象描述：即用少量状态信息和一组对资源的操作来表征该资源，而忽略其内部结构与实现细节。
管程正是基于这一思想构建的。它利用一个共享数据结构来表示系统中的共享资源，并将对该数据结构的所有操作封装为一组过程。进程对共享资源的申请、释放等操作，都必须通过调用这些过程来完成。这组过程可根据资源的当前状态决定是否允许访问：若条件满足，则处理请求；否则，将进程阻塞。由此确保任一时刻至多只有一个进程使用该共享资源，从而统一管理所有对共享资源的访问，实现进程互斥。这个由共享数据结构及其操作过程共同组成的资源管理程序，称为管程(monitor)。形式上，管程定义了一个数据结构，以及一组可在该数据结构上被并发进程调用的操作；这些操作不仅能修改管程内部的数据，还能协调进程之间的同步行为。
形式上，一个管程由以下四部分组成。
- 管程的名称。
- 局部于管程内部的共享数据结构说明。
- 对该数据结构进行操作的一组过程（或函数）。
- 对共享数据进行初始化的语句。
典型的管程定义如下：
monitor Demo { // ① 定义一个名称为Demo的管程 // ② 定义共享数据结构，对应系统中的某种共享资源 共享数据结构 S; // ④ 对共享数据结构初始化的语句 init code() { S = 5; // 初始可用资源数为5 } // ③ 操作过程1：申请资源 take_away() { 对共享数据结构S的一系列处理； S--; // 可用资源数-1 } // ③ 操作过程2：归还资源 give_back() { 对共享数据结构S的一系列处理； S++; // 可用资源数+1 }}熟悉面向对象程序设计的读者会发现，管程与类(class)高度相似。
- 封装性：管程将对共享资源的操作封装起来，其内部的共享数据结构只能被管程自身的过程访问。外部进程必须通过调用这些过程才能访问资源。例如，在上例中，申请资源需调用
take_away()，归还资源则需调用give_back()。 - 互斥性：任一时刻仅允许一个进程执行管程内的过程，从而实现互斥访问。若多个进程同时调用
take_away()或give_back()，则只有当前进程完成其所调用的过程后，下一个进程才能开始执行，这一机制确保了对共享数据S的互斥访问。
管程与进程的区别：
- 进程拥有私有数据结构（如PCB），而管程管理的是公共数据结构(如缓冲区)。
- 进程执行通用计算任务，而管程专注于同步控制与资源管理。
- 引入进程是为了实现并发，而引入管程是为了解决共享资源的互斥访问问题。
- 进程是主动执行的实体，而管程是被动调用的模块，即进程通过调用管程中的过程来操作共享数据。
- 多个进程可并发执行，但对同一管程的多个调用是互斥的，即同一时刻仅一个进程可在该管程内执行。
- 进程具有动态的生命周期（从创建到撤销），而管程是操作系统中的静态资源管理模块，仅供进程调用。
2. 条件变量
当一个进程进入管程后，若因条件不满足而需要等待，它必须释放对管程的占用；否则，其他进程将无法进入管程，从而导致系统停滞。为解决这一问题，管程引入了条件变量(condition)，将不同的阻塞原因分别抽象为独立的条件变量。通常，一个进程可能因多种条件不满足而被阻塞，因此管程中可以设置多个条件变量。每个条件变量维护一个等待队列，用于记录所有因该条件而阻塞的进程。对条件变量仅支持两种操作：wait 和 signal。
x.wait：当条件变量 x 所代表的条件不满足时，当前执行管程过程的进程调用 x.wait()，将自身加入 x 的等待队列，并自动释放管程，从而允许其他进程进入。
x.signal：当 x 所代表的条件发生变化（可能已满足）时，调用 x.signal()，唤醒一个因等待该条件而阻塞在 x 上的进程。
条件变量的定义和使用示例如下：
monitor Demo { 共享数据结构 S; condition x; // 定义一个条件变量x init code() { ... } take_away() { // 资源不足，在条件变量x上阻塞等待 if (S <= 0) x.wait(); 资源足够，分配资源，做一系列相应处理； } give_back() { 归还资源，做一系列相应处理； if (有进程在等待) x.signal(); // 唤醒一个阻塞进程 }}条件变量与信号量的比较。相似点：wait/signal 操作与P/V操作均可实现进程的阻塞与唤醒。不同点：信号量具有整数值，反映可用资源数量；而条件变量不维护数值，仅用于线程排队和通知。在管程中，资源数量由共享变量（如S）显式记录，条件变量只负责同步。
2.3.7 本节小结
本节开头提出的问题的参考答案如下。
-
为什么要引入进程同步的概念？
在多道程序环境下，多个进程并发执行，彼此之间存在相互制约关系。为协调这些关系，确保进程能够正确、有序地协作或竞争共享资源，操作系统引入了进程同步的概念。
-
不同的进程之间会存在什么关系？
进程之间主要存在两种基本的制约关系：同步与互斥。同步是指为完成共同任务而建立的多个进程，在某些关键点上需要协调工作次序，通过等待或传递信息所形成的协作关系。互斥是指当一个进程正在访问临界资源（处于临界区）时，其他进程必须等待；只有当前进程退出临界区后，其他进程才被允许进入，以保证对临界资源的独占访问。
-
当单纯用本节介绍的方法解决这些问题时会遇到什么新的问题吗？
当两个或多个进程各自占用某些资源，又同时请求对方所持有的资源时，可能形成一种互相等待的局面。若无外部干预，这些进程将永久阻塞，无法继续推进，这种现象称为死锁。其形成原因、必要条件、检测方法及解决方案将在下一节中详细介绍。