第二章 习题解答

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