让天下没有难学的技术
竞态条件与临界区
竞态条件与临界区
作者：Jakob Jenkov 译者： 校对：丁一
在同一程序中运行多个线程本身不会导致问题，问题在于多个线程访问了相同的资源。如，同一内存区（变量，数组，或对象）、系统（数据库，web services等）或文件。实际上，这些问题只有在一或多个线程向这些资源做了写操作时才有可能发生，只要资源没有发生变化,多个线程读取相同的资源就是安全的。
多线程同时执行下面的代码可能会出错：
public class Counter {
protected long count = 0;
public void add(long value){
this.count = this.count +
想象下线程A和B同时执行同一个Counter对象的add()方法，我们无法知道操作系统何时会在两个线程之间切换。JVM并不是将这段代码视为单条指令来执行的，而是按照下面的顺序：
从内存获取 this.count 的值放到寄存器
将寄存器中的值增加value
将寄存器中的值写回内存
观察线程A和B交错执行会发生什么：
this.count = 0;
A: 读取 this.count 到一个寄存器 (0)
B: 读取 this.count 到一个寄存器 (0)
将寄存器的值加2
B: 回写寄存器值(2)到内存. this.count 现在等于 2
A: 将寄存器的值加3
A: 回写寄存器值(3)到内存. this.count 现在等于 3
两个线程分别加了2和3到count变量上，两个线程执行结束后count变量的值应该等于5。然而由于两个线程是交叉执行的，两个线程从内存中读出的初始值都是0。然后各自加了2和3，并分别写回内存。最终的值并不是期望的5，而是最后写回内存的那个线程的值，上面例子中最后写回内存的是线程A，但实际中也可能是线程B。如果没有采用合适的同步机制，线程间的交叉执行情况就无法预料。
竞态条件 & 临界区
当两个线程竞争同一资源时，如果对资源的访问顺序敏感，就称存在竞态条件。导致竞态条件发生的代码区称作临界区。上例中add()方法就是一个临界区,它会产生竞态条件。在临界区中使用适当的同步就可以避免竞态条件。
原创文章，转载请注明： 转载自本文链接地址:
英文名ticmy，本站的翻译主编，主要负责译文的翻译和校对工作，目前就职于阿里巴巴，对并发编程、JVM运行原理、正则等颇有兴趣；个人博客：http://www.ticmy.com/；同时，还是户外摄影爱好者。
Latest posts by 丁 一 ()
Related posts:
(25 votes, average: 4.52 out of 5)
Loading...本文所属图书&>&
本书按照操作系统教学大纲的要求，并参照全国联考大纲编写。全书共6章，主要内容包括：操作系统概述、处理器管理、进程同步、通信和死锁、存储器管理、文件管理及设备管理。每章按知识点分节，每节先总结核心概念...&&
1. 单项选择题
【例3-1-1】在操作中，临界区是&&&&& 。
A. 一个缓冲区&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& B. 一段共享数据区
C. 一段程序&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& D. 一个互斥资源
解：进程中访问临界资源的那段代码称为临界区。本题答案为C。
【例3-1-2】以下关于临界资源的叙述中，正确的是&&&&& 。
A. 临界资源是非共享资源&&&&&&&&&&&&&&&&&&&&&&&& B. 临界资源是任意共享资源
C. 临界资源是互斥的共享资源&&&&&&&&&&&&&&&&& D. 临界资源是同时共享资源
解：对于多个进程而言，临界资源是共享的，但又是互斥访问的。本题答案为C。
【例3-1-3】以下&&&&& 不属于临界资源。
A. 打印机&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& B. 非共享数据
C. 共享变量&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& D. 共享缓冲区
解：打印机、共享变量和共享缓冲区都只允许一次一个进程使用。本题答案为B。
【例3-1-4】在操作中，要对并发进程进行同步的原因是&&&&& 。
A. 进程必须在有限的时间内完成&&&&&&&&&&&&&&&&& B. 进程具有动态性
C. 并发进程是异步的&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& D. 进程具有结构性
解：进程同步是指进程之间一种直接的协同工作关系，这些进程的并发是异步的，它们相互合作，共同完成一项任务。本题答案为C。
【例3-1-5】关于临界区问题的一个算法（假设只有进程P0和P1可能会进入临界区）如下（i为0或1）：
&&& retry:if (turn&&-1) turn=i;
&&& if (turn&&i)
&&& turn:= -1;
&&& 临界区;
&&& turn:=0；
&&& 其他区;
该算法&&&&& 。
A. 不能保证进程互斥进入临界区，且会出现&饥饿&现象
B. 不能保证进程互斥进入临界区，但不会出现&饥饿&现象
C. 保证进程互斥进入临界区，但会出现&饥饿&现象
D. 保证进程互斥进入临界区，不会出现&饥饿&现象
解：该算法是用类PASCAL语言描述的，改用类C语言如下：
void P0()&&&&&& & //进程P0
&&& {&& while (turn!=0)
&&&&&&&&&&& if (turn!= -1) turn=0;
&&&&&&& turn=-1;
&&&&&&& 临界区;
&&&&&&& turn=0；
&&&&&&& 其他区;
&&& } while (true);
void P1()&&&&&& & //进程P1
&&& {&& while (turn!=1)
&&&&&&&&&&& if (turn!= -1) turn=1;
&&&&&&& turn=-1;
&&&&&&& 临界区;
&&&&&&& turn=0；
&&&&&&& 其他区;
&&& } while (true);
若一个进程P0已经判断turn!= -1，还未修改turn= 0之前，时间片已用完，转入进程调度，又选择另一个进程P1运行，该进程接着判断turn!= -1，它将turn=1，之后进入临界区执行。当它未退出临界区之前，它的时间片已用完，转入进程调度，又选择进程P0运行。进程P0继续完成turn=0，之后它也进入临界区执行，这样两个进程同时处于临界区中，显然错误。由于两个进程都能进入临界区，所以没有出现&饥饿&现象。本题答案为B。
【例3-1-6】下述选项中体现原语特点的是&&&&& 。
A. 并发性&&&&&&&&&&&&&&&& B. 共享性&&&&&&&&&&&&& C. 结构性&&&&&&&&&&&&&&&& D. 不可分割性
解：原语指作为一个单一的、不可分割的原子操作。本题答案为D。
【例3-1-7】在操作系统中，P、V操作是一种&&&&& 。
A. 机器指令 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& B. 时钟中断
C. 作业控制命令&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& D. 低级进程通信原语
解：P、V操作交换的信息量小，是低级进程通信原语。本题答案为D。
【例3-1-8】进程从执行状态到阻塞状态可能是由于&&&&& 。
A. 进程调度程序的调度&&&&&&&&&&&&&&&&&&&&&&&&& B. 当前运行进程的时间片用完
C. 当前运行的进程执行了P操作&&&&&&&&&&& D. 当前运行进程执行了V操作
解：当前运行的进程执行P操作，若此时请求的资源不能分配，则进程从执行状态到阻塞状态。本题答案为C。
【例3-1-9】在非抢占式调度下，运行进程执行V操作后，其状态&&&&& 。
A. 不变&&&&&&&&&&&&&&&&&&&& B. 要变&&&&&&&&&&&&&&&&& C. 可能要变&&&&&&&&&&&&& D. 可能不变
解：进程调度方式有抢占式和非抢占式两种，在抢占式方式下，一旦有优先级高于当前执行进程优先级的进程时，便立即发生进程调度，转让CPU。而在非抢占式方式下，即使在就绪队列中有优先级高于当前执行进程优先级的进程，当前进程仍将继续占有CPU，直到由于该进程自已的原因而让出CPU。当前运行的进程执行V操作可能唤醒一个新进程，由于采用非抢占式调度方式，新进程不会立即分配到CPU，当前进程仍将继续占有CPU，所以其状态不变。采用本题答案为A。
【例3-1-10】用V操作唤醒一个等待进程时，被唤醒进程的状态变为&&&&& 。
A. 运行&&&&&&&&&&&&&&&&&&&& B. 阻塞&&&&&&&&&&&&&&&&& C. 就绪&&&&&&&&&&&&&&&&&&&& D. 完成
解：被唤醒进程只能从等待状态变为就绪状态，当获得CPU后才能变为运行状态。本题答案为C。
【例3-1-11】用来实现进程同步和互斥的P、V操作实际上是由&&&&& 过程组成的。
A. 一个可被中断的 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&& B. 一个不可被中断的
C. 两个可被中断的&& &&&&&&&&&&&&&&&&&&&&&&&&&&& D. 两个不可被中断的
解：P、V原语通过操作信号量来处理进程之间同步和互斥的问题，其核心就是一段不可分割、不可中断的程序。本题答案为D。
【例3-1-12】在用信号量机制实现互斥时，信号量的初值为&&&&& 。
A. 0&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& B. 1&&&&&&&&&&&&&&&&&&&&&&&&&& C. -1 &&&&&&&&&&&&&&& D. 2
解：互斥时信号量的初值一般为1，同步时信号量的初值大于等于1。本题答案为B。
【例3-1-13】用P、V操作实现进程同步，信号量的初值为&&&&& 。
A. -1&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& B. 0&&&&&&&&&&&&&&&&&&&&&&&&&& C. 1 &&&&&&&&&&&&&&&&& D. 由用户确定
解：用P、V操作实现进程同步，信号量的初值应根据具体情况来确定。若期望的消息尚未产生，则对应的初值应设为0；若期望的消息已经存在，则信号量的初值应设为一个非0的正整数。本题答案为D。
【例3-1-14】实现进程同步时，每一个消息与一个信号量对应，进程&&&&& 可把不同的消息发送出去。
A. 在同一信号量上调用P操作&&&&&&&&&&&&&&&&&&&&&&&&&& B. 在不同信号量上调用P操作
C. 在同一信号量上调用V操作&&&&&&&&&&&&&&&&&&&&&&&&& D. 在不同信号量上调用V操作
解：在实现进程同步时，P、V操作放在不同的进程中，V操作用于向其他同步进程发送消息。本题答案为D。
【例3-1-15】如果有4个进程共享同一程序段，则每次允许3个进程进入该程序段，若用P、V操作作为同步机制，则信号量的取值范围是&&&&& 。
A. -1～4 &&&&&&&&&&&&&&&&&&&&&&&& B. -2～2 &&&&&&&&&&&&&&&&& C. -1～3 &&&&&&&&&& D. -3～2
解：每次允许3个进程进入，可能出现的情况是：①没有进程进入；②有一个进程进入；③有两个进程进入；④有3个进程进入；⑤有3个进程进入并有一个进程等待进入。这5种情况对应的信号量值为3、2、1、0、-1。本题答案为C。
【例3-1-16】在9个生产者、6个消费者共享8个单元缓冲区的生产者-消费者问题中，互斥使用缓冲区的信号量的初始值为&&&&& 。
A. 1 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& B. 6&&&&&&&&&&&&&&&&&&&&&&&&&& C. 8&&&&&&&&&&&&&&&&&&& D. 9
解：在生产者-消费者问题中，缓冲区是临界资源，在同一时间段只允许一个进程使用它，所以互斥信号量的初始值为1。本题答案为A。
【例3-1-17】对信号量X执行P操作时，若&&&&& 则进程进入等待状态。
A. X-1&0&&&&&&&&&&&&&&&&&&&&&&&& B. X-1&0&&&&&&&&&&&&&&&& C. X-1&0&&&&&&&&&&& D. X-1&0
解：信息量X为整数，执行P操作后，X-1&0即X&1，不满足X&0，则该进程进入等待状态。本题答案为A。
【例3-1-18】对信号量X执行V操作时，若&&&&& 则唤醒阻塞队列中的队首进程。
A. X+1&0& &&&&&&&&&&&&&&&&&&&&& B. X+1&0 &&&&&&&&&&&&&& C. X+1&0&&&&&&&&&&& D. X+1&0
解：信息量X为整数，执行V操作后，X+1&0即X&-1，满足X&0，则从等待队列中移出一个队首进程进入就绪队列。本题答案为B。
【例3-1-19】若信号量S的初值为2，当前值为-1，则表示有&&&&& 等待进程。
A. 0个&&&&&&&&&&&&&&&&&& B. l个&&&&&&&&&&&&&&&&&&&&&&& C. 2个&&&&&&&&&&&&&&&&&&&& D. 3个
解：当信号量的值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程个数。本题答案为B。
【例3-1-20】若信号量S的初值为3，当前值为-2，则表示有&&&&& 等待进程。
A. 2个&&&&&&&&&&&&&&&&&& B. 3个 &&&&&&&&&&&&&&&&&&&&& C. 4个 &&&&&&&&&&&&&&&&&&& D. 5个
解：当信号量的值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程个数。本题答案为A。
【例3-1-21】若信号量S的初值为3，当前值为1，则表示有&&&&& 等待进程。
A. 0个 &&&&&&&&&&&&&&&& B. 1个&&&&&&&&&&&&&&&&&&&&&& C. 2个 &&&&&&&&&&&&&&&&&&& D. 3个
解：当信号量的值大于0时，表示还有资源可以分配，没有等待的进程。本题答案为A。
【例3-1-22】两个并发进程共享一个临界资源，设互斥信号量为mutex，若mutex=0，则&&&&& 。
A. 表示没有进程进入临界区
B. 表示有一个进程进入临界区
C. 表示有一个进程进入临界区，另一个进程等待进入
D. 表示有两个进程进入临界区
解：对于两个并发进程，互斥信号量为mutex，则mutex的初值为1，任何时刻只能有一个进程访问临界区。若没有进程进入临界区，则mutex为1；若一个进程进入临界区，另一个进程在等待进入，则mutex为-1；若一个进程进入临界区，则mutex为0；不可能出现两个进程都进入临界区的情况。本题答案为B。
【例3-1-23】对于两个并发进程，设互斥信号量为mutex（初值为1），若mutex=1，则&&&&& 。
A. 表示没有进程进入临界区
B. 表示有一个进程进入临界区
C. 表示有一个进程进入临界区，另一个进程等待进入
D. 表示有两个进程进入临界区
解：当没有进程等待进入临界区时，mutex值为1。本题答案为A。
【例3-1-24】对于两个并发进程，设互斥信号量为mutex（初值为1），若mutex=-1，则&&&&& 。
A. 表示没有进程进入临界区
B. 表示有一个进程进入临界区
C. 表示有一个进程进入临界区，另一个进程等待进入
D. 表示有两个进程进入临界区
解：当有一个进程进入临界区且有一个进程等待进入临界区时，mutex=-1。本题答案为C。
【例3-1-25】当一进程因在互斥信号量mutex上执行P(mutex)操作而被阻塞，则此时mutex的值为&&&&& 。
A. 大于0&&&&&&&&&&&&&&&&&&& B. 小于0 &&&&&&&&&&&&&&&& C. 大于等于0&&&&&&& D. 小于等于0
解：当mutex&0，则将该进程插入到mutex的等待队列中。本题答案为B。
【例3-1-26】当一进程因在互斥信号量mutex上执行V(mutex)操作而导致唤醒另一个进程时，则此时mutex的值为&&&&& 。
A. 大于0&&&&&&&&&&&&&&&&&&& B. 小于0&&&&&&&&&&&&&&&&& C. 大于等于0&&&&&&& D. 小于等于0
解：当mutex&0时，则从mutex的等待队列中移出第一个该进程并插入到就绪队列中。本题答案为D。
【例3-1-27】如果系统中有n个进程，则就绪队列中进程的个数最多为&&&&& 。
A. n+1&&&&&&&&&&&&&&&&&&&&&&& B. n &&&&&&&&&&&&&&&&&&&&&&& C. n-1 &&&&&&&&&&&&&&&&& D. 1
解：一个计算机系统中至少有一个处理器，通常处理器上有一个进程执行，因此就绪队列中进程个数最多为n-1。本题答案为C。
【例3-1-28】若一个系统中共有5个并发进程涉及某个相同的变量A，则变量A的相关临界区是由&&&&& 个临界区构成的。
A. 1& &&&&&&&&&&&&&&&&&&&&&&& B. 3 &&&&&&&&&&&&&&&&&&&&&&& C. 5&&&&&&&&&&&&&&&&&&&&&& D. 6
解：这里的临界区是操作共享变量A的程序段，5个并发进程共有5个操作共享变量A的程序段。本题答案为C。
【例3-1-29】设有n个进程共用一个相同的程序段，如果每次最多允许m个进程（m&n）同时进入临界区，则信号量的初值为&&&&& 。
A. n&&&&&&&&&&&&&&&&&&&&&&&&&&& B. m&&&&&&&&&&&&&&&&&&&&&&&& C. m-n&&&&&&&&&&&&&&&&&& D. -m
解：刚开始时，临界区中没有进程，此时信号量S的值为m，每一个进程进入临界区，S减1，减到-(n-m)为止。本题答案为B。
【例3-1-30】下述哪个选项不是管程的组成部分&&&&& 。
A. 局限于管程的共享数据结构
B. 对管程内数据结构进行操作的一组过程
C. 管程外过程调用管程内数据结构的说明
D. 对局限于管程的数据结构设置初始值的语句
解：管程由局限于管程的共享变量说明、对管程内的数据结构进行操作的一组过程以及对局限于管程的数据设置初始值的语句组成，故本题答案为C。
【例3-1-31】以下关于管程的描述中错误的是&&&&& 。
A. 管程是进程同步工具，解决信号量机制中大量同步操作分散的问题
B. 管程每次只允许一个进程进入管程
C. 管程中signal操作的作用和信号量机制中的V操作相同
D. 管程是被进程调用的，管程是语法单位，无创建和撤销
解：管程的signal操作与信号量机制中的V操作不同，前者必须在wait操作之后。本题答案为C。
【例3-1-32】原语是一种特殊的广义指令，又称原子操作，它应该在&&&&& 的状态下执行。
解：本题答案为：不可中断。
【例3-1-33】信号量的物理意义是，当信号量值大于零时表示&& ①&& ，当信号量值小于零时表示&& ②&& 。
解：本题答案为：①可分配资源的个数 ②等待使用该资源的进程的个数。
【例3-1-34】在使用P、V操作实现进程互斥时，调用&& ①&& 相当于申请一个共享资源，调用&& ②&& 相当于归还共享资源的使用权。
解：本题答案为：①P操作 ②V操作。
【例3-1-35】执行一次信号量S的P操作，使S.value的值减1后，如果S.value的值&&&&& 时，调用进程阻塞等待。
解：本题答案为：&0。
【例3-1-36】每执行一次P操作，信号量S的值减1，如果S&0，则该进程&& ①&& ，若S&0，则&& ②&& 该进程，并把它插入到该&& ③&& 对应的&& ④&& 队列中，重新开始进程调度。
解：本题答案为：①继续执行 ②阻塞 ③信号量 ④等待或阻塞。
【例3-1-37】每执行一次V操作，信号量S的值加1，如果S&0，则该进程&& ①&& ，若S&0，则从该&& ②&& 对应的&& ③&& 队列中移出一个进程，并把它插入到&& ④&& 队列中，重新开始进程调度。
解：本题答案为：①继续执行 ②信号量 ③等待或阻塞 ④就绪。
【例3-1-38】并发进程之间的基本关系有&& ①&& 和& &②&& ，其中&& ②&& 是指进程之间的一种间接制约关系。
解：进程同步称为进程之间的一种协同关系，也称为直接制约关系，进程互斥称为进程之间的一种间接制约关系。本题答案为：①同步 ②互斥。
【例3-1-39】&&&&& 是指并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。
解：本题答案为：进程同步。
【例3-1-40】&&&&& 是指当若干个并发进程都要使用某一共享资源时，任何时刻最多只允许一个进程去使用，其他要使用该资源的进程必须等待，直到占用资源者释放了该资源。
解：本题答案为：进程互斥。
【例3-1-41】利用P、V操作管理相关临界区时，必须成对出现，在进入临界区之前要调用&& ①&& ，在完成临界区操作后要调用&& ②&& 。
解：本题答案为：①P操作 ②V操作。
【例3-1-42】在利用信号量实现进程互斥时，应将&& ①&& 置于&& ②&& 和&& ③&& 之间。
解：在利用信号量实现进程互斥时，应将临界区置于P操作和V操作之间。本题答案为：①临界区 ②P操作 ③V操作。
【例3-1-43】有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号量值的变化范围是&&&&& 。
解：临界资源应互斥使用，互斥信号量m的初值为1。当没有进程使用临界资源时，m值为1；有一个进程使用临界资源且无进程等待使用该资源时，m值为0；有一个进程使用临界资源且有一个进程等待使用该资源时，m值为-1；依此类推，最多可能有m-1个进程等待使用该临界资源。本题答案为：1～-(m-1)。
【例3-1-44】设有4个进程共享一程序段，而每次最多允许两个进程进入该程序段，则信号量的取值范围是&&&&& 。
解：为允许2个进程进入该程序段，信号量的初值应为2；当有1个进程进入该程序段且无其他进程申请进入该程序段时，信号量值为1；当有2个进程进入该程序段且无其他进程申请进入该程序段时，信号量值为0；当有2个进程进入该程序段且有1个进程申请进入该程序段时，信号量值为-1；当有2个进程进入该程序段且有2个进程申请进入该程序段时，信号量值为-2。本题答案为：2～-2。
【例3-1-45】判断以下叙述的正确性。
（1）对临界资源应采用互斥访问方式来实现共享。
（2）仅当一个进程退出临界区以后，另一个进程才能进入相应的临界区。
（3）临界段是指进程中用于实现进程互斥的那段代码。
（4）如果信号量S的当前值为-5，则表示系统中共有5个进程。
（5）进程间的互斥是一种特殊的同步关系。
（6）若信号量的初值为1，用P、V操作能限制不能有任何进程进入临界区操作。
（7）P、V操作只能实现进程互斥，不能实现进程同步。
（8）P、V操作是一种原语，在执行时不能打断。
（9）在信号量上除了能执行P、V操作外，不能执行其他任何操作。
解：（1）正确。
（2）正确。临界区只能互斥访问
（3）错误。
（4）错误。如果信号量S的当前值为-5，则表示系统中共有5个进程在等待，还可能有一个进程在执行态，若干个进程在就绪态。
（5）正确。
（6）错误。若信号量的初值为1，用P、V操作能限制只有一个进程进入临界区操作。
（7）错误。P、V操作既可以实现进程互斥，也可以实现进程同步。
（8）正确。
（9）错误。信号量可以赋初值。
【例3-1-46】简述进程同步与互斥之间的区别和联系。
解：并发进程的执行会产生相互制约的关系：一种是进程之间竞争使用临界资源，只能让它们逐个使用，这种现象称为互斥，是一种竞争关系；另一种是进程之间协同完成任务，在关键点上等待另一个进程发来的消息，以便协同一致，是一种协作关系。进程同步与互斥的比较如表3.1所示。
表3.1& 进程同步与互斥的比较
进程－进程
进程－资源－进程
时间次序上受到某种限制
竞争不到某一临界资源时不允许进程工作
相互清楚对方的存在及作用，交换信息
不一定清楚其他进程的情况
往往指有几个进程共同完成一个任务
往往指多个任务多个进程间通信制约
示例：生产者与消费者之间、发送者与接收者之间、作者与读者之间
示例：交通十字路口、若干用户使用一台打印机
【例3-1-47】进程之间存在哪几种制约关系？各是什么原因引起的？以下活动各属于哪种制约关系？
（1）若干学生去馆借书。
（2）两队进行篮球比赛。
（3）流水线生产的各道工序。
（4）商品生产和社会消费。
解：进程之间存在两种制约关系，即同步和互斥。
l&&&&&& 同步是由于并发进程之间需要协调完成同一个任务时引起的一种关系，为一个进程等待另一个进程向它直接发送消息或数据时的一种制约关系。
l&&&&&& 互斥是由于并发进程之间竞争系统的临界资源引起的，为一个进程等待另一个进程已经占有的、必须互斥使用的资源时的一种制约关系。
（1）是互斥关系，同一本书只能被一个学生借阅，或者任何时刻只能有一个学生借阅一本书。
（2）是互斥关系，篮球是互斥资源。
（3）是同步关系，一个工序完成后开始下一个工序。
（4）是同步关系，生产商品后才能消费。
【例3-1-48】以下两个进程A和B之间体现出一种什么关系，为什么？
进程A：&&&&&&&&&&&&&&&&&&&&&&&&&&& 进程B：
while (true)&&&&&&&&&&&&&&&&&&&&&&& while (true)
{&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&{
&&& A1:收到监视器的信号;&&&&&&&&&&&&& B1:延迟10分钟;
&&& A2:count=count+1;&&&&&&&&&&&&& B2:打印count的值;
}&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& B3:count=0;
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&}
解：进程A、B之间体现出一种互斥关系，因为在进程A中，A2语句对共享变量count进行加1操作，而进程B中要对共享变量count进行打印和置0操作。这两个进程不能交叉进行，否则会出现与时间有关的错误。
【例3-1-49】下列解决临界段问题的软件算法能保证临界段的互斥访问吗？请说明原因。
进程Pi（i＝1,2,&）：
while (true)
{&& while (s&=0);
&&& 临界区代码;
&&& 非临界区代码;
其中，s为一个整形变量，初值为1。
解：不能。当多个进程速度完全相同时，都会进入临界区。
【例3-1-50】以下是对两个进程P0和P1互斥进入临界区的解法，指出该解法存在的问题并予以改正。
enum boolean {false，true};
boolean flag[2] = {false，false};
{&& flag[0]=
&&& while(turn!=0)
&&& {&& while (flag[1]==true);
&&&&&&& turn=0;
&&& 临界区;
&&& flag[0]=
&&& 其他代码;
} while(true);
{&& flag[1]=
&&& while(turn!=1)
&&& {&& while (flag[0]==true);
&&&&&&& turn=1;
&&& 临界区;
&&& flag[1]=
&&& 其他代码;
} while(true);
解：假设turn=0，并先执行P1，出现的问题如下。
flag[1]=true
while (turn!=1)&&&&&& && &&& &&& //条件满足
while (flag[0]==true)&& &&& //条件不满足
此时切换执行进程P0
flag[0]=true
while (turn!=0)&&&&&& && &&& &&& //条件不满足
进入进程P0的临界区执行
此时切换执行进程P1
while (turn!=1)&&&&&& && &&& &&& //条件不满足
进入进程P1的临界区执行
这样两个进程都进入了临界区，违反了&忙则等待&的原则。可改正为前面软件实现方法的解法4算法。
【例3-1-51】以下算法用于解决两个临界段问题，判断其正确性。如果不正确，举例说明该算法违背了关于临界段问题的哪条准则。
两个进程P0、P1共享如下变量：
bool flag[0..1]={false,false};&&&&&& //flag数组元素初值均为false
int turn=0或1;&&&&&&&&&&&&&&&&&&&&&& & &&& //turn的初值为0或1
{&& flag[0]=
&&& while (trun==1)
&&& {&& while (flag[0]);
&&&&&&& turn=0;
&&& flag[1]=
&&& 临界区;
&&& 非临界区;
} while(true);
{&& flag[1]=
&&& while (turn==0)
&&& {&& while (falg[1]);
&&&&&&& turn=1;
&&& flag[0]=
&&& 临界区;
&&& 非临界区;
} while(true);
解：该解法不正确，违背了临界区的互斥准则。
例如，令turn=1，当P0执行到第二个while语句并使之在此时中断，并执行P1，而P1能成功地进入其临界区，并置flag[0]=false；当P1正在临界区执行时发生中断，进程P0执行，P0此时也能进入临界区，从而导致P0、P1均进入各自的临界区。
【例3-1-52】进程A和B共享一个变量，因此在各自的程序里都有自已的临界区。现在进程A在临界区里。试问进程A的执行能够被别的进程打断吗？能够被进程B打断吗？（这里&打断&的含义是调度新进程运行，使进程A暂停执行）。
解：当进程A在自已的临界区中执行时，能够被别的进程打断，没有任何限制。当进程A在自已的临界区中执行时，也能够被进程B打断，不过这种打断是有限制的，即当进程B执行到要求进入自已的临界区时，就会被阻塞，这是因为在它打断进程A时，进程A正在临界区中还没有出来，既然进程A在临界区中，进程B当然就无法进入自已的临界区。
【例3-1-53】信号量上的P、V操作只是对信号量的值进行减1或加1操作吗？在信号量上不能够执行除P、V操作外的其他操作吗？
解：根据信号量的定义可知，P、V操作并非只是对信号量进行减1或加1操作，更重要的是在减1或加1后，还要判断运算的结果。对于P操作，判断后调用进程自已有可能继续运行，也可能阻塞等待；对于V操作，判断后调用进程最后总是继续运行，但之前可能会唤醒在信号量队列上等待的进程。
在信号量上除了能执行P、V操作外，还可以对信号量赋初值。
【例3-1-54】请问需要互斥操作的两进程有执行先后次序要求吗？列举一个用P、V操作进行互斥访问的例子，说明信号量初值。
解：需要互斥操作的两进程没有执行先后的次序要求。
例如，两个进程A和B共享一个计数器count（初值=0），使用信号量s（初值=1）：
程序A：&&&&&&&&&&&&&&&&&&&&&&& 程序B：
&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&& &
P(s);&&&&&&&&&&&&&&&&&&&&&&& &&&&&& P(s);
count++;&&&&&&&&&&&&&&&&&&&&&&& &&& count++;
V(s);&&&&&&&&&&&&&&&&&&&&&&& &&&&&& V(s);
&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&& &
【例3-1-55】以下两个并发执行的进程，它们能正确运行吗？如果不能，请改正。
{&& Cobegin
&&& {&& 进程P1
&&&&&&& {&& int y,z;
&&&&&&&&&&& x=1; y=0;
&&&&&&&&&&& if (x&=1) y=y+1;
&&&&&&&&&&& z=y;
&&&&&&& 进程P2
&&&&&&& {&& int t,u;
&&&&&&&&&&& x=0; t=0;
&&&&&&&&&&& if (x&=1) t=t+2;
&&&&&&&&&&& u=t;
解：这两个进程不能正确地并发运行。它们都对同一变量x进行操作，x是一个临界资源，但没有进行保护。改正的结果如下：
Semaphore S=1;&&&&&& //访问x的互斥信号量
{&& Cobegin
&&& {&& 进程P1
&&&&&&& {&& int y,z;
&&&&&&&&&&& P(S);
&&&&&&&&&&& x=1; y=0;
&&&&&&&&&&& if (x&=1) y=y+1;
&&&&&&&&&&& V(S);
&&&&&&&&&&& z=y;
&&&&&&& 进程P2
&&&&&&& {&& int t,u;
&&&&&&&&&&& P(S);
&&&&&&&&&&& x=0; t=0;
&&&&&&&&&&& if (x&=1) t=t+2;
&&&&&&&&&&& V(S);
&&&&&&&&&&& u=t;
本题只须将x的操作包含在P(S)、V(S)中间即可。
【例3-1-56】设有4个进程共享一个程序段，而每次最多允许两个进程进入该程序段，则信号量的取值范围是多少？
解：所有可能的情况是：①没有进程进入该程序段，信号量值为2；②有1个进程进入该程序段且无其他进程申请进入该程序段时，信号量值为1；③有2个进程进入该程序段且无其他进程申请进入该程序段时，信号量值为0；④有2个进程进入该程序段且有1个进程申请进入该程序段时，信号量值为-1；⑤有2个进程进入该程序段且有2个进程申请进入该程序段时，信号量的值为-2。故本题答案为：-2～2。
【例3-1-57】设有n个进程共享一个程序段，对于如下两种情况：
（1）如果每次只允许一个进程进入该程序段。
（2）如果每次最多允许m个进程（m&n）同时进入该程序段。
试问所采用的信号量初值是否相同？信号量的变化范围如何？
解：（1）由于每次只允许一个进程进入该程序段，因此可以将该程序段看成是临界资源，应设置初值为1的信号量。当没有进程进入该程序段时，信号量的值为1；当有1个进程进入该程序段且没有进程等待进入该程序段时，信号量的值为0；当有1个进程进入该程序段且有1个进程等待进入该程序段时，信号量的值为-1；最多可能有n-1个进程等待进入该程序段，所以信号量的取值范围为：1&信号量&-(n-1)。
（2）由于每次最多允许m个进程同时进入该程序段，因此可以将这个程序段看成是m个程序段，每个进程使用一个程序段，应设置初值为m的信号量。当没有进程进入该程序段时，信号量的值为m；当有1个进程进入该程序段且没有进程等待进入该程序段时，信号量的值为m-1；当有1个进程进入该程序段且有1个进程等待进入该程序段时，信号量的值为m-2；最多可能有n-m个进程等待进入该程序段，所以信号量的取值范围为：m&信号量&-(n-m)。
【例3-1-58】设有两个优先级相同的进程P1和P2，如下所示。信号量S1和S2的初值均为0，试问P1、P2并发执行后，x、y、z的值各是多少？
进程P1：&&&&&&&&&&&& &&&&&&& 进程P2：
y=1;&&&&&&&&&&&&&&&&&&& &&&& x=1;
y=y+2;&&&&&&&&&&&&&& &&&&&&& x=x+1;
V(S1);&&&&&&&&&&&&&& &&&&&&& P(S1);
z=y+1;&&&&&&&&&&&&&& &&&&&&& x=x+y;
P(S2);&&&&&&&&&&&& &&&&&&&& V(S2);
y=z+y;&&&&&&&&&&&&&&& &&&&&& z=x+z;
解：根据进程中的信号量操作得到这些语句执行的前趋图如图3.12所示。从中看到，无论调度顺序如何，进程执行到语句7时x的值为5，y的值为3。由于语句3的执行结果不受语句7的影响，语句3执行后，z的值为4。此后语句4和语句8可以并发执行。若语句4先执行，则两进程执行结束后，x的值为5，y的值为7，z的值为9。若语句8先执行，则两进程执行结束后，x的值为5，y的值为12，z的值为9。
图3.12& 语句执行的前趋图
【例3-1-59】设缓冲区大小为n，指出以下生产者-消费者问题解法中的错误，并改正。
Producer()&&&&&&&&&& //生产者进程
{&& while(true)
&&& {&& 生产一个产品
&&&&&&& P(mutex);
&&&&&&& P(empty);
&&&&&&& Buffer(in)=
&&&&&&& in=(in+1) % n
&&&&&&& V(mutex);
Consumer()&&&&&&&&&& //消费者进程
{&& while(true)
&&& {&& P(mutex);
&&&&&&& P(full);
&&&&&&& nextc=buffer(out);
&&&&&&& Out=(out+1) %
&&&&&&& V(mutex);
&&&&&&& 消费产品
解：生产者-消费者问题中的错误是：信号量未赋初值；P操作的次序不对；缺V操作。改正如下：
Semaphore mutex=1,full=0,empty=n;
Producer()&&&&&&&&&& //生产者进程
{&& while (true)
&&& {&& 生产一个产品
&&&&&&& P(empty);
&&&&&&& P(mutex);
&&&&&&& Buffer(in)=
&&&&&&& in=(in+1)%n;
&&&&&&& V(mutex);
&&&&&&& V(full);
Consumer()&&&&&&&&&& //消费者进程
{&& while (true)
&&& {&& P(full);
&&&&&&& P(mutex);
&&&&&&& nextc=buffer(out);
&&&&&&& out=out+1;
&&&&&&& V(mutex);
&&&&&&& V(empty);
&&&&&&& 消费产品
【例3-1-60】某车站售票厅，任何时间最多可容纳100名购票者进入，当售票厅少于100名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答以下问题：
（1）P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。
（2）根据所定义的信号量，插入应执行的P、V操作以保证进程能够正确地并发执行。
{&& Cobegin
&&&&&&& ProcessPi（i=1,2,&,n）
&&&&&&& {&& 进入售票厅;
&&&&&&&&&&& 退出;
（3）若欲购票者最多为n个人，写出信号量可能的变化范围（最大值和最小值）。
解：（1）应定义一个信号量S，S的初值为100，当0&S&100时，允许厅外的购票者进入；当S=0时，厅内已有100人，欲购票者暂不能进入；当S&0时，|S|表示等待进入者的人数。
（2）用P、V操作保证进程正确执行的程序如下：
Semaphore S=100;
{&& Cobegin
&&& {&& ProcessPi（i=1,2,3,&,n）
&&&&&&& {&& P(S);
&&&&&&&&&&& 进入售票厅;
&&&&&&&&&&& 购票;
&&&&&&&&&&& 退出;
&&&&& &&&&&&V(S);
（3）若购票者最多为n人，则信号量S的变化范围：100-n&S&100。
【例3-1-61】用P、V操作解决读者－写者问题如下：
Semaphore S=1;
Semaphore Sr=1;
{&& Cobegin
&&& {&& 读者进程Readeri（i=1,&,n）
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(Sr);
&&&&&&&&&&&&&&& rc=rc+1;
&&&&&&&&&&&&&&& if (rc==1) P(S);
&&&&&&&&&&&&&&& V(Sr);
&&&&&&&&&&&&&&& 读文件;
&&&&&&&&&&&&&&& P(Sr);
&&&&&&&&&&&&&&& rc=rc-1;
&&&&&&&&&&&&&&& if (rc==0) V(S);
&&&&&&&&&&&&&&& V(Sr);
&&&&&&&&&&& }
&&&&&&& 写者进程Writerj（j=1,&,m）
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(S);
&&&&&&&&&&&&&&& 写文件;
&&&&&&&&&&&&&&& V(S);
&&&&&&&&&&& }
请回答以下问题：
（1）信号量Sr的作用是什么？
（2）程序中什么语句用于读-写互斥、写-写互斥？
（3）若规定最多只有5个进程同时读，怎么修改程序？
解：（1）信号量Sr的作用是为了保护变量rc（记录同时进行读操作的读进程个数），实施对rc的互斥访问。
（2）程序语句中&if (rc==1) P(S)&中的P(S)用于读-写互斥，即只要有一个或以上的读进程读文件时，就禁止写进程写文件。写者进程中的P(S)用于实施写-写互斥和读-写互斥，即只要有一个写进程写文件时，就禁止其他读进程读文件、写进程写文件。
（3）如果最多只允许5个进程同时读，需要增加一个信号量S5，初值为5，修改程序如下：
Semaphore S=1;
Semaphore Sr=1;
Semaphore S5=5;
{&& Cobegin
&&& {&& 读者进程Readeri（i=1,&,n）
&&&&&&& {&& P(S5);&&&&&&&&&&&&&&&&&& &&& //递减同时读文件的进程数
&&&&&&&&&&& while (true)
&&&&&&&&&&& {&& P(Sr);
&&&&&&&&&&&&&&& rc=rc+1;
&&&&&&&&&&&&&&& if (rc==1) P(S);
&&&&&&&&&&&&&&& V(Sr);
&&&&&&&&&&&&&&& 读文件;
&&&&&&&&&&&&&&& P(Sr);
&&&&&&&&&&&&&&& rc=rc-1;
&&&&&&&&&&&&&&& if (rc==0) V(S);
&&&&&&&&&&&&&&& V(Sr);
&&&&&&&&&&&&&&& V(S5);&&&&&&&&&&&&&& &&& //递增同时读文件的进程数
&&&&&&&&&&& }
&&&&&&& 写者进程Writerj（j=1,&,m）
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(S);
&&&&&&&&&&&&&&& 写文件;
&&&&&&&&&&&&&&& V(S);
&&& &&&&&&&&}
【例3-1-62】有一对夫妻在某银行申请了一个共同的账号，办理了正副两张银行卡。每张银行卡都可独立存款和取款，规定每次存款或取款的金额为1000元（约定可透支）。自动存取款机中为银行卡设置了如下两个进程：
int amount=0;
{&& Cobegin
&&& {&& SAVE()&&&&&&&&&& & //进程SAVE
&&&&&&& {&&
&&&&&&&&&&& k=
&&&&& &&&&&&k=k+1000;
&&&&&&&&&&& amount=k;
&&&&&&&&&&& &
&&&&&&& TAKE()&&&&&&&&&& & //进程TAKE
&&&&&&& {&&
&&&&&&&&&&& t=
&&&&&&&&&&& t=t-1000;
&&&&&&&&&&& amount=t;
&&&&&&&&&&& &
回答下列问题：
（1）上述进程执行时会产生怎样的错误？为什么？
（2）为保证系统的安全，可采用P、V操作来管理。请完善上述程序，以确保系统的安全。
解：（1）会产生与时间有关的错误。因正副卡都可以存取款，且存取款是随机的，故两个进程就可能并发执行。由于它们都涉及共享变量amount，当交替访问amount时就会出错。
（2）将amount作为临界资源，设置一个信号量S实现其互斥操作（初值为1）。完善后的程序如下：
int amount=0;
Semaphore S=1;
{&& Cobegin
&&& {&& SAVE()&&&&&&&&&& & //进程SAVE
&&&&&&& {&&
&&&&&&&&&&& P(S);
&&&&&&&&&&& k=
&&&&&&&&&&& k=k+1000;
&&&&&&&&&&& amount=k;
&&&&&&&&&&& V(S);
&&&&&&&&&&& &
&&&&&&& TAKE()&&&&&&&&&& & //进程TAKE
&&&&&&& {&&
&&&&&&&&&&& P(S);
&&&&&&&&&&& t=
&&&&&&&&&&& t=t-1000;
&&&&&&&&&&& amount=t;
&&&&&&&&&&& V(S);
&&&&&&&&&&& &
【例3-1-63】管程是由哪几部分组成的？为什么要引入条件变量？
解：（1）局部于管程的共享变量的说明；一组操作函数；初始化语句。
（2）当进程通过管程请求临界资源未能满足时，将排在队列上等待。等待的原因可能有多个，为了区分它们而引入了条件变量。
5. 进程描述题
【例3-1-64】如图3.13（a）所示，给出了6个进程合作完成某一任务的前趋图，试用P、V操作描述它。
图3.13& 进程之间的前趋关系
解法1：如图3.13（a）所示，设置进程是否执行完毕的5个信号量，对应的P、V操作如下：
Semaphore s1=s2=s3=s4=s5=0;
{&& Cobegin
&&&&&&& P1();P2();P3();P4();P5();P6();
{&& 执行代码; V(s1); V(s1); V(s1); }
{&& P(s1); 执行代码; V(s2); }
{&& P(s1); 执行代码; V(s3); }
{&& P(s1); 执行代码; V(s4); }
{&& P(s2); P(s3); 执行代码； V(s5); }
{&& P(s4); P(s5); 执行代码; }
解法2：如图3.13（b）所示，设置表示进程直接前趋关系的7个信号量，对应的P、V操作如下：
Semaphore a=b=c=d=e=f=g=0;
{&& Cobegin
&&&&&&& P1();P2();P3();P4();P5();P6();
{&& 执行代码; V(a); V(b); V(c); }
{&& P(a); 执行代码; V(d); }
{&& P(b); 执行代码; V(e); }
{&& P(c); 执行代码; V(f); }
{&& P(d); P(e); 执行代码; V(g); }
{&& P(g); P(f); 执行代码; }
【例3-1-65】使用信号量机制实现：进程A和进程B共享浮点数组data[1000]，它们共同完成对data中浮点数据的累加计算，由进程A输出最终的累加结果。
解：设置这样的共享变量：sum=0.0（存放累加结果），i=0（数组遍历下标），data[1000]。定义一个互斥信号量mutex，初值=1，用P、V操作实现本题功能的程序如下：
Semaphore mutex=1;
double sum=0.0,data[1000];
{&& Cobegin
&&&&&&& A();B();
A()&&&&&&& &&&&&& //进程A
{&& for(;;)
&&& {&& P(mutex);
&&&&&&& if(i&=1000)
&&&&&&& sum+=data[i]; i++;
&&&&&&& V(mutex);
&&& printf(&sum=%d\n&,sum);
B()&&&&&&&&&&& && //进程B
{&& for(; ;)
&&& {&& P(mutex);
&&&&&&& if(i&=1000)
&&&&&&& sum+=data[i]; i++;
&&&&&&& V(mutex);
【例3-1-66】对于生产者－消费者问题，若缓冲区中缓冲区单元只有一个，生产者和消费者各只有一人，如图3.14所示。用P、V原语实现生产者和消费者的同步操作。
图3.14& 一个单元的缓冲区
解：这样的问题为典型的同步问题。设置两个信号量，empty表示最初可用的缓冲区单元个数，初值为1；full表示最初可消费的产品个数，初值为0。对应的程序描述如下：
Semaphore empty=1;
Semaphore full=0;
{&& Cobegin
&&& {&& producer&&&&&&&&&&&&&&& && //生产者进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(empty);&&&&&&& & //排斥送产品
&&&&&&&&&&&&&&& 送产品到缓冲区;
&&&&&&&&&&&&&&& V(full);&&&&&&& && //允许取产品
&&&&&&&&&&& }
&&&&&&& consumer&&&&&&&&& &&&&&&&& //消费者进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(full);&&&&&&& && //排斥取产品
&&&&&&&&&&&&&&& 从缓冲区取产品;
&&&&&&&&&&&&&&& V(empty);&&&&&&& & //允许放产品
&&&&&&&&&&& }
【例3-1-67】有n+1个进程，即A1，&，An和B，如图3.15所示，A1，&，An进程通过同一缓冲区各自不断地向B发送消息，B不断地获取消息，刚开始时缓冲区为空，使用P、V操作来正确实现它。
图3.15& n+1个进程
解：本题相当于多个生产者、一个消费者，且缓冲区只有一个缓冲单元的情况。进程Ai发送消息时和B要同步。对应的程序如下：
Semaphore Sa=1;
Semaphore Sb=0;
{&& Cobegin
&&& {&& 进程Ai（i=1,&,n)
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(Sa);& &&&&&&&&&&&&&&& //A申请使用缓冲区发消息
&&&&&&&&&&&&&&& 向缓冲区发送消息;
&&&&&&&&&&&&&&& V(Sb);&&&&&&&&&&&&&&& && //允许B取消息
&&&&&&&&&&& }
&&&&&&& 进程B
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(Sb);&&&&&&&&&&&&&&& & //B申请使用缓冲区从中取消息
&&&&&&&&&&&&&&& 从缓冲区取消息;
&&&&&&&&&&& &&&&V(Sa);&&&&&&&&&&&&&&& && //允许A发消息
&&&&&&&&&&& }
【例3-1-68】对于生产者－消费者问题，若缓冲区中缓冲区的单元有n个，生产者和消费者各只有一人，如图3.16所示。用P、V原语实现生产者和消费者的同步操作。
图3.16& n个单元的缓冲区
解：设置3个信号量，empty表示最初可用的缓冲区单元个数，初值为n；full表示最初可消费的产品个数，初值为0。由于缓冲区对于生产者和消费者而言是一个临界资源，因此需要设置一个互斥信号量mutex。对应的程序描述如下：
Semaphore empty=n;&&&&&&&&&&&& &&&&&& //初始时空的缓冲区单元个数
Semaphore full=0;&&&&&&&&&&&& &&&&&&& //初始时满的缓冲区单元个数
Semaphore mutex=1;&&&&&&& &&&&&&&&&&& //控制对临界区访问的互斥信号量
{&& Cobegin
&&& {&& producer&&&&&&&&&&&&&&&&&&& &&& //生产者进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(empty);&&&&&&&&&&& && //申请一个空缓冲区单元
&&&&&&&&&&&&&&& P(mutex);&&&&&&&&&& &&& //互斥访问缓冲区
&&&&&&&&&&&&&&& 送一个产品到缓冲区;
&&&&&&&&&&&&&&& V(mutex);&&&&&&&&&&& && //允许访问缓冲区
&&&&&&&&&&&&&&& V(full);&&&&&&&&&& &&&& //释放一个满缓冲区单元
&&&&&&&&&&& }
&&&&&&& consumer&&&&&&&&&&&&&&&&&&& &&& //消费者进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(full);&&&&&&&&&&& &&& //申请一个满缓冲区单元
&&&&&&&&&&&&&&& P(mutex);&&&&&&&&&&& && //互斥访问缓冲区
&&&&&&&&&&&&&&& 从缓冲区取一个产品;
&&&&&&&&&&&&&&& V(mutex);&&&&&&&&&& &&& //允许访问缓冲区
&&&&&&&&&&&&&&& V(empty);&&&&&&&&&&& && //释放一个空缓冲区单元
&&&&&&&&&&& }
【例3-1-69】某杂技团进行走钢丝表演。在钢丝的A、B两端各有n名演员（n&1）在等待表演。只要钢丝上无人时便允许一名演员从钢丝的一端走到另一端。现要求两端的演员交替地走钢丝，且从A端的一名演员先开始。请问，把一名演员看作一个进程时，怎样用P、V操作来进行控制？请写出能进行正确管理的程序。
解：钢丝是一个临界资源，需互斥使用，设置一个信号量S1（初值为1），另外A端和B端要交替同步，设置一个同步信号量S2（初值为0）。对应的程序描述如下：
Semaphore S1=1,S2=0;
{&& Cobegin
&&& {&& Ai();
&&&&&&& Bi();
Ai()&&&&&&&&&&&&&&& &&&&&& //A端演员进程，i=1,2,&,n
{&& P(S1);
&&& 从A端到B端表演;
&&& V(S2);
Bi()&&&&&&&&&&&&&& &&&&&&& //B端演员进程，i=1,2,&,n
&&& 从B端到A端表演;
&&& V(S1);
【例3-1-70】在一个盒子里，混装了个数相等的围棋白子和黑子。现在要用自动分拣系统把白子和黑子分开。设系统有两个进程P1和P2，其中P1拣白子，P2拣黑子。规定每个进程每次只拣一子。当一个进程正在拣子时，不允许另一个进程同时拣子；当一个进程拣一子后，必须让另一个进程去拣。试写出这两个并发进程能正确执行的程序。
解：这是一个典型的同步问题，设置两个信号量S1和S2来协调P1、P2之间的同步。此外，由于这样同步后不存在进程P1和进程P2之间同时拣子的竞争问题，因此不必设置互斥信号量，如图3.17所示。
假设先让P1拣白子，则信号量S1和S2的初值分别为1和0。两个并发进程相应的程序如下：
Semaphore S1=1;
Semaphore S2=0;
{&& Cobegin
&&& {&& 进程P1
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(S1);&&&&&&& &&&&& //申请拣白子
&&&&&&&&&&&&&&& 拣一白子;
&&&& &&&&&&&&&&&V(S2);&&&&&&& &&&&& //允许拣黑子
&&&&&&&&&&& }
&&&&&&& 进程P2
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(S2);&&&&&&& &&&&& //申请拣黑子
&&&&&&&&&&&&&&& 拣一黑子;
&&&&&&&&&&&&&&& V(S1);&&&&&&& &&&&& //允许拣白子
&&&&&&&&&&& }
图3.17& 两个进程的同步操作
【例3-1-71】设公共汽车上有一个司机和一个售票员，它们的活动如图3.18所示，问这两个活动是什么同步关系？请用信号量机制实现他们的同步。
解：司机和售票员的活动有着直接的相互制约关系，司机只有等到售票员关好门后才能启动汽车，售票员只有等到司机停好车后才能开门，如图3.19所示。
&& &&&&&&&&
&&&&&&&&& 图3.18& 司机和售票员的活动&&&& &&&&&&&&&&&&&图3.19& 司机和售票员进程同步活动
利用Start信号量表示是否可以启动汽车，即为允许司机启动汽车的信号量。Open信号量表示是否可以开门，即为允许售票员开门信号量。它们的初值均为0，表示不允许司机启动汽车和售票员开门。司机和售票员的同步活动描述如下：
Semaphore Start=0;
Semaphore Open=0;
{&& Cobegin
&&& {&& 司机进程
&&&&&&& {&& while (true)
&&&&&& &&&&&{&& P(Start);&&&&&&& & //司机申请启动汽车
&&&&&&&&&&&&&&& 启动汽车;
&&&&&&&&&&&&&&& 正常行车;
&&&&&&&&&&&&&&& 到站停车;
&&&&&&&&&&&&&&& V(Open);&&&&&&& && //允许售票员开车门
&&&&&&&&&&& }
&&&&&&& 售票员进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& 关车门;
&&&&&&&&&&&&&&& V(Start);&&&&&&& & //允许司机启动汽车
&&&&&&&&&&&&&&& 售票;
&&&&&&&&&&&&&&& P(Open);&&&&&&& && //售票员申请开车门
&&&&&&&&&&&&&&& 开车门;
&&&&&&&&&&& }
【例3-1-72】有3个并发进程R、T、P，它们共享了一个可循环使用的缓冲区B，缓冲区B中共有n个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放到缓冲区B的一个单元中；进程T负责处理读入的字符，若发现读入的字符中有空格符，则把它改为&,&；进程P负责把处理后的字符取出并打印输出。当缓冲区B单元中的字符被进程P取出后，则又可用来存放下一次读入的字符，如图3.20所示。请用P、V操作为同步机制写出它们能正确并发执行的程序。
解：本题也是基于生产者－消费者问题的求解方法。R、T、P 3个进程需要同步操作，为此设置empty、transfer和printer 3个信号量。对应的程序如下：
图3.20& n个单元的缓冲区
char B[n];&&&&&&&&& &&&&&&&&&&&&&&&&&&& //缓冲区B
Semaphore empty=n;&&&&&&&&&&&&&&&&&&& //缓冲区中空的单元数
Semaphore transfer=0;&&&&&&&&&&&&&&& //需要转换格式的字符数
Semaphore printer=0;&&&&&&&&&&&&&&& & //需要打印的字符数
int i=0,j=0,k=0;&&&&&&&&&&&&&&&&&&& && //缓冲区数组的下标
{&& Cobegin
&&& {&& 进程R
&&&&&&& {&&
&&&&&&&&&&& while (true)
&&&&&&&&&&& {&& 输入一个字符到
&&&&&&&&&&&&&&& P(empty);&&&&&&&&&&& && //递减空缓冲区的单元数
&&&&&&&&&&&&&&& B[i]=
&&&&&&&&&&&&&&& i=(i+1)%n;
&&&&&&&&&&&&&&& V(transfer);&&&&&&& && //递增需要转换的字符数
&&&&&&&&&&& }
&&&&&& &进程T
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(transfer);&&&&&&& && //递减需要转换的字符数
&&&&&&&&&&&&&&& if (B[j]==' ')
&&&&&&&&&&&&&&&&&&& B[j]=',';
&&&&&&&&&&&&&&& j=(j+1)%n;
&&&&&&&&&&&&&&& V(printer);&&&&&&&&&&& //递增需要打印的字符数
&&&&&&&&&&& }
&&&&&&& 进程P
&&&&&&& {&&
&&&&&&&&&&& while (true)
&&&&&&&&&&& {&& P(printer);&&&&&&&&&&& //递减需要打印的字符数
&&&&&&&&&&&&&&& ch=B[k];
&&&&&&&&&&&&&&& k=(k+1)%n;
&&&&&&&&&&&&&&& V(empty);&&&&&&&&&&& && //递增空缓冲区的单元数
&&&&&&&&&&&&&&& 打印
&&&&&&&&&&& }
【例3-1-73】设有4个进程A、B、C、D共享一个缓冲区，如图3.21所示。进程A负责循环地从文件读一个整数并放入缓冲区；进程B从缓冲区中循环读取MOD 3为0的整数并累计求和；进程C从缓冲区中循环读取MOD 3为1的整数并累计求和；进程D从缓冲区中循环读取MOD 3为2的整数并累计求和。请用P、V操作写出能正确执行的程序。
图3.21& 一个单元的缓冲区
解：本题基于生产者－消费者问题的求解方法。A、B、C、D 4个进程同步操作，如图3.21所示。设有empty、SB、SC、SD 4个信号量。对应的程序如下：
Semaphore empty=1;&&&&&&&&&&&&&&&&&&& &&&& //缓冲区中空的单元数
Semaphore SB=0;&&&&&&&&&&&&&&&&&&&&&&& //缓冲区中MOD 3为0的整数个数
Semaphore SC=0;&&&&&&&&&&&&&&&&&&&&&&& //缓冲区中MOD 3为1的整数个数
Semaphore SD=0;&&&&&&&&&&&&&&&&&&&&&&& //缓冲区中MOD 3为2的整数个数
{&& Cobegin
&&& {&& 进程A
&&&&&&& {&& while (true)
&&&&&&&&&&& {&&
&&&&&&&&&&&&&&& 输入一个整数
&&&&&&&&&&&&&&& P(empty);&&&&&&&&&&& &&&&&& //互斥向缓冲区中放入整数
&&&&&&&&&&&&&&& 将num放入缓冲区;
&&&&&&&&&&&&&&& if (num MOD 3==0)
&&&&&&&&&&&&&&&&& &&V(SB);&&&&&&&&&&& &&&&&& //允许B进程执行
&&&&&&&&&&&&&&& else if (num MOD 3==1)
&&&&&&&&&&&&&&&&&&& V(SC);&&&&&&&&&&& && &&& //允许C进程执行
&&&&&&&&&&&&&&& else
&&&&&&&&&&&&&&&&&&& V(SD);&&&&&&&&&&& && &&& //允许D进程执行
&&&&&&&&&&& }
&&&&&&& 进程B
&&&&&&& {&& while (true)
&& &&&&&&&&&{&& P(SB);&&&&&&&&&&&&&&& & &&& //互斥执行B进程
&&&&&&&&&&&&&&& 从缓冲区中取整数并累计;
&&&&&&&&&&&&&&& V(empty);&&&&&&&&&&& && //允许向缓冲区中放入整数
&&&&&&&&&&& }
&&&&&&& 进程C
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(SC);&&&&&&&&&&&&&&& & //互斥执行C进程
&&&&&&&&&&&&&&& 从缓冲区中取整数并累计;
&&&&&&&&&&&&&&& V(empty);&&&&&&&&&&& && //允许向缓冲区中放入整数
&&&&&&&&&&& }
&&&&&&& 进程D
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(SD);&&&&&&&&&&&&&&& & //互斥执行D进程
&&&&&&&&&&&&&&& 从缓冲区中取整数并累计;
&&&&&&&&&&&&&&& V(empty);&&&&&&&&&&& && //允许向缓冲区中放入整数
& &&&&&&&&&&}
【例3-1-74】有3个进程PA、PB和PC协作解决文件打印问题：PA将文件记录从磁盘读入内存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录，如图3.22所示。缓冲区的大小和一个记录大小一样。请用P、V操作来保证文件的正确打印。
图3.22& 进程间的合作方式
解：设置4个信号量empty1、empty2、full1、full2，信号量empty1、empty2分别表示缓冲区1及缓冲区2是否为空，其初值为1；信号量full1、full2分别表示缓冲区1及缓冲区2是否有记录可供处理，其初值为0。同步描述如下：
Semaphore empty1=1;
Semaphore empty2=1;
Semaphore full1=0;
Semaphore full2=0;
{&& Cobegin
&&&&&&& PA();PB();PC();
PA()&&&&&&&&&&& &&&&& //PA进程
{&& while(true)
&&& {&& 从磁盘读一个记录;
&&&&&&& P(empty1);
&&&&&&& 将记录存入缓冲区1;
&&&&&&& V(full1);
PB()&&&&&&&&&&& &&&&& //PB进程
{&& while(true)
&&& {&& P(full1);
&&&&&&& 从缓冲区1中取出记录;
&&&&&&& V(empty1);
&&&&&&& P(empty2);
&&&&&&& 将记录存入缓冲区2;
&&&&&&& V(full2);
PC()&&&&&&&&&&& &&&&& //PC进程
{&& while(true)
&&& {&& P(full2);
&&&&&&& 从缓冲区2中取出记录;
&&&&&&& V(empty2);
&&&&&&& 打印记录;
【例3-1-75】有3个进程GET、COPY和PUT，它们的工作流程如图3.23所示，用P、V操作解决它们的同步问题。
解：GET、COPY和PUT进程之间有4个同步问题，设置如下4个同步信号量：
l&&&&&& S1：控制COPY和GET的&可以拷贝&同步，初值为0。
l&&&&&& S2：控制COPY和GET的&拷贝结束&同步，初值为0。
l&&&&&& S3：控制PUT和COPY的&可以打印&同步，初值为0。
l&&&&&& S4：控制PUT和COPY的&打印完毕&同步，初值为0。
如图3.24所示，表示了GET、COPY和PUT进程之间的协同关系。
图3.23& 3个进程的工作流程
图3.24& GET、COPY和PUT进程之间的协同关系
对应的进程描述如下：
Semaphore S1=0;
Semaphore S2=0;
Semaphore S3=0;
Semaphore S4=0;
{&& Cobegin
&&&&&&& GET();COPY();PUT();
GET()&&&&&&&&&&&&&&& //GET进程
{&& while(true)
&&& {&& 从文件F取一个记录送至缓冲区R中;
&&&&&&& V(S1);
&&&&&&& P(S2);
COPY()&&&&&&&&&&&&&&& //COPY进程
{&& while(true)
&&& {&& P(S1);
&&&&&&& 将缓冲区R中的记录拷贝到缓冲区T中;
&&&&&&& V(S2);
&&&&&&& V(s3);
&&&&&&& P(S4);
PUT()&&&&&&&&&&&&&&& //PUT进程
{&& while(true)
&&& {&& P(S3);
&&&&&&& 将缓冲区T中的记录打印输出;
&&&&&&& V(S4);
【例3-1-76】桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子放苹果（apple），妈妈专向盘子放桔子（orange）。两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。
解：本题原型为生产者－消费者问题，只是由一种产品改为两种水果，所以将表示满缓冲区单元个数的一个信号量改为表示盘中苹果的个数和桔子个数的两个信号量，设置如下信号量：
l&&&&&& empty：记录允许向盘子中放入水果的个数，初值为2。
l&&&&&& apple：盘子中已放入的苹果的个数，初值为0。
l&&&&&& orange：盘子中已放入的桔子的个数，初值为0。
l&&&&&& mutex：向盘子中取、放操作是一个互斥操作，也就是说盘子对于取、放水果而言是一个临界资源，为此设置一个信号量，其初值为1。
本题4个进程的同步与互斥活动的描述如下：
Semaphore mutex=1;
Semaphore empty=2;
Semaphore apple=0;
Semaphore orange=0;
{&& Cobegin
&&& {&& 进程father&&&&&&&&&&&&&&& & //父亲进程
&&&&&&& {&& while (true)
&&& &&&&&&&&{&& P(empty);&&&&&&& & //减少盘中可放入的水果数
&&&&&&&&&&&&&&& P(mutex);&&&&&&& & //申请向盘中取、放水果
&&&&&&&&&&&&&&& 向盘中放苹果;
&&&&&&&&&&&&&&& V(mutex);&&&&&&& & //允许向盘中取、放水果
&&&&&&&&&&&&&&& V(apple);&&&&&&& & //递增盘中的苹果数
&&&&&&&&&&& }
&&&&&&& 进程mother&&&&&&&& &&&&&&&& //母亲进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(empty);&&&&&&& & //减少盘中可放入的水果数
&&&&&&&&&&&&&&& P(mutex);&&&&&&& & //申请向盘中取、放水果
&&&&&&&&&&&&&&& 向盘中放桔子;
&&&&&&&&&&&&&&& V(mutex);&&&&&&& & //允许向盘中取、放水果
&&&&&&&&&&&&&&& V(orange);&&&&&&& //递增盘中的桔子数
&&& &&&&&&&&}
&&&&&&& 进程daughteri（i=1,2）&&& //两女儿进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(apple);&&&&&&& & //减少盘中苹果数
&&&&&&&&&&&&&&& P(mutex);&&&&&&& & //申请向盘中取、放水果
&&&&&&&&&&&&&&& 取盘中苹果;
&&&&&&&&&&&&&&& V(mutex);&&&&&&& & //允许向盘中取、放水果
&&&&&&&&&& &&&&&V(empty);&&&&&&& & //递增盘中可放入的水果数
&&&&&&&&&&& }
&&&&&&& 进程sonj（j=1,2）&&&&&&& && //两儿子进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(orange);&&&&&&& //减少盘中桔子数
&&&&&&&&&&&&&&& P(mutex);&&&&&&& & //申请向盘中取、放水果
&&&&&&&&&&&&&&& 取盘中桔子;
&&&&&&&&&&&&&&& V(mutex);&&&&&&&& & ／/允许向盘中取、放水果
&&&&&&&&&&&&&&& V(empty);&&&&&&& & //递增盘中可放入的水果数
&&&&&&&&&&& }
【例3-1-77】桌子上有一个盘子，可以放一个水果。爸爸总是放苹果到盘子中，而妈妈总是放香蕉到盘子中，一个儿子专等吃盘子中的香蕉，而一个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。
解：本题与上题类似，只需简单修改（empty=1），但由于这里盘中水果数为1，儿子和女儿数也为1，所以可以采用同步方法来求解。设置如下信号量：
l&&&&&& apple：是否允许从盘子中取苹果，初值为0。
l&&&&&& banana：是否允许从盘子中取香蕉，初值为0。
l&&&&&& mutex：向盘子中取、放操作是一个互斥操作，也就是说盘子对于取、放水果而言是一个临界资源，为此设置一个信号量，其初值为1（表示可以向盘放水果）。
爸爸和女儿、妈妈和儿子之间存在同步关系，这4个进程的同步如图3.25所示。
图3.25& 4个进程的同步
本题4个进程的描述如下：
Semaphore mutex=1;
Semaphore apple=0;
Semaphore banana=0;
{&& Cobegin
&&& {&& 进程father&&&&&&&&&&& //父亲进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(mutex);&&& & //申请向盘中放水果
&&&&&&&&&&&&&&& 向盘中放苹果;
&&&&&&&&&&&&&&& V(apple);&&& & //允许取苹果
&&& &&&&&&&&}
&&&&&&& 进程mother&&&&&&&&&&& //母亲进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(mutex);&&& & //申请向盘中放水果
&&&&&&&&&&&&&&& 向盘中放香蕉;
&&&&&&&&&&&&&&& V(banana);&&& //允许取香蕉
&&&&&&&&&&& }
&&&&&&& 进程daughter&&& &&&&&& //女儿进程
&&&&&&& {& &while (true)
&&&&&&&&&&& {&& P(apple);&&& & //申请向盘中取苹果
&&&&&&&&&&&&&&& 取盘中苹果;
&&&&&&&&&&&&&&& V(mutex);&&& & //允许向盘中放水果
&&&&&&&&&&& }
&&&&&&& 进程son&&&&&&&&&&&&&&& //儿子进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(banana);&&& //申请向盘中取香蕉
&&&&&&&& &&&&&&&取盘中香蕉;
&&&&&&&&&&&&&&& V(mutex);&&& & //允许向盘中放水果
&&&&&&&&&&& }
【例3-1-78】有一个师父进程和三个学徒进程，每个学徒连续不断地组装产品。做一个产品需要A、B、C三种零件各一个，这三个学徒分别掌握A零件、B零件、C零件多个。师傅源源不断提供上述三种零件，但他每次只将其中的两种零件各一个放在桌面上，具有另一种零件的学徒就可以组装产品，且做完后给师傅发信号，然后师傅再拿出两种零件各一个放在桌面上，如此反复，试写出一算法描述他们的活动。（假设通过i = rand() % 3产生0～2的随机数）。
解：三个学徒编号为0～2，设置三个信号量，用数组a表示，初值均为0，桌面作为临界区为互斥操作设置一个信号量mutex，其初值为1。对应的同步描述如下：
Semaphore a[3]=[0,0,0]; //设a[0]代表学徒0，a[1]代表学徒1，a[2]代表学徒2
Semaphore mutex=1;
{&& Cobegin
&&&&&&& sf();xt(0);xt(1);xt(2);
sf()&&&&&&& //师傅进程
{&& while（true）
&&& {&& i=rand()%3;
&&&&&&& j=rand()%3;
&&&&&&& P(mutex);
&&&&&&& 放两个零件到桌面；
&&&&&&& if (i!=j)
&&&&&&& {&& if (i==0 && j==1) V(a[2]);
&&&&&&&&&&& else if (i==1 && j==2) V(a[0]);
&&&&&&&&&&& eles V(a[1]);
xt(i)&&&&&& //学徒i进程（i=1,1,2）
{&& while（true）;
&&& {&& P(a[i]);
&&&&&&& 取两个零件组装产品；
&&&&&&& V(mutex);
【例3-1-79】有一个东西方向的独木桥，如图3.26所示，每次只能有一人通过，且不允许人在桥上停留。东、西两端各有若干人在等待过桥。请用P、V操作来实现东西两端人过桥的问题。
图3.26& 独木桥过桥问题
解：对于东、西两端的人过桥而言，独木桥就是一个临界资源，所以设置一个互斥信号量mutex，其初值为1。用P、V操作来实现东西两端人过桥问题的描述如下：
Semaphore mutex=1;
{&& Cobegin
&&& {&& 进程easti（i=1,2,&）&&&&&&& && //东端人过桥进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(mutex);&&&&&&& & &&& //互斥其他人过桥
&&&&&&&&&&&&&&& 从东向西方向过桥;
&&&&&&&&&&&&&&& V(mutex);&&&&&&& & &&& //允许其他人过桥
&&&&&&&&&&& }
&&&&&&& 进程westj（j=1,2,&）&&&&&&& && //西端人过桥进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(mutex);&&&&&&& & &&& //互斥其他人过桥
&&&&&&&&&&&&&&& 从西向东方向过桥;
&&&&&&&&&&&&&&& V(mutex);&&&&&&& & &&& //允许其他人过桥
&&&&&&&&&&& }
【例3-1-80】假设有一座东西向的车辆单行道的桥，如图3.27所示，每次允许同方向的若干车辆通过（即桥上可以有多个同方向的车辆通过）。在桥上没有车辆时，任何一端的车辆都允许上桥通过，当有车辆上桥后，同端的车辆可以继续上桥，但另一端的车辆不能上桥。请用P、V操作来实现东西两端人过桥的问题。
图3.27& 车辆过桥问题
解：本题基于读者－写者问题算法（写进程优先）。设置两个变量：eastn记录从东端上桥到西端的车辆数，westn记录从西端上桥到东端的车辆数，它们的初值均为0。这两个变量都是互斥访问的，为此设置两个互斥访问的信号量meast和mwest，它们的初值均为1。对于从东端过桥和从西端过桥的车辆而言，桥上没有车辆时，谁先请求谁先过桥，所以再设置一个互斥访问信号量wait，其初值为1。用P、V操作来实现东西两端车辆过桥问题的描述如下：
int eastn=0;&&&&&&&&&&&&&&&&&&& && //记录从东端上桥到西端的车辆数
int westn=0;&&&&&&&&&&&&&&&&&&& && //记录从西端上桥到东端的车辆数
Semaphore meast=1;&&&&&&&&& &&& //保护eastn变量的信号量
Semaphore mwest=1;&&&&&&&&&& &&& //保护westn变量的信号量
Semaphore wait=1;&&&&&&&&&&&&&&& //确定东、西两端过桥请求过桥顺序互斥信号量
{&& Cobegin
&&& {&& 进程easti（i=1,2,&）&&&& //东端车辆过桥进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(wait);&&&&&&&& & //东端车辆先请求，则先过桥
&&&&&&&&&&&&&&& P(meast);&&&&&&& & //互斥访问eastn变量
&&&&&& &&&&&&&&&if (eastn==0)& &&& //若东端第一辆车过桥，则禁止西端车辆过桥
&&&&&&&&&&&&&&&&&&& P(mwest);
&&&&&&&&&&&&&&& eastn=eastn+1;& && //东端过桥车辆数增1
&&&&&&&&&&&&&&& V(meast);&&&&&&& & //恢复访问eastn变量
&&&&&&&&&&&&&&& V(wait);&&&&&&& && //恢复车辆过桥
&&&&&&&&&&&&&&& 从东端向西端过桥;
&&&&&&&&&&&&&&& P(meast);&&&&&&& & //互斥访问eastn变量
&&&&&&&&&&&&&&& eastn--;&&&&&&&&&& //东端过桥车辆数减1
&&&&&&&&&&&&&&& if (eastn==0)&& && //若东端没车辆过桥，则允许西端车辆过桥
&&&&&&&&&&&&&&&&&&& V(mwest);
&&&&&&&&&&&&&&& V(meast);&&&&&& && //恢复访问eastn变量
&&&&&&&&&&& }
&&&&&&& 进程westj（j=1,2,&）&&& & //西端车辆过桥进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(wait);&&&&&&& && //西端车辆先请求，则先过桥
&&&&&&&&&&&&&&& P(mwest);&&&&&& && //互斥访问westn变量
&&&&&&&&&&&&&&& if (westn==0)&& && //若西端第一辆车过桥，则禁止东端车辆过桥
&&&&&&&&&&&&&&&&&&& P(meast);
&&&&&&&&&&&&&&& westn=westn+1;& && //西端过桥车辆数增1
&&&&&&&&&&&&&&& V(mwest);&&&&&& && //恢复访问westn变量
&&&&&&&&&&&&&&& V(wait);&&&&&&& && //恢复车辆过桥
&&&&&&&&&&&&&&& 从西端向东端过桥;
&&&&&&&&&&&&&&& P(mwest);&&&&&& && //互斥访问westn变量
&&&&&&&&&&&&&&& westn--;&&&&&&&& && //西端过桥车辆减1
&&&&&&&&&&&&&&& if (westn==0)& &&& //若西端没车辆过桥，则允许东端车辆过桥
&&&&&&&&&&&&&&&&&&& V(meast);
&&&&&&&&&&&&&&& V(mwest);&&&&&& && //恢复访问westn变量
&&&&&&&&&&& }
【例3-1-81】对于上题的单车道简易桥，最大可载重4辆汽车。请定义合适的信号量，正确使用P、V操作，给出任一车辆通过该桥的管理算法。
解：在上题的基础上，增设一个信号量scount，表示桥上最多可同时上桥的车辆数，其初值为4。用P、V操作来实现任一车辆通过该桥的管理算法如下：
int eastn=0;&&&&&&&&&&&&&&&&&&& && //记录从东端上桥到西端的车辆数
int westn=0;&&&&&&&&&&&&&&&&&&& && //记录从西端上桥到东端的车辆数
Semaphore meast=1;&&&&&&&&&&&& && //保护eastn变量的信号量
Semaphore mwest=1;&&&&&&&&&&&& && //保护westn变量的信号量
Semaphore scount=4;&&&&&&&&&&& && //表示桥上车辆计数信号量
Semaphore wait=1;&&&&&&&&&&&&& && //确定东、西两端过桥请求过桥顺序的互斥信号量
{&& Cobegin
&&& {&& 进程easti（i=1,2,&）&&&&& //东端车辆过桥进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(wait);&&&&&&& && //东端车辆先请求，则先过桥
&&&&&&&&&&&&&&& P(meast);&&&&&& && //拒绝访问eastn变量
&&&&&&&&&&&&&& &if (eastn==0)& &&& //若东端第一辆车过桥，则禁止西端车辆过桥
&&&&&&&&&&&&&&&&&&& P(mwest);
&&&&&&&&&&&&&&& eastn=eastn+1;&& & //东端过桥车辆数增1
&&&&&&&&&&&&&&& V(meast);&&&&&&&& & //恢复访问eastn变量
&&&&&&&&&&&&&&& V(wait);&&&&&&&&& & //恢复车辆过桥
&&&&&&&&&&&&&&& P(scount);&&&&&& & //递减还可同时上桥的车辆数
&&&&&&&&&&&&&&& 从东端向西端过桥;
&&&&&&&&&&&&&&& V(scount);&&&&&& & //递增还可同时上桥的车辆数
&&&&&&&&&&&&&&& P(meast);&&&&&&& & //拒绝访问eastn变量
&&&&&&&&&&&&&&& eastn--;&&&&&&&& && //东端过桥车辆数减1
&&&&&&&&&&&&&&& if (eastn==0)& &&& //若东端没车辆过桥，则允许西端车辆过桥
&&&&&&&&&&&&&&&&&&& V(mwest);
&& &&&&&&&&&&&&&V(meast);&&&&&& && //恢复访问eastn变量
&&&&&&&&&&& }
&&&&&&& 进程westj（j=1,2,&）&& && //西端车辆过桥进程
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(wait);&&&&&&& && //西端车辆先请求，则先过桥
&&&&&&&&&&&&&&& P(mwest);&&&&&& && //拒绝访问westn变量
&&&&&&&&&&&&&&& if (westn==0)& &&& //若西端第一辆车过桥，则禁止东端车辆过桥
&&&&&&&&&&&&&&&&&&& P(meast);
&&&&&&&&&&&&&&& westn=westn+1; //西端过桥车辆数增1
&&&&&&&&&&&&&&& V(mwest);&&&&& &&& //恢复访问westn变量
&&&&&&&&&&&&&&& V(wait);&&&&& &&& //恢复车辆过桥
&&&&&&&&&&&&&&& P(scount);&&& &&& //递减还可同时上桥的车辆数
&&&&&&&&&&&&&&& 从西端向东端过桥;
&&&&&&&&&&&&&&& V(scount);&&&&&&&&&&& & //递增还可同时上桥的车辆数
&&&&&&&&&&&&&&& P(mwest);&&&&&&&&&&& && //拒绝访问westn变量
&&&&&&&&&&&&&&& westn--;&&&&&&&&&&&&&&& //西端过桥车辆数减1
&&&&&&&&&&&&&&& if (westn==0)&&&&&&& & //若西端没车辆过桥，则允许东端车辆过桥
&&&&&&&&&&&&&&&&&&& V(meast);
&&&& &&&&&&&&&&&V(mwest);&&&&&&&&&&& && //恢复访问westn变量
&&&&&&&&&&& }
【例3-1-82】有两个合作进程P1、P2，它们从一台输入/输出设备读入数据，P1进程读入数据a，P2进程读入数据b，输入设备是一台独占设备，如图3.28所示。两个进程做如下计算：
P1：x=a+b;
P2：y=a*b;
图3.28& 两个进程的工作流程
计算完成后结果x、y由进程P1输出。用信号量实现进程P1、P2的同步算法。
解：两个进程的同步情况如图3.29所示，由于输入设备是一台独占设备，所以input(a)和input(b)只能互斥执行。设置4个信号量，s1表示数据a是否读入，s2表示数据b是否读入，s3表示是否完成y=a*b计算，mutex表示对输入设备的互斥访问。对应的同步算法如下：
Semaphore s1=0,s2=0,s3=0，mutex=1;
{&& Cobegin
&&&&&&& {&& P1()&&&&&&&&&&&&&&& //P1进程
&&&&&&&&&&& {&& P(mutex);
&&&&&&&&&&&&&&& input(a);
&&&&&&&&&&&&&&& V(mutex);
&&&&&&&&&&&&&&& V(s1);
&&&&&&&&&&&&&&& P(s2);
&&&&&&&&&&&&&&& x=a+b;
&&&&&&&&&&&&&&& P(s3);
&&&&&&&&&&&&&&& 输出x、y;
&&&&&&&&&&& }
&&&&&&&&&&& P2()&&&&&&&&&&&&&&& //P2进程
&&&&&&& &&&&{&& P(mutex);
&&&&&&&&&&&&&&& input(b);
&&&&&&&&&&&&&&& V(mutex);
&&&&&&&&&&&&&&& V(s2);
&&&&&&&&&&&&&&& P(s1);
&&&&&&&&&&&&&&& y=a*b;
&&&&&&&&&&&&&&& V(s3);
&&&&&&&&&&& }
&&&&&&& Coend
图3.29& 两个进程的同步情况
【例3-1-83】有一个阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列出一个表目，包括座位号、姓名，读者离开时撤销登记信息。阅览室有100个座位。试用P、V操作描述这些进程间的同步关系。
解：设置如下3个信号量：
l&&&&&& seats：表示阅览室中空座位数，其初值为100。
l&&&&&& readers：记录阅览室中的读者数，其初值为0。
l&&&&&& mutex：互斥信号量（对于读者而言，阅览室是一个临界资源，任何时刻最多只有一位读者填写登记表或撤销登记），其初值为1。
对应的算法描述如下：
Semaphore seats=100;
Semaphore readers=0;
Semaphore mutex=1;
{&& Cobegin
&&& {&& 读者进入阅览室进程readerini（i=1,&,n）
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(seats);&&&&&&& & //递减空座位数
&&&&&&&&&&&&&&& P(mutex);&&&&&&& & //排斥其他读者访问阅览室
&&&&&&&&&&&&&&& 填写登记表;
&&&&&&&&&&&&&&& 进入阅览室;
&& &&&&&&&&&&&&&V(mutex);&&&&&&& & //允许其他读者访问阅览室
&&&&&&&&&&&&&&& V(readers);&&&&&&& //递增读者数
&&&&&&&&&&& }
&&&&&&& 读者离开阅览室进程readerouti（i=1,&,n）
&&&&&&& {&& while (true)
&&&&&&&&&&& {&& P(readers);&&&&&&& //递减读者数
&&&&&&&&&&&&&&& P(mutex);&&&&&&& & &&& //排斥其他读者访问阅览室
&&&&&&&&&&&&&&& 撤销登记;
&&&&&&&&&&&&&&& 离开阅览室;
&&&&&&&&&&&&&&& V(mutex);&&&&&&& & &&& //允许其他读者访问阅览室
&&&&&&&&&&&&&&& V(seats);&&&&&&& & &&& //递增空座位数
&&&&&&&&&&& }
【例3-1-84】复印室有一个操作员为顾客复印资料，有5把椅子供顾客休息并等待复印。如果没有顾客，则操作员休息。当顾客来到复印室时，如果有空椅子则坐下来。当操作员空闲时顾客站起来唤醒操作员进行复印，复印完后离开复印室；如果没有空椅子则离开复印室。试用P、V操作实现顾客和操作员活动的同步。
解：本题等同于理发师睡觉问题，其操作员和顾客的工作流程如图3.30所示（图中虚框是另设的）。对应的程序描述如下：
图3.30& 操作员和顾客工作流程
int waiting=0;&&&&&&&&&&& &&& //等待的顾客(含正在复印的人数，最多不超过6人)
Semaphore mutex=1; &&&&& &&& //用于waiting变量的互斥操作
Semaphore standup=1;&&&&&&& //顾客站起来准备复印的人数
Semaphore wchair=1;&&&&& &&& //空椅子的个数
Semaphore ready=0;&&&&&&& && //是否有顾客准备好
Semaphore finish=0;&&&&&&& & //操作员是否完成复印
{&& Cobegin
&&&&&&& operator();
&&&&&&& customer();
void operator()&&&&&&&&&& &&& &&& //操作员进程
{&& while (true)
&&& {&& P(ready);&&&&&&& &&&&& &&& //有顾客准备好了
&&&&&&& 复印;
&&&&&&& V(finsish);&&&&&& &&& &&& //允许其他顾客复印
void customer()&&&&&&&&&&& && &&& //顾客进程
{&& P(mutex);&&&&&&&&&&&&&&& & &&& //互斥waiting变量的操作
&&& if (waiting&6)&& &&&&&&&& &&& //如果有空的椅子，就找到椅子坐下等待
&&& {&&&&&&&&&&&&&&&&&&&&&& &&& &&& //含正在复印的顾客，最多可6个人等待
&&&&&&& waiting=waiting+1;&&& &&& //等待顾客数增1
&&&&&&& V(mutex);&&&&&&&&&&& & &&& //允许waiting变量的操作
&&& {&& V(mutex);&&&&&&&&&&& & &&& //允许waiting变量的操作
&&&&&&& 离开;
&&& P(wchair);&&&&&&&&&&&&&&& &&& //找一个空椅子坐下
&&& P(standup);&&&&&&& &&&&&&&&&&& //再站起来准备复印
&&& V(wchair);&&&&&&&&&&&&&&& &&& //允许其他人坐空椅子
&&& V(ready);&&&&&&&&&&&&&&& & &&& //该顾客准备好了
&&& P(finish);&&&&&&&&&&&&&&& &&& //等待操作员完成
&&& V(standup);&&&&&&& &&&&&&&&&&& //离开复印室
&&& P(mutex);&&&&&&&&&&&&&&& & &&& //互斥waiting变量的操作
&&& waiting=waiting-1;&&&&&&& &&& //等待顾客数减1
&&& V(mutex);&&&&&&&&&&&&&&& &&&&& //允许waiting变量的操作
【例3-1-85】画图说明管程的组成，并利用管程解决生产者－消费者问题。
解：管程的组成如图3.31所示，用代码描述如下：
monitor 管程名
{&& 共享变量说明;
&&& 过程1;
&&& 过程n;
&&&&&&& 共享变量初始化语句序列;
图3.31& 管程的组成
利用管程解决生产者－消费者问题，仍使用有N个缓冲区的环形缓冲区，每个缓冲区可容纳一个数据记录。In是空缓冲区的头指针，Out是满缓冲区的头指针。用notfull作为没有满缓冲区的条件变量，notempty作为没有空缓冲区的条件变量。用Count作为当前满缓冲区的数量，代码如下：
Monitor ProcedureConsumer
{&& Record buffer[N];&&&&&&&&&&& &&& //缓冲区buffer中可放N个Record类型的数据
&&& int In,Out,C
&&& Condition notempty,&&& & //信号量定义
&&& append(Record x)&&&&&&&&&&&&&&& && //过程append
&&& {&& if (Count==N) wait(notempty);&&& //缓冲区满，等待
&&&&&&& buffer[In]=x;&&&&&&&&&&&&&&& & //将x放在环形缓冲区中
&&&&&&& In=(In+1) % N;
&&&&&&& Count=Count+1;&&&&&&&&&&&&&&& //递增满缓冲的单元数
&&&&&&& signal(notfull);
&&& take(Record x)&&&&&&&&&&&&&&&&&&& //过程take
&&& {&& if (Count==0) wait(notfull); //缓冲区空，等待
&&&&&&& x=buffer[Out];
&&&&&&& Out=(Out+1) % N;&&&&&&&&&&& && //从环形缓冲区中取出x
&&&&&&& Count=Count&1;&&&&&&&&&&&&&&& //递减满缓冲单元数
&&&&&&& signal(notempty);
&&&&&&& In=Out=Count=0&&&&&&&&&&&&&&& //初始化语句
//以上为管程
{&& Cobegin
&&& {&& produceri;
&&&&&&& consumerj;
进程produceri（i=1,2,&）&&&&& &&&&&&&&&&&& //生产者进程
&&& while (true)
&&& {&& 生产x;
&&&&&&& append(x);
进程consumerj（j=1,2,&）&&&&&&&&&&&&&&& && //消费者进程
&&& while (true)
&&& {&& take(x);
&&&&&&& 消费或处理x;
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。
文章下载读书