5.9可以用二元信号量实现一般信号量。我们使用semWaitB操作和semSignalB操作以及两个二元信号量delay和mutex。考虑下面的代码

Void semWait(semaphor s) {

semWaitB(mutex); s--; if (s<0) {

semSignalB(mutex); semWaitB(delay); } Else

Semsignalb(mutex) }

Void semSignal(semaphore s); {

semWaitB(mutex); s++; if(s<=0)

semSignalB(delay); semSignalB(mutex); }

最初。S被设置成期待的信号量值，每个semwait操作将信号量减1，每个semsignal操作将信号量加1.二元信号量mutex被初始化成1，确保在更新在更新s时保证互斥，二元信号量delay被初始化成0，用于挂起进程，

上面的程序有一个缺点，证明这个缺点，并提出解决方案。提示：假设两个进程，每个都在s初始化为0时调用semwait（s）,当第一个刚刚执行了semsignalb（mutex）但还没有执行semwaitb（delay），第二个调用semwait（s）并到达同一点。现在需要做的就是移动程序的一行.

答：假设两个进程，每个都在s被初始化成0时调用semWait（s），当第一个刚执行了semSignalB（mutex）但还没有执行semWaitB（delay）时，第二个调用semWait（s）并到达同一点。因为s=-2 mutex没有锁定，假如有另外两个进程同时成功的调用semSignal（s），他们接着就会调用semsignalb（delay），但是第二个semsignalb没有被定义。

解决方法就是移动semWait程序中end前的else一行到semSignal程序中最后一行之前。因此semWait中的最后一个semSignalB(mutex)变成无条件的，semSignal中的semSignalb(mutex)变成了有条件的。

5.10 1978年，dijkstra提出了一个推测，即使用有限数目的弱信号量，没有一种解决互斥的方案，使用于数目未知但有限的进程且可以避免饥饿。1979年，j.m.morris提出 了一个使用三个弱信号量的算法，反驳了这个推测。算法的行为可描述如下，如果一个或多个进程正在semwait（s）操作上等待，另一个进程正在执行semsignal（s），则信号量s的值未被修改，一个等待进程被解除阻塞，并且这并不取决于semwait（s）。除了这三个信号量外，算法使用两个非负整数变量，作为在算法特定区域的进程的计数器。因此，信号量A和B被初始化为1，而信号量M和计数器NA，NM被初始化成0.一个试图进入临界区的进程必须通过两个分别由信号量A和M表示路障，计数器NA和NM分别含有准备通过路障A以及通过路障A但还没有通过路障M的进程数。在协议的第二部分，在M上阻塞的NM个进程将使用类似于第一部分的串联技术，依次进入他们的临界区，定义一个算法实现上面的描述。 答：这个程序由[RAYN86]提供： var a, b, m: semaphore;

29

na, nm: 0 ? +∞;

a := 1; b := 1; m := 0; na := 0; nm := 0; semWait(b); na ← na + 1; semSignal(b); semWait(a); nm ← nm + 1; semwait(b); na ← na – 1;

if na = 0 then semSignal(b); semSignal(m) else semSignal(b); semSignal(a) endif;

semWait(m); nm ← nm – 1; ;

if nm = 0 then semSignal(a) else semSignal(m) endif;

5.11下面的问题曾被用于一个测试中：

侏罗纪公园有一个恐龙博物馆和一个公园，有m个旅客和n辆车，每辆车只能容纳一名旅客。旅客在博物馆逛了一会儿，然后派对乘坐旅客车。当一辆车可用时，它载入一名旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客进程和n个进程。下面的代码框架是在教室的地板上发现的。忽略语法错误和丢掉的变量声明，请判定它是否正确。注意，p和v分别对应于semwait和semsignal。 Resource Jurassic_Park()

Sem car_avail:=0,car_taken:=0,car_fillde:=0.passenger_released:=0 Process passenger(i:=1 to num_passengers)

Do true->nap(int(random(1000*wander_time))) P(car avail);V(car_taken);P(car_filled) P(passenger_released) Od

End passenger

Process car(j:=1 to num_cars)

Do true->V(car_avail);P(car_taken);V(car_filled) Nap(int(random(1000*ride_time))) V(passenger_released) Od End car

End Jurassic_Park 答：这段代码有一个重要问题.在process car中的代码 V(passenger_released)能够解除下面一种旅客的阻塞,被阻塞在P(passenger_released)的这种旅客不是坐在执行V()的车里的旅客.

5.12在图5.9和5.3的注释中，有一句话是“仅把消费者临界区（由s控制）中的控制语句移出还是不能解决问题，因为这将导致死锁”，请用类似于表5.3的表说明。

答： 1 2 3 4 5 Producer SemWaitB(S) n++ If(n==1) (semSignalB(delay)) semSignalB(s) Consumer s 1 0 0 0 1 n 0 0 1 1 1 delay 0 0 0 1 1 30

6 7 8 9 10 semWaitB(s) semWaitB(delay) semWaitB(s) n-- If(n==0) (semWaitB(delay)) 1 0 1 1 0 0 0 0 生产者和消费者都被阻塞。 5.13考虑图5.10中定义的无限缓冲区生产者/消费者问题的解决方案。假设生产者和消费者都以大致相同的速度运行，运行情况如下：

生产者：append;semSignal;produce;···append;semSignal 消费者：consume;take;semWait;consume;take;semWait;

生产者通常管理给换成区一个元素，并在消费者消费了前面的元素后发信号。生产者通常添加到一个空缓冲去中，而消费者通常取走缓冲区中的唯一元素。尽管消费者从不在信号量上阻塞，但必须进行大量的信号量调用，从而产生相当多的开销。

构造一个新程序使得能在这种情况下更加有效。

提示：允许n的值为-1，这表示不仅缓冲区为空，而且消费者也检测到这个事实并将被阻塞，直到生产者产生新数据。这个方案不需要使用图5.10中的局部变量m。

答：

这个程序来自于[BEN82] program producerconsumer; var n: integer;

s: (*binary*) semaphore (:= 1); delay: (*binary*) semaphore (:= 0); procedure producer; begin repeat produce;

semWaitB(s); append; n := n + 1;

if n=0 then semSignalB(delay); semSignalB(s) forever end;

procedure consumer; begin repeat

semWaitB(s); take;

n := n – 1; if n = -1 then begin

semSignalB(s); semWaitB(delay); semWaitB(s) end;

31

consume;

semSignalB(s) forever end;

begin (*main program*) n := 0; parbegin

producer; consumer parend end.

5.14考虑图5.13.如果发生下面的交换，程序的意义是否会发生改变？

a.semWait(e);semWait(s) b.semSignal(s);semSignal(n) c.semWait(n);semWait(s) d.semSignal(s);semSignal(e)

答：只要交换顺序都会导致程序错误。信号量s控制进入临界区，你只想让临界区区域包括附加或采取功能。

5.15在讨论有限缓冲区（见图5.12）生产者/消费者问题时，注意我们的定义允许缓冲区中最多有n-1个入口？

a.这是为什么？

b.请修改程序，以不久这种低调？

答：如果缓冲区可以容纳n个入口，问题在于如何从一个满的缓冲区中区分出一个空的缓冲区，考虑一个有六个位置的缓冲区，且仅有一个入口，如下： A Out in 然后，当一个元素被移出，out=in。现在假设缓冲区仅有一个位置为空： D E A B C In out 这样，out=in+1.但是，当一个元素被添加，in被加1后，out=in，当缓冲区为空时同理。 b．你可以使用一个可以随意增加和减少的辅助的变量，count。

5.16这个习题说明了使用信号量协调三类进程。圣诞老人在他北极的商店中睡眠，他只能被一下两种情况之一唤醒：（1）所有九头驯鹿都从南太平洋的假期回来了，或者（2）某些小孩在制作玩具时遇到了困难。为了让圣诞老人多睡会，这些孩子只有在是那个人都遇到困难时才唤醒他。当三个孩子的问题得到解决时，其他想访问圣诞老人的孩子必须等到那些孩子返回。如果圣诞老人醒来后发现在三个孩子在他的店门口等待，并且最后一头驯鹿已经从热带回来。则圣诞老人决定让孩子门等到圣诞节之后，因为准备最后一天哦iuxunlu必须与其他unlu在暖棚中等待并且还没有套上缰绳做成雪橇前回来。请用信号量解决这个问题。 答：santa:圣诞老人reindeer:驯鹿elf:小孩子sleigh:雪橇toys:玩具

32