《操作系统精髓与设计原理·第五版》练习题及答案(DOC) 下载本文

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; 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)

31

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

32

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 Producer SemWaitB(S) n++ If(n==1) (semSignalB(delay)) 5 6 7 8 9 semSignalB(s) semWaitB(s) semWaitB(delay) semWaitB(s) n-- If(n==0) (semWaitB(delay)) 10 1 1 0 1 1 1 0 1 0 0 0 Consumer s 1 0 0 0 n 0 0 1 1 delay 0 0 0 1 生产者和消费者都被阻塞。

33

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);

34

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; consume; semSignalB(s) forever end;

begin (*main program*)

35