四、计算题

1、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

页号 0 1 2 3 物理块号 3 7 11 8 则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。

1．解： 页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件“用户编程空

间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。

逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的分析，下划线部分为页内地址，编码 “000 10” 为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是11（十进制），即物理块地址为：10 11，拼接块内地址10 0101 1100，得10 1110 0101 1100，即2E5C（H）。 2、对于如下的页面访问序列：

1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5

当内存块数量为3时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？写出依次产生缺页中断后应淘汰的页。（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。要求写出计算步骤。）

2．解：

采用先进先出（FIFO）调度算法，页面调度过程如下：

2 3 4 1 2 5 1 2 3 4 5 页面次序 1

主存

页面 情况

1 1 2 1 2 3 4 2 3 4 1 3 4 1 2 5 1 2 5 3 2 5 3 4 共产生缺页中断9次。依次淘汰的页是1、2、3、4、1、2。

采用最近最少使用（LRU）调度算法，页面调度过程如下： 页面次序 主存 页面 情况

1 1 2 1 2 3 1 2 3 4 4 2 3 1 4 1 3 2 4 1 2 5 5 1 2 1 2 3 3 1 2 4 3 4 2 5 3 4 5 共产生缺页中断10次。依次淘汰的页是1、2、3、4、5、1、2。 3、下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么?

空闲分区表

分区号 1 2 3 4 5

大小 32K 10K 5K 218K 90K

起始地址 100K 150K 200K 220K 530K

3．解：若采用最佳适应算法，在申请96K存储区时，选中的是5号分区，5号分区大小 与申请空间大d,-致，应从空闲分区表中删去该表项；接着申请20K时，选中1号分区，分配后1号分区还剩下12K；最后申请200K，选中4号分区，分配后剩下18K。显然采用最佳适应算法进行内存分配，可以满足该作业序列的需求。为作业序列分配了内存空间后，空闲分区表如表5-3(a)所示。

若采用首次适应算法，在申请96K存储区时，选中的是4号分区，进行分配后4号分 区还剩下122K；接着申请20K，选中1号分区，分配后剩下12K；最后申请200K，现有 的五个分区都无法满足要求，该作业等待。显然采用首次适应算法进行内存分配，无法满 足该作业序列的需求。这时的空闲分区表如表5．3(b)所示。

分配后的空闲分区表

(a)

分区号 1 2 3 4

大小 12K 10K 5K 18K

(b)

分区号 1 2 3 4 5

大小 12K 10K 5K 122K 96K

起始地址 100K 150K 200K 220K 530K

4、某采用段式存储管理的系统为装入主存的一个作业建立下表所示的段表．

段表 段号 0 1 2 3 4 回答下列问题：

660 140 100 580 960 段长 2219 3300 90 1237 1959 主存起始地址 起始地址 100K 150K 200K 220K

（1）计算该作业访问[0, 432], [l, 10], [2, 500]时（方括号中第一元素为段号，第二元素为段内地址）的绝对地址．

（2）总结段式存储管理的地址转换过程． 4．答：

(1)[0,432]→ (432<660)2219+432=2651 [1，10] →(10<140)3300+10=3310

[2，500]→(因500>100所以地址越界，产生中断) (2)总结段式存储管理的地址转换过程如下： ①从逻辑地址中取出段号和段内地址。

②根据段号，从段表中取出该段在主存中的始址和段长。

③比较段内地址和段长，如段内地址≤段长，则继续下一步，否则产生越界中段，程序中断(非法操作)。

④计算本段始址+段内地址，得到绝对地址。

1.假设一个系统中有5个进程,它们的到达时间和服务时间如表1所示,忽略I/0以及其他开销时间,若分别按先来先服务(FCFS)、非抢占及抢占的短进程优先（SPF）、高响应比优先(HRRF)、时间片轮转(RR,时间片=1)调度算法进行CPU调度,请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。 表1进程到达和需服务时间

进程 A B C D E 到达时间 服务时间 0 2 4 6 8 3 6 4 5 2 分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS算法选择最早进入就绪队列的进程投入执行;SPF算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新就绪的进程运行时间比正在执行的进程的剩余运行时间短,则新进程将抢占CPU;HRRF算法选择响应比最高的进程投入执行;RR算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间片。 答：各进程的完成时间、周转时间和带权周转时间(如表2所示) 表2进程的完成时间和周转时间 FCFS 进程 完成时间 周转时间 A 3 3 B 9 7 C D E 平 均 13 18 20 9 12 12 8.6 带权周转时间 1.00 1.17 2.25 2.40 6.00 2.56 3 9 15 20 11 SPF(非抢占) 完成时间 周转时间 3 7 11 14 3 7.6 带权周转时间 1.00 1.17 2.75 2.80 1.5 1.84 完成时间 SPF(抢占) 周转时间 3 3 15 13 8 4 20 10 14 2 7.2 带权周转时间 1.00 2.16 1.00 2.80 1.00 1.59 HRRF RR(q=1) 完成时间 周转时间 3 3 9 7 13 20 15 9 14 7 8 带权周转时间 1.00 1.17 2.25 2.80 3.5 2.14 完成时间 周转时间 4 4 18 17 20 15 16 13 14 7 10.8 带权周转时间 1.33 2.67 3.25 2.8 3.5 2.71 3.在银行家算法中，若出现下述资源分配情况： 进 程 A B C D A B C D A B C D P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 Allocation Need Available 试问:（1)该状态是否安全? (2)如果进程P2提出请求Request（0,2,2,2〉后,系统能否将资源分配给它? 解:(1)利用银行家算法对此时刻的资源分配情况进行分析,可得此时刻的安全性分析情况。 进 程 Allocation Work+Allocation Finish A B C D A B C D A B C D A B C D 1 6 5 4 1 9 8 6 1 9 9 10 2 9 9 10 3 12 14 14 true true true true true Work Need P0 1 6 2 2 0 0 1 2 0 0 3 2 P3 P4 1 6 5 4 0 6 5 2 0 3 3 2 1 9 8 6 0 6 5 6 0 0 1 4 P1 1 9 9 10 1 7 5 0 1 0 0 0 P2 2 9 9 10 2 3 5 6 1 3 5 4 从上述分析中可以看出，此时存在一个安全序列{P0,P3,P4,P1,P2},故该状态是安全的。