1、习题课1 答案习题课： Wait.Signal 操作必须成对出现，有一个Wait操作就一定有一个Signal 操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现 如果Wait(S1) 和 Wait(S2)两个操作在一起，那么Wait 操作的顺序至关重要,一个同步Wait 操作与一个互斥Wait 操作在一起时同步Wait 操作在互斥 Wait 操作前 而两个Signal 操作无关紧要1、生产者-消费者问题的同步算法中，为什么颠倒生产者进程中的两个Wait 操作的次序，将导致进程死锁？（南京航空航天大学2002年硕士入学考题）Procedure producer beg
2、tn repeat生产数据 ; Wait(mutex); Wait(E);“分给空缓冲区并调整指针 P 的临界段”;Signal (mutex);“向空缓冲区 装入数据”; Signal (F); forever这是因为有可能出现这样一种特殊情况：在某个时刻，缓冲区中已经放满了产品且没有进程在工作，如果此时系统调度生产者进程运行的话，Wait(mutex)能顺利通过（此时mutex =0），但是当它执行Wait(E)时，由于此时的E=0-1=-10,所以生产者进程只能阻塞，等待消费者进程取走一个产品后释放缓冲单元。而此时如果有消费者进程过来运行，当它顺利通过Wait(F)后，在执行Wait(m
3、utex)，此时的 mutex=-1，因此消费者进程也被阻塞了，这样消费者进程和生产者进程都处于等待状态，从而产生了死锁。2、兄弟俩共同使用一个账号 , 每次限存或取 10 元 , 存钱与取钱的进程分别如下所示 :( 南京大学 2000 年试题 )begin amount:integer; amout:=0;cobegin process SAVEm1:integer ; begin m1:=amount; m1:=m1+10; amout:=m1; end; process TAKEm2:integer ; begin m2:=amount; m2:=m2-10; amout:=m2; en
4、d; coend; end;由于兄弟俩可能同时存钱和取钱 , 因此两个进程是并发的。若哥哥先存了两次钱 , 但在第三次存钱时 , 弟弟在取钱。请问最后账号 amount 上面可能出现的值 ? 如何用 Wait 、 Signal 操作, 实现两并发进程的互斥执行 ?答 : 哥哥存了两次钱后,共享变量 amount 的值为 20 。哥哥的第三次存钱与弟弟的取钱同时进行 ,如果两者顺序执行 , 则最后账号 amount 的值为 20； 如果在一个进程的执行过程 中 , 进行 CPU 调度 , 转去执行另一进程 , 则最后 amount 的值取决于 amount:=m1及amount:=m2 的执行先
5、后次序 , 若前者先执行 ,则最后 amount 的值为 10, 若后者先执行 ,则最后 amount 的值为 30 。因此 , 最后账号 amount 上面可能出现的值有 10、20、30。上述问题中 , 共享变量 amount 是一个临界资源 , 为了实现两并发进程对它的互斥访问 ,为它设置一初值为 1 的互斥信号量 mutex, 并将上述算法修改为 : begin amount: integer; Mutex: semaphore;amout:=0;mutex=1;cobegin process SAVEm1:integer ; beginWait(mutex); m1:=amount;
6、 m1:=m1+10; amout:=m1; Signal(mutex);end;process TAKEm2:integer ; beginWait(mutex); m2:=amount; m2:=m2-10; amout: = m2; Signal(mutex);end; coend; end;3、（华中理工大学 1999，哈工大2000年研究生人学试题 ) 设公共汽车上 , 有一位司机和一位售票员 , 它们的活动如下： 司机 : 售票员 : 启动车辆； 关车门； 正常行车； 售票；到站停车； 开车门；请分析司机与售票员之间的同步关系 , 如何用信号量和 wait signal操作实现。
7、【分析】在汽车的行驶过程中,为了安全起见 ,显然要求 : 只有售票员关车门后司机才能启动车辆 ; 汽车到站停车后才能开车门。所以司机和售票员在到站、开门、关门、启动车辆 这几个活动之间存在着同步关系。用两个信号量 S1 、 S2 分别表示是否可以开车和是否可以开门 ,S1 ,S2的初值为 0。用wait signal操作实现司机进程和售票员进程同步的关系为：司机 : 售票员 : Wait(S1)关车门启动车辆 Signal(S1)Signal(S1)正常行车 售票到站停车 Wait(S2)Signal(S2)Signal(S2) 开车门具体的 Wait 、 SignalSignal 原语算法描
8、述如下:int S1=O ; int S2=O;Main( ) cobegin driver( ) /*司机的活动*/ Busman( ) /*售票员的活动*/ coend Driver( ) while (true)Wait(S1);启动车辆 ; 正常行车 ; 到站停车 ; Signal(S2);busman ( ) while (true)关车门 ；Signal(S1);售票 ; Wait(S2);开车门 ; 4、有一个理发师 , 一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客 , 则理发师便在理发椅上睡觉 ; 当一个顾客到来时 , 必须叫醒理发师进行理发 ; 如果理发师正在理
9、发时有别的顾客来到 , 则如果有空椅子可坐 , 他就坐下来等 , 如果没有空椅子,他就离开。为理发师和顾客各编一段程序描述他们的行为。 ( 西安电子科技大学2000年研究生试题 ) 【分析】考虑一下理发师 (barber) 重复的下列活动：睡觉 为顾客理发； 顾客 (customers) 重复的下列活动 : 在椅子上等候；理发；离开；显然 , 理发师在处要考查是否有顾客等候理发 ,如果没有,理发师睡觉；在处理发师等待最先进入理发店的顾客唤醒 , 开始理发。顾客在处先看是否有座位 ,没有则离开；等候理发的顾客在处被理发师唤醒 ( 最先理发的顾客要唤醒理发师 )；理发结束后离开。在这两个活动中 ,
10、 从资源的角度来看 , 理发师是顾客争用的资源 , 用信号量 barber 表 示 , 初值为 0; 除此以外 , 顾客还要争用 n 张椅子 , 信号量 customers 表示等候理发的顾客数 , 初值为 0；最后设置信号量 mutex 用于这两个活动对资源 barber 、 customers 的互斥 ,初值为1。使用三个信号量 ；customers 用于记录等候的顾客的数量；barbers 用于表示理发师是否在理发；mutex用于进程之间的互斥。 另外还需使用一个变量 waiter, 也是用于记录等候的顾客的数量。include”prototypes.h”define CHAIRS nT
11、ype defintsemaphore;customers=0barbers=0Mutex=1;Waiter=0; /*等待理发的人数*/Void Customer(void)wait(mutex);If(waiterCHAIRS)waiter=waiter+1;signal(customers);signal(mutex);wait(barbers);get_haircut();Elsesignal(mutex);Void Barber(void) while(ture)Wait(customers); /*是否有等候理发的顾客*/Wait(mutex);Waiter=water-1; /*
12、等候理发的顾客数减1*/Signal(mutex);Signal(barbers);Cut_hair(); /*理发师理发*/5、哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子一个简单的解法是，用一个信号量表示一支筷子，这五个信号量构成信号量数组，其描述为： var chopstick:array04 of semaphore;所有信号量初始值为1，第I个哲学家的活动课描述为：Repeatwait(c
13、hopsticki);wait(chopstick(i+1) mod 5); eat; signal(chopsticki);signal(chopstick(i+1) mod 5); think;until false;为防止死锁发生可采取的措施： 最多允许4个哲学家同时就餐； 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）； 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿设一个信号量Sm来限制同时进餐的人数，Sm=4.Pi:Repeatthink for while;
14、wait(Sm);wait(chopsticki);wait(chopstick(i+1) mod 5);eat;signal(chopsticki);signal(chopstick(i+1) mod 5);signal(Sm); until falsePi:Repeatthink;if (i mod 2)=1 then beginwait(chopsticki);wait(chopstick(i+1) mod 5);endelse beginwait(chopstick(i+1) mod 5);wait(chopsticki);endeatsignal(chopsticki);signal
15、(chopstick(i+1) mod 5); until false6. 有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记信号，阅览室中共有100个座位，请问：(1) 为描述读者的动作，应编写几个程序？设置几个进程？进程与程序间的对应关系如何？(2) 用类Pascal语言和Wait, Signal操作写出这些进程间的同步算法。答：(1) 应编写1个程序；设置2个进程；进程与程序间的对应关系是：多对多对1。(2) beginS1:=100 (有100个座位)S2:=0 (没有阅读者)mutex: =1cobeginP1: repeatWait(S1);wait(mutex);登记信息;Signal(muetx);Signal(S2)就座，阅读； until false coendendP2: repeatwait(S2)Wait(mutex);消掉信息;Signal(muetx);Signal(S1);离开阅览室; until false
