计算机操作系统典型例题解析之三-

{while(1){wait(S1);if(ab==0)wait(Sab);ab=ab+1;signal(S1);车辆从a点驶向b点wait(S1);ab=ab-1;if(ab==0)signal(Sab); signal(S1);}}voidPb(){while(1){wait(S2);if(ba==0)wait(Sab);ba=ba+1;signal(S2);车辆从b点驶向a点;wait(S2);ba=ba-1; if(ba==0)signal(Sab)signal(S2);main(){cobegin{Pab ();Pba ();}} 【例16】在公共汽车上，司机和售票员的工作流程如图3-4所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。

司机 启动车辆 正常行车

售票员 关车门 售票 开车门

到站停车

图3-4 司机和售票员工作流程图

分析：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。在本题中，设置两个信号量：S1、S2，S1表示是否允许司机启动汽车，其初值为0；S2表示是否允许售票员开门，其初值为0。 答：则该问题描述如下：Semaphoere S1=S2=0;void Driver(){while(1){ wait(S1); 启动车辆； 正常行车；到站停车；

9

signal(S2);} }void Busman(){while(1){ 关车门； signal（S1）； 售票； wait（S2）； 开车门； }}main(){ cobegin{ Driver(); Busman();}}

【例17】用信号量集机制解决哲学家进餐问题。

分析：哲学家进餐问题也是典型的同步问题，它由Dijkstra提出并解决。该问题的描述是，有五个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子继续思考。经分析可知，筷子是临界资源，在一段时间内只允许一个哲学家使用。因此，可以用一个信号量表示一支筷子，由五个信号量构成信号量数组。其描述如下： semaphore chopstick[4]={1,1,1,1,1};

信号量集机制分为AND型信号量集机制和一般“信号量集”机制。AND同步机制的基本思想是，将进程在整个运行过程中所需要的所有临界资源一次性全部分配给进程，待该进程使用完后再一起释放。只要尚有一个资源未能分配给该进程，其他所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配采取原子操作方式，要么全部分配到进程，要么一个也不分配。避免死锁的发生。

为此，在wait操作中增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait（Simultaneous Wait）。其定义如下：Swait(S1,S2,?,Sn){if (S1≥1&&?&&Sn≥1) for (i=1;i<=n;i++) Si--;elsePlace the process in the waiting queue associated with the Si found with Si＜1,and set the program count of this process to the beginning of Swait operation.}Ssignal(S1,S2,

…,Sn){for (i=1;i<=n;i++)Si++;Remove

10

all the process waiting in the queue associated with Si into the ready queue.}

在记录型信号量机制中，wait(s)或signal(s)操作仅能对信号量施以增1或减1的操作，即每次只能获得或释放一个单位的临界资源。当一次需要n个某类资源时，便需要进行n次wait(s)操作，显然这是低效的。此外，在某些情况下，当资源数量低于某一下限值时便不予分配。因而，在每次分配之前都必须测试该资源的数量是否大于测试值t。基于上述两点可以对AND信号量机制进行扩充，形成一般化的“信号量集”机制。Swait操作可描述如下：

Swait(S1,t1,d1,S2,t2,d2,?,Sn,tn,dn){if (S1≥t1&&?&&Sn≥tn) for (i=1;i<=n;i++) Si=Si-di;elsePlace the process in the waiting queue associated with the Si found with Si＜ti,and set the program count of this process to the beginning of Swait operation.}Ssignal(S1,t1,d1,S2,t2,d2,?,Sn,tn,dn){

for (i=1;i<=n;i++){Si=Si+di;Remove all the process waiting in the queue associated with Si into the ready queue. }}

答：用AND信号量机制可获得最简洁的解法： semaphore chopstick[4]={1,1,1,1,1};

void process(int i){while (1){ Swait(chopstick[(i+1) mod 5], chopstick[i]);...eat;... Ssignal(chopstick[(i+1)

mod

5],

chopstick[i]);...think;}}main(){cobeginprocess(0); process(1);process(2);process(3);process(4);} 除此以外，还可以采用另外两种方法解决哲学家进餐问题：

11

①至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。

②规定奇数号哲学家先拿他左边的筷子，然后再去拿他右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五个哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐。

【例18】试用管程解决哲学家进餐问题。

分析：我们认为哲学家可以处于这样三种状态之一：即进餐、饥饿和思考。相应地，引入数据结构： enum status{ thinking,hungry,eating } enum status state[5];

我们还为每一位哲学家设置一个条件变量self(i)，每当哲学家饥饿，但又不能获得进餐所需的筷子时，他可以执行self(i).wait操作来推迟自己进餐。条件变量可描述为：condition self[5]; 答：则用于解决哲学家进餐问题的管程描述如下： monitor dining-philosophers{enum status{ thinking,hungry,eating};enum status state[5];

condition self[5]; entry pickup(int i){ state[i]=hungry; test(i); if (state[i]

≠eating)self(i).wait}entry putdown(int

i){ state[i]=thinking;test(i-1 mod 5);test(i+1 mod 5);}test(int i);{ if (state[i-1 mod 5]≠eating &&

12