操作系统 - - - - 课后答案(1) 下载本文

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

13主存中有两个空间区如图所示,

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次。

33

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

17 一台机器有48位虚地址和32位物理地址,若页长为8KB,问页表共有多少个

页表项?如果设计一个反置页表,则有多少个页表项? 答:因为页长8KB占用13住,所以,页表项有235个。反置页表项有219个。

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++)

34

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

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时的工作流程,并说明你采用什么分配算法。

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的装入要求。

35

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

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%。

CH5 应用题参考答案

36