文档介绍：六算法题
16. Jruassic ,每辆车只能容纳一个旅客。旅客在博物馆逛了一会儿,然后排队乘坐旅行车。当一辆车可用时,它载入一个旅客,然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩,则想坐车的旅客需要等待;如果一辆车已经就绪,但没有旅客等待,那么这辆车等待。使用信号量同步m个旅客和n辆车的进程。(10分)
解:
visitors=m; cars=n; mutex=1;
Pvi() Pci()
{ repeat { repeat
wait(cars); wait(visitors);
wait(mutex); wait(mutex);
get on; start;
travell; run;
get off; stop;
signal(cars); signal(visitors);
wait(mutex); wait(mutex);
until false; until false;
} }
(reader -- writer problems ) (10分)
在计算机体系中,对一个共享文件进行操作的进程可分为两类:读操作和写操作,它们分别被称为读者和写者。访问该文件时读者和写者,写者和写者间必须实现互斥。只有在没有读者访问文件时,写者才允许修改文件。或者写者在修改文件时不允许读者去读,否则会造成读出的文件内容不正确。试写出算法描述读者和写者的问题。
解: 为了实现读者与写者的同步和互斥,我们设置一个信号量S,用于读者与写者之间或写者与读者之间的互斥,初值为“1”。用一个变量rc 表示当前正在读的读者个数,当进程可以去读或读结束后都要改变rc 的值,因此rc 又成为若干读进程的共享变量,它们必须互斥地修改rc。故必须定义另一个用于互斥的信号量Sr,初值也是“1”。读者--写者问题可描述如下:
S, Sr:semaphore; int rc = 0; S=Sr=1;
process Reader I (i=1,2,...,m) process Writer j (j=1,2,...,k)
begin begin
P(Sr); rc = rc+1; P(S);
if (rc==1) P(S); Write file F;
V(Sr); V(S);
read file F; end
P(Sr); rc = tc-1;
if (rc==0) V(S);
V(Sr);
end
19、生产者和消费者问题(10分)
有一组生产者P1,P2,……,PM和一组消费者C1,C2,……,CK,他们通过由n个环形缓冲区构成的缓冲池进行通信,生产者把产品放入缓冲区,消费者从缓冲区取产品来消费。请用wait和signal原语实现他们的同步操作。
解:生产者和消费者问题
begin
Var mutex,empty,full:semaphore:=1,n,0;
until false ;
end
buffer:array[0,…,n-1] of item;
in,out:integer := 0,0;
parbegin
producer: begin
repeat
p