资源预览内容
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
第9页 / 共10页
第10页 / 共10页
亲,该文档总共10页全部预览完了,如果喜欢就下载吧!
资源描述
四、计算题1、某虚拟存储器的用户编程空间共32个页面,每页为1KB,内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下:页号 物理块号0 31 72 113 8则逻辑地址 0A5C(H)所对应的物理地址是什么?要求:写出主要计算过程。1解: 页式存储管理的逻辑地址分为两部分:页号和页内地址。由已知条件“ 用户编程空间共 32 个页面”,可知页号部分占 5 位;由“每页为 1KB”,1K=2 10,可知内页地址占 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)调度算法,页面调度过程如下:页面次序 1 2 3 4 1 2 5 1 2 3 4 51 1 1 4 4 4 5 5 52 2 2 1 1 1 3 3主存页面情况 3 3 3 2 2 2 4共产生缺页中断 9 次。依次淘汰的页是 1、2、3、4、1、2。采用最近最少使用(LRU)调度算法,页面调度过程如下:共产生缺页中断 10 次。依次淘汰的页是 1、2、3、4、5、1、2。3、下表给出了某系统中的空闲分区表,系统采用可变式分区存储管理策略。现有以下作业序列:96K、20K、200K。若用首次适应算法和最佳适应算法来处理这些作业序列,试问哪一种算法可以满足该作业序列的请求,为什么?空闲分区表页面次序 1 2 3 4 1 2 5 1 2 3 4 51 1 1 4 4 4 5 3 3 32 2 2 1 1 1 1 4 4主存页面情况 3 3 3 2 2 2 2 51234532K10K5K218K90K100K150K200K 220K530K分区号1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4大小1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4起始地址1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P43解:若采用最佳适应算法,在申请 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)123412K10K5K18K100K150K200K 220K分区号1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4大小1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4起始地址1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4 (b)1234512K10K5K122K96K100K150K200K 220K530K分区号1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4大小1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P4起始地址1 7 5 02 3 5 60 6 5 20 6 5 6P2P3P44、某采用段式存储管理的系统为装入主存的一个作业建立下表所示的段表段表段号 段长 主存起始地址0 660 22191 140 33002 100 903 580 12374 960 1959回答下列问题:(1)计算该作业访问0, 432, l, 10, 2, 500时(方括号中第一元素为段号,第二元素为段内地址)的绝对地址(2)总结段式存储管理的地址转换过程4答:(1)0,432 (432100 所以地址越界,产生中断)(2)总结段式存储管理的地址转换过程如下:从逻辑地址中取出段号和段内地址。根据段号,从段表中取出该段在主存中的始址和段长。比较段内地址和段长,如段内地址段长,则继续下一步,否则产生越界中段,程序中断(非法操作)。计算本段始址+段内地址,得到绝对地址。1.假设一个系统中有 5 个进程,它们的到达时间和服务时间如表 1 所示,忽略 I/0 以及其他开销时间,若分别按先来先服务(FCFS)、非抢占及抢占的短进程优先(SPF)、高响应比优先(HRRF)、时间片轮转(RR,时间片=1)调度算法进行 CPU 调度,请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。表 1 进程到达和需服务时间分析:进程调度的关键是理解和掌握调度所采用的算法。FCFS 算法选择最早进入就绪队列的进程投入执行;SPF 算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新就绪的进程运行时间比正在执行的进程的剩余运行时间短,则新进程将抢占 CPU;HRRF 算法选择响应比最高的进程投入执行;RR 算法中,就绪进程按 FIFO 方式排队,CPU 总是分配给队首的进程,并只能执行一个时间片。答:各进程的完成时间、周转时间和带权周转时间(如表 2 所示)表 2 进程的完成时间和周转时间进程 A B C D E 平 均FCFS完成时间周转时间带权周转时间331.00971.171392.2518122.4020126.008.62.56SPF(非抢占 ) 完成时间 3 9 15 20 11 进程 到达时间 服务时间A 0 3B 2 6C 4 4D 6 5E 8 2周转时间带权周转时间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.在银行家算法中,若出现下述资源分配情况:Allocation Need Available进 程A B C D A B C D A B C DP0P1P2P3P40 0 3 21 0 0 01 3 5 40 3 3 20 0 1 40 0 1 21 7 5 02 3 5 60 6 5 20 6 5 61 6 2 2试问:(1)该状态是否安全?(2)如果进程 P2 提出请求 Request(0,2,2,2后,系统能否将资源分配给它?解:(1)利用银行家算法对此时刻的资源分配情况进行分析,可得此时刻的安全性分析情况。Work Need Allocation Work+Allocation进 程A B C D A B C DA B C D A B C DFinishP0P3P4P1P21 6 2 21 6 5 41 9 8 61 9 9 102 9 9 100 0 1 20 6 5 20 6 5 61 7 5 02 3 5 60 0 3 20 3 3 20 0 1 41 0 0 01 3 5 41 6 5 41 9 8 61 9 9 102 9 9 103 12 14 14truetruetruetruetrue从上述分析中可以看出,此时存在一个安全序列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)试分配并修改相应数据结构,资源分配情况如下:Allocation Need Available进 程A B C D A B C D A B C DP0P1P2P3P40 0 3 21 0 0 02 5 7 60 3 3 20 0 1 40 0 1 21 7 5 01 1 3 40 6 5 20 6 5 60 4 0 0再利用安全性算法检查系统是否安全,可用资源 Available (0,4,0,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不能将资源分配给 P2。3 某请求分页系统,用户空间为 32KB,每个页面 1KB,主存 16KB。某用户程序有 7 页长,某时刻该用户进程的页表如下:页号 物理块号 是否在 TLB0 8 是1 7 是2 4 否3 10 否4 5 否5 3 是6 2 是(1)计算两个逻辑地址:0AC5H、1AC5H 对应的物理地址。(2)已知主存的一次存取为 1.5us,对于 TLB 表(快表)的查询时间可以忽略,则访问上述两个逻辑地址共耗费多少时间?答 (1 ) 每页 1kb 代表页内偏移量为低地址 10 位,剩余的为页号,所以 0AC5H 对应的页号为 2,物理块为 4,说以物理地址为 12C5H, 同理可得 1AC5H 对应的物理地址为0AC5H.(2)耗时为 11.5us+21.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、 某请求分页管理系统,假设进程的页表如下:页号 页框号 有效位 装入时间0 101H 1 21 0 2 254H 1 4页面大小为 4KB,一次内存的访问时间为 100 纳秒(ns),一次快表(TLB)的访问时间是 10ns,处理一次缺页的平均时间为
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号