司机的活动: P1: do{ P(start); 启动车辆; 正常行车; 到站停车; V(open); }while (1); 售票员的活动: P2: do{ 关车门; V(start); 售票; P(open); 开车门; }while (1);
16. 设有A、B、C三组进程，它们互斥地使用某一独占型资源R，使用前申请，使用后释放。资源分配原则如下:
(1) 当只有一组申请进程时，该组申请进程依次获得R；
(2) 当有两组申请进程时，各组申请进程交替获得R，组内申请进程依次获得R； (3) 当有三组申请进程时，各组申请进程轮流获得R，组内申请进程依次获得R。 试用信号灯和PV操作分别给出各组进程的申请活动程序段和释放活动程序段。 解：
int free=1;//设备状态标志 semaphore mutex=1;
semaphore qa=qb=qc=0; //各组等待队列
int counta=countb=countc=0;//等待队列长度 A组申请： A组释放： P(mutex); P(mutex); if(free==1){ if(countb>0){ free=0; countb--; V(mutex); V(qb); } }else{ else{ if(countc>0){ counta++; countc--; V(mutex); V(qc); P(qa); }else{ } if(counta>0){
counta-- V(qa); }else{ free=1; } } } } A组进程活动可以给出B组和C组进程活动。
21
17. 设自行车生产线上有一只箱子，其中有N个位置(N≥3)，每个位置可存放一个车架或一个车轮; 又设有三个工人，其活动分别为: 工人1活动： do {
加工一个车架; 车架放入箱中; }while(1)
工人2活动： do {
加工一个车轮; 车轮放入箱中; }while(1)
工人3活动： do {
箱中取一车架; 箱中取二车轮; 组装为一台车; }while(1)
试分别用信号灯与PV操作、管程、会合实现三个工人的合作，要求解中不含死锁。 解：用信号灯与PV操作实现三个工人的合作，管程与会合解法可仿照给出。
首先不考虑死锁问题，工人1与工人3、工人2与工人3构成生产者与消费者关系，这两对生产/消费关系通过共同的缓冲区相联系。从资源的角度来看，箱子中的空位置相当于工人1和工人2的资源，而车架和车轮相当于工人3的资源。定义三个信号灯如下： semaphore empty=N;//空位置 semaphore wheel=0;//车轮 semaphore frame=0;//车架 三位工人的活动分别为： 工人1活动： 工人2活动： do { do { 加工一个车架; 加工一个车轮; P(empty); P(empty); 车架放入箱中; 车轮放入箱中; V(frame); V(wheel); }while(1) }while(1)
工人3活动：
do {
P(frame); 箱中取一车架; V(empty); P(wheel); P(wheel); 箱中取二车轮; V(empty); V(empty); 组装为一台车; }while(1)
分析上述解法易见，当工人1推进速度较快时，箱中空位置可能完全被车架占满或只留有一个存放车轮的位置，而当此时工人3同时取2个车轮时将无法得到，而工人2又无法将新加工的车轮放入箱中；当工人2推进速度较快时，箱中空位置可能完全被车轮占满，而当此时工人3取车架时将无法得到，而工人1又无法将新加工的车架放入箱中。上述两种情况都意味着死锁。
为防止死锁的发生，箱中车架的数量不可超过N-2，车轮的数量不可超过N-1，这些限制可以用两个信号灯来表达。 semaphore s1=N-2;
22
semaphore s2=N-1;
如此，可以给出不含死锁的完整解法如下： 工人1活动： 工人2活动： do { do { 加工一个车架; 加工一个车轮; P(s1); P(s2); P(empty); P(empty); 车架放入箱中; 车轮放入箱中; V(frame); V(wheel); }while(1) }while(1)
工人3活动：
do {
P(frame); 箱中取一车架; V(empty); V(s1); P(wheel); P(wheel); 箱中取二车轮; V(empty); V(empty); V(s2); V(s2);
组装为一台车; }while(1)
详细描述还应考虑对箱子单元的描述以及访问互斥问题。建议车架放在箱子的一端，车轮放在箱子的另一端，车架与车轮都采用后进先出的管理方式。
18. 一座小桥(最多只能承重两个人)横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。试用信号灯和PV操作写出南、北两岸过桥的同步算法。 解：桥上可能没有人，也可能有一人，也可能有两人。 (a) 两人同时过桥(b) 两人都到中间(c) 南(北)来者到北(南)段
共需要三个信号量，load用来控制桥上人数，初值为2，表示桥上最多有2人；north用来控制北段桥的使用，初值为1，用于对北段桥互斥；south用来控制南段桥的使用，初值为1，用于对南段桥互斥。 semaphore load=2; semaphore north=1; semaphore south=1;
tosouth(){ P(load); P(north); 过北段桥; 到桥中间; V(north); P(south); 过南段桥;
tonorth(){ P(load); P(south); 过南段桥; 到桥中间 V(south); P(north); 过北段桥;
23
到达南岸 V(south); V(load); } 到达北岸 V(north); V(load); }
19.某寺庙，有小和尚、老和尚若干．庙内有一水缸，由小和尚提水入缸，供老和尚饮用。水缸可容纳 30 桶水，每次入水、取水仅为1桶，不可同时进行。水取自同一井中，水井径窄，每次只能容纳一个水桶取水。设水桶个数为5个，试用信号灯和PV操作给出老和尚和小和尚的活动。
semaphore empty=30;// 表示缸中目前还能装多少桶水，初始时能装30桶水 semaphore full=0;// 表示缸中有多少桶水，初始时缸中没有水
semaphore buckets=5;// 表示有多少只空桶可用，初始时有5只桶可用 semaphore mutex_well=1;// 用于实现对井的互斥操作 semaphore mutex_bigjar=1; // 用于实现对缸的互斥操作
young_monk(){ old_monk(){ while(1){ while(){ P(empty); P(full); P(buckets); P(buckets); go to the well; P(mutex_bigjar); P(mutex_well); get water; get water; V(mutex_bigjar); V(mutex_well); drink water; go to the temple; V(buckets); P(mutex_bigjar); V(empty); pure the water into the big jar; } V(mutex_bigjar); } V(buckets); V(full); } }
20. 设系统中有5台类型相同的打印机，依次编号为1～5。 又设系统中有n个使用打印机的进程，使用前申请，使用后释放。 每个进程有一个进程标识，用于区别不同的进程。 每个进程还有一个优先数，不同进程的优先数各异。当有多个进程同时申请时，按照进程优先数由高到低的次序实施分配。 试用信号灯和PV操作实现对于打印机资源的管理，即要求编写如下函数和过程:
(1) 函数 require(pid，pri): 申请一台打印机。参数pid为进程标识，其值为1到n的整数; pri为进程优先数，其值为正整数; 函数返回值为所申请到打印机的编号，其值为1到5的整数;
(2) 过程 return(prnt): 释放一台打印机。参数prnt为所释放打印机的编号，其值为1到5的整数。
24
解：
#define N 5
bool flag[N+1];//flag[0]表示可用打印机数,
//flag[i]表示第i号打印机的状态（1<=i<=N），0表示占用，1表示空闲 PCB *queue=NULL;//进程阻塞队列
semaphore mutex_flag=1;//用于对flag数组的互斥操作 semaphore mutex_queue=1;//用于对阻塞队列的互斥操作
process(int i,int priority){ int print;
print=require(i,priority); use print; return(print); }
int require(int pid,int priority){ P(mutex_flag); if(flag[0]>0){ flag[0]--;
for(int i=1;i V(mutex_flag); return i; } else{ V(mutex_flag); p(mutex_queue); 将进程pid按其优先数插入到等待队列queue中； V(mutex_queue); } } return(int print){ P(mutex_flag); if(queue==NULL){ flag[0]++; flag[print]=1; V(mutex_flag); } else{ 25