青岛理工大学操作系统4练习题.doc

操作系统常见题解析及模拟题内容【例2】对一个将页表存放在内存中的分页系统:（1）如访问内存需要02s，有效访问时间为多少?（2）如果加一快表，且假定在快表中找到页表项的机率高达90，则有效访问时间又是多少(假定查快表需花的时间为0)?答：（1）有效访问时间为：202=04s（2）有效访问时间为：0902+(109)202022 ps。【例3】某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K，拥有物理空间1M。（1）写出逻辑地址的格式。（2）若不考虑访问权限等，进程的页表有多少项?每项至少有多少位?（3）如果物理空间减少一半，页表结构应相应作怎样的改变?答：（1）该系统拥有逻辑空间32页，故逻辑地址中页号必须用5位来描述：而每页为2K，因此，页内地址必须用11位来描述，这样可得到它的逻辑地址格式如下：1511100页号页内地址 (2)每个进程最多有32个页面，因此，进程的页表项最多为32项；若不考虑访问权限等，则页表项中只需给出页所对应的物理块块号，1M的物理空间可分成29个内存块，故每个页表项至少有9位 (3)如果物理空间减少一半，则页表中页表项数仍不变，但每项的长度可减少1位。【例4】已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、l、2、3页分别被分配到主存的2、4、6、7块中。 (1)将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。 (2)以十进制的逻辑地址1023为例画出地址变换过程图。 答：(1)对上述逻辑地址，可先计算出它们的页号和页内地址(逻辑地址除以页面大小，得到的商为页号，余数为页内地址)，然后通过页表转换成对应的物理地址。 逻辑地址1023：10231K，得到页号为0，页内地址为1023，查页表找到对应的物理块号为2，故物理地址为21K+1023=3071。 逻辑地址2500：25001K，得到页号为2，页内地址为452，查页表找到对应的物理块号为6，故物理地址为6IK+452=6596。 逻辑地址3500：3500IK，得到页号为3，页内地址为428，查页表找到对应的物理块号为7，故物理地址为71K+428=7596。 逻辑地址4500：45001K，得到页号为4，页内地址为404，因页号不小于页表长度，故产生越界中断。 (2)逻辑地址1023的地址变换过程如下图所示，其中的页表项中没考虑每页的访问权限。【例5】已知某系统页面长4KB，页表项4字节，采用多层分页策略映射64位虚拟地址空间。若限定最高层页表占1页，问它可以采用几层分页策略。（浙江大学2000年考题）答：由题意，64位虚拟地址的虚拟空间大小为264.页面长为4KB,页表项4字节，所以一个页面可存放1K个表项。由于最高层页表占1页，也就是说其页表项个数最多为1K个，每一项对应一页，每页又可存放1K个页表项，依次类推可知，采用的分页层数为：6层。【例6】对于下表所示的段表，请将逻辑地址(0，137)，(1，4000)，(2，3600)，(5，230)转换成物理地址。段号内存始址段长O50K10Kl60K3K270K5K3120K8K4150K4K段表 答：(1)段号0小于段表长5，故段号合法；由段表的第0项可获得段的内存始址为50K，段长为10K；由于段内地址137，小于段长10K，故段内地址也是合法的，因此可得出对应的物理地址为50K+137=5l337。(2)段号l小于段表长，故段号合法；由段表的第l项可获得段的内存始址为60K，段长为3K：经检查，段内地址4000超过段长3K，因此产生越界中断。(3)段号2小于段表长，故段号合法；由段表的第2项可获得段的内存始址为70K，段长为5K；故段内地址3600也合法。因此，可得出对应的物理地址为70K+3600=75280。(4)段号5等于段表长，故段号不合法，产生越界中断。【例7】在一个请求分页系统中，假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，目前它还没有任何页装入内存，当分配给该作业的物理块数目M为3时，请分别计算采用OPT、LRU和FIFO页面淘汰算法时访问过程中所发生的缺页次数和缺页率。答：(1)使用FIFO算法时，访问过程中发生缺页的情况为：当物理块数目M为3时，缺页次数为9，缺页率为912(如下表所示)。432143543215444111555555333444442222223333311(2)使用OPT算法时，访问过程中发生缺页的情况为：当物理块数目M为3时，缺页次数为7，缺页率为712(如下表所示)。432143543215444444444444333333332112111555555（3）使用LRU算法时，访问过程中发生缺页的情况为：当物理块数目M为3时，缺页次数为lO，缺页率为1012(如下表所示)。432143543215444111555222333444444112223333335【例8】某页式虚拟存储管理系统的物理空间共3K，页面大小为1K，一进程按下列地址顺序引用内存单元：3635，3632，1140，3584，2892，3640，0040，2148，1700，2145，3209，0000，1102，1100。如果上述数字均为十进制数，而内存中尚未装入任何页。给出使用LRU算法时的缺页次数，并与FIFO时的情况进行比较。 答：根据题意，分配给作业的内存块数为3，而页面的引用次序为：3、3、1、3、2、3、O、2、l、2、3、O、l、1。因此，可以计算出，采用LRU算法时，缺页次数为8，采用FIFO算法时，缺页次数为6。LRU算法用最近的过去来作为预测最近的将来的依据，一般认为其有较好的性能，但实现时，要记录最近在内存的每个页面的使用情况，比FIFO困难，其开销也大。有时，因页面的过去和未来的走向之间并无必然的联系，如上面，LRU算法的性能就没有想象中的那么好。【例9】某虚拟存储器的用户空间共有32个页面，每页1K，主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7，而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C、103C、1A5C转换成物理地址。 答：由题目所给条件可知，该系统的逻辑地址有15位，其中高5位为页号，低10位为页内 地址；物理地址有14位，其中高4位为页帧号，低10位为页帧内地址。另外，由于题目中给出的逻辑地址是十六进制数，故可先将其转换成二进制数以直接获得页号和页内地址，再完成地址的转换如右图所示，逻辑地址(0A5C)16的页号为(00010)2，即2，故页号合法；从页表中找到对应的内存块号为4，即(0100)2与页内地址 (10 0101 1100)2拼接形成物理地址(010010 0101 1100)2即(125C)16。(2)逻辑地址(103C)16的页号为4，页号合法，但该页未装入内存，故产生缺页中断。(3)逻辑地址(1A5C)16的页号为6，为非法页号，故产生越界中断。【例10】现有一请求调页系统，页表保存在寄存器中。若有一个被替换的页未被修改过，则处理一个缺页中断需要8 ms；若被替换的页已被修改过，则处理一个缺页中断需要20 ms。内存存取时间为ls，访问页表的时间可忽略不计。假定70被替换的页被修改过，为保证有效存取时间不超过2s，可接受的最大缺页率是多少? 答：如果用p表示缺页率，则有效存取时间不超过2 us可表示为：(1-p)1s+p(0720 ms+038 ms+ls)2s因此可计算出： p1/164000.00006 即可接受的最大缺页率为000006。【例10】假如一个程序的段表如下表所示，其中合法位为1表示段在内存，存取控制字段中w表示可写，R表示可读，E表示可执行。对下面的指令，在执行时会产生什么样的结果?段号合法位内存始址段长保护码其他信息O0500100Wl1100030R213000200E31800080R40500040R(1)STORE R1，0，70(2)STORE R1, 1，20(3)LOAD R1, 3，20(4)LOAD R1, 3，100(5)JMP 2，100答：(1)指令STORE R1，O，70。从段表的第0项可读出第0段的合法位为0，表示相应段未装入内存，因此地址变换机构将产生一缺段中断，以请求OS将其调入内存。(2)指令STORE Rl，1，20。从段表的第1项可以看出，虽然指令中的逻辑地址合法，段也已在内存，但本指令对内存的访问方式(写)与保护码字段(只读)不符，故硬件将产生保护性中断信号。(3) LOAD R1, 3，20。从段表的第3项可读出第3段的合法位为1，内存始址为8000，段长为80，存取控制为R，因此，逻辑地址合法，访问方式也合法，形成物理地址8020后，指令将把该单元的内容读到寄存器R1中。(4)指令LOAD R1, 3，100。从段表的的第3项可读出第3段的合法位为l，内存始址为8000，段长为80，存取控制为R，因此，指令的逻辑地址中段内地址超过了段长，地址变换机构将产生越界中断信号。(5)指令JMP 2，100。从段表的第2项可读出第2段的合法位为1，内存始址为3000，段长为200，访问权限为E，因此逻辑地址与访问方式都合法，形成物理地址3100，指令执行后，将跳转到内存单元3100处继续执行。4.2 练习题及答案一、单项选择题1位示图法可用于（）。A.页式虚拟存储管理中页面置换B.可变式分区存储管理中空闲区的分配和回收C.分页式存储管理中主存空闲块的分配和回收D.文件目录的查找2下列（）存储方式不能实现虚拟存储器。A.分区B.页式 C.段式D.段页式3操作系统处理缺页中断时，选择一种好的调度算法对主存和辅存中的信息进行高效调度尽可能地避免（）。A.碎片B.CPU空闲C.多重中断D.抖动4可变分区存储管理系统中，若采用最佳适应分配算法，“空闲区表”中的空闲区可按（）顺序排列。A.长度递增B.长度递减C.地址递增D.地址递减5分页式存储管理的主要特点是（）。A.要求处理缺页中断B.要求扩充主存容量C.不要求作业装入到主存的连续区域D.不要求作业全部同时装人主存6LRU页面调度算法淘汰（）的页。A.最近最少使用 B.最近最久未使用C.最先进入主存 D.将来最久使用7虚拟存储技术是（）。A.扩充主存物理空间技术B.扩充主存逻辑地址空间技术C.扩充外存空间的技术D.扩充输入/输出缓冲区技术8虚拟存储器实际容量受（）限制。A.物理主存的大小B.计算机的地址结构C.磁盘容量D.数据存放的绝对地址9分区分配内存管理方式的主要保护措施是（）。A.界地址保护 B.程序代码保护 C.数据保护 D.栈保护 10页面置换算法中（）不是基于程序执行的局部性理论。A.先进先出调度算法B.LRU C.LFUD.最近最不常用调度算法11在存储管理中，采用覆盖与交换技术的目的是（）。A.节省主存空间 B.物理上扩充主存容量C.提高CPU的效率 D.实现主存共享12分页虚拟存储管理中，缺页中断时，欲调度一页进入主存中，内存己无空闲块，如何决定淘汰已在主存的块时，（）的选择是很重要的。A.地址变换 B.页面置换算法C.对换方式 D.覆盖技术13动态重定位技术依赖于（）。A.重定位装入程序 B.重定位寄存器C.地址结构 D.目标程序14很好地解决了“零头”问题的存储管理方法是（）。A.分页存储管理方式 B.分段存储管理方式C.多重分区管理 D.可变式分区管理15某基于动态分区存储管理的计算机，其主存容量为55mb（初试为空间），采用最佳适配（Best fit）算法，分配和释放的顺序为：分配15mb，分配30mb，释放15mb，分配8mb，此时主存中最大空闲分区的大小是（ ）A.7mbB.9mbC.10mbD.15mb16系统“抖动”现象的发生是由（）引起的。A.交换的信息量过大 B.置换算法选择不当C.内存容量不足 D.请求分页管理方案17在可变分区存储管理中，某作业完成后要收回其主存空间，该空间可能与相邻空闲区合并，修改空闲区表使空闲区始址改变但空闲区数不变的是（）情况。A.有上邻空闲区也有下邻空闲区B.有上邻空闲区但无下邻空闲区C.无上邻空闲区但有下邻空闲区D.无上邻空闲区且也无下邻空闲区18可变分区管理中，首次适应分配算法可将空闲区表中的空闲区栏目按（）顺序排列。A.地址递增 B.长度递增C.地址递减 D.长度递减19一个分段存储管理系统中，地址长度为32位，其中段号占8位，则段长最大（）。A.2的8次方字节B.2的16次方字节 C.2的24次方字节D.2的32次方字节20存储管理主要管理的是（ ）。A.外存存储器用户区 B.外存存储器系统区C.主存储器用户区 D.主存储器系统区21虚拟存储管理系统的基础是程序的（）理论。A.全局性B.虚拟性C.局部性D.动态性22下述（）页面置换算法会产生Belady现象。A.最佳置换算法 B.先进先出算法C.LRU算法 D.Clock算法23作业执行中发生了缺页中断，经操作系统处理后，应让其执行（）指令。A.被中断的前一条 B.被中断的后一条C.被中断的 D.启动时的第一条24可变分区方式常用的主存分配算法中，（）总是找到能满足作业要求的最小空闲区分配。A.最佳适应算法 B.首次适应算法C.最坏适应算法 D.循环首次适应算法25可变分区方式常用的主存分配算法中，（）总是找到能满足作业要求的最大空闲区分配。A.最佳适应算法 B.首次适应算法C.最坏适应算法 D.循环首次适应算法26段页式存储管理中，地址映射表是（）。A.每个作业或进程一张段表，两张页表 B.每个作业或进程的每个段一张段表，一张页表C.每个作业或进程一张段表，每个段一张页表D.每个作业一张页表，每个段一张段表27采用（）不会产生内部碎片A.分页存储管理 B.分段存储管理C.固定分区存储管理 D.段页式存储管理28在请求分页存储管理中，若采用FIFO页面淘汰算法，则当分配的页面数增加时，缺页中断的次数（）。A.减少 B.增加C.无影响 D.可能增加也可能减少29段式存储管理中，处理零头问题可采用（）方法。A.重定位B.拼接C.Spooling技术D.覆盖技术30适合多道程序运行的存储管理中，存储保护是为了（）。A.防止一个作业占用同一个分区B.防止非法访问磁盘文件C.防止非法访问磁带文件D.防止各道作业相互干扰二、填空题1在存储器管理中，页是信息的_单位，段是信息的_单位。页面大小由_确定，段的大小由_确定。2如果一个程序为多个进程所共享，那么该程序的代码在执行的过程中不能被修改，即程序应该是 。3将作业地址空间中的逻辑地址转换为主存中的物理地址的过程称为 。4为了解决碎片问题，可采用一种方法，将内存中的所有作业进行移动，使原来分散的多个小分区拼接成一个大分区，这种方法称为 。6页表的作用是 。7程序执行的局部性原理体现在 局部性和 局部性两个方面。8在分页虚拟存储管理方式中，常采用的页面置换算法有： ，淘汰不再使用或最远的将来才使用的页； ，选择淘汰在主存驻留时间最长的页； ，选择淘汰离当前时刻最近的一段时间内使用得最少的页。9所谓虚拟存储器是指具有 功能和 功能，能从 上对内存容量进行扩充的一种存储器系统。10在分页存储管理方式中，当要按照给定的逻辑地址进行读/写时，需要 次访问内存。11可变分区中为提高主存利用率，采用 技术，但这样做花费处理器时间，增加系统开销。12可变分区存储管理中主存预先不分区，作业装入主存时，在主存用户空闲区内划分出一块与 大小适合的连续区域装入。13段页式存储管理兼顾了 在逻辑上清晰和 存储管理上方便的优点。14页面调度算法的选择是很重要的，如果选用了一个 调度算法就会出现这样的现象，刚被淘汰的页面又立即要用，把它调入，不久又被调出，调出不久又再次调入，如此反复，使调度时间非常频繁，以致大部分时间都花费在来回调度上，这种现象叫做 ，又称 。15页式存储管理中，进行存储分配时，以 为单位进行分配，采用不连续的分配办法，作业信息可以按 分散在主存不连续的 中。16. 在一个采用页式虚拟存储管理的系统中，某进程依次要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，若作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，回答下列问题：（1）按FIFO调度算法将产生 次缺页中断，依次淘汰页号为 。（2）按LRU调度算法将产生 次缺页中断，依次淘汰页号为 。三、问答题1简述页和段的区别。2什么是虚拟存储器？如何实现分页虚拟存储管理系统？3采用请求分页虚拟存储管理的系统，接收了一个共7页的作业，作业执行时依次访问的页为1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。若采用最近最少用（LRU）调度算法，作业在得到两块主存空间和四块主存空间时各会产生缺页中断？如果采用先进先出（FIFO）调度算法又会有怎样的结果？4有一个程序要把100100数组置初值为“0”，现假定有两个主存块可用来存放数组信息，主存块的大小为可存放200个数组元素，数组中的元素按行编址。两个主存块的初始状态都为空，若编程编制如下： Var A: arrary1.100 of array1.100 of integer; for j:=1 to 100 do for i:=1 to 100 do Ai,j:=0; Var A: arrary1.100 of array1.100 of integer; for i:=1 to 100 do for j:=1 to 100 do Ai,j:=0;当采用LRU页面调度算法时各会产生多少次缺页中断？5某采用分页存储管理的系统中，物理地址占20位，逻辑地址中页号占6位，页大小为1KB，问：该系统的内存空间大小为多少？每块的大小为多少？逻辑地址共几位，每个作业最大长度为多少？若0页放在3块中，1页放在7块中，2页放在9块中，逻辑地址0420H对应的物理地址是多少？6. 某计算机系统有缓冲寄存器（Cache）,内存（M），辅存寄存器实现虚拟存储器。如果数据在缓冲寄存器中，访问它需要Ams;如果数据在内存而不在缓冲寄存器中，需要Bms将其装入缓冲器，然后才能访问它；如果数据在辅助存储器，需要Cms将其装入内存，然后再装入缓冲寄存器才能访问它。假定：缓冲寄存器命中率为（N-1）/N，内存命中率为（M-1）/M。请问：访问一次数据的平均时间是多少？要求：分别给出各级存储器的访问时间，平均时间，平均时间的化简结果。7.（8分）（2009年考研题）请求分页管理系统中，假设某进程的页表内容如下表所示。 页号页框号有效位（存在位）0101H11-02254H1页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设TLB初始为空；地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问： （1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。 （2） 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。 解答：(1) 因为页大小为4KB，所以虚地址中的低12位表示页内地址，剩余高位表示页号。则十六进制虚地址的低三位为页内地址，最高位为页号。因此访问上述三个虚地址所需时间如下：2362H： 页号为2，页内地址为362H。访问快表10ns，未命中；访问内存中的页表100ns，根据页表指示该页在内存，根据页框号形成物理地址再次访问内存100ns，共计10ns+100ns*2=210ns。1565H： 页号为1，页内地址为565H。访问快表10ns，未命中；访问内存中的页表100ns，根据页表指示该页不在内存，处理缺页108ns，再次访问快表10ns命中，根据页框号形成物理地址再次访问内存100ns，共计10ns*2+100ns*2+108ns=328ns。25A5H：页号为2，页内地址为5A5H。访问快表10ns，命中（访问2362H时已更新TLB），根据页框号形成物理地址访问内存100ns，共计10ns+100ns=110ns。（2）虚地址1565H的页号为1，页内地址为565H。目前页0、页2在内存，访问页1时发生缺页，根据LRU置换算法和局部淘汰策略，将页0换出页1换入，因此页1对应的页框号为101H，则虚地址1565H的物理地址为101565H。8.（8分）（2010年考研题）设某计算机的逻辑地址空间和物理地址空间均为64KB.按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB.操作系统采用固定分配局部置换策略为此进程分配4个页框（Page Fame）。页号页根号装入时刻访问位071301142301222001391601当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题：（1）、该逻辑地址对应的页号是多少？（2）、若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（3）、若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，示意图如下。）解答：（1）逻辑地址空间为64KB，则逻辑地址为16位，因为页大小为1K，所以页内偏移地址为10位，因此高6位是页号。17CAH=(0001 0111 1100 1010)2，所以逻辑地址17CAH对应的页号为5。（2）若采用先进先出（FIFO）置换算法，则被置换的页面所在页框为7，所以对应的物理地址为（0001 1111 1100 1010）2=1FCAH（3）若采用时钟（CLOCK）置换算法，则被置换的页面所在页框为2，所以对应的物理地址为（0000 1011 1100 1010）2=0BCAH参考答案一、单项选择题1.C 2.A 3.D 4.A 5.C 6.B 7.B 8.B 9.A 10.A 11.A 12.B 13.B 14.A 15.D16.B 17.C 18.A 19.C 20.C 21.C 22.B 23.C 24.A 25.C 26.C 27.B 28. D29.B 30.D二、填空题1物理 逻辑 系统 用户作业本身2可重入的3地址转换4紧凑6实现从页号到物理块号的映射7时间 空间8最佳置换算法 先进先出算法 最近最少使用算法9请求调入 置换 逻辑10211紧凑12作业大小相同13段式 页式14不合适、抖动、颠簸15块、页、主存块165，0、1、26，2、0、1、3三、问答题1分页和分段有许多相似之处，但是在概念上两者完全不通，主要表现在：页是信息的物理单位，分页是为了系统管理内存的方便而进行的，故对用户而言，分页是不可见的，是透明的；段是信息的逻辑单位，分段是作业逻辑上的要求