操作系统练习题答案

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

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次,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 25 《操作系统教程》(第三版)CH1应用题参考答案

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。15KB选中

分区8,恰好分配故应删去分区8。最后无法满否18KB的申请,应该等待。 4)下次适应算法

12KB选中分区3,这时分区3还剩8KB。10KB选中分区4,这时分区4还剩8KB。15KB选中分区8,恰好分配故应删去分区8。最后无法满否18KB的申请,应该等待。

5 给定内存空闲分区,按地址从小到大为:100K、500K、200K、300K和600K。现有用户进程依次分别为212K、417K、112K和426K,(1)分别用first-fit、best-fit和worst-fit算法将它们装入到内存的哪个分区?(2) 哪个算法能最有效利用内存? 答:按题意地址从小到大进行分区如图所示。

分区号 分区长

1 100KB

2 500KB

3 200KB

4 300KB

5 600KB

(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算法能最有效利用内存

26

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

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))×(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 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 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(八进制)是合法地址,于是,物理地址

27

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

为100与位移1 100 101 110并接,得到:八进制物理地址100 1 100 101 110。

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

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

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

28

联系客服:779662525#qq.com(#替换为@)