第四章 作业参考答案

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

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

9. 某计算机有cache、内存、辅存来实现虚拟存储器。如果数据在cache中，访问它需要20ns；如果在内存但不在cache，需要60ns将其装入缓存，然后才能访问；如果不在内存而在辅存，需要12µs将其读入内存，然后，用60ns再读入cache，然后才能访问。假设cache命中率为0.9，内存命中率为0.6，则数据平均访问时间是多少(ns)？ 答：200.9[(6020)0.6(120006020)0.4]0.1506ns。

12. 某计算机系统提供24位虚存空间，主存为218B，采用分页式虚拟存储管理，页面尺

寸为1KB。假定用户程序产生了虚拟地址11123456（八进制），而该页面分得块号

为100(八进制)，说明该系统如何产生相应的物理地址及写出物理地址。

答：因为系统页面尺寸为1KB，所以24位逻辑地址中后10位是页内位移。虚拟地址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并接，得到：八进制物理地址001000000 1 100 101 110=201456（八进制）。

22. 某计算机有4个页框，每页的装入时间、最后访问时间、访问位R、修改位D如下表所示（时间用时钟点数表示）。分别用NRU、FIFO、LRU、二次机会算法，问分别淘汰哪一页？

Page Loaded Last reference R D 0 126 269 0 0 1 230 250 1 0 2 110 273 1 1 3 160 280 1 1

答：装入时间越小，则装入越早；同样，最近访问时间越小，则访问越早。于是： (1)NRU 淘汰page0

(2)FIFO淘汰page2 (3)LRU淘汰page1

(4) 二次机会算法 淘汰page0

26.某虚存的用户空间为1024KB，页面大小为4KB，主存空间为512KB。已知用户的10、11、12、13号虚页分得主存页框号为62、78、25、36，求出虚地址0BEBCH的实地址。 答：虚地址0BEBCH(16进制)的二进制形式为：0000 1011 1110 1011 1100。由于页面大小为4KB ，故其中后12位是页内位移，则得到虚地址的页号为：11。查页表得知11号页面对应的页框号为78，已知主存为512KB ，故主存有128个页框，则78是合法的页框号，所以虚地址0BEBCH(16进制)对应的实地址(16进制)是：4EEBCH。

28.设某系统中作业J1、J2、J3，占用内存的情况如下图所示。现有一个长度为20KB的作业J4要装入内存，当采用可变分区分配方式时，请回答：(1) J4装入前的内存已分配表和未分配表的内容；(2)写出装入作业J4的工作流程，并说明采用何种分配算法。

0 10KB 18KB 30KB 40KB 54KB 70KB

操作系统 J1 J2 J3 答：(1) J4装入前的内存已分配表和未分配表的内容如下：

已分配表 未分配表 起址 长度 状态 起址 长度 状态 0KB 10KB J1 10KB 18KB 未分配 28KB 30KB J2 58KB 40KB 未分配 98KB 54KB J3 152KB 70KB 未分配

(2)将未分配表按照长度从小到大排序，则：

采用最先适应算法和最佳适应算法，作业J4装入时，将40KB大小的空闲区进行划分，形成一个20KB大小的已分配区域（J4）和一个20KB大小的未分配区域；

采用最坏适应分配算法，作业J4装入时，将70KB大小的空闲区进行划分，形成一个20KB大小的已分配区域（J4）和一个50KB大小的未分配区域； 将未分配表按照长度从大到小排序，则：

采用最先适应算法和最坏适应算法，作业J4装入时，将70KB大小的空闲区进行划分，形成一个20KB大小的已分配区域（J4）和一个50KB大小的未分配区域；

采用最佳适应分配算法，作业J4装入时，将40KB大小的空闲区进行划分，形成一个20KB大小的已分配区域（J4）和一个20KB大小的未分配区域；

38. 假设一个任务被划分成4个大小相等的段，每段有8项的页描述符表，若页面大小

一为2KB。试问段页式存储系统中：(a)每段最大尺寸是多少?(b)该任务的逻辑地址空间最大为多少?(c)若该任务访问到逻辑地址空间5ABCH中的一个数据，试给出逻辑地址的格式。

答：段数22 =4，每段有23=8页，页大小为211=2KB。

(a) 故每段最大为214B=16KB。

(b)逻辑地址空间最大4×16KB=64KB。

(c) 若该任务访问到逻辑地址空间5ABCH，其二进制表示为： 0101 1010 1011 1100

所以，逻辑地址表示为：01 011 ***********

5ABCH的逻辑地址为：第1段 第3页，位移由后11位给出。

45. 有两台计算机P1和P2，它们各有一个硬件高速缓冲存储器C1和C2，且各有一个主存储器M1和M2。其性能为：

C1 C2 M1 M2

存储容量 4KB 4KB 2MB 2MB 存取周期 60ns 80ns 1μs 0.9μs

若两台机器指令系统相同，它们的指令执行时间与存储器的平均存取周期成正比。如果在执行某个程序时，所需指令或数据在高速缓冲存储器中存取到的概率P是0.7，试问：这两台计算机哪个速度快？当P=0.9时，处理器的速度哪个快？

答：CPU平均存取时间为：T=p×T1+(1-p)×T2，T1为高速缓冲存储器存取周期，T2为主存储器存取周期，p为高速缓冲存储器命中率。 (1) 当p=0.7时，

P1平均存取时间为：0.7×60+(1-0.7)×1μs=342ns P2平均存取时间为：0.7×80+(1-0.7)×0.9μs=326ns

故计算机P2比P1处理速度快。

(2) 当p=0.9时，

P1平均存取时间为：0.9×60+(1-0.9)×1μs=154ns P2平均存取时间为：0.9×80+(1-0.9)×0.9μs=162ns

故计算机P1比P2处理速度快。