四、综合应用题(每题10分，共40分).
（p 、v操作）
1、请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。
1． 答：将独木桥的两个方向分别标记为A和B；并用整形变量countA和countB分别表示A、B方向上已在独木桥上的行人数，初值为0；再设置三个初值都1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现两个方向的行人对独木桥的互斥使用。则具体描述如下：
Var SA,SB,mutex:semaphore:=1,1,1;
CountA,countB:integer:=0,0:
begin
parbegin
process A: begin
wait(SA);
if(countA=0) then wait(mutex);
countA:=countA+1;
signal(SA);
过独木桥；
wait(SA);
countA:=countA-1;
if (countA=0) then signal(mutex);
signa(SA);
end
process B: begin
wait(SB);
if(countB=0) then wait(mutex);
countB:=countB+1;
signal(SB);
过独木桥；
wait(SB);
countB:=countB-1;
if (countB=0) then signal(mutex);
signa(SB);
end
parend
end
2. 有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。解释P、V操作的含义，并用P、V操作来保证文件的正确打印。
（1）P、V操作是两条原语，定义如下：
P操作：P操作记为P(S)，其中S为一信号量，它执行时主要完成下述动作：
S=S-1
若S>=0，则进程继续运行。 若S<0，则该进程被阻塞，并将它插入该信号量的等待队列中。
V操作：V操作记为V(S)，其中S为一信号量，它执行时主要完成下述动作： S=S+1
若S>0，则进程继续运行。
若S<=0，则从信号量的等待队列中移出队首进程。使其变为就绪状态。
（2）描述如下：
Var empty1,empty2,full1,full2:semaphore:=1,1,0,0; begin
parbegin process1: begin
repeat
从磁盘读一个记录；
P(empty1);
将记录存入缓冲区1；
V(full1);
until false;
end
process 2: begin repeat
P(full1);
从缓冲区1取出纪录；
V(empty1); P(empty2);
将记录存入缓冲区2；
V(full2);
until false;
end
process 3: begin repeat
P(full2);
从缓冲区2取出纪录；
V(empty2);
打印记录；
until false;
end
parend
3. 设某台机挂有两个I/O通道：分别挂一台输入机和一台打印机。卡片机上有一叠数据卡片，现在要把这些数据逐一输入到缓冲区buffe1，然后再复制到缓冲区buffe2，并在打印机上打印出来。系统可设哪些进程来完成这个任务？用P-V原语写这些进程的同步算法。 buffer1 buffer2 get copy put
卡片 打印机
由上图可见，系统可设3个进程：输入进程、复制进程、打印进程；分别用进程R、进程C、进程P来表示。
这些进程之间的相互制约关系：
R受C的约束；C受R、P的约束；P受C的约束。
设4个信号量：S1=1，S2=0，S3=1，S4=0 （有几个制约设几个信号量，信号量的初值根据资源是否可以用设置）
同步算法如下：
4.假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作，请用记录型信号量机制实现上述问题的同步。
Var sum,mutex:semaphore:=100,1;
begin
parbegin
进入: begin
wait(sum);
wait(mutex);
登记；
signal(mutex);
进入阅览室；
End
离开: begin
wait(mutex);
登记；
signal(mutex);
离开阅览室；
signal(sum); end
parend
End
（进程调度）
1、在两道环境下有四个作业，已知它们进入系统的时间、估计运行时间，系统分别采用短作业优先作业调度算法（可抢占式）和最高响应比优先调度算法（可抢占式），分别给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间。
1、答：系统采用短作业优先调度：
作业 进入时间 估计运行时间（分钟） 开始时间 结束时间 周转时间（分钟） 带权周转时间
JOB1 10：00 30 10：00 11：05 65 2.167
JOB2 10：05 20 10：05 10：25 20 1
JOB3 10：20 5 10：25 10：30 20 4
JOB4 10：30 10 10：30 10：40 20 2
作业的周转时间：31.25 带权周转时间：2.29 125
9.167
系统采用高响应比作业优先调度：
作业 进入时间 估计运行时间（分钟） 开始时间 结束时间 周转时间（分钟） 带权周转时间
JOB1 10：00 30 10：00 10：30 30 1
JOB2 10：05 20 10：35 10：55 50
2.5
JOB3 10：20 5 10：30 10：35 25 5
JOB4 10：30 10 10：55 11：05 35 3.5
作业的周转时间：35 带权周转时间：3 140 12
2．假设有 4 道作业，它们提交的时刻及执行时间由下表给出，计算在单道程序环境下，采用先来先服务调度算法、最短作业优先算法、最高响应比优先算法的平均周转时间和平均带权周转时间，并指出它们的调度顺序。
作业 提交时间 运行时间
1 8.0 2.0
2 8.5 0.5
3 9.0 0.1
4 9.5 0.2
2、答：先来先服务调度算法 作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间
1 8.0 2.0 8.0 10.0 2.0 1.0
2 8.5 0.5 10.0 10.5 2.0 4.0
3 9.0 0.1 10.5 10.6 1.6 16.0
4 9.5 0.2 10.6 10.8 1.3 6.5
T=1.725 W=6.875
最短作业优先算法
作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间
1 8.0 2.0 8.0 10.0 2 1
2 8.5 0.5 10.3 10.8 2.3 4.6
3 9.0 0.1 10.0 10.1 1.1 11
4 9.5 0.2 10.1 10.3 0.8 4
T=1.55 W=5.15
最高响应比优先算法
响应比Rp＝作业响应时间／运行时间＝作业等待时间＋作业运行时间
＝１＋作业等待时间／作业运行时间
作业 提交时间 运行时间 开始时间 完成时间 Rp 周转时间 带权周转时间
1 8.0 2.0 8.0 10.0 1 2 1
2 8.5 0.5 10.1 10.6 3.2 2.1 4.2
3 9.0 0.1 10.0 10.1 10 1.1 11
4 9.5 0.2 10.6 10.8 5.5 1.3 6.5
T=1.625 W=5.675
3、假设进程到达时间和要求服务时间如下表：。
进程名 A B C D E F
到达时间 0 1 2 3 4 5
服务时间 4 3 5 6 2 4
(1)计算采用FCFS和SJF调度算法各进程的周转时间和带权周转时间。
(2)基于时间片的轮转调度算法中，时间片分别为1和4时，计算各进程的周转时间和带权周转时间。
答：
进程名 A B C D E F 平均
到达时间 0 1 2 3 4 5
服务时间 4 3 5 6 2 4
FCFS 完成时间 4 7 12 18 20 24
周转时间 4 6 10 15 16 19 11.67
带权周转时间 1 2 2 2.5 8 4.75 2.85
SJF 完成时间 4 9 18 24 6 13
周转时间 4 8 16 21 2 8 9.8
带权周转时间 1 2.67 3.2 3.5 1 2 2.23