begin wait(c);S4;signal(f);end; begin wait(d);S5;signal(g);end; begin wait(e);S6;singal(h);end;

begin wait(f);wait(g); wait(h); S7;end; parend end (2)

Var a,b,c,d,e,f,g,h,i,j; semaphore:=0,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;singal(i);end; 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) ，那么消费者会认为生产者没有生产而阻塞，而生产者会不断生产，直到empty为0后阻塞，然后两个进程陷入“死等”状态。

如果缺少了signal(empty)开始两进程可同步运行。但当empty为0 时生产者会因此而阻塞，然后消费者进程继续运行直到full也为0阻塞，然后两个进程陷入“死等”状态。 24、在生产者—消费者问题中，如果将两个wait操作即wait(full)和wait(mutex)互换位置，或者将signal(mutex)与signal(full)互换位置，结果会如何？

【解】如果将wait(full)和wait(mutex)互换位置，则如果consumer先进入临界区，就会一直等待full，但由于没有signal(mutex) ，producer将无法进入临界区而等待，则两个进程相互等待，陷入死锁。

如果signal(full)与signal (mutex)互换位置,则会使full的值不再是等待的consumer进程数目。

var mutex,empty,full:semaphore:=1,n,0;

buffer:array[0,?,n-1]of item; in,out:integer:=0,0; Begin

parbegin

producer: begin repeat

??

producer an item in nextp;

第 5 页 共 36 页

??

wait(mutex);//前2句颠倒则死锁 wait(empty);

buffer(in):=nextp; in:=(in+1)mod n;

signal(full); //后2句颠倒不死锁 signal(mutex); until false; end consumer: begin

repeat

wait(full); wait(mutex);

nextc:=buffer(out); out:=(out+1)mod n; signal(mutex); signal(empty);

consume the item in nextc; until false; end Parend end

由于V操作是释放资源，因此对调V操作的次序无关紧要。 而对调P操作的次序则可能导致死锁。 这时因为对调P操作后，有可能出现这样一种特殊情况：在某一时刻缓冲池中已装满了产品且缓冲池中无进程工作（这时信号量full的值为n，信号量empty的值为0，信号量mutex的值为1），若系统此时调度生产者进程运行，生产者进程又生产了一个产品，它执行P(mutex)并顺利进入临界区（这时mutex值为0），随后它执行p(empty)时因没有空闲缓冲区而受阻等待，等待消费者进程进入缓冲池取走产品以释放出缓冲区；

消费者进程执行p(full)后再执行p(mutex)时，因缓冲池被生产者进程占据而无法进入。 这样就形成了生产者进程在占有临界资源的情况下，等待消费者进程取走产品，而消费者进程又无法进入临界区取走产品的僵局，此时两进程陷入死锁。

25、我们为某临界资源设置一把锁W，当W=1时表示关锁；当W=0时表示锁已打开。试写出开锁和关锁原语，并利用它们去实现互斥。 【解】我们采用一个变量W作为“锁”，代表某个临界资源的状态，W=0（false,锁已打开）表示该资源未用，W=1（true，关锁）表示该资源正被使用。同时，用一段程序作为开锁原语，用另一段程序作为关锁原语，要进入临界区的进程首先要执行关锁原语，当它退出临界区时，要执行开锁原语。从而实现对临界区的互斥控制。两个原语的作用是：

加锁原语lock

测试W是否为0 若W=0，让W=1 若W=1，继续测试

第 6 页 共 36 页

开锁原语unlock

使W=0

可见，加锁原语首先要判断临界区中有无进程，若W=0，表示无进程进入临界区，它可以马上进入，并立即将W置为1，同时禁止其他进程进入。若W=1，表示已经有进程进入，它只得等待。这种机构简单方便，但存在CPU的时间浪费，因为等待进入临界区的进程将不断循环测试W，等待W变为0。

26、试修改下面生产者-消费者问题解法中的错误：

producer: begin repeat ?

produce an item in nextp; wait(mutex); wait(full);

buffer(in):=nextp; signal(mutex); until false; end

consumer: begin repeat

wait(mutex); wait(empty);

nextc:=buffer(out); out:=out+1; signal(mutex);

consume item in nextc; until false; end

修改为： producer:

begin repeat

produce an item in nextp; wait (empty); wait (mutex);

buffer (in): =nextp; in:=(in+1) mod n; signal (mutex); signal (full) until false; end

consumer：

第 7 页 共 36 页

begin

repeat

wait (full);

wait(mutex);

nextc:=buffer(out); out:=(out+1) mod n; out:=out+1; signal(mutex);

signal(empty);

consume item in nextc; until false end

27、试利用记录型信号量机制写出一个不会出现死锁的哲学家进餐问题的算法。

28、在测量控制系统中的数据采集任务时，把所采集的数据送往一单缓冲区；计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两任务共享单缓冲区的同步算法。 【解】算法如下：

Var mutex, empty, full: semaphore: =1,1,0; buffer: item; begin

parbegin

Receive: begin

repeat

Wait(empty); Wait(mutex); buffer: =nextp; Signal(mutex); Signal(full); until false end

Get: begin repeat

Wait (full); Wait (mutex); nextp: =buffer; Signal (mutex); Signal (empty); until false end parend

第 8 页 共 36 页