《操作系统教程》（第三版）CH4应用题参考答案
为212K、417K、112K和426K，(1)分别用first-fit、best-fit和worst-fit算法将它们装入到内存的哪个分区?(2) 哪个算法能最有效利用内存? 答：按题意地址从小到大进行分区如图所示。
(1) 1)first-fit 212KB选中分区2，这时分区2还剩288KB。417KB选中分区5，这时分区5还剩183KB。
112KB选中分区2，这时分区2还剩176KB。426KB无分区能满足，应该等待。
2)best-fit 212KB选中分区4，这时分区4还剩88KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区3，这时分区3还剩88KB。426KB选中分区5，这时分区5还剩174KB。
3)worst-fit 212KB选中分区5，这时分区5还剩388KB。417KB选中分区2，这时分区2还剩83KB。112KB选中分区5，这时分区5还剩176KB。426KB无分区能满足，应该等待。 (2) 对于该作业序列，best-fit算法能最有效利用内存
6 一个32位地址的计算机系统使用二级页表，虚地址被分为9位顶级页表，11位二级页表和偏移。试问：页面长度是多少？虚地址空间共有多少个页面？
答：由于32-9-11=12，所以，页面大小为4KB，页面的个数为220 个。
7 一进程以下列次序访问5个页：A、B、C、D、A、B、E、A、B、C、D、E；假定使用FIFO替换算法，在内存有3个和4个空闲页框的情况下，分别给出页面替换次数。
答：内存有3个和4个空闲页框的情况下，页面替换次数为9次和10次。出现了Belady现象，增加分给作业的内存块数，反使缺页中断率上升。
8 某计算机有缓存、内存、辅存来实现虚拟存储器。如果数据在缓存中，访问它需要Ans；如果在内存但不在缓存，需要Bns将其装入缓存，然后才能访问；如果不在内存而在辅存，需要Cns将其读入内存，然后，用Bns再读入缓存，然后才能访问。假设缓存命中率为（n-1）/n，内存命中率为（m-1）/m，则数据平均访问时间是多少？ 答：
数据在缓存中的比率为：(n-1)/n
数据在内存中的比率为：(1-(n-1)/n)×(m-1)/m=(m-1)/nm 数据在辅存中的比率为：(1-(n-1)/n)×(1-(m-1)/m)=1/nm
故数据平均访问时间是=((n-1)/n)×A+((1-(n-1)/n)×(m-1)/m)×(A+B)+( (1-(n-1)/n)×(1-(m-1)/m))×
21
分区号 分区长 1 100KB 2 500KB 3 200KB 4 300KB 5 600KB 《操作系统教程》（第三版）CH4应用题参考答案
(A+B+C)=A+B/n+C/nm
9 某计算机有cache、内存、辅存来实现虚拟存储器。如果数据在cache中，访问它需要20ns；如果在内存但不在cache，需要60ns将其装入缓存，然后才能访问；如果不在内存而在辅存，需要12ms将其读入内存，然后，用60ns再读入cache，然后才能访问。假设cache命中率为0.9，内存命中率为0.6，则数据平均访问时间是多少(ns)？ 答：506ns。
10 有一个分页系统，其页表存放在主存里，(1)如果对内存的一次存取要1.2微秒，试问实现一次页面访问的存取需花多少时间？(2)若系统配置了联想存储器，命中率为80×%，假定页表表目在联想存储器的查找时间忽略不计，试问实现一次页面访问的存取时间是多少？ 答：(1)2.4微秒 (2) 0.8×1.2+0.2×2.4=0.76+0.48=1.24微秒
11给定段表如下：
段 号 0 1 2 3 4 段 首 址 219 2300 90 1327 1952 段 长 600 14 100 580 96 给定地址为段号和位移：1）[0，430]、2）[3，400]、3）[1，1]、4）[2，500]、5）[4，42]，试求出对应的内存物理地址。
答：1)449 2)1727 3)2301 4)越界 5)1994
12 某计算机系统提供24位虚存空间，主存为218B，采用分页式虚拟存储管理，页面尺寸为1KB。假定
用户程序产生了虚拟地址11123456（八进制），而该页面分得块号为100(八进制)，说明该系统如何产生相应的物理地址及写出物理地址。
答：虚拟地址11123456（八进制）转化为二进制为： 001 001 001 010 011 100 101 110
其中前面为页号，而后10位为位移：001 001 001 010 01--------1 100 101 110。由于主存大小为218B，页面尺寸为1KB，所以，主存共有256块。所以，块号为100(八进制)是合法地址，于是，物理地址为100与位移1 100 101 110并接，得到：八进制物理地址100 1 100 101 110。
13主存中有两个空间区如图所示，
22
《操作系统教程》（第三版）CH4应用题参考答案
0K
15K 125K
100K 50K 现有作业序列依次为：Job1要求30K；Job2要求70K；Job3要求50K；使用首次适应、最坏适应和最佳适应算法处理这个作业序列，试问哪种算法可以满足分配？为什么？
答：首次适应、最坏适应算法处理这个作业序列可以满足分配，最佳适应算法不行。因为后者会分割出无法使用的碎片，浪费内存，从而，不能满足所有作业的内存需求。
14 设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048字节，内存总共
有8个存储块。试问逻辑地址至少应为多少位？内存空间有多大？ 答：逻辑地址211 ×24 ，故为15位。内存大小为23×211=214B=16KB。
15 在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为
2F6AH，且第0、1、2页依次存在物理块10、12、14号中，问相应的物理地址为多少？ 答：因为逻辑地址长度为16位，而页面大小为4096字节，所以，前面的4位表示页号。把2F6AH转换成二进制为：0010 1111 0110 1010，可知页号为2。故放在14号物理块中，写成十六进制为：EF6AH。
16 有矩阵：VAR A：ARRAY[1‥100,1‥100] OF integer；元素按行存储。在一虚存系统中，采
用LRU淘汰算法，一个进程有3页内存空间，每页可以存放200个整数。其中第1页存放程序，且假定程序已在内存。 程序A：
FOR i：＝1 TO 100 DO FOR j：＝1 TO 100 DO A[i,j]：＝0； 程序B：
FOR j：＝1 TO 100 DO FOR i：＝1 TO 100 DO A[i,j]：＝0；
分别就程序A和B的执行进程计算缺页次数。
答：题中100×100=10000个数据，每页可以存放200个整数，故一共存放在50个页面中。由于元素按行存储，第1行、第2行放在第1页，?，第99行、第100行放在第50页。故对于程序A，缺页中断为50次。对于程序B，缺页中断为5000次。
23
《操作系统教程》（第三版）CH4应用题参考答案
17 一台机器有48位虚地址和32位物理地址，若页长为8KB，问页表共有多少个页表项?如果设计一
个反置页表，则有多少个页表项?
答：因为页长8KB占用13住，所以，页表项有235个。反置页表项有219个。
18 在虚拟页式存储管理中，为解决抖动问题，可采用工作集模型以决定分给进程的物理块数，有如
下页面访问序列：
窗口尺寸△＝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。
24
…… 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 《操作系统教程》（第三版）CH4应用题参考答案
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、
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时的工作流程，并说明你采用什么分配算法。
0 10k 18k 30k 40k
OS J1 J2 25
《操作系统教程》（第三版）CH4应用题参考答案
54k 70k
J3 答：(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内存，吞吐率增加多少?
答：由题意可知，内存中可以存放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%。
26