操作系统存储管理习题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章第五章 存储管理习题,1、某系统采用,动态分区,存储管理技术，某时刻内存中有三个空闲区，它们的首地址和大小分别为：,空闲区1 (100KB,10KB) 空闲区2(200KB,30KB),空闲区3 (300KB,15KB),(1)画出该时刻内存分配图；,(2)用首次适应法和最佳适应法画出此时的空闲分区链；,(3)有如下作业序列：,作业1 需求15KB，作业2 需求16KB，,作业3 需求10KB，,用哪种算法能将该作业序列装入内存？(给出简要分配过程),100K,(1),110K,200K,230K,300K,315K,10KB,30KB,15KB,(2),100K,10KB,200K,30KB,300K,15KB,首次适应法,最佳适应法,100K,10KB,300K,15KB,200K,30KB,100K,110K,200K,230K,300K,315K,10KB,30KB,15KB,(3),100K,110K,200K,230K,300K,315K,10KB,15KB,15KB,作业1,215K,首次适应法,100K,110K,200K,230K,300K,315K,作业3,14KB,作业1,作业2,216K,100K,110K,200K,230K,300K,315K,10KB,30KB,15KB,最佳适应法,2、考虑一个由8个页面，每页1K字节组成的逻辑空间，把它映射到由32个物理块组成的存储器。问：,（1）有效的逻辑地址有多少位？,（2）有效的物理地址有多少位？,解此题的关键是要知道在分页管理中，“页”和“块”是一样大小的，这样才知道物理存储器是,32K,。,（,1,）,逻辑地址有,13,位,（,2,）物理地址有,15,位,3、若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，3000，5012转化为相应的物理地址。,页号,块号,0,1,2,3,2,3,1,6,为了描述方便，设页号为P，页内位移为W，逻辑地址为A，内存地址为M，页面大小为L，,根据 P=int(A/L) W=A mod L,对于逻辑地址1011,P=int(1011/1024)=0,W=1011 mod 1024=1011,A=1101=(0,1101),查页表0号页在2号块，所以物理地址为M=1024*2+1101= 3059。,对于逻辑地址为2148,P=2148/1024=2,W=2148 mod 1024=100,A=2148=(2,100),查页表2号页在1号块，所以物理地址为M=1024*1+100=1124。,对于逻辑地址为3000,P=3000/1024=2,W=3000 mod 1024=952,A=3000=(2,952),查页表2号页在1号块，所以物理地址为M=1024*1+952=1976,对于逻辑地址5012,P=5012/1024=4,W=5012 mod 1024=916,因页号超过页表长度，该逻辑地址非法。,4、某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。试问：（1）逻辑地址的有效位是多少？（2）物理地址需要多少位？（3）假定某时刻系统用户的第0，1，2，3页分别分配的物理块号为5，10，4，7，试将虚地址0A5C和093C变换为物理地址。,（1）程序空间的大小为32KB，因此逻辑地址的有效位数是15位。,（2）内存储空间的大小是16KB，因此物理地址至少需要14位。,（3）页面大小为1KB，虚地址0A5C(,000,10,10,0101,1100,)表示页号为00010，页内地址是1001011100。该页在内存的第4块，即块号为0100，因此0A5C的物理地址是，即125CH。,（4）用同样的方法可以求得，093C的物理地址是113CH。,5、考虑一个分页存储器，其页表存放在内存。(*),（1）若内存的存取周期为0.6us，则CPU从内存取一条指令（或一个操作数）需多少时间？,（2）若使用快表且快表的命中率为75，则内存的平均存取周期为多少？,假定访问快表的时间可以忽略不计,（,1,）因为页表放在内存，故取一条指令（或一个操作数）须访问两次内存，所以需,0.6us,2 = 1.2us,的时间。,（,2,）这里假定访问快表的时间可以忽略不计，命中快表时取数只要一次访存，故此时的平均存取周期为,0.6us,0.75+1.2us,(,1-0.75)=0.75us,关键,:,要知道访问快表的时间可以忽略不计和平均存取周期的概念。,6、某段式存储管理系统中，有一作业的段表（SMT）如下表所示，求逻辑地址0，65，1，55，2，90，3，20对应的主存地址（按十进制）。（其中方括号中的第一个元素为段号，第二个元素为段内地址）,段号,段长（容量）,主存起始地址,状态,0,1,2,3,200,50,100,150,600,850,1000,1,1,1,0,逻辑地址0，65：对应的主存地址为60065665。,逻辑地址1，55：因段内地址超过段长，所以产生段地址越界中断。,段号,段长（容量）,主存起始地址,状态,0,1,2,3,200,50,100,150,600,850,1000,1,1,1,0,逻辑地址2，90：对应的主存地址为1000901090。,逻辑地址3，20：因为状态位为0，即该段在辅存中，所以产生缺段中断。,段号,段长（容量）,主存起始地址,状态,0,1,2,3,200,50,100,150,600,850,1000,1,1,1,0,虚拟内存的实际大小由系统的逻辑地址结构、主存、辅存容量共同决定。,虚拟内存容量的理论值是2,10,*2,20,=1G；,最大段内地址为2,20,=1M，超过512K的内存容量，故最大实际段长为512k而不是1M。,所以可计算虚拟存储容量为,2,10,*512K =2,10,*0.5M=0.5G。,0.5G2G，因此虚拟存储器的实际容量是0.5G。,7、有一计算机系统，内存容量为512K，辅存容量为2G，逻辑地址形式为：段号2920bit 段内地址190bit。求其虚拟存储器的实际容量？(*),8、在请求分页存储管理系统中，存取一次内存的时间是8us，查询一次快表的时间是1us，缺页中断的时间是20us，,假设页表的查询与快表的查询同时进行 。当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。(*),1、求对某一数据进行一次存取可能需要的时间？,2、连续对同一页面上的数据进行4次连续读取，求每次读取数据可能需要的时间?,当系统对数据进行存取时，有,3,种可能性。,1,、,所存取的数据的页面在内存，其页表项已经存储到快表，,此时存取数据的时间是：查询快表的时间,+,存取内存数据的时间,=1us+8us= 9us,2,、,所存取的数据的页面在内存，但是其页表项没有存储到快表,，没有命中快表，此时存取数据的时间是：查询页表的时间,+,存取内存数据的时间,=8us+8us= 16us,3,、,所存取的数据的页面不在内存，发生缺页中断，,此时存取数据的时间是：,查询页表的时间,+,缺页中断的时间,+,访问页表的时间,+,存取内存数据的时间,=8us+20us+8us+8us = 44us,当对某一数据进行,4,次连续读取时：,第,1,次可能的时间分别为：,1us+8us= 9us,；,8us+8us= 16us,；,8us+20us+8us+8us=44,us,。,第,2,次时，对应页面的页表项已经交换到快表中。因为存取是连续的，不存在页面被淘汰的可能性，所以第,2,次、第,3,次、第,4,次的存取时间是一样的，消耗的时间为,1us+8us= 9us,。,9、考虑一个有快表的请求分页系统设内存的读写周期为1us,内外存之间传送一个页面的平均时间为5ms，其中， 80%情况下命中快表，10%情况下页面失效（缺页）求内存的有效存取时间。(*),内存的有效存取时间EAT(Efficent Access Time)也叫平均存取时间AAT(Average Access Time)，其计算公式如下：,EAT命中快表时的存取时间快表命中率,命中内存时的存取时间内存命中率,页面失效时的存取时间页面失效率,将题中的已知条件代入可得,EAT=1us80%,+2us（100-80-10）%,+(1us+5000us+1us+1us)10%,=0.8us+0.2us+500.3us,=501.3us,10、一个使用快表的页式虚存，（1）快表的命中率为70，内存的存取周期为1us；（2）缺页时，若内存有可用空间或被置换的页面在内存未被修改过，则处理一个缺页需8ms，否则需20ms，假定被置换的页面60是属于后一种情况。问：为了保证有效存取时间不超过2us，问可接受的最大缺页率是多少？,设可接受的最大缺页率为p，则有,1us0.7+ 命中快表,2us(1-0.7-p)+ 命中页表,(0.48ms+0.620ms) p 缺页,=2us,即 0.7+0.6-2p+3200p+1200p=2,15198p=0.7,p=0.000046,11、在分页存储管理系统中，存取一次内存的时间是8us，查询一次快表的时间是1us，缺页中断的时间是20us。假设页表的查询与快表的查询同时进行，当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。一个作业最多可保留3个页面在内存。,现开始执行一作业，系统连续对作业的、5、7、6、4、2各页面的数据进行1次存取，如分别采用FIFO算法和最优页面置换算法，求每种算法下存取这些数据需要的总时间 ？,LRU,第2页面：208*3,第4页面：20 +8*3,第5页面：20 +8*3,第2页面：8+1,第7页面：20 +8*3,第6页面：20+8*3,第4页面：20+ 8*3 第8页面：20+8*3,因此总的时间是（208*3）*7+（8+1）=317,OPT,第2页面：208*3,第4页面：20 +8*3,第5页面：20 +8*3,第2页面：8+1,第7页面：20 +8*3,第6页面：20+8*3,第4页面：8+1 第8页面：8+1,因此总的时间是 (208*3）*5 +(8+1)*3=247,12、在某分页虚存系统中，测得,CPU,和磁盘的利用率如下，试指出每种情况下的问题和措施。*,(1) CPU,的利用率为,15,，盘利用率为,95,；,(2) CPU,的利用率为,88,，盘利用率为,3,；,(3) CPU,的利用率为,13,，盘利用率为,5,。,（,1,）可能已出现了抖动现象，应减少系统的进程数；,（,2,）系统比较正常，可考虑适当增加进程数以提高资源利用率；,（,3,）,CPU,和磁盘的利用率都较低，必须增加并发进程数。,在内存管理中，“内零头”和“外零头”各指的是什么？在固定式分区分配、可变式分区分配、页式虚拟存储系统、段式虚拟存储系统中，各会存在何种零头？为什么？,内零头（又称内部碎片）：给一个作业分配的存储块长度为n，在其中存储的作业长度为m，则剩下的长度为（n-m）的空间，成为该存储块的内部碎片；,若存储块长度为n，在该系统所采用的调度算法下，较长时间内无法选出一道长度不超过该块的作业，则称该块为外零头（外部碎片）。,在固定式分区分配中两种零头均会存在，因为空间划分是固定的，无论作业长短，存储单元均不会随之变化，若作业短而存储块长则产生内零头，若作业长而存储块短则产生外零头。,在可变式分区分配中只有外零头而无内零头，因为空间划分是依作业长度进行的，是要多少给多少，但剩下的部分太短而无法再分，则称为外零头。,页式虚存中会存在内零头而无外零头，因存储空间与作业均分为等长单元，所以不存在无法分配的单元，但作业长度并不刚好为页面大小的整数倍，因此在最后一页会有剩余空间，即为内零头。,段式虚存中会存在外零头而无内零头，因段式的空间划分类似于可变分区分配，根据段长分配，要多少给多少，但会剩余小空间无法分配，则为外零头。,为什么要引入逻辑地址？,(1) 使用物理地址的程序只有装入程序所规定的内存空间上才能正确执行，如果程序所规定内存空间不空闲或不存在，程序都无法执行；,(2) 使用物理地址编程意味着由程序员分配内存空间，程序员无法事先协商每个程序所应占的内存空间的位置,这在多道程序系统中，势必造成程序所占内存空间的相互冲突；,(3) 在多道程序系统中，系统无法保证程序执行时，它所需的内存空间都空闲。,基于上述原因，必须引入一个统一的、在编程时使用的地址，它能够在程序执行时根据所分配的内存空间将其转换为对应的物理地址，这个地址就是逻辑地址。,逻辑地址的引入为内存的共享、保护和扩充提供方便。,试比较静态重定位和动态重定位,“重定位”实际上指的是相互联系的两件事情：,一是确定一个待执行程序在内存中的位置；,二是将程序中的逻辑地址转换成物理地址。,后一件事情是由前一件事情决定的。,试比较静态重定位和动态重定位。,静态重定位的特点,实现容易，无需增加硬件地址变换机构；,一般要求为每个程序分配一个连续的存储区；,在重定位过程中，装入内存的代码发生了改变；,在程序执行期间不再发生地址的变换；,在程序执行期间不能移动，且难以做到程序和数据的共享，其内存利用率低。,动态重定位特点,实现要依靠硬件地址变换机构，且存储管理软件算法较复杂；,程序代码是按原样装入内存的，在重定位的过程中也不发生变化(重定位产生的物理地址存放在内存地址寄存器中),同一代码中的同一逻辑地址，每执行一次都要重定位一次；,只要改变基地址，就可以很容易地实现代码在内存中的移动；,动态重定位可以将程序分配到不连续的存储区中；,所以，尽管动态重定位需要硬件支持，但支持程序浮动，便于利用零散的内存空间，利于实现信息共享和虚拟存储，所以现代计算机大都采用动态重定位。另外，实现虚拟存储器需要动态重定位技术的支持。,在实存管理上，管理方法主要分成哪两种类型？,实存管理的方法主要分成：,(1)连续:,用户程序需要占用连续的内存空间，如分区存储管理；,(2)离散:,用户程序不需要占用连续的内存空间，如分页、分段、段页等管理，一个用户程序在内存可能是不连续的，如果它有不只一页或一段的话。,为什么在分页和分段管理下取一条指令或一个操作数通常需两次访存？如何解决这一问题？,因为用于地址变换的页表或段表也是存放在内存的，,为了将,CPU,给出的逻辑地址变成物理地址，首先就要访问内存的页表和段表，然后，根据形成的物理地址再取指令或数据，这就要两次访存。,解决这一问题的办法是提供一个称之为“快表”的硬件，用以存放当前运行进程的页表或段表的部分内容，“快表”的访问时间很快，因此可以节约访问页表和段表的时间。,存储器访问具有时间和空间的“局部性”，因此快表的命中率一般可达,70%,到,90%,；页表和段表是在系统执行过程中，每时每刻都需要访问的，因此，访问时间的微小缩短，其累计节约的时间却可以达到很大。,为什么分段管理下的程序共享和保护比分页管理更有意义.,因为段是一个有意义的逻辑整体，如主程序、子程序、数据表格、工作空间等，就如书本上的一章或一个自然段。,而页只是一个物理尺寸，不一定有完整的意义，如书本上的一页。,程序共享当然希望被共享的对象是一个有意义的整体，如一个子程序；,至于程序保护，指的是每个进程都应按所拥有的存取权访问不同的程序，而存取权,(R,W,E等)当然对一个有完整意义的对象才更有意义。,所以就共享和保护而言，分段管理比分页管理更有意义。,为什么说分段系统较之分页系统更易于实现信息共享和保护？如何实现。,(1),为了实现共享，必须在各共享者的段表或页表中分别有指向共享内存块的表目。,(2),对分段式系统，被共享的程序或数据可作为单独的一段。在物理上它是一段，在不同的进程中，可以对应不同的逻辑段，相对来说比较易于实现。,(3),对分页管理，则要困难的多。必须保证被共享的程序或数据占有整数块，以便与非共享部分分开。,(4),分段系统的共享是通过两个（或多个）进程的段表之相应表目都指向同一个物理段，并设置共享计数来实现的。,什么是抖动现象？如何消除这种现象？,抖动现象，是在虚存管理下，用于页面（在内、外存之间）对换的时间比程序的有效运行时间还要多的这样一种现象。它可以是一进程内部的局部性抖动，也可以是整个系统的全局性抖动。,造成这种情况固然与置换算法和页面走向有关，但其根本原因是多道系统内的进程数太多，从而分给每个进程的页面数太少。,因此，解决这一问题的最有效的办法是减少系统内的进程数。,Denning于1980年提出了“L=S准则”，即调整系统内的进程数，使得产生缺页的平均间隔时间（L）等于系统处理进程缺页的平均时间（S）。理论和实践表明，此时的CPU利用率最高。,覆盖技术的基本思想是什么？,若一个大的程序是由多个相对独立的程序模块组成，且有些模块是相互排斥的，即执行甲就不会执行乙，,在这种情况下，就没有必要将该程序的所有模块装入内存，,可将那些二者（或多者）执行时取其一的模块处理成“覆盖”，让它们共享内存的一个“覆盖区”。,这样就可大大节省内存空间，达到用小内存运行大程序的目的。,覆盖技术与虚拟存储技术有何本质不同？,虚拟存储器对于程序员时,透明,的，不需要程序员了解程序结构、覆盖的区域、时机，不需要精心的设计程序及其数据结构，所有的操作由操作系统自动完成。,覆盖的程序段的,最大长度,要受到物理内存容量的限制，而虚拟存储器的最大长度不受物理内存容量的限制，只受计算机地址结构的限制。,交换技术与虚存中使用的调入调出技术有何相同和不同之处？,主要相同点:是都要在内存与外存之间交换信息,主要区别:,交换技术换出换进一般是整个进程(proc结构和共享正文段除外)，因此一个进程的大小受物理存储器的限制；,而虚存中使用的调入调出技术在内存与外存之间来回传递的是存储页或存储段，而不是整个进程，从而使得进程映射具有了更大的灵活性，且允许进程的大小比可用的物理存储空间大的多。,