操作系统习题及答案四
_四、计算题1、某虚拟存储器的用户编程空间共 32个页面， 每页为 1KB，内存为 16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号031721138则逻辑地址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）调度算法，页面调度过程如下：页面次序123412512345主存111444555页面22211133情况3332224共产生缺页中断9 次。依次淘汰的页是1、 2、 3、 4、1、 2。采用最近最少使用（LRU）调度算法，页面调度过程如下：页面次序123412512345主存1114445333页面222111144情况33322225共产生缺页中断10 次。依次淘汰的页是1、2、 3、 4、 5、 1、 2。3、下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列： 96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么?空闲分区表精品资料_分区号大小起始地址132K100K210K150K35K200K4218K220K590K530K3解：若采用最佳适应算法，在申请96K 存储区时，选中的是5 号分区， 5 号分区大小与申请空间大d,- 致，应从空闲分区表中删去该表项；接着申请20K 时，选中 1 号分区，分配后 1 号分区还剩下12K；最后申请200K，选中 4 号分区，分配后剩下18K。显然采用最佳适应算法进行内存分配，可以满足该作业序列的需求。为作业序列分配了内存空间后，空闲分区表如表5-3(a) 所示。若采用首次适应算法，在申请96K 存储区时，选中的是4 号分区，进行分配后4 号分区还剩下 122K；接着申请 20K，选中 1 号分区，分配后剩下 12K；最后申请 200K，现有的五个分区都无法满足要求，该作业等待。显然采用首次适应算法进行内存分配，无法满足该作业序列的需求。这时的空闲分区表如表53(b) 所示。分配后的空闲分区表(a)分区号大小起始地址112K100K210K150K35K200K418K220K(b)分区号大小起始地址112K100K210K150K35K200K4122K220K596K530K4、某采用段式存储管理的系统为装入主存的一个作业建立下表所示的段表段表段号段长主存起始地址06602219114033002100903580123749601959回答下列问题：精品资料_（ 1）计算该作业访问 0, 432, l, 10, 2, 500时（方括号中第一元素为段号，第二元素为段内地址）的绝对地址（ 2）总结段式存储管理的地址转换过程4答：(1)0,432 (432<660)2219+432=26511， 10 (10<140)3300+10=33102， 500 ( 因 500>100 所以地址越界，产生中断)(2) 总结段式存储管理的地址转换过程如下：从逻辑地址中取出段号和段内地址。根据段号，从段表中取出该段在主存中的始址和段长。比较段内地址和段长，如段内地址段长，则继续下一步， 否则产生越界中段， 程序中断 ( 非法操作 ) 。计算本段始址+段内地址，得到绝对地址。1. 假设一个系统中有 5 个进程 , 它们的到达时间和服务时间如表 1 所示 , 忽略 I/0 以及其他开销时间 , 若分别按先来先服务 (FCFS) 、非抢占及抢占的短进程优先（ SPF）、高响应比优先(HRRF)、时间片轮转 (RR, 时间片 =1) 调度算法进行CPU调度 , 请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。表 1 进程到达和需服务时间进程到达时间 服务时间A03B26C44D65E82分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS算法选择最早进入就绪队列的进程投入执行 ;SPF 算法选择估计运行时间最短的进程投入执行, 采用抢占方式时 , 若新就绪的进程运行时间比正在执行的进程的剩余运行时间短, 则新进程将抢占 CPU;HRRF算法选择响应比最高的进程投入执行;RR算法中 , 就绪进程按 FIFO 方式排队 ,CPU总是分配给队首的进程 , 并只能执行一个时间片。答：各进程的完成时间、周转时间和带权周转时间( 如表 2 所示 )表 2 进程的完成时间和周转时间进程ABCDE平 均完成时间39131820FCFS周转时间37912128.6带权周转时间1.001.172.252.406.002.56SPF(非抢占 )完成时间39152011精品资料_周转时间37111437.6带权周转时间1.001.172.752.801.51.84完成时间31582010SPF(抢占 )周转时间31341427.2带权周转时间1.002.161.002.801.001.59完成时间39132015HRRF周转时间3791478带权周转时间1.001.172.252.803.52.14完成时间418172015RR(q=1)周转时间4161314710.8带权周转时间1.332.673.252.83.52.713. 在银行家算法中，若出现下述资源分配情况：AllocatioNeedAvailablen进 程A B C DA B C DA B C DP0003200121622P110001750P213542356P303320652P400140656试问 : （ 1) 该状态是否安全 ?(2) 如果进程P2 提出请求 Request （ 0,2,2,2后 , 系统能否将资源分配给它 ?解:(1)利用银行家算法对此时刻的资源分配情况进行分析, 可得此时刻的安全性分析情况。进 程WorkNeedAllocationWork+AllocationFinisA B C DA B C D A B C DA B C Dh
