操作系统习题及答案四

四、计算题1、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号031721138则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。1．解：页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。逻辑地址0A5C（H）所对应的二进制表示形式是：000101001011100，根据上面的分析，下划线部分为页内地址，编码“00010”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是11（十进制），即物理块地址为：1011，拼接块内地址1001011100，得10111001011100，即2E5C（H）。2、对于如下的页面访问序列：1，2，3，4，1，2，5，1，2，3，4，5当内存块数量为3时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？写出依次产生缺页中断后应淘汰的页。（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。要求写出计算步骤。）2．解：采用先进先出（FIFO）调度算法，页面调度过程如下：页面次序123412512345主存页面情况111444555222111333332224共产生缺页中断9次。依次淘汰的页是1、2、3、4、1、2。采用最近最少使用（LRU）调度算法，页面调度过程如下：共产生缺页中断10次。依次淘汰的页是1、2、3、4、5、1、2。3、下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么?空闲分区表页面次序123412512345主存页面情况1114445333222111144333222253．解：若采用最佳适应算法，在申请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)(b)4、某采用段式存储管理的系统为装入主存的一个作业建立下表所示的段表．段表段号段长主存起始地址06602219114033002100903580123749601959回答下列问题：1234512K10K5K122K96K100K150K200K220K530K分区号1750235606520656P2P3P4大小1750235606520656P2P3P4起始地址1750235606520656P2P3P4123412K10K5K18K100K150K200K220K分区号1750235606520656P2P3P4大小1750235606520656P2P3P4起始地址1750235606520656P2P3P41234532K10K5K218K90K100K150K200K220K530K分区号1750235606520656P2P3P4大小1750235606520656P2P3P4起始地址1750235606520656P2P3P4（1）计算该作业访问[0,432],[l,10],[2,500]时（方括号中第一元素为段号，第二元素为段内地址）的绝对地址．（2）总结段式存储管理的地址转换过程．4．答：(1)[0,432]→(432660)2219+432=2651[1，10]→(10140)3300+10=3310[2，500]→(因500100所以地址越界，产生中断)(2)总结段式存储管理的地址转换过程如下：①从逻辑地址中取出段号和段内地址。②根据段号，从段表中取出该段在主存中的始址和段长。③比较段内地址和段长，如段内地址≤段长，则继续下一步，否则产生越界中段，程序中断(非法操作)。④计算本段始址+段内地址，得到绝对地址。1.假设一个系统中有5个进程,它们的到达时间和服务时间如表1所示,忽略I/0以及其他开销时间,若分别按先来先服务(FCFS)、非抢占及抢占的短进程优先（SPF）、高响应比优先(HRRF)、时间片轮转(RR,时间片=1)调度算法进行CPU调度,请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。表1进程到达和需服务时间分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS算法选择最早进入就绪队列的进程投入执行;SPF算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新就绪的进程运行时间比正在执行的进程的剩余运行时间短,则新进程将抢占CPU;HRRF算法选择响应比最高的进程投入执行;RR算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间片。答：各进程的完成时间、周转时间和带权周转时间(如表2所示)表2进程的完成时间和周转时间进程ABCDE平均FCFS完成时间周转时间带权周转时间331.00971.171392.2518122.4020126.008.62.56SPF(非抢占)完成时间39152011进程到达时间服务时间A03B26C44D65E82周转时间带权周转时间31.0071.17112.75142.8031.57.61.84SPF(抢占)完成时间周转时间带权周转时间331.0015132.16841.0020142.801021.007.21.59HRRF完成时间周转时间带权周转时间331.00971.171392.2520142.801573.582.14RR(q=1)完成时间周转时间带权周转时间441.3318162.6717133.2520142.81573.510.82.713.在银行家算法中，若出现下述资源分配情况：进程AllocationNeedAvailableABCDABCDABCDP0P1P2P3P400321000135403320014001217502356065206561622试问:（1)该状态是否安全?(2)如果进程P2提出请求Request（0,2,2,2〉后,系统能否将资源分配给它?解:(1)利用银行家算法对此时刻的资源分配情况进行分析,可得此时刻的安全性分析情况。进程WorkNeedAllocationWork+AllocationFinishABCDABCDABCDABCDP0P3P4P1P2162216541986199102991000120652065617502356003203320014100013541654198619910299103121414truetruetruetruetrue从上述分析中可以看出，此时存在一个安全序列{P0,P3,P4,P1,P2},故该状态是安全的。（2）P2提出请求Request2(1,2,2,2),按银行家算法进行检查：Request2(1,2,2,2)≤Need2(2,3,5,6)Request2(1,2,2,2)≤Available(1,6,2,2)试分配并修改相应数据结构，资源分配情况如下：进程AllocationNeedAvailableABCDABCDABCDP0P1P2P3P400321000257603320014001217501134065206560400再利用安全性算法检查系统是否安全,可用资源Available(0,4,0,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能将资源分配给P2。3某请求分页系统，用户空间为32KB，每个页面1KB，主存16KB。某用户程序有7页长，某时刻该用户进程的页表如下：页号物理块号是否在TLB08是17是24否310否45否53是62是（1）计算两个逻辑地址：0AC5H、1AC5H对应的物理地址。（2）已知主存的一次存取为1.5us，对于TLB表（快表）的查询时间可以忽略，则访问上述两个逻辑地址共耗费多少时间？答（1）每页1kb代表页内偏移量为低地址10位，剩余的为页号，所以0AC5H对应的页号为2，物理块为4，说以物理地址为12C5H,同理可得1AC5H对应的物理地址为0AC5H.（2）耗时为1×1.5us+2×1.5us=4.5us4什么叫重定位？它有哪两种方式？这两种方式有什么区别？由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改(变换)，则程序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。5在具有快表的段页式存储管理方式中，如何实现地址变换？答：物理地址=该段在主存的起始地址+页框号*大小+页内地址。第二次作业：1、在某请求分页管理系统中，一个作业共5页，作业执行时一次访问如下页面：1，4，3，1，2，5，1，4，2，1，4，5，若分配给该作业的主存块数为3，分别采用FIFO，LRU，Clock页面置换算法，试求出缺页中断的次数及缺页率。答FIFO缺页次数为9，缺页率为3/4LRU缺页数为9，缺页率为3/4Clock缺页数为9，缺页率为3/42、某请求分页管理系统，假设进程的页表如下：页号页框号有效位装入时间0101H121—0—2254H14页面大小为4KB，一次内存的访问时间为100纳秒（ns），一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为100毫秒（已含更新TLB和页表的时间），进程的驻留集大小固定为2个页框，采用FIFO法置换页面。假设1）TLB初始为空；2）地址转换时，先访问TLB，若TLB未命中时再访问页表（忽略TLB更新时间）；3）有效位为0表示页面不在内存中。请问：（1）该系统中，一次访存的时间下限和上限各是多少？（给出计算过程）（2）若已经先后访问过0、2号页面，则虚地址1565H的物理地址是多少？（给出计算过程）答（1）一次访存时间下限10ns+100ns+100ns，上限10ns+100ns+100ms+100ns（2）基于上述访问序列，当访问虚地址1565H时产生缺页中断，合法驻留集为2，必须从表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H3、设某计算机的逻辑地址空间和物理地址空间均为128KB，按字节编址。若某进程最多需要6页数据存储空间，页面大小为1KB，操作系统采用固定分配局部置换策略为该进程分配4个页框（物理块）。在时刻300前该进程各页面的访问情况如下表所示：页号页框号（块号）装入时间访问位071301142301222001391801当进程执行到时刻300时，要访问逻辑地址为17CAH的数据，请回答下列问题：（1）该逻辑地址对应的页号是多少？（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（3）若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。设搜索下一页的指针顺时针方向移动，且当前指向2号页框，示意图如下：9号页框2号页框4号页框7号页框2号页3号页0号页1号页17CAH=(0001011111001010)2（1）页大小为1K，则页内偏移地址为10位，前6位是页号，所以逻辑地址对应的页号为：5（2）FIFO：被置换的页面所在页框为7，所以对应的物理地址为（000111111100101