（二）应用题
第二章
1.有三个并发进程P、Q和R以及一对供存储数据的缓冲BufI和BufO，P进程把数据输入BufI，R进程输出BufO中的数据。Q地把BufI中的数据变换后送入BufO，在上述假定之下,使三个进程实现最大并行性。试在下述类PASCAL程序中虚线位置分别填上信号量、信号量初值和P、V操作实现三个进程正确的并发执行。
BufI BufO P Q R
Program ito;
var BufI,BufO:buffer;
(信号量)﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎:SEMAPHORE:= (信号量初值)﹎﹎﹎﹎﹎﹎﹎﹎； begin parbegin procedure P begin repeat
input from IO;
﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎ Add to BufI;
﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎ until false end;
procedure Q; begin repeat
﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎ Remove from BufI;
﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎ transform;
﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎ Add to BufO;
﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎ until false end;
procedure R; begin repeat
﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎ Remove from BufO;
﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎
16
Output ...; until false end; parend end
2.桌上有一个空盒，盒内只允许放一个水果。妈妈轮流向盒内放桔子和苹果，儿子专等吃盒中的桔子，女儿专等吃盒中的苹果。若盒内已有水果，放者必须等待，若盒内没有自己吃的水果，吃者必需等待。试在下述类PASCAL程序中虚线位置分别填上信号量、信号量初值和P、V操作实现三个进程正确的并发执行。
var (信号量)﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎：semaphore：= (信号量初值) ﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎； begin parbegin 妈:begin
repeat
準備 ﹎﹎﹎﹎﹎﹎﹎﹎ 向盒内放桔子 ﹎﹎﹎﹎﹎﹎﹎﹎ 準備
﹎﹎﹎﹎﹎﹎﹎﹎ 向盒内放苹果 ﹎﹎﹎﹎﹎﹎﹎﹎ until false end
儿：begin repeat
﹎﹎﹎﹎﹎﹎﹎﹎ 拿盒中的桔子 ﹎﹎﹎﹎﹎﹎﹎﹎ 吃桔子
until false end 女：begin repeat
﹎﹎﹎﹎﹎﹎﹎﹎
拿盒中的苹果 ﹎﹎﹎﹎﹎﹎﹎﹎ 吃苹果
until false end parend end
17
3．假定在一个处理机上执行以下五个作业： 作业号 到达时间 运行时间 A 0 4 B 1 3 C 2 5 D 3 2 E 4 4
(1)画出采用FCFS调度算法时调度图，并计算每个作业的周转时间和计算平均周转时间。 (2)画出采用SJF调度算法时调度图，并计算每个作业的周转时间和计算平均周转时间。 (3)写出采用HRN（响应比高者优先）调度算法时选择作业号的次序和选择作业的依据（各作业的响应比）。
4．试描述避免死锁的银行家算法，若系统运行中出现下述资源分配情况 进程 ALLOCATION NEED AVAILABLE A B C D A B C D A B C D P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6
该系统是否安全？如果进程P2此时提出资源申请（1，2，2，2），系统能否将资源分配给它？为什么？
答案：
1．解:
首先找出两进程并发执行时必须在执行序列上遵循的同步规则：第1条同步规则是只有当P进程“Add to BufI”后，Q进程才能来“Remove from BufI”，否则Q进程只能等待。为了满足第1条同步规则，设置一个同步信号量fullI，它是后做动作的Q进程拥有的私有资源，它是Q进程动作“Remove from BufI”成功所需的资源――缓冲器BufI装满输入数据，由于初始时缓冲器BufI空，它的初值为0。后做动作的Q进程在动作“Remove from BufI”前对信号量fullI施加P操作，表示申请资源。由于它又是消耗性的资源，必须由先做动作“add to BufI”的P进程在动作完成后对信号量fullI施加V操作，表示释放资源。（这在课件答案中用红的颜色字表示）
两进程并发执行时必须在执行序列上遵循的同步规则还有三个： 第二条同步规则是只有当Q进程“Remove from BufI”后，P进程才能将“add to BufI”,否则P进程也只能等待。为了满足第2条同步规则，设置另一个同步信号量emptyI，它是后做动作的进程P所拥有的私有资源，它代表的资源是缓冲器BufI空，它的初值为1 。后做动作的P进程在“add to BufI”动作前对信号量emptyI施加P操作，表示申请资源。由于它又是消耗性的资源，必须由它的合作进程Q“Remove from BufI”后对emptyI信号量施加V操作来释放资源。（这在课件答案中用黑的颜色字表示）
第三条同步规则是只有当Q进程“Add to BufO”后，R进程才能来“Remove from BufO”，
18
否则R进程只能等待。为了满足第3条同步规则，设置一个同步信号量fullO，它是后做动作的R进程拥有的私有资源，它是R进程动作“Remove from BufO”成功所需的资源――缓冲器BufO装满处理过的数据，由于初始时缓冲BufO器空，它的初值为0。后做动作的R进程在动作“Remove from BufO”前对信号量fullO施加P操作，表示申请资源。由于它又是消耗性的资源，必须由先做动作“add to BufO”的Q进程在动作完成后对信号量fullO施加V操作，表示释放资源。（这在课件答案中用绿的颜色字表示）
第四条同步规则是只有当R进程“Remove from BufO”后，Q进程才能将“add to BufO”,否则Q进程也只能等待。为了满足第4条同步规则，设置另一个同步信号量emptyO，它是后做动作的进程Q所拥有的私有资源，它代表的资源是缓冲器BufO空，它的初值为1 。后做动作的Q进程在“add to BufO”动作前对信号量emptyO施加P操作，表示申请资源。由于它又是消耗性的资源，必须由它的合作进程R在“Remove from BufO”后对emptyO信号量施加V操作来释放资源。（这在课件答案中用兰的颜色字表示）
Program ito;
var BufI,BufO:buffer;
(信号量)﹎emptyI,fullI,emptyO,fullO﹎:SEMAPHORE:= (信号量初值)﹎1,0,1,0;﹎； begin parbegin procedure P begin repeat
input from IO;
﹎﹎﹎﹎ P(emptyI) ;﹎﹎﹎﹎ Add to BufI;
﹎﹎﹎﹎ V(fullI) ;﹎﹎﹎﹎ until false end;
procedure Q; begin repeat
﹎﹎P(fullI) ;﹎﹎﹎ Remove from BufI;
﹎﹎V(emptyI) ;﹎﹎﹎﹎ transform;
﹎﹎P(emptyO) ;﹎﹎﹎﹎ Add to BufO;
﹎﹎V(fullO) ;﹎﹎﹎﹎﹎ until false end;
procedure R; begin repeat
﹎﹎P(fullO) ;﹎﹎﹎
19
Remove from BufO; ﹎ V(emptyO) ;﹎﹎ Output ...; until false end; parend end
2.解:
var (信号量)﹎﹎S , S1 , S2 ﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎：semaphore：= (信号量初值) ﹎﹎1 , 0 , 0 ﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎﹎； begin parbegin 妈:begin repeat
準備
﹎﹎ P (S ) ﹎﹎ 向盒内放桔子
﹎﹎ V (S1 ) ﹎﹎ 準備
﹎﹎ P (S ) ﹎﹎ 向盒内放苹果 ﹎﹎ V (S2) ﹎﹎ until false end
儿：begin repeat
﹎﹎ P (S1 ) ﹎﹎ 拿盒中的桔子 ﹎﹎ V (S) ﹎﹎ 吃桔子
until false end 女：begin repeat
﹎﹎ P (S2 ) ﹎﹎ 拿盒中的苹果
﹎﹎ V (S) ﹎﹎ 吃苹果
until false end parend end
20