操作系统第4章测验题

1/12第4章存储器管理4.1典型例题解读【例1】某系统采用动态分区分配方式管理内存，内存空间为640K，高端40K用来存放操作系统。在内存分配时，系统优先使用空闲区低端的空间。对下列的请求序列：作业1申请130K、作业2申请60K、作业3申请100K、作业2释放60K、作业4申请200K、作业3释放100K、作业1释放130K、作业5申请140K、作业6申请60K、作业7申请50K、作业6释放60K，请分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后内存的实际使用情况。首次适应算法最佳适应算法动作已分配分区(作业，始址，大小)空闲分区（始址，大小)己分配分区（作业，始址，大小)空闲分区(始址，大小)作业1申请130Kl，0,130130,470l，O，130130,470作业2申请60Kl，0,1302,130,60190,4101，O，1302,130,60190,410作业3申请100K1,0,1302,130,603,190,100290,3101，O，1302,130,603,190,100290,310作业2释放60Kl，0,1303,190,100130,60290,310l，0,1303,190,100130,60290,310作业4申请200K1，O，1303,190,1004,290,200130,60490,1lOl，0,1303,190,1004,290,200130,60490.110作业3释放100Kl，0，1304,290,200130，160490,110l，0，1304,290,200490，110130，160作业l释放130K4,290,2000,290490,1104,290,200490,1100,290作业5申请140K4,290,2005,0,140140，150490,1104,290,2005,0,140490，110140，150作业6申请60K4,290,2005，O，1406,140,60200,90490,1104,290,2005,0，1406,490,60550,50140,150作业7申请50K4,290,2005,0,1406,140,607，200,50250,40490,1104,290,2005，O，1406,490,607,550,50140,150作业6释放60K4,290,2005,0,1407,200,50140,60250,40490,1104,290,2005,0，1407,550,50490,60140，1502/12答：使用首次适应算法和最佳适应算法进行上述内存的分配和回收后，内存的实际使用情况分别如图(a)和(b)所示。0作业5140K200K作业7250K290K作业4490K600KOS640K（a）0作业5140K290K作业4490K550K作业7600KOS640K(b)【例2】对一个将页表存放在内存中的分页系统:（1）如访问内存需要0．2μs，有效访问时间为多少?（2）如果加一快表，且假定在快表中找到页表项的机率高达90％，则有效访问时间又是多少(假定查快表需花的时间为0)?答：（1）有效访问时间为：2×0．2=0．4μs（2）有效访问时间为：0．9×0．2+(1—0．9)×2×0．2＝0．22ps。【例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：1023／1K，得到页号为0，页内地址为1023，查页表找到对应的物理块3/12号为2，故物理地址为2×1K+1023=3071。②逻辑地址2500：2500／1K，得到页号为2，页内地址为452，查页表找到对应的物理块号为6，故物理地址为6×IK+452=6596。③逻辑地址3500：3500／IK，得到页号为3，页内地址为428，查页表找到对应的物理块号为7，故物理地址为7×1K+428=7596。④逻辑地址4500：4500／1K，得到页号为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，因此产生越界中断。4/12(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，缺页率为9／12(如下表所示)。432143543215√√√√√√√√√444111555555333444442222223333311(2)使用OPT算法时，访问过程中发生缺页的情况为：当物理块数目M为3时，缺页次数为7，缺页率为7／12(如下表所示)。432143543215√√√√√√√444444444444333333332112111555555（3）使用LRU算法时，访问过程中发生缺页的情况为：当物理块数目M为3时，缺页次数为lO，缺页率为10／12(如下表所示)。432143543215√√√√√√√√√√444111555222333444444112223333335【例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转换成物理地址。5/12答：由题目所给条件可知，该系统的逻辑地址有15位，其中高5位为页号，低10位为页内地址；物理地址有14位，其中高4位为页帧号，低10位为页帧内地址。另外，由于题目中给出的逻辑地址是十六进制数，故可先将其转换成二进制数以直接获得页号和页内地址，再完成地址的转换如右图所示，逻辑地址(0A5C)16的页号为(00010)2，即2，故页号合法；从页表中找到对应的内存块号为4，即(0100)2与页内地址(1001011100)2拼接形成物理地址(01001001011100)2即(125C)16。(2)逻辑地址(103C)16的页号为4，页号合法，但该页未装入内存，故产生缺页中断。(3)逻辑地址(1A5C)16的页号为6，为非法页号，故产生越界中断。【例10】现有一请求调页系统，页表保存在寄存器中。若有一个被替换的页未被修改过，则处理一个缺页中断需要8ms；若被替换的页已被修改过，则处理一个缺页中断需要20ms。内存存取时间为lμs，访问页表的时间可忽略不计。假定70％被替换的页被修改过，为保证有效存取时间不超过2μs，可接受的最大缺页率是多少?答：如果用p表示缺页率，则有效存取时间不超过2us可表示为：(1-p)×1μs+p×(0．7×20ms+0．3×8ms+lμs)≤2μs因此可计算出：p≤1/16400≈0.00006即可接受的最大缺页率为0．00006。【例10】假如一个程序的段表如下表所示，其中合法位为1表示段在内存，存取控制字段中w表示可写，R表示可读，E表示可执行。对下面的指令，在执行时会产生什么样的结果?段号合法位内存始址段长保护码其他信息O0500100Wl1100030R213000200E31800080R40500040R(1)STORER1，[0，70](2)STORER1,[1，20](3)LOADR1,[3，20](4)LOADR1,[3，100](5)JMP[2，100]答：(1)指令STORER1，[O，70]。从段表的第0项可读出第0段的合法位为0，表示相应段未装入内存，因此地址变换机构将产生一缺段中断，以请求OS将其调入内存。(2)指令STORERl，[1，20]。从段表的第1项可以看出，虽然指令中的逻辑地址合法，段也已在内存，但本指令对内存的访问方式(写)与保护码字段(只读)不符，故硬件将产生保护性中断信号。6/12(3)LOADR1,[3，20]。从段表的第3项可读出第3段的合法位为1，内存始址为8000，段长为80，存取控制为R，因此，逻辑地址合法，访问方式也合法，形成物理地址8020后，指令将把该单元的内容读到寄存器R1中。(4)指令LOADR1,[3，100]。从段表的的第3项可读出第3段的合法位为l，内存始址为8000，段长为80，存取控制为R，因此，指令的逻辑地址中