四、计算题1某虚拟存储器的用户编程空间共32个页面，每页为1KB,内存为16KBo假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：则逻辑地址0A5C（H）所对应的物理地址是什么？要求：写出主要计算过程。
1. 解：页式存储管理的逻辑地址分为两部分：页号和页内地址。
由已知条件用户编程空间共32个页面”可知页号部分占5位；由每页为1KB” 1K=210,可知内页地址占10位。
由内存为16KB'，可知有16块，块号为4位。
逻辑地址0A5C（ H）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的分析，下划线部分为页内地址，编码000 10 ”为页号，表示该逻辑地址对应的页号为2o查页表，得到物理块号是11（十进制），即物理块地址为：10 11,拼接块内地址10 0101 1100, 得10 1110 0101 1100 ，即2E5C（ H）o2、对于如下的页面访问序列：1, 2 , 3 , 4 , 1 , 2 , 5 , 1 , 2 , 3 , 4 , 5当内存块数量为3时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？写出依次产生缺页中断后应淘汰的页。
（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。
要求写出计算步骤。
）2. 解：采用先进先出（FIFO ）调度算法，页面调度过程如下：共产生缺页中断9次。
依次淘汰的页是1、2、3、4、1、2共产生缺页中断10次。
依次淘汰的页是1、2、3、4、5、1、2o3、下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。
现有以下作业序列：96K、20K、200K o若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？空闲分区表分区号大小起始地址132K100K210K150K35K200K4218K220K590K530K3•解：若采用最佳适应算法，在申请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)分区号大小起始地址112K100K210K150K35K200K418K220K(b)分区号大小起始地址112K100K210K150K35K200K4122K220K596K530K4回答下列问题:(1)计算该作业访问[0, 432], [I, 10], [2, 500] 为段号，第时（方括号中第一兀素二元素为段内地址）的绝对地址.（2）总结段式存储管理的地址转换过程.4•答:（1）[0,432] T（432<660）2219+432=2651[1 , 10] T（10<140）3300+10=3310[2 , 500] T（因500>100所以地址越界，产生中断）（2）总结段式存储管理的地址转换过程如下：①从逻辑地址中取出段号和段内地址。
②根据段号，从段表中取出该段在主存中的始址和段长。
③比较段内地址和段长，如段内地址w段长，则继续下一步，否则产生越界中段，程序中断（非法操作）。
④计算本段始址+段内地址，得到绝对地址。
1. 假设一个系统中有5个进程，它们的到达时间和服务时间如表1所示,忽略I/0以及其他开销时间，若分别按先来先服务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRF）、时间片轮转（RR,时间片=1）调度算法进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。
表1进程到达和需服务时间分析：进程调度的关键是理解和掌握调度所采用的算法。
FCFS算法选择最早进入就绪队列的进程投入执行;SPF算法选择估计运行时间最短的进程投入执行，采用抢占方式时，若新就绪的进程运行时间比正在执行的进程的剩余运行时间短，则新进程将抢占CPU;HRRF算法选择响应比最高的进程投入执行;RR算法中，就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间片。
答：各进程的完成时间、周转时间和带权周转时间（如表2 所示）表23. 在银行家算法中，若出现下述资源分配情况:3某请求分页系统，用户空间为32KB,每个页面1KB,主存16KB某用户程序有7页长，某时刻该用户进程的页表如下：(1)计算两个逻辑地址：0AC5H 1AC5H寸应的物理地址。
(2)已知主存的一次存取为1.5US，对于TLB表(快表)的查询时间可以忽略，则访问上述两个逻辑地址共耗费多少时间？答(1)每页1kb代表页内偏移量为低地址10位，剩余的为页号，所以0AC5H对应的页号为2，物理块为4,说以物理地址为12C5H, 同理可得1AC5H对应的物理地址为0AC5H.(2)耗时为1 X 1.5us+2 X 1.5us=4.5us4什么叫重定位？它有哪两种方式？这两种方式有什么区别？由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改（变换），则程序必将无法执行。
为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。
5在具有快表的段页式存储管理方式中，如何实现地址变换？答：物理地址=该段在主存的起始地址+页框号*大小+页内地址。
第二次作业：1、在某请求分页管理系统中，一个作业共5页，作业执行时一次访问如下页面：1，4，3,1，2，5，1，4，2，1，4，5，若分配给该作业的主存块数为3，分别采用FIFO, LRUClock页面置换算法，试求出缺页中断的次数及缺页率。
答FIFO 缺页次数为9,缺页率为3/4LRU缺页数为9,缺页率为3/4Clock缺页数为9，缺页率为3/42、某请求分页管理系统，假设进程的页表如下：页面大小为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前该进程各页面的访问情况如下表所示：当进程执行到时刻 300时，要访问逻辑地址为 17CAH 的数据，请回答下列问题: (1)该逻辑地址对应的页号是多少？(2)若采用先进先出(FIFO )置换算法，该逻辑地址对应的物理地址是多少？要求给出计 算过程。
(3)若采用时钟(CLOCK 置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。
设搜索下一页的指针顺时针方向移动，且当前指向2号页框，示意图如下:17CAH=(0001 0111 1100 1010)2(1 )页大小为1K ,则页内偏移地址为5(2) FIFO :被置换的页面所在页框为2=1FCAH(3) CLOC K 被置换的页面所在页框为2=0BCAH并有一下请求序列等待访问磁盘： 请求序列： 1, 2, 3, 4, 5, 6 , 7, 8, 9预访问柱面号：150, 50 , 178, 167 , 87, 43 , 23 , 160 , 85试用最短寻找时间优先算法和电梯调度算法，分别排出实际处理上述请求的次序 第一题：序列(柱面号)_ 最短寻找时间优先算法9(85)、5(87)、2(50)、6(43)、7(23)、1(150)、8(160)、4(167)、3(178) 电梯调度算法 9(85)、5(87)、1(150)、8(160)、4(167)、3(178)、2(50)、6(43)、7(23)第二题：磁盘有199个磁道，当前磁头在 54#磁道上，并向磁道号减小的方向上移动，现有一下请求序列等待访问磁盘： 请求序列 12 3 4 5 6 7 8带访问的柱面号 99 184 38 123 15 125 66 68 试用最短寻找时间优先算法和电梯调度算法， 分别排出实际处理上述请求的次序，并计算出他们的平均寻道长度 第二题：序列(柱面号) 最短寻找时间优先算法7(66) 8(68) 3(38) 5(15) 1(99) 4(123) 6(125) 2(184)12+2+30+23+84+24+2+59=236平均寻道长度236/8=29.5 电梯调度算法3(38) 5(15) 7(66) 8(68) 1(99) 4(123) 6(125) 2(184)10位，前6位是页号，所以逻辑地址对应的页号为： 7,所以对应的物理地址为( 0001 1111 1100 1010) 2,所以对应的物理地址为(0000 1011 1100 1010)16+23+51+2+31+24+2+59=208平均寻道长度208/8=26四、计算题1、假定在单CPU条件下有下列要执行的作业：作业到来的时间是按作业编号顺序进行的(即后面作业依次比前一个作业迟到一个时间单位)。
(1)用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。
(2)对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？(3)对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少？1 •解：(1) 非抢占式优先级算法(3分)作业1 作业3 作业2I ----------------------- 1 ------ 1 -------- 1 ------ 1 ------------------------------------------------------10 10 13 17(2) 和(3)2、若后备作业队列中等待运行的同时有三个作业J1、J2、J3，已知它们各自的运行时间为a、b、c,且满足a<b<a,试证明采用短作业优先算法调度能获得最小平均作业周转时间。