计算机操作系统第三版答案 6 / 28
后，应对mutex执行signal 操作，释放该临界资源。利用信号量实现进程互斥的进程描述 如下：
Var mutex: semaphore:=1； begin parbegin
process 1: begin repeat
wait(mutex)； critical section signal(mutex)； remainder seetion until false； end
process 2: begin repeat
wait(mutex)； critical section signal(mutex)； remainder section until false； end parend
22．试写出相应的程序来描述图2-17所示的前驱图。 答：（a）Var a, b, c, d, e, f, g, h; semaphore:= 0, 0, 0, 0, 0, 0, 0, 0; begin parbegin
begin S1; signal(a); signal(b); end;
begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); S6; signal(h); end;
begin wait(f); wait(g); wait(h); S7; end; parend end
（b）Var a, b, c, d, e, f, g, h,i,j; semaphore:= 0, 0, 0, 0, 0, 0, 0,0,0, 0; begin parbegin
begin S1; signal(a); signal(b); end;
begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); signal(f); end; begin wait(c); S4; signal(g); end; begin wait(d); S5; signal(h); end; begin wait(e); S6; signal(i); end;
6
计算机操作系统第三版答案 7 / 28
begin wait(f); S7; signal(j); end;
begin wait(g);wait(h); wait(i); wait(j); S8; end; parend end 23．在生产者消费者问题中，如果缺少了signal(full)戒signal(empty),对执行结果有何影响？ 答：如果缺少signal(full)，那么表明从第一个生产者进程开始就没有改变信号量full 值，即使缓冲池产品已满，但full 值还是0，这样消费者进程执行wait(full)时认为缓冲池是空而取不到产品，消费者进程一直处于等待状态。
如果缺少signal(empty)，在生产者进程向n个缓冲区投满产品后消费者进程才开始从中取产品，这时empty=0，full=n，那么每当消费者进程取走一个产品empty 值并不改变，直到缓冲池取空了，empty 值也是0，即使目前缓冲池有n 个空缓冲区，生产者进程要想 再往缓冲池中投放产品也会因为申请不到空缓冲区被阻塞。
24．在生产消费者问题中，如果将两个wait 操作即wait(full)和wait(mutex)互换位置，戒者将signal(mutex)不signal（full）互换位置，结果如何？
答：将wait(full)和wait(mutex)互换位臵后，可能引起死锁。考虑系统中缓冲区全满时，若一生产者进程先执行了wait(mutex)操作并获得成功，则当再执行wait(empty)操作时，它将因失败而进入阻塞状态，它期待消费者进程执行signal(empty)来唤醒自己，在此之前，它不可能执行signal(mutex)操作，从而使试图通过执行wait(mutex)操作而进入自己的临界区的其他生产者和所有消费者进程全部进入阻塞状态，这样容易引起系统死锁。若signal(mutex)和signal(full)互换位臵后只是影响进程对临界资源的释放次序，而不会引起系统死锁，因此可以互换位臵。
25．我们在为某一临界资源设置一把锁W，当W=1时表示关锁，当W=0时表示锁已打开。 试写出开锁和关锁的原诧，并利用他们实现互斥。 答：整型信号量：lock(W): while W=1 do no-op W:=1;
unlock(W): W:=0;
记录型信号量：lock(W): W:=W+1; if(W>1) then block(W, L) unlock(W): W:=W-1;
if(W>0) then wakeup(W, L) 例子：
Var W:semaphore:=0； begin repeat lock(W);
critical section unlock(W);
remainder section until false; end
26．试修改下面生产者－消费者问题解法中的错诨: 答： producer: begin repeat
7
计算机操作系统第三版答案 8 / 28
?
producer an item in nextp; wait(mutex);
wait(full); /* 应为wait(empty),而且还应该在wait(mutex)的前面 */ buffer(in):=nextp;
/* 缓冲池数组游标应前移: in:=(in+1) mod n; */ signal(mutex); /* signal(full); */ until false; end
consumer: begin repeat
wait(mutex);
wait(empty); /* 应为wait(full),而且还应该在wait(mutex)的前面 */ nextc:=buffer(out);
out:=out+1; /* 考虑循环，应改为: out:=(out+1) mod n; */ signal(mutex);/* signal(empty); */ consumer item in nextc; until false; end
27．试利用记录型信号量写出一个丌会出现死锁的哲学家迚餐问题的算法. 答：Var chopstick:array[0,?,4] of semaphore;
所有信号量均被初始化为1，第i 位哲学家的活动可描述为： Repeat
Wait(chopstick[i]);
Wait(. chopstick[(i+1) mod 5]); ? Ea.t ; ?
Signal(chopstick[i]);
Signal(chopstick[(i+1) mod 5]) Ea.t ; ? Think; 11
Until false; 28．在测量控制系统中的数据采集仸务，把所采集的数据送一单缓冲区；计算仸务从该单 缓冲中叏出数据迚行计算.试写出利用信号量机制实现两者共享单缓冲的同步算法。 答： a. Var mutex, empty, full: semaphore:=1, 1, 0; gather: begin repeat ??
8
计算机操作系统第三版答案 9 / 28
gather data in nextp; wait(empty); wait(mutex); buffer:=nextp; signal(mutex); signal(full); until false; end
compute: begin repeat ??
wait(full); wait(mutex); nextc:=buffer; signal(mutex); signal(empty);
compute data in nextc; until false; end
b. Var empty, full: semaphore:=1, 0; gather: begin repeat ??
gather data in nextp; wait(empty); buffer:=nextp; signal(full); until false; end
compute: begin repeat ??
wait(full); nextc:=buffer; signal(empty);
compute data in nextc; until false; end
29．画图说明管程由哪几部分组成，为什么要引入条件发量？
答：管程由四部分组成：①管程的名称；②局部于管程内部的共享数据结构说明；③对该数据结构进行操作的一组过程；④对局部于管程内部的共享数据设臵初始值的语句； 当一
9
计算机操作系统第三版答案 10 / 28
个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程，则其它进程无法进入管程，被迫长时间地等待。为了解决这个问题，引入了条件变量condition。
30．如何利用管程来解决生产者不消费者问题？
答：首先建立一个管程，命名为ProclucerConsumer，包括两个过程： （1）Put（item）过程。生产者利用该过程将自己生产的产品放到缓冲池，用整型变 量count 表示在缓冲池中已有的产品数目，当count≥n 时，表示缓冲池已满，生产者须 等待。 （2）get（item）过程。消费者利用该过程从缓冲池中取出一个产品，当count≤0 时，表示缓冲池中已无可取的产品，消费者应等待。 PC 管程可描述如下： type producer-consumer =monitor Var in,out,count:integer;
buffer:array[0,…,n-1]of item; notfull，notempty:condition; procedure entry dot(item) begin
if count>=n then not full.wait; buffer(in):=nextp; in:=(in+1)mod n; count:=count+1;
if notempty.queue then notempty.signal; end
procedure entry get(item) begin
if count<=0 then not full.wait; nextc:=buffer(out); out:=(out+1)mod n; count:=count-1;
if notfull.quene then notfull.signal; end
begin in:=out:=0; count:=0 end
在利用管程解决生产者一消费者问题时，其中的生产者和消费者可描述为： producer: begin pepeat
produce an inem in nestp PC.put(item); until false; end
consumer: begin repeat
PC.get(item);
consume the item in enxtc; until false;
10