计算机操作系统试题ji答案(14)

70 60 60

45 40 15

车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步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; } }

17.读者与写者问题 (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

18、若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。

（1）先来先服务算法；

（2）最短寻道时间优先算法。

（3）扫描算法（当前磁头移动的方向为磁道递增）（10分） 解：

（1）磁道访问顺序为：20，44，40，4，80，12，76 寻道时间=（20+24+4+36+76+68+64）*3=292*3=876 （2）磁道访问顺序为：40，44，20，12，4，76，80 寻道时间=（0+4+24+8+8+72+4）*3=120*3=360

（3）磁道访问顺序为：40，44，76，80，20，12，4 寻道时间=（0+4+32+4+60+8+8）*3=116*3=348

19、生产者和消费者问题 （10分）

有一组生产者P1，P2，??，PM和一组消费者C1，C2，??，CK，他们通过由n个环形缓冲区构成的缓冲池进行通信，生产者把产品放入缓冲区，消费者从缓冲区取产品来消费。请用wait和signal原语实现他们的同步操作。

解：生产者和消费者问题 begin

Var mutex,empty,full:semaphore:=1,n,0; buffer:array[0,…,n-1] of item; in,out:integer := 0,0; parbegin

producer: begin repeat produce next product ; wait (empty); wait (mutex); buffer(in):=nextp ; in := (in+1) mod n ; signal (full); signal (mutex); until false ; end consumer: begin repeat wait (full); wait (mutex); nextc := buffer(out); out := (out+1) mod n; signal (empty); signal (mutex); consume the item in nextc; until false ; end

parend end

20、请用信号量描述哲学家进餐问题。（15分） 解：哲学家进餐问题（15分）

public void philosopher (int i) { while (true) { think();

wait (fork[i]);

wait (fork [(i+1) % 5]); eat();

signal(fork [(i+1) % 5]); signal(fork[i]); } }

21．今有三个并发进程R，M，P，它们共享了一个可循环使用的缓冲区B，缓冲区B共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“，”；进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。请用PV操作为同步机制写出它们能正确并发执行的程序。 （10分） 解：（10分）

begin

Var mutex,input,calculate,output:semaphore:=1,n,0,0; buffer:array[0,…,n-1] of item; in,mid,out:integer := 0,0,0; proR() { do { wait (input); wait (mutex); buffer(in):=input data; in := (in+1) mod n ; signal (calculate); signal (mutex); while true ; } proM() { do { wait (calculate); wait (mutex); buffer(middle):=calculate data ; mid := (mid+1) mod n ; signal (output); signal (mutex); } while true ; } proP() { do { wait (output);