《操作系统教程》（第三版）CH1应用题参考答案
答：(1)系统四个进程需要使用的资源数为R1各2台，R2各1台。可见资源数不足，同时
各进程申请资源在先，有可能产生死锁发生的四个条件，故系统可能产生死锁。
(2) 当三个进程执行完申请资源R1，开始执行申请资源R2时，第四个进程会因没有资
源R1而被阻塞。当三个进程执行完申请资源R2后，系统还剩1个R2资源。而这三个进程因执行申请第二个资源R1而全部被阻塞，系统进入死锁。
P1 P2 ● ● ● ●●●● P3
P4 16 假定某计算机系统有R1和R2两类可再使用资源（其中R1有两个单位，R2有一个单
位），它们被进程P1，P2所共享，且已知两个进程均以下列顺序使用两类资源。 →申请R1→申请R2→申请R1→释放R1→释放R2→释放R1→
试求出系统运行过程中可能到达的死锁点，并画出死锁点的资源分配图（或称进程－资源图）。 答：当两个进程都执行完第一步(都占用R1) 时，系统进入不安全状态。这时无论哪个进程执行完第二步，死锁都会发生。可能到达的死锁点：进程P1占有一个R1和一个R2，而进程P2占有一个R1。或者相反。这时己形成死锁。进程---资源图为：
P1 P1 ． ． P1
P1 17 桌上有一只盘子，最多可以容纳两个水果，每次仅能放入或取出一个水果。爸爸向盘子
中放苹果(apple)，妈妈向盘子中放桔子(orange)，两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。试用：(1)信号量和P、V操作，(2)管程，来实现爸爸、妈妈、
26
《操作系统教程》（第三版）CH1应用题参考答案
儿子、女儿间的同步与互斥关系。
答：(1)用信号量和P、V操作。
类似于课文中的答案，扩充如下：1) 同步信号量初值为2；2) 要引进一个互斥信号量mutex，用于对盘子进行互斥；3)盘子中每一项用橘子、苹果2个枚举值。
var
plate ARRAY[0,1] of (apple, orange);
flag0,flag1:boolean; mutex:semaphore;
sp:semaphore; /* 盘子里可以放几个水果 */ sg1，sg2:semaphore; /* 盘子里有桔子，有苹果?*/ sp := 2; /* 盘子里允许放入二个水果*/ sg1:=sg2:= 0; /* 盘子里没有桔子，没有苹果 */ flag0:=flag1:=false;mutex:=1; cobegin process son process father begin begin L3: P(sg1); L1: 削一个苹果; P(mutex); P(sp); if (flag0 & plate[0]= =桔子) then P(mutex); { x := plate[0];flag0:=false;} if (flag0==false) then else { x:= plate[1]; flag1:=false;} {plate [0]:=苹果; flag0:=true;} V(mutex); else { plate[1]:=苹果; flag1:=true; } V(sp); V(mutex); 吃桔子; V(sg2); goto L3; goto L1; end; end; process daughter process mother begin begin L4: P(sg2); L2: 剥一个桔子; P(mutex); P(sp); if (flag0 & plate[0]= =苹果) then P(mutex); { x := plate[0];flag0:=false;} if (flag0==false) then else { x:= plate[1]; flag1:=false;} {plate [0]:=桔子; flag0:=true;} V(mutex); else { plate[1]:=桔子; flag1:=true; } V(sp); V(mutex); 吃苹果; V(sg1); goto L4; goto L2; end; end; coend.
18 有P1、P2、P3三个进程共享一个表格F，P1对F只读不写，P2对F只写不读，P3对F先读
后写。进程可同时读F，但有进程写时，其他进程不能读和写。用(1)信号量和P、V操作，(2)管程编写三进程能正确工作的程序。 答：(1)信号量和P、V操作。
27
《操作系统教程》（第三版）CH1应用题参考答案
这是读--写者问题的变种。其中，P3既是读者又是写者。读者与写者之间需要互斥，写者
与写者之间需要互斥，为提高进程运行的并发性，可让读者尽量优先。 var rmutex,wmutex:semaphore;
rmutex:=wmutex:=1; count:integer;count:=0; cobegin {
process P1
begin repeat
P(rmutex);
count:=count+1;
if count=1 then P(wmutex); V(rmutex); Read F; P(rmutex);
count:=count-1;
if count=0 then V(wmutex); V(rmutex); untile false; end process P2
begin repeat
P(wmutex); Write F; V(wmutex);
untile false;
process P3
begin repeat
P(rmutex);
count:=count+1;
if count=1 then P(wmutex); V(rmutex); Read F; P(rmutex);
count:=count-1;
if count=0 then V(wmutex); V(rmutex); P(wmutex); Write F; V(wmutex); untile false;
28
《操作系统教程》（第三版）CH1应用题参考答案
end }
coend
CH4 应用题参考答案
1 在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是： 1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6。
分别用FIFO、OPT和LRU算法，对分配给程序3个页框、4个页框、5个页框和6个页框的情况下，分别求出缺页中断次数和缺页中断率。
答： 页框数 FIFO LRU OPT 3 16 15 11 4 14 10 8 5 12 8 7 6 9 7 7
只要把表中缺页中断次数除以20，便得到缺页中断率。
2 在一个请求分页虚拟存储管理系统中，一个作业共有5页，执行时其访问页面次序为：(1) 1、4、3、1、2、5、1、4、2、1、4、5。
(2) 3、2、1、4、4、5、5、3、4、3、2、1、5。 若分配给该作业三个页框，分别采用FIFO和LRU面替换算法，求出各自的缺页中断次数和缺页中断率。
答：(1) 采用FIFO为9次，9/12=75%。采用LRU为8次，8/12=67%。 (2) 采用FIFO和LRU均为9次，9/13=69%。
3 一个页式存储管理系统使用FIFO、OPT和LRU页面替换算法，如果一个作业的页面走向为：
(1) 2、3、2、1、5、2、4、5、3、2、5、2。 (2) 4、3、2、1、4、3、5、4、3、2、1、5。 (3 )1、2、3、4、1、2、5、1、2、3、4、5。 当分配给该作业的物理块数分别为3和4时，试计算访问过程中发生的缺页中断次数和缺页中断率。
答：(1) 作业的物理块数为3块，使用FIFO为9次，9/12=75%。使用LRU为7次，
7/12=58%。使用OPT为6次，6/12=50%。
作业的物理块数为4块，使用FIFO为6次，6/12=50%。使用LRU为6次，6/12=50%。使用OPT为5次，5/12=42%。
(2) 作业的物理块数为3块，使用FIFO为9次，9/12=75%。使用LRU为10次，
29
《操作系统教程》（第三版）CH1应用题参考答案
10/12=83%。使用OPT为7次，7/12=58%。
作业的物理块数为4块，使用FIFO为10次，10/12=83%。使用LRU为8
次，8/12=66%。使用OPT为6次，6/12=50%。
其中，出现了Belady现象，增加分给作业的内存块数，反使缺页中断率上升。
4 在可变分区存储管理下，按地址排列的内存空闲区为：10K、4K、20K、18K、7K、9K、12K和15K。对于下列的连续存储区的请求：(1)12K、10K、9K，(2)12K、10K、15K、18K试问：使用首次适应算法、最佳适应算法、最差适应算法和下次适应算法，哪个空闲区被使用？
答：(1) 空闲分区如图所示。 分区号 分区长
1 10KB
2 4KB
3 20KB
4 18KB
5 7KB
6 9KB
7 12KB
8 15KB
1)首次适应算法
12KB选中分区3，这时分区3还剩8KB。10KB选中分区1，恰好分配故应删去分
区1。9KB选中分区4，这时分区4还剩9KB。 2)最佳适应算法
12KB选中分区7，恰好分配故应删去分区7。10KB选中分区1，恰好分配故应删
去分区1。9KB选中分区6，恰好分配故应删去分区6。 3)最差适应算法
12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。
9KB选中分区8，这时分区3还剩6KB。 4)下次适应算法 12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。9KB选中分区6，恰好分配故应删去分区6。 (2) 原始分区情况同上图。 1)首次适应算法
12KB选中分区3，这时分区3还剩8KB。10KB选中分区1，恰好分配故应删去分
区1。15KB选中分区4，这时分区4还剩3KB。最后无法满否18KB的申请，应该等待。
2)最佳适应算法
12KB选中分区7，恰好分配故应删去分区7。10KB选中分区1，恰好分配故应删
去分区1。15KB选中分区8，恰好分配故应删去分区8。18KB选中分区4，恰好分配故应删去分区4。 3)最差适应算法
12KB选中分区3，这时分区3还剩8KB。10KB选中分区4，这时分区4还剩8KB。
30