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 signal(mutex); } } 23、根据如下的前趋图写出可并发执行的程序：（10分） 2 1 5 3 4 6 7 解：（10） 评分：变量、进程、程序主体每项一分。 var a,b,c,d,e,f,g,h,i:semaphore := 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(c); S3; signal(e);signal(f); end begin wait(b); S4; signal(g); end begin wait(d);wait(e) S5; signal(h); end begin wait(f); wait(g); S6 ; signal(i); end begin wait(h); wait(i); S7; end parend end 24、在公共汽车上，乘客上完后，售票员关门，驾驶员开车，售票员售票，到站汽车停稳后，售票员开门，乘客上下车，售票员和驾驶员之间密切配合，直到下班。请用信号量描述公共汽车上售票员与驾驶员的工作过程。（10分） 解：建立驾驶员和售票员两进程，驾驶员进程执行过程如下： （1） 判售票员关门没有 （2） 开车 （3） 到站后停车 （4） 重复（1）－（3） 售票员执行过程如下： （1） 判断乘客上完没有 （2） 关门 （3） 售票 （4） 判车停稳没有