操作系统例题PPT课件

.,存储管理习题,.,例1,1.某系统采用动态分区管理技术。某时刻在内存有三个空闲区，它们的首地址和大小分别是：空闲区1（100KB，10KB），空闲2（200KB，30KB），空闲区3（300KB，15KB），现有如下作业序列：作业1需要15KB，作业2需求16KB，作业3需求10KB。要求：（1）画出该时刻内存分配图。（2）用首次适应算法和最佳适应算法画出此时的自由主存队列结构。,.,（1）将作业序列装入主存之前，内存的分配图如下所示：,.,（2）首次适应算法的自由主存队列结构为：,（2）最佳适应算法的自由主存队列结构为：,.,例2,2.在分页系统中地址结构长度为16位,页面大小为2K,作业地址空间为6K,该作业的各页依次存放在2、3、6号物理块中，相对地址2500处有一条指令store1,4500，请给出该作业的页表和该指令的物理单元以及数据存放的物理单元。,.,答案,页面大小为2K，即2048字节；作业地址空间6K，则占用页数为3，编号为0、1、2，依次存放在2、3、6号物理块中，作业页表如下：相对地址为2500字节，应在第2500/2048=1号页面，余数452即为页内位移，所以对应的物理块号为3，得到物理地址为2048*3+452=6596；相对地址4500/2048=2号页面，页内位移为404，对应的物理块号为6，得到物理地址为2048*6+404=12692。,.,例3,3.某操作系统的存储管理采用页式管理系统，系统的物理地址空间大小为32K，页的大小是4K。假定某进程的大小为32页，请回答如下问题：（1）写出逻辑地址的格式。（2）如果不考虑权限位，该进程的页表有多少项？每项至少多少位？,.,答案,页面大小是4K，即212，进程大小是32页，即25。（1）逻辑地址应有17位，其中011位是页内位移，1216位是页号。（2）该进程页表有32项，每项5位。,.,例4,4.对一个将页表放在内存中的分页系统：（1）如果访问内存需要（2）如果增加一个快表，且假定在快表中找到页表项的概率高达90%，则有效访问时间表又是多少（假定查找快表需花的时间为0）？,.,答案,每次访问数据时，若不使用快表，则需要两次访问内存，即先从内存的页表中读出页对应的块号，然后再根据形成的物理地址去存取数据；使用快表时，若能从快表中直接找到对应的页表项，则可立即形成物理地址去访问相应的数据，否则，仍需两次访问内存。（1）有效访问时间为：（2）有效访问时间为：,.,例5,5.在分页存储管理系统中，逻辑地址的长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且0、1、2页依次存放在物理块5、10、11中，问相应的物理地址是多少？,.,答案,分析：在分页存储管理系统中进行地址转换时，地址变换机构将自动把逻辑地址转化为页号和页内地址，如果页号不小于页表长度，则产生越界中断；否则便以页号为索引去检索页表，从中得到对应的块号，并把块号和页内位移分别送入物理地址寄存器的块号和块内位移字段中，形成物理地址。答案：由分析所给条件可知，分页存储管理系统的逻辑地址结构如下图：逻辑地址2F6AH的二进制表示如下：0010111101101010页号页内位移由此可知逻辑地址2F6AH的页号为2，小于页表长度3，没有越界，该页存放在第11个物理块中，用十六进制表示块号为B，所以物理地址为BF6AH。,.,例7,7.某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C和093C变换为物理地址。,.,答案,虚拟地址为0A5C，对应的二进制数为：0000101001011100。其中，页内偏移量占10位地址码，为25C。因第页存储在号块中，其基地址为：0001000000000000,这样，虚拟地址为十六进制的125C。虚拟地址为093C，对应的二进制数为：0000100100111100。其中，页内偏移量占10位地址码，为13C。因第2号页存储在4号块中，其基地址为：0001000000000000，01000100111100。这样，虚拟地址为十六进制的113C。,.,例8,8.在采用页式存储管理的系统中，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像表（即页表）如下：试借助地址变换（要求画出地址变换图）求出有效逻辑地址4865所对应的物理地址。,.,分析与解答,逻辑地址4865指的是2号页中偏移地址为769的存储单元（4865-4096=769）。而内存6号块的起始地址是12288（2048*6），因此对应的物理地址为13057（12288+769）。地址变换图如下：,+,.,例9,9.设一段表如图所示那么，逻辑地址（2，88）对应的物理地址是多少？逻辑地址（4，100）所对应的物理地址是多少？,.,分析与解答,(1)2号段所占的内存空间基地址是90，段内地址是88，因此访存的物理地址应当是二者相加：90+88=178。(2)在分段存储管理系统中，段的长度是不固定的。因此段表内需要登记各段的实际长度，用以检查CPU产生的访存地址是否超界。题中第2部分给出的段内地址是100，而段的长度是96，因此将产生越界中断，无任何物理地址产生。,.,例10,10.某页式存储管理系统中，地址寄存器长度为24位，其中页号占14位，则主存的分块大小应该是多少字节？程序最多占有多少页？,.,分析与解答,主存的分块大小占10位，应为1K个字节，即210。程序最多可以占有16K个页，即214。,0,9,10,23,逻辑地址,在分页机制中，需要将用户的线性地址空间划分成二维地址空间。让地址的高位部分作为页号，低位部分作为分块的大小，也称位移量。,.,例11,11.某虚拟存储器的用户空间共有32个页面，每页1K，主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7，而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C转换成物理地址。,.,分析与解题,逻辑地址有15位，其中高5位为页号，低10位为页内地址；物理地址有14位，其中高4位为块号，低10位为块内地址。逻辑地址(0A5C)16的页号为(00010)2，即2，故页号合法。从页表中找到对应的内存块号为4，即(0100)2;与页内地址(1001011100)2拼接形成物理地址(01001001011100)2,即(125C)16。,逻辑地址,0,5,A,1,C,C,5,2,物理地址125C,页号2,块号4,页内地址25C,块内地址25C,.,例12,在一个使用交换技术(Swapping)的系统中,按地址从低到高排列的内存空间长度是:10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB。对于下列顺序段的请求：（1）12KB（2）10KB（3）15KB（4）18KB（5）12KB分别使用首次适配、最佳适配、最差适配和下次适配算法说明空间的使用情况，并说明对暂时不能分配情况的处理方法。,.,分析与解题,首次适配：（1）12KB：2#区（2）10KB：0#区（3）15KB：3#区（4）18KB：失败（5）12KB：6#区最佳适配：1）12KB：6#区（2）10KB：0#区（3）15KB：7#区（4）18KB：3#区（5）12KB：2#区最差适配：1）12KB：2#区（2）10KB：3#区（3）15KB：7#区（4）18KB：失败（5）12KB：6#区下次适配：1）12KB：2#区（2）10KB：3#区（3）15KB：7#区（4）18KB：失败（5）12KB：6#区上述算法中，只有最佳适配算法是分配成功的，其他3种算法都在第4段请求（18KB）出现时分配失败。当出现暂时不能分配的情况时，系统可以采用拼接技术，将内存中的进程移动到存储器的一端，使夹杂于其间的空闲小空间移动到另一端，形成一个较大的可用空间，以满足用户的需求。,.,例13,13.某页式存储管理系统中，地址寄存器长度24位，其中页号占14位，则主存的分块大小应该是（）字节，程序最多占有（）页。A.210B.10C.14D.214E.24F.224,.,分析与解答,本题的考核要点是内存分页管理机制，主要涉及页面长度的划分方法。我们知道，在分页机制中，需要将用户的线性地址空间划分成二维地址空间。让地址的高位部分作为页号，低位部分作为分块的大小，也称位移量，见下图所示。主存的分块大小占10位，应为1K个字节，即210。因此，第1个选项是A，程序最多可以占有16K个页，即214，第2个选项是D。,.,例14,14.假设一个分页存储管理系统具有快表，多数活动页表项都可以存在其中。如果页表放在内存中，内存访问时间是1s,若快表的命中率是85%，则有效存取时间为多少？若快表的命中率为50%，那么有效存取时间为多少？,.,分析与解答,本题的考核要点是内存分页存储管理中，具有快表机制的访问过程，涉及的内容有：1）当快表的命中率是85%时，有效存取时间为：0.851+(1-0.85)(1+1)=1.15m2）当快表的命中率是50%时，有效存取时间为：0.51+(1-0.5)(1+1)=1.5m,.,例15,15.在可变式分区分配方案中，某一作业完成后系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲数减1的情况是（）。A.无上邻空闲区，也无下邻空闲区B.有上邻空闲区，但无下邻空闲区C.有下邻空闲区，但无上邻空闲区D.有上邻空闲区，也有下邻空闲区,.,分析与解答,本题的考核要点是可变分区管理系统的空闲分区回收问题。当用户归还一个空闲分区后，系统在挂入空闲分区链表时需要将相邻空闲分区合并，形成一个大的空闲分区，因此涉及的内容有：1）无上邻空闲区，也无下邻空闲区的情况下，系统将回收的空闲分区挂入空闲链表，使空闲分区总数增加1。2）有上邻空闲区，但无下邻空闲区的情况下，系统将回收的空闲分区并入上邻分区中，使空闲分区总数不增不减。3）有下邻空闲区，但无上邻空闲区的情况下，系统将回收的空闲分区并入下邻分区中，使空闲分区总数不增不减。4）有上邻空闲区，也有下邻空闲区的情况下，系统将回收的空闲分区与上/下邻分区合并为一个大分区，使空闲分区总数减1。,.,例16,16.在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为3、4时，试计算采用下述页面淘汰算法时的缺页率（假设开始执行时主存中没有页面），并比较所得结果。（1）最佳置换淘汰算法（2）先进先出淘汰算法（3）最近最久未使用淘汰算法,.,题解,（1）根据所给页面走向，使用最佳页面淘汰算法时，页面置换情况如下所示。,缺页率：7/12,（A）,.,题解,缺页率：6/12,（B）,.,题解,（2）根据所给页面走向，使用先进先出页面淘汰算法时，页面置换情况如下所示。,缺页率：9/12,（A）,.,题解,缺页率：10/12,（B）,由上述结果可以看出，对先进先出算法而言，增加分配给作业的内存块数反而使缺页率上升，这种异常现象称为Belady现象。,.,题解,（3）根据所给页面走向，使用最近最久未使用页面淘汰算法时，页面置换情况如下所示。,缺页率：10/12,（A）,.,题解,缺页率：8/12,（B）,由上述结果可以看出，增加分配给作业的内存块数可以降低缺页率。,.,例17,17.有一页式系统,其页表存放在主存中.(1)如果对主存的一次存取需要1.5m,试问实现一次页面访问的存取时间是多少?(2)如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,试问此时的存取时间为多少?,.,解答,若页表存入在内存中,则要实现二次页面访问需要两次访问主存,一次是访问页表,确定所存取页面的物理地址,第二次才根据该地址存取页面数据.(1)由于页表存在主存,因此,CPU必须两次访问主存才能获得所需数据,所以实现一次页面访问的存取时间为:1.52=3m.(2)在系统增加了快表后,在快表中找到页表项的概率为85%,所以实现一次页面访问的存取时间为:0.851.5+(1-0.85)21.5=1.725m,.,例18,某请求分页存储管理系统使用一级页表,假设页表总在主存中。（1）如果一次存储器访问需要200ns，那么访问一个数