think(); wait (room); wait (fork[i]); wait (fork [(i+1) % 5]); eat();
signal (fork [(i+1) % 5]); signal (fork[i]); signal (room); void main() {
parbegin (philosopher (0), philosopher (1), philosopher (2), philosopher (3), philosopher (4));
15．考虑一个有150个存储器单元的系统，如下分配给三个进程： 进程
最大
占有
}
} }
———————————————————— 1 2 3
70 60 60
45 40 15
使用银行家算法，以确定下面的任何一个请求是否安全：
a．第4个进程到达，最多需要60个存储单元，最初需要25个单元； b．第4个进程到达，最多需要60个存储单元，最初需要35个单元； 如果安全给出安全序列；若不安全给出结果分配简表。（10分） 解：进程 最大 占有 尚需 可用 ———————————————————————— 1 70 45 25 25 2 60 40 20 3 60 15 45 4 60 25 35
安全序列为：1、2、3、4
所以系统是安全的，可以进行分配。 b． 进程 最大 占有 尚需 可用 ———————————————————————— 1 70 45 25 15 2 60 40 20 3 60 15 45 4 60 35 25
当前可用的资源不够任何一个进程运行完毕，所以不安全。
16. Jruassic 公园有一个恐龙博物馆和一个公园.有m个旅客和n辆车,每辆车只能容纳一个旅客。旅客在博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它载入一个旅客，然后绕公园行驶任意长的时间。如果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; } }
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); wait (mutex); buffer(out):=calculate data ; out := (out+1) mod n ; signal (input); signal (mutex); } while true ; }
22.理发店里有一位理发师、一把理发椅子和五把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，而如果有空椅子可坐，他们就坐下来等，如果没有空椅子，他就离开。这里的问题是为理发师和顾客各编写一段程序来描述他们行为，并用wait和signal原语操作实现其同步。（10分） 解：理发师问题
#define CHAIRS 5 /*为等候的顾客准备椅子数*/ typedef int semaphore; /* 运用你的想像力*/ semphore customers=0; /*等候服务的顾客数*/ semaphore barbers=0 /*等候服务的理发师数*/ semaphore mutex=1; /*用于互斥*/
int waiting=0; /*还没理发的等候顾客*/ void barber (void) { while(TRUE) {
wait(customers); /*如果顾客数是0，则睡觉*/ wait(mutex); /*要求进程等候*/ waiting=waiting-1; /*等候顾客数减1*/
signal(barbers); /*一个理发师现在开始理发*/ signal(mutex); /*释放等候*/ cut_hair(); /*理发（非临界区操作）*/ }
void customers (void) { wait(mutex);
if (waiting