14.【解答】

2026 旧版 · 非 2027 主源 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 14.【解答】

本题是一个典型的利用信号量实现前驱关系的同步问题。

Semaphore a=b=c=d=e=f=g=h=0; //定义进程执行顺序的信号量
CoBegin
process P1(){
执行P1的任务;
V(a); //实现先P1后P2的同步关系
V(b); //实现先P1后P3的同步关系
}
process P2(){
P(a); //检查P1是否已运行完成
执行P2的任务;
V(c); //实现先P2后P4的同步关系
V(d); //实现先P2后P5的同步关系
}
process P3(){
P(b); //检查P1是否已运行完成
执行P3的任务;
V(e); //实现先P3后P4的同步关系
V(f); //实现先P3后P5的同步关系
}
process P4(){
P(c); //检查P2是否已运行完成
P(e); //检查P3是否已运行完成
执行P4的任务;
}


&lt;!-- page: 152 --&gt;

```lisp
V(g); //实现先 P4 后 P6 的同步关系
}
process P5(){
P(d); //检查 P2 是否已运行完成
P(f); //检查 P3 是否已运行完成
执行 P5 的任务;
V(h); //实现先 P5 后 P6 的同步关系
}
process P6(){
P(g); //检查 P4 是否已运行完成
P(h); //检查 P5 是否已运行完成
执行 P6 的任务;
CoEnd


## 15.【解答】

本题是经典的生产者-消费者问题。把缓冲区的每 20 个字视为一个基本单位，因此缓冲区共有 $1000 / 20 = 50$ 个空位。设置互斥信号量 mutex，用于对缓冲区的访问；还需要设置两个同步信号量：full 表示缓冲区已有多少数据，empty 表示缓冲区还有多少空位置。

Semaphore mutex=1; //互斥使用缓冲区
Semaphore full1=0; //表示缓冲区已有多少个 20 字数据，初值为 0
Semaphore empty=50; //表示缓冲区还有多少个 20 字空位，初值为 50
process P(){
p(empty);   for(int i=0; i&amp;lt;2; ++i) {
P(mutex);     p(full); P(mutex);
read();     get();
V(mutex);     V(mutex); V(empty);
V(full);     p(full); P(mutex);
}
get(); V(mutex); V(empty);
comp();
}
print();
}


## 16.【解答】

供应者与 3 个抽烟者分别是同步关系。由于供应者无法同时满足两个或以上的抽烟者，3 个抽烟者对抽烟这个动作互斥（或者理解为互斥访问桌子）。显然这里有 4 个进程。供应者作为生产者向 3 个抽烟者提供材料。设置信号量 offer1, offer2, offer3 分别表示烟草和纸组合的资源、烟草和胶水组合的资源、纸和胶水组合的资源，信号量 finish 用于互斥进行抽烟动作。代码如下：

int num=0; //存储随机数
semaphore offer1=0; //定义信号量对应烟草和纸组合的资源
semaphore offer2=0; //定义信号量对应烟草和胶水组合的资源
semaphore offer3=0; //定义信号量对应纸和胶水组合的资源
semaphore finish=0; //定义信号量表示抽烟是否完成
process P1(){
while(1){
num++;
num=num%3;
if(num==0)
V(offer1); //提供烟草和纸
else if(num==1)
V(offer2); //提供烟草和胶水
else
V(offer3); //提供纸和胶水
任意两种材料放在桌子上;
P(finish);
}


&lt;!-- page: 153 --&gt;

```c
}
}
process P2() {
//拥有烟草者
while(1) {
P(offer3);
拿纸和胶水，卷成烟，抽掉;
V(finish);
}
}
process P3() {
//拥有纸者
while(1) {
P(offer2);
拿烟草和胶水，卷成烟，抽掉;
V(finish);
}
}
process P4() {
//拥有胶水者
while(1) {
P(offer1);
拿烟草和纸，卷成烟，抽掉;
V(finish);
}
}


## 17. 【解答】

互斥资源：缓冲区只能互斥访问，因此设置互斥信号量 mutex。

同步问题：$\mathrm{P}_1, \mathrm{P}_2$ 因为奇数的放置与取用而同步，设同步信号量 odd；$\mathrm{P}_1, \mathrm{P}_3$ 因为偶数的放置与取用而同步，设置同步信号量 even；$\mathrm{P}_1, \mathrm{P}_2, \mathrm{P}_3$ 因为共享缓冲区，设同步信号量 empty，初值为 $N$。程序如下：

semaphore mutex=1; //缓冲区操作互斥信号量
semaphore odd=0, even=0; //奇数、偶数进程的同步信号量
semaphore empty=N; //空缓冲区单元个数信号量
cobegin(
Process P1()
while(True)
{
x=produce(); //生成一个数
P(empty); //判断缓冲区是否有空单元
P(mutex); //缓冲区是否被占用
Put();
V(mutex); //释放缓冲区
if(x%2==0)
V(even); //若是偶数，向 P3 发出信号
else
V(odd); //若是奇数，向 P2 发出信号
}
Process P2()
while(True)
{
P(odd); //收到 P1 发来的信号，已产生一个奇数
P(mutex); //缓冲区是否被占用
getodd();
V(mutex); //释放缓冲区
V(empty); //向 P1 发信号，多出一个空单元
countodd();
}
}


&lt;!-- page: 154 --&gt;

```c
Process P3()
while(True)
{
P(even); //收到 P1 发来的信号，已产生一个偶数
P(mutex); //缓冲区是否被占用
geteven(); //释放缓冲区
V(mutex); //问 P1 发信号，多出一个空单元
counteven();
}
}coend


## 18.【解答】

互斥资源：取号机（一次只有一位顾客领号），因此设置互斥信号量 mutex。

同步问题：顾客需要获得空座位等待叫号。营业员空闲时，将选取一位顾客并为其服务。空座位的有无会影响等待顾客的数量，顾客的有无决定了营业员是否能开始服务，因此分别设置信号量 empty 和 full 来实现这一同步关系。另外，顾客获得空座位后，需要等待叫号和被服务。这样，顾客与营业员就服务何时开始又构成了一个同步关系，定义信号量 service 来完成这一同步过程。

semaphore empty=10; //空座位的数量，初值为 10
semaphore mutex=1; //互斥使用取号机
semaphore full=0; //已占座位的数量，初值 0
semaphore service=0; //等待叫号
cobegin
{
Process 顾客 i
{
P(empty); //等空位
P(mutex); //申请使用取号机
从取号机上取号;
V(mutex); //取号完毕
V(full); //通知营业员有新顾客
P(service); //等待营业员叫号
接受服务;
}
Process 营业员
{
while(True) {
P(full); //没有顾客则休息
V(empty); //离开座位
V(service); //叫号
为顾客服务;
}
}
}coend


## 19.【解答】

出入口一次仅允许一人通过，设置互斥信号量 mutex，初值为 1。博物馆最多可以同时容纳 500 人，因此设置信号量 empty，初值为 500。

semaphore empty=500; //博物馆可以容纳的最多人数
semaphore mutex=1; //用于出入口资源的控制
cobegin
参观者进程 i:
{
...
P(empty); //可容纳人数减 1
}



<!-- page: 155 -->

P(mutex); //互斥使用门
进门;
V(mutex);
参观;
P(mutex); //互斥使用门
出门;
V(mutex);
V(empty); //可容纳人数增1
...
}
coend


## 20. 【解答】

这是典型的生产者和消费者问题，只对典型问题加了一个条件，只需在标准模型上新加一个信号量，即可完成指定要求。

设置4个变量 mutex1, mutex2, empty 和 full, mutex1 用于控制一个消费者进程在一个周期(10次)内对缓冲区的访问，初值为 1: mutex2 用于控制进程单次互斥地访问缓冲区，初值为 1: empty 代表缓冲区的空位数，初值为 1000: full 代表缓冲区的产品数，初值为 0。伪代码如下：

semaphore empty=1000; //空缓冲区数
semaphore full=0; //非空缓冲区数
semaphore mutex1=1; //用于实现生产者之间的互斥
semaphore mutex2=1; //用于实现消费者之间的互斥
int in=0;
int out=0;


生产者进程

while(TRUE) {
produce;
P(empty);
P(mutex1);
put an item into buf[in];
in=(in+1) mod n;
V(mutex1);
V(full);
}


消费者进程

while(TRUE) {
P(mutex2);
for(int i=0; i&amp;lt;10; i++) {
P(full);
get an item from buf[out];
out=(out+1) mod n;
V(empty);
}
V(mutex2);
Consume;
}


## 21. 【解答】

本题是一个典型的生产者-消费者问题。A 和 B 既是生产者，又是消费者。首先分析题中的互斥关系，信箱 A 和信箱 B 作为生产者-消费者问题中的缓冲区，需要互斥访问，因此设置两个信号量 mutex_A 和 mutex_B。然后分析 A 和 B 的同步关系，A 有两个动作，分别是从信箱 A 中取出邮件和将新邮件放入信箱 B，因此设置信号量 Full_A 和 Empty_B，用来保证信箱 A 中有邮件可以取，信箱 B 中有空间可以放。B 的分析同理。因此本题的所有信号量设置如下：

semaphore Full_A = x; // Full_A 表示 A 的信箱中的邮件数量


&lt;!-- page: 156 --&gt;

```txt
semaphore Empty_A = M-x; // Empty_A 表示 A 的信箱中还可存放的邮件数量
semaphore Full_B = y; // Full_B 表示 B 的信箱中的邮件数量
semaphore Empty_B = N-y; // Empty_B 表示 B 的信箱中还可存放的邮件数量
semaphore mutex_A = 1; // mutex_A 用于 A 的信箱互斥
semaphore mutex_B = 1; // mutex_B 用于 B 的信箱互斥


互斥信号量的 PV 操作直接放置在对信箱操作的前后。在 A 取邮件之前需执行 P(Full_A)来检查信箱 A 中是否有邮件可取，取出邮件之后需执行 V(Empty_A)，表示新增了一个邮件大小的空间；在 A 将邮件放入邮箱 B 之前需执行 P(Empty_B)来检车信箱 B 中是否有空间可以放，放完邮件之后需执行 V(Full_B)，表示信箱 B 增加了一个邮件。B 的分析同理。

Cobegin

[tbl-36.md](tbl-36.md)

Coend

## 22.【解答】

对于这类问题：

首先，找出有可能需要互斥访问的变量，只有全局变量才可能需要互斥访问，也就是说，含全局变量的代码段才可能是临界区。而局部变量是不需要互斥访问的，就算不同的进程之间都有相同名字的局部变量，但对不同的进程来说，它们只认识属于自己的局部变量。

其次，有关互斥的难点不在于找出哪些变量有可能需要互斥访问，而要理解互斥是进程之间对某个变量的互斥，不能脱离具体的进程来谈某个变量需不需要互斥访问。前面说了全局变量有可能需要互斥访问，但也不一定，因为这要看进程对它的操作，因此，一组互斥关系需要指出是哪些进程对哪个变量的互斥。例如，考虑两种情况：第一种情况是，进程 1 和进程 2 需要对共享变量 C 互斥访问，进程 1 和进程 3 也需要对变量 C 互斥访问，这是两组不同的互斥关系，而不能简单地理解为对 C 的互斥；第二种情况是，进程 1、2、3 两两之间都需要对变量 C 互斥访问。这种情况与第一种情况的差别是，第一种情况允许进程 2、3 对变量 C 的访问是不互斥的。若题目给出的是第一种情况，而我们采用了第二种情况去解题，则可能有同学认为，我依然满足了题目的要求啊，进程 1、2 之间以及进程 1、3 之间对 C 的访问都是互斥的，但这样降低了并发度，因为第二种情况允许进程 2、3 对变量 C 的访问是不互斥的，这也是 PV 互斥的最大难点，就是在没有准确找准互斥关系的条件下，容易导致程序的并发度降低，从而扣分。

本题的分析如下。


<!-- page: 157 -->

首先，全局变量是 $x$、$y$、$z$，只有对这三个变量的访问才可能需要互斥。线程1涉及 $x$、$y$ 的访问（只读），线程2涉及 $y$、$z$ 的访问（只读），线程3涉及 $y$、$z$ 的访问（读和写）。

其次，找互斥关系，根据什么原则呢？答案是读者-写者原则。读和读之间不需要互斥，读和写之间、写和写之间需要互斥。因此，本题的互斥关系如下：第一对，thread1和thread3之间需要对变量 $y$ 的访问互斥；第二对，线程2和线程3之间需要对变量 $y$ 的访问互斥；第三对，线程2和线程3之间需要对变量 $z$ 访问的互斥。正确找出所有互斥关系后，接下来的操作就很简单。因为有三组互斥关系，所以定义三个互斥信号量，分别为 $\text{mutex\_y1} = 1$、$\text{mutex\_y2} = 1$ 和 $\text{mutex\_z} = 1$，然后分别将它们加到线程代码段的相应位置。例如，在线程1的 $w = \text{add}(x, y)$ 和线程3的 $y = \text{add}(y, w)$ 上下用 $\text{mutex\_y1}$ 夹住；在线程2的 $w = \text{add}(y, z)$ 和线程3的 $z = \text{add}(z, w)$ 上下用 $\text{mutex\_y2}$ 夹住；在线程2的 $w = \text{add}(y, z)$ 和线程3的 $y = \text{add}(y, w)$ 上下用 $\text{mutex\_z}$ 夹住。

semaphore mutex_y1=1; //mutex_y1用于thread1与thread3对变量y的互斥访问
semaphore mutex_y2=1; //mutex_y2用于thread2与thread3对变量y的互斥访问
semaphore mutex_z=1; //mutex_z用于thread2与thread3对变量z的互斥访问


互斥代码如下：

[tbl-37.md](tbl-37.md)

## 23.【解答】

回顾传统的哲学家问题，假设餐桌上有 $n$ 名哲学家、$n$ 根筷子，那么可以用这种方法避免死锁（本书考点讲解中提供了这一思路）：限制至多允许 $n-1$ 名哲学家同时“抢”筷子，那么至少会有 1 名哲学家可以获得两根筷子并顺利进餐，于是不可能发生死锁的情况。

本题可以用碗这个限制资源来避免死锁：当碗的数量 $m$ 小于哲学家的数量 $n$ 时，可以直接让碗的资源量等于 $m$，碗保不会出现所有哲学家都拿一侧筷子而无限等待另一侧筷子进而造成死锁的情况；当碗的数量 $m$ 大于或等于哲学家的数量 $n$ 时，为了让碗起到同样的限制效果，我们让碗的资源量等于 $n-1$，这样就能保证最多只有 $n-1$ 名哲学家同时进餐，所以得到碗的资源量为 $\min\{n-1, m\}$。在进行PV操作时，碗的资源量起限制哲学家取筷子的作用，所以需要先对碗的资源量进行P操作。具体过程如下：

//信号量
semaphore bowl; //用于协调哲学家对碗的使用
semaphore chopsticks[n]; //用于协调哲学家对筷子的使用
for(int i=0;i&amp;lt;n;i++) //设置两名哲学家之间筷子的数量
chopsticks[i]=1;


&lt;!-- page: 158 --&gt;

```txt
bowl=min(n-1,m); //bowl≤n-1，确保不死锁
CoBegin
while (TRUE) { //哲学家 i 的程序
思考;
P(bowl); //取碗
P(chopsticks[i]); //取左边筷子
P(chopsticks[(i+1)%n]); //取右边筷子
就餐;
V(chopsticks[i]);
V(chopsticks[(i+1)%n]);
V(bowl);
}
CoEnd


## 24.【解答】

本题是一个典型的利用信号量实现前驱关系的同步问题。首先画出各个操作之间的执行顺序图，可以看出，A、B、D 的执行不需要任何前提条件。执行完 A 和 B 之后才能执行 C，存在两对同步关系：A→C 和 B→C，设置两个同步变量 SAC = 0 和 SBC = 0，完成 A 和 B 之后分别执行 V(SAC) 和 V(SBC)，表示 A 或 B 已完成；执行 C 之前需要执行 P(SAC) 和 P(SBC)，检查 A 和 B 是否完成。执行完 C 和 D 之后才能执行 E，也存在两对同步关系：C→E 和 D→E，因此再设置两个同步变量 SCE = 0 和 SDE = 0，完成 C 和 D 之后分别执行 V(SCE) 和 V(SDE)，表示 C 或 D 已完成；执行 E 之前需要执行 P(SCE) 和 P(SDE)，检查 C 和 D 是否完成。


semaphore SAC = 0; //控制 A 和 C 的执行顺序
semaphore SBC = 0; //控制 B 和 C 的执行顺序
semaphore SCE = 0; //控制 C 和 E 的执行顺序
semaphore SDE = 0; //控制 D 和 E 的执行顺序


5个操作可描述为如下。

CoBegin
A() {
完成动作 A:
V(SAC); //实现 A、C 之间的同步关系
}
B() {
完成动作 B:
V(SBC); //实现 B、C 之间的同步关系
}
C() {
//C 必须在 A、B 都完成后才能完成
P(SAC);
P(SBC);
完成动作 C;
V(SCE); //实现 C、E 之间的同步关系
}
D() {
完成动作 D;
V(SDE); //实现 D、E 之间的同步关系
}
E() {


&lt;!-- page: 159 --&gt;

```txt
//E必须在完成C、D之后执行
P (SCE);
P (SDE)
完成动作E;
}
CoEnd


25. 【解答】

1）信号量S是能被多个进程共享的变量，多个进程都可通过wait()和signal()对S进行读、写操作。所以，wait()和signal()操作中对S的访问必须是互斥的。
2）方法1错误。在wait()中，当 $S \leq 0$ 时，关中断后，其他进程无法修改S的值，while语句陷入死循环。方法2正确。方法2在循环体中有一个开中断操作，这样就可以使其他进程修改S的值，从而避免while语句陷入死循环。
3）用户程序不能使用开/关中断指令实现临界区互斥。因为开中断和关中断指令都是特权指令，不能在用户态下执行，只能在内核态下执行。

26. 【解答】

本题是一个典型的利用信号量实现前驱关系的同步问题。需要强调的是，只有不同进程之间的操作才需要进行同步。进程T1依次执行A、E、F，进程T2依次执行B、C、D。我们需要分析哪些操作必须在另一个进程的某个操作完成之后才能执行。由图可知，对进程T1来说，E必须在进程T2执行完C后才能执行；对进程T2来说，C必须在进程T1执行完A后才能执行。因此，有两对同步关系：A→C和C→E。为了实现这两对同步关系，定义两个同步信号量S_AC和S_CE*进程T1执行完A后，发出信号signal(S_AC)，表示A已执行完成；进程T2准备执行C之前，等待信号wait(S_AC)，检查A是否执行完成。同理，进程T2执行完C后，发出信号signal(S_CE)，表示C已执行完成；进程T1准备执行E之前，等待信号wait(S_CE)，检查C是否执行完成。这样就保证了两个进程之间的同步。

[tbl-38.md](tbl-38.md)

27. 【解答】

1）if语句无法实现对临界区的互斥访问，因为if语句执行后，不论结果如何，线程都能访问临界区。本题使用swap指令和lock变量来实现对临界区的互斥访问，当线程不能进入临界区时，本身并不会主动放弃CPU，因此需要让线程在进入区中循环检查lock值，可以使用while循环，当lock值为TRUE时，线程一直执行while循环的内容，直到lock值被修改为FALSE时，线程才能进入临界区，因此将进入区中的语句“if(key==TRUE) swap key, lock”修改为“while(key==TRUE) swap key, lock”。在退出区中，代表该线程对临界资源的访问已经结束，此时需要将lock值设为FALSE，代表其他线程可以访问临界区，因此将退出区中的语句“lock=TRUE”修改为“lock=FALSE”。
2）否。因为多个线程可以并发执行newSwap()，newSwap()执行时传递给形参b的是共享变量lock的地址，在newSwap()中对lock既有读操作又有写操作，并发执行时不能保证实现两个变量值的原子交换，从而导致并发执行的线程同时进入临界区。例如，线程A和


<!-- page: 160 -->

线程 B 并发执行，初始时 lock 值为 FALSE，当线程 A 执行完 *a = *b 后发生了进程调度，切换到线程 B 执行，线程 B 执行完 newSwap 后发生线程切换，此时线程 A 和 B 都能进入临界区，不能实现互斥访问。