文档介绍:计算机操作系统****题
六算法题
16. Jruassic ,每辆车只能容纳一个旅客。旅客在博物馆逛了一会儿,然后排队乘坐旅行车。当一辆车可用时,它载入一个旅客,然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩,则想坐车的旅客需要等待;如果一辆车已经就绪,但没有旅客等待,那么这辆车等待。使用信号量同步m个旅客和n辆车的进程。(10分)
解:
visitors=m;
Pvi()
{ repeat cars=n;
mutex=1; Pci() { repeat wait(visitors); wait(mutex); start; run; wait(cars); wait(mutex); get on; travell; get off; signal(cars); wait(mutex); until false; }
stop; signal(visitors); wait(mutex); 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原语
实现他们的同步操作。
,M,P,它们共享了一个可循环使用的缓冲区B,缓冲区B共有N个单元。进程R负责从输入设备读信息,每读一个字符后,把它存放在缓冲区B的一个单元中;进程M负责处理读入的字符,若发现读入的字符中有空格符,则把它改成“,”;进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后,则