《操作系统教程》（第三版）CH1应用题参考答案

18 在虚拟页式存储管理中，为解决抖动问题，可采用工作集模型以决定分给进程的物理块数，

有如下页面访问序列： …… 2 5 1 6 3 3 7 8 9 1 6 2 3 4 3 4 3 4 4 4 3 4 4 3 ……

△ t1 △ t2

窗口尺寸△＝9，试求t1、t2时刻的工作集。 答：t1时刻的工作集为：{1，2，3，6，7，8，9}。t时刻的工作集为：{3，4}。

19 有一个分页虚存系统，测得CPU和磁盘的利用率如下，试指出每种情况下的存在问题和可采

取的措施：(1)CPU利用率为13%，磁盘利用率为97% (2)CPU利用率为87%，磁盘利用率为3% (3)CPU利用率为13%，磁盘利用率为3% 。 答：(1)系统可能出现抖动，可把暂停部分进程运行。(2)系统运行正常，可增加运行进程数以进一步提高资源利用率。(3)处理器和设备和利用率均很低，可增加并发运行的进程数。

20 在一个分页虚存系统中，用户编程空间32个页，页长1KB，主存为16KB。如果用户程序有

10页长，若己知虚页0、1、2、3，已分到页框8、7、4、10 ，试把虚地址0AC5H和1AC5H转换成对应的物理地址。 答：虚地址0AC5H对应的物理地址为：12C5H。而执行虚地址1AC5H会发现页表中尚未有分配的页框而发生缺页中断，由系统另行分配页框。

21 某计算机有4个页框，每页的装入时间、最后访问时间、访问位R、修改位D如下所示(时间

用时钟点数表示)：

page loaded last ref R D 0 126 279 0 0 1 230 260 1 0 2 120 272 1 1 3 160 280 1 1

分别用FIFO、LRU、二次机会算法分别淘汰哪一页? 答：(1)FIFO 淘汰page2。 (2)LRU 淘汰page1。

(3) 二次机会 淘汰page0。 22 考虑下面的程序：

for (i=0;i<20；i++)

for(j=0;j<10;j++) a[i]：=a[i]×j

试举例说明该程序的空间局部性和时间局部性。

答：当数组元素a[0]，a[1]，?，a[19]存放在一个页面中时，其空间局部性和时间局部性较好，也就是说，在很短时间内执行都挂行循环乘法程序，而且数组元素分布在紧邻连续的存储单元中。当数组元素存放在不同页面中时，其时间局部性虽相同，但空间局部性较差，因为处理的数组元素分布在不连续的存储单元中。

23 一个有快表的请页式虚存系统，设内存访问周期为1微秒，内外存传送一个页面的平均时间为5毫秒。

如果快表命中率为75%，缺页中断率为10%。忽略快表访问时间，试求内存的有效存取时间。 答：快表命中率为75%，缺页中断率为10%，所以，内存命中率为15%。故内存的有效存取时间=1×75%+2×15%+(5000+2)×10%=501.25微秒。

24 假设某虚存的用户空间为1024KB，页面大小为4KB，内存空间为512KB。已知用户的虚页10、11、

29

《操作系统教程》（第三版）CH1应用题参考答案

12、13页分得内存页框号为62、78、25、36，求出虚地址0BEBC(16进制)的实地址(16进制)是多少?

答：虚地址0BEBC(16进制)的二进制形式为：0000 1011 1110 1011 1100。由于页面大小为4KB，故其中

后12位是位移，所以，虚地址的页号为：11。查页表分得内存对应页框号为：78。已知内存空间为512KB，故内存共有128个页框，78是合法物理块。把78化为16进制是4E，虚地址0BEBC(16进制)的实地址(16进制)是：4EEBC。

25 某请求分页存储系统使用一级页表，假设页表全部放在主存内，： 1)若一次访问主存花120ns，那么，访问一个数据的时间是多少?

2)若增加一个快表，在命中或失误时需有20ns开销，如果快表命中率为80%，则访问一个数据的

时间为多少? 答：1) 120ns×2=240ns。

2) (120+20)×80%+(120+120+20)×20%=174ns。

26 设某系统中作业J1，J2，J3占用主存的情况如图。今有一个长度为20k的作业J4要装入主存，当采用

可变分区分配方式时，请回答：

(1) J4装入前的主存已分配表和未分配表的内容。

(2) 写出装入J4时的工作流程，并说明你采用什么分配算法。

OS 0

J1 10k

18k

J2 30k

40k

J3 54k

70k

答：(1)主存已分配表共有三项，由作业J1、J2、J3占用，长度依次为：10k、30k和54k。未分配表共有三项：空闲区1、空闲区2和空闲区3，长度依次为18k、40k和70k。

(2)作业J4装入时，采用直接分配，搜索未分配表，空闲区1不能满足。所以，要继续搜索未分配表，空闲区2可以满足J4的装入要求。 27 考虑下列的段表：

段号 始址 段长 0 200 500 1 890 30 2 120 100 3 1250 600 4 1800 88

对下面的逻辑地址，求物理地址，如越界请指明。1) <0,480> 2)<1,25> 3)<1,14> 4)<2,200> 5) <3,500> 6)<4,100>。

答：1)680 2)915 3)904 4)越界 5)1750 6) 越界。

28 请页式存储管理中，进程访问地址序列为：10,11,104,170,73,305,180,240,244,445,467，366。试问

1)如果页面大小为100，给出页面访问序列。2)进程若分得3个页框，采用FIFO和LRU替换算法，求缺页中断率? 答：1) 页面访问序列为1，1，2，2，1，4，2，3，3，5，5，4。

2)FIFO为5次，缺页中断率为5/12=41.6%。LRU为6次，缺页中断率为6/12=50%。 LRU反比FIFO缺页中断率高。

29 假设计算机有2M内存，其中，操作系统占用512K，每个用户程序也使用512K内存。如果所有

程序都有70%的I/O等待时间，那么，再增加1M内存，吞吐率增加多少?

30

《操作系统教程》（第三版）CH1应用题参考答案

答：由题意可知，内存中可以存放3个用户进程，而CPU的利用率为：1-(70%)3 =1-(0.7)3 =65.7%。再

增加1M内存，可增加2个用户进程，这时CPU的利用率为：1-(70%)5 =1-(0.7)5=83.2%。故再增加1M内存，吞吐率增加了：83.2%÷65.7%-100%=27%。

30 一个计算机系统有足够的内存空间存放4道程序，这些程序有一半时间在空闲等待I/O操作。问

多大比例的CPU时间被浪费掉了? 答：(50%)4 =(1/2)4=1/16。

31 如果一条指令平均需1微秒，处理一个缺页中断另需n微秒，给出当缺页中断每k条指令发生一

次时，指令的实际执行时间。 答：(1+n/k)微秒。

32 一台计算机的内存空间为1024个页面，页表放在内存中，从页表中读一个字的开销是500ns。为

了减少开销，使用了有32个字的快表，查找速度为100ns。要把平均开销降到200ns需要的快表命中率是多少? 答：设快表命中率是x，则内存命中率为1-x。于是：500(1-x)+100x=200,解方程得x=75%。

CH5 应用题参考答案

1 旋转型设备上信息的优化分布能减少为若干个I/O服务的总时间。设磁鼓上分为20个区，每区存

放一个记录，磁鼓旋转一周需20毫秒，读出每个记录平均需用1毫秒，读出后经2毫秒处理，再继续处理下一个记录。在不知当前磁鼓位置的情况下：（1）顺序存放记录1、??，记录20时，试计算读出并处理20个记录的总时间；（2）给出优先分布20个记录的一种方案，使得所花的总处理时间减少，且计算出这个方案所花的总时间。 答：定位第1个记录需10ms。读出第1个记录，处理花2ms，这时已到了第4个记录，再转过18个记录(花18ms)才能找到记录2，所以，读出并处理20个记录的总时间：

10+3+(1+2+18)×19=13+21×19=412ms

如果给出优先分布20个记录的方案为：1，8，15，2，9，16，3，10，17，4，11，18，5，12，

19，6，13，20，7，14。当读出第1个记录，花2ms处理后，恰好就可以处理记录2，省去了寻找下一个记录的时间，读出并处理20个记录的总时间： 10+3+3×19=13+247=260ms

2 现有如下请求队列：8，18，27，129，110，186，78，147，41，10，64，12；试用查找时间最短

优先算法计算处理所有请求移动的总柱面数。假设磁头当前位置下在磁道100。

答：处理次序为：100-110-129-147-186-78-64-41-27-18-12-10-8。移动的总柱面数：264。

3 上题中，分别按升序和降序移动，讨论电梯调度算法计算处理所有存取请求移动的总柱面数。 答：升序移动次序为：100-110-129-147-186-78-64-41-27-18-12-10-8。移动的总柱面数：264。 降序移动次序为：100-78-64-41-27-18-12-10-8-110-129-147-186。移动的总柱面数：270。

4 某文件为连接文件，由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为512字

节，并依次存放在50、121、75、80、63号磁盘块上。现要读出文件的1569字节，问访问哪一个磁盘块? 答：80号磁盘块

5 对磁盘存在下面五个请求： 请 求 1

柱 面 号 7 磁 头 号 2 31

扇 区 号 8 《操作系统教程》（第三版）CH1应用题参考答案

2 3 4 5 7 7 30 3 2 1 5 6 5 2 3 6 假如当前磁头位于1号柱面。试分析对这五个请求如何调度，可使磁盘的旋转圈数为最少？

答：使磁盘的旋转圈数为最少的调度次序为：5、3、2、1、和4。

6 有一具有40个磁道的盘面，编号为0~39，当磁头位于第11磁道时，顺序来到如下磁道请求：磁

道号：1、36、16、34、9、12；试用1）先来先服务算法FCFS、2）最短查找时间优先算法SSTF、3）扫描算法SCAN等三种磁盘驱动调度算法，计算出它们各自要来回穿越多少磁道？ 答：1)FCFS为111。 2)SSTF为61。 3)SCAN为60(先扫地址大的请求)，为45(先扫地址小的请求)。 7 假定磁盘有200个柱面，编号0~199，当前存取臂的位置在143号柱面上，并刚刚完成了125号

柱面的服务请求，如果请求队列的先后顺序是：86，147，91，177，94，150，102，175，130；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。 (1)先来先服务算法FCFS；

(2)最短查找时间优先算法SSTF； (3)扫描算法SCAN。 (4)电梯调度。 答：(1)先来先服务算法FCFS为565，依次为143-86-147-91-177-94-150-102-175-130。

(2)最短查找时间优先算法SSTF为162，依次为143-147-150-130-102-94-91-86-175-177。 (3)扫描算法SCAN为169，依次为143-147-150-175-177-199-130-102-94-91-86。

(4)电梯调度为125(先向地址大的方向)，依次为143-147-150-175-177-102-94-91-86。为148(先向地址小的方向) 依次为143-130-102-94-91-86-147-150-175-177。

8

除FCFS外，所有磁盘调度算法都不公平，如造成有些请求饥饿，试分析：(1)为什么不公平？(2)提出一种公平性调度算法。(3)为什么公平性在分时系统中是一个很重要的指标？

答：(1)对位于当前柱面的新请求，只要一到达就可得到服务，但对其他柱面的服务则不然。如SSTF

算法，一个离当前柱面远的请求，可能其后不断有离当前柱面近的请求到达而得不到服务(饥饿)。 (2)可划定一个时间界限，把这段时间内尚未得到服务的请求强制移到队列首部，并标记任何新请求不能插到这些请求前。对于SSTF算法来说，可以重新排列这些老请求，以优先处理。 (3)可避免分时进程等待时间过长而拉长响应时间。

9

若磁头的当前位置为100柱面，磁头正向磁道号减小方向移动。现有一磁盘读写请求队列，柱面号依次为：190，10，160，80，90，125，30，20，29，140，25。若采用最短寻道时间优先和电梯调度算法，试计算出各种算法的移臂经过的柱面数？

答：采用SSTF处理次序为：100-90-80-125-140-160-190-30-29-25-20-10，总柱面数为：310。采用电梯调度处理次序为：100-90-80-30-29-25-20-10-125-140-160-190，总柱面数为：270。

10 若磁头的当前位置为100柱面，磁头正向磁道号增加方向移动。现有一磁盘读写请求队列，柱面号依

次为：23，376，205，132，19，61，190，398，29，4，18，40。若采用先来先服务、最短寻道时间优先和扫描算法，试计算出各种算法的移臂经过的柱面数？

答：采用先来先服务处理次序为：100-23-376-205-132-19-61-190-398-29-4-18-40，总柱面数为：1596。

采用SSTF处理次序为：100-132-190-205-61-40-29-23-19-18-4-376-398，总柱面数为：700。 采用SCAN处理次序为：100-132-190-205-376-398-61-40-29-23-19-18-4，总柱面数为：692。

CH6 应用题参考答案

32