14

一组进程的执行顺序如下图所示，圆圈P1，P2，P3，P4，P5，P6表示进程，弧上的字母a,b，c, d,e,f,g,h表示同步信号量，请用P，V操作实现进程的同步。

---

semaphore a = b = c = d = e = f = g = h = 0;
CoBegin
process P1()
{执行P1;V(a);V(b);
}
process P2()
{P(a);执行P2;V(c);V(d);
}
process P3()
{P(b);执行P3;V(e);V(f);
}
process P4()
{P(c);P(e);执行P4;V(g);
}
process P5()
{P(d);P(f);执行P5;V(h);
}
process P6()
{P(g);P(h);执行P6;
}
CoEnd

15

有3个进程P、P1、P2合作处理数据，P从输入设备读数据到缓冲区，缓冲区可存1000个字。
P1和P2的功能一样，都是从缓冲区取出数据并计算，再打印结果。请用信号量的P,V操作实现。
其中，语句
read()从输入设备读入20个字到缓冲区；
get()从缓冲区取出 20个字；
comp()计算40个字输出并得到结果的1个字；
print()打印结果的2个字。

---

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

semaphore mutex = 1;      // 互斥使用缓冲区
semaphore full = 0;       // 表示缓冲区中已有多少个20字数据
semaphore empty = 50;     // 表示缓冲区中还有多少个20字空位process P()
{P(empty);P(mutex);read();V(mutex);V(full);
}
process P1/P2()
{P(full);get();P(full);get();comp();V(empty);print();V(empty);print();
}

16

假设有3个抽烟者和1个供应者。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。
三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。
供应者无限提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就将另外两种材料放到桌上，如此重复，让3个抽烟者轮流抽烟。

---

供应者与3个抽烟者分别是同步关系，三个抽烟者对抽烟这个动作互斥
设置信号量offer1，offer2，offer3分别表示烟草和纸，烟草和胶水，纸和胶水
信号量finish用于互斥进程抽烟动作

int num = 0;     // 存储随机数
semaphore offer1 = offer2 = offer3 = finish = 0;
// finish表示抽烟是否完成
process P1()
{while (1){num++;num = nun % 3;if (num == 0)V(offer1);else if (num == 1)V(offer2);elseV(offer3);任意两种材料放在桌子上P(finish);}
}
process P2()
{while (1){P(offer3);抽烟;V(finish);}
}
process P3()
{while (1){P(offer2);抽烟;V(finish);}
}
process P4()
{while (1){P(offer1);抽烟;V(finish);}
}

18

某银行提供1个服务窗口和10个供顾客等待的座位。
顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。
取号机每次仅允许一位顾客使用。
当营业员空闲时，通过叫号选取一位顾客，并为其服务。
顾客和营业员的活动过程描述如下：

cobegin
{process 顾客i{从取号机获取一个号码；等待叫号；获取服务；}process 营业员{while(TRUE){叫号；为客户服务；}}
}
coend

请添加必要的信号量和P，V操作，实现上述过程中的互斥与同步。
要求写出完整的过程，说明信号量的含义并赋初值。

---

互斥资源：取号机，设置互斥信号量mutex
同步问题：空座位的有无影响等待顾客的数量，顾客的有无决定了营业员是否能开始服务，因此分别设置信号量empty和full来实现这一同步关系
顾客获得空座位后，需要等待叫号和被服务，又是一个同步关系，定义信号量service

semaphore empty = 10;   // 空座位的数量
semaphore mutex = 1;    // 互斥使用取号机
semaphore full = 0;     // 已占座位的数量
semaphore service = 0;  // 等待叫号
cobegin
{process 顾客i{P(empty);       // 申请空座位-1P(mutex);       // 申请取号机-1从取号机获取一个号码；V(mutex);       // 释放取号机+1V(full);        // 释放一个已占座位，数量+1P(service);     // 消耗一个叫号，-1获取服务；}process 营业员{while(TRUE){P(full);    // 申请一个已占座位，数量-1V(empty);   // 释放一个空座位，数量+1V(service); // 释放一个叫号，+1为客户服务；}}
}
coend

20

系统中有多个生产者进程和多个消费者进程，共享一个能存放1000 件产品的环形缓冲区（初始为空）。
缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；
缓冲区未空时，消费者进程可从缓冲区取走一件产品，否则等待。
要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品。
请使用信号量P，V操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。

---

生产者和消费者问题
设置4个信号量mutex1，mutex2，empty和full，
mutex1用于控制一个消费者进程在一个周期内对缓冲区访问，初值为1
mutex2用于控制进程在单次互斥地访问缓冲区，初值为1
empty代表缓冲区的空位数，初值为1000
full代表缓冲区的产品数，初值为0

semaphore mutex1 = 1;     // 用于实现消费者周期内的互斥
semaphore mutex2 = 1;     // 用于实现访问缓冲区的互斥
semaphore empty = 1000;   // 空缓冲区数
semaphore full = 0;       // 非空缓冲区数producer()
{while (1){生产一个产品;P(empty);        // 申请一个空位P(mutex2);       // 互斥使用缓冲区把产品放入缓冲区;V(mutex2);       // 释放缓冲区V(full);         // 释放一个产品}
}consumer()
{while (1){P(mutex1);       // 消费者使用缓冲区for (int i = 0; i < 10; ++i){P(full);             // 消耗一个产品P(mutex2);           // 互斥使用缓冲区从缓冲区取出一件产品;V(mutex2);           // 释放缓冲区V(empty);            // 释放一个空位消费这件产品;}V(mutex1);      // 消费者释放缓冲区}
}

21

有A，B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题。
将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。
假设A的信箱最多放M个邮件，B的信箱最多放N个邮件。
初始时A的信箱中有x个邮件（0<x<M）， B的信箱中有y个邮件（0<y<N）。
辩论者每取出一个邮件，邮件数减1。
A和B两人的操作过程描述如下：

CoBegin
A{while(TRUE){从A的信箱中取出一个邮件；回答问题并提出一个新问题；将新邮件放入B的信箱； }
}
B
{while(TRUE){从B的信箱中取出一个邮件；回答问题并提出一个新问题；将新邮件放入A的信箱；}
}
Coend

当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。
当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。
请添加必要的信号量和PV操作，以实现上述过程的同步。要求写出完整的过程，并说明信号量的含义和初值。

---

生产者消费者问题
A和B既是生产者也是消费者，信箱A和B是缓冲区，需要互斥访问
设置fullA = x，emptyA = m-x，fullB = y，emptyB = N-y，mutexA = 1，和mutexB = 1
互斥信号量的PV操作直接夹住对信息的操作
对信箱A操作之前，检查fullA是否有邮件可取，放入B时检查emptyB是否有空余空间可以放，放完后执行V(fullB)，表示B中增加了一个邮件

CoBegin
A{while(TRUE){P(fullA);P(mutexA);从A的信箱中取出一个邮件;V(mutexA);V(emptyA);回答问题并提出一个新问题;P(emptyB);P(mutexB);将新邮件放入B的信箱;V(mutexB);V(fullB); }
}
B
{while(TRUE){P(fullB);P(mutexB);从B的信箱中取出一个邮件;V(mutexB);V(emptyB);回答问题并提出一个新问题;P(emptyA);P(mutexA);将新邮件放入A的信箱;V(mutexA);V(fullA);}
}
Coend

23

有n（n≥3）名哲学家围坐在一张圆桌边，每名哲学家交替地就餐和思考。
在圆桌中心有m（m≥1）个碗，每两名哲学家之间有一根筷子。每名哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。
为使尽可能多的哲学家同时就餐，且防止出现死锁现象，
请使用信号量的P，V操作描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。

---

当碗的数量m小于哲学家数量n时，直接让碗的资源量等于m，避免死锁
当m大于n时，让碗的资源量=n-1，避免死锁
在PV操作时，要先P碗

semaphore bowl;
semaphore chopsticks[n];
for (int i = 0; i < n; i++)
{chopsticks[i] = 1;
}
bowl = min(n-1, m);CoBegin
while (TRUE)
{思考;P(bowl);P(chopsticks[i]);P(chopsticks[(i+1) % n]);就餐;V(chopsticks[i]);V(chopsticks[(i+1) % n);V(bowl);
}
CoEnd

25

下表给出了整型信号量S的wait(和signalO操作的功能描述，以及采用开/关中断指令实现信号量操作互斥的两种方法。
功能描述

Semaphore S;
wait(S)
{while(S<=0);S = S-1;
}signal(S)
{S = S + 1;
}

方法1

Semaphore S;
wait(S)
{关中断;while (S <= 0); S = S-1;开中断;
}signal(S)
{ 关中断;S = S + 1; 开中断;
}

方法2

Semaphore S;
wait(S)
{关中断;while(S <= 0){开中断;关中断;}S = S-1; 开中断;
}signal(S)
{ 关中断; S = S + 1; 开中断;
}

请回答下列问题。

1. 为什么在wait()和signal()操作中对信号量S的访问必须互斥执行？
2. 分别说明方法1和方法2是否正确。若不正确，请说明理由。
3. 用户程序能否使用开/关中断指令实现临界区互斥？为什么？

---

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