操作系统第五章(15)

练习题:某程序在逻辑地址100处有一条取数指令LOAD1，500，而500单元内存放数据51888。假设程序被分配到内存起始地址5000单元时，试用图示意，采用下述各种方式下的该指令及数据地址的物理地址及相应地址的变换过程。（1）静态重定位（2）采用重定位寄存器实现动态重定位（3）采用页表映象方式，假定页面大小为100单元，其页表各页映射到50，51，52，53，54，55，…,59物理页上。3.解（1）如图0…100LOAD1,500…50051888…地址空间…5000…5100Load1,5500…5500518885999…内存说明：静态重定位是在该程序装入内存时,由装入程序进行地址重定位，因此，程序指令中的地址在装入过程中加以修改，以适应程序装在与原地址空间不一致的物理空间。（2）如图0…100LOAD1,500…50051888999…地址空间……51888……内存5000+5005500（3）如图所示……51888……内存页表首址页表长550050151252353454555656757858959+逻辑地址：500500页号页内位移55×100+0=5500页面大小为100单元5.5.1.3请求分页存储管理页式管理是将程序全部装入内存；请求分页存储管理是可以将程序按照页全部链接后，部分装入内存，页表将进行扩充；余下的部分如何安排呢？余下的部分是以文件的形式存入作为辅存的磁盘上。通过中断采用置换算法，将其调入。当调入时需要建立一个辅助页表练习：某计算机系统采用请求页式存储管理方法，其提供给用户一个容量为221B的虚存，实存（内存）容量为218B。页面大小为210B，如果一个进程访问一个数据，其地址为（0123456）8（八进制表示的地址），请你给出该虚拟地址对应的物理地址（实地址）。假设此数据所在的虚页号对应的实页面物理块号为8页面，要求也用八进制表示。解：页的划分为0123456对应的2进制为00001010011100101110实页号为（00001000110010111019页号P109页内地址W0021456该数据的实地址为（021456）8练习:设有一个采用请求分页存储管理的系统，其内存容量为512KB，虚存容量为2048KB,页面大小为2KB。试问（1）内存物理地址应设多少位（2）内存中有多少物理块（3）最大块号是多少（4）虚存地址应设多少位（5）地址空间最多可有多少页（6）页内最大的位移量是多少（7）最小的位移是多少？解：（1）19位219=512K（2）256块512/2=256（3）255（4）21位221=2048（5）1024页2048k/2k=1024（6）1023（7）0练习:分页管理，页面大小100B，下面一道程序中的逻辑地址是多少？请用页号和页内位移来表示，并用二进制数。（1）从263中取数（2）写数到264（3）写数到265（4）写数到901（5）从902中区数（6）Halt解：263=2(页号)×100+63(位移量)63=00111111（1）（0010，00111111）。（2）（0010，01000000）。（3）（0010，01000001）。（4）（1001，00000001）。（5）（1001，00000010）。（6）无需操作数，故无需地址。一个由4个页面（页号为0-3）、每页由1024个字节组成的程序，把它装入一个由8个物理块（块号为0-7）组成的存储器中，装入情况如表1-7-3所示。己知下面的逻辑地址（其中方括号中的第一个元素为页号，第二个元素为页内地址），请按页表求出对应的物理地址。（1）[0，100]；（2）[1，179]；（3）[2，785]；（4）[3，1010]。表1-7-3逻辑页号内存块号03152632解：因为每页有1024B，所以内存中每块也有1024B。故内存中每块的起始地址为（每块起始地址＝块号X块长）：0块：00001块：10242块：20483块：30724块：40965块：51206块：61447块：7168（1）的物理地址为：3072+100=3172；（2）的物理地址为：5120+179=5299；页面首址页表长（3）的物理地址为：6144+785=6929；（4）的物理地址为2048+1010=3058。5.5.1.4置换算法功能：需要调入页面时，选择内存中哪个物理页面被置换。称为replacementpolicy。目标：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测；页面锁定(framelocking)：用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现方法为在页表中加上锁定标志位(lockbit)。返回最佳算法(OPT,optimal)最近最久未使用算法(LRU,LeastRecentlyUsed)先进先出算法(FIFO)轮转算法(clock)最不常用算法(LFU,LeastFrequentlyUsed)页面缓冲算法(pagebuffering)1.最佳算法(OPT,optimal)选择“未来不再使用的”或“在离当前最远位置上出现的”页面被置换。这是一种理想情况，是实际执行中无法预知的，因而不能实现。可用作性能评价的依据。2.最近最久未使用算法(LRU,LeastRecentlyUsed)一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。硬件机构如：3.先进先出算法(FIFO)选择建立最早的页面被置换。可以通过链表来表示各页的建立时间先后。性能较差。较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出。并且有Belady现象。Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。Belady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S,N)时而增大，时而减小。Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。Belady现象的例子进程P有5页程序访问页的顺序为：1,2,3,4,1,2,5,1,2,3,4,5；如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；FIFO123412512345页0123412555344页112341222533页21234111255缺页xxxxxxx√√xX√如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；FIFO123412512345页0123444512345页112333451234页21222345123页3111234512缺页xxxx√√xxxxxx4.轮转算法(clock)每页有一个使用标志位(usebit)，若该页被访问则置userbit=1。置换时采用一个指针，从当前指针位置开始按地址先后检查各页，寻找usebit=0的页面作为被置换页。指针经过的userbit=1的页都修改userbit=0，最后指针停留在被置换页的下一个页。也称最近未使用算法(NRU,NotRecentlyUsed)，它是LRU(最近最久未使用算法)和FIFO的折衷。Stateofbufferjustpriortoapagereplacement012345678n...Page9use=1Page19use=1Page1use=0Page45use=1Page191use=1Page556use=0Page13use=0Page67use=1Page33use=1Page222use=0nextframepointer准备换入Stateofbufferjustafterthenextpagereplacement012345678n...Page9use=1Page19use=1Page1use=0Page45use=0Page191use=0Page727use=1Page13use=0Page67use=1Page33use=1Page222use=0停留在下一页5.最不常用算法(LFU,LeastFrequentlyUsed)选择到当前时间为止被访问次数最少的页面被置换；每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；6.页面缓冲算法(pagebuffering)被置换页面的选择和处理：用FIFO算法选择被置换页，把被置换的页面放入两个链表之一。如果页面未被修改，就将其归入到空闲页面链表的末尾否则将其归入到已修改页面链表。它是对FIFO算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面；需要调入新的物理页面时，将新页面内容读入到空闲页面链表的第一项所指的页面，然后将第一项删除。空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，而被访问的页面可以返还作为进程的内存页。当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表，这样能大大减少I/O操作的次数。OPT432143543215页1432111555211页243333333555页34444444444xxxx33x33xx3共缺页中断7次7.置换算法举例某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。选择“未来不再使用的”或“在离当前最远位置上出现的”页面被置换。LRU432143543215页1432143543215页243214354321页34321435432xxxxxxx33xxx共缺页中断10次选择内存中最久未使用的页面被置换FIFO432143543215页1432143555211页243214333522页34321444355xxxxxxx33xx3共缺页中断9次5.5.2简单段式(simplesegmentation)页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一致。1.简单段式管理的基本原理将程序的地址空间划分为若干个段(segment)，程序加载时，分配其所需的所有段（内存分区），这些段不必连续；物理内存的管理采用动态分区。需要CPU的硬件支持。程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段。可以分别编写和编译可以针对不同类型的段采取不同的保护可以按段为单位来进行共享，包括通过动态链接进行代码共享优点：没有内碎片，外碎片可以通过内存紧缩来消除。便于改变进程占用空间的大小。缺点：进程全部装入内存。B0SA0NY0LX0PM0K逻辑段号01234作业1的地址空间01234K3200P1500L6000N8000S5000长度段地址01234段号10003200500060008000PKSLN主存操作系统2.简单段式管理的数据结构进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段基址(baseaddress)和段长度系统段表：系统内所有占用段空闲段表：内存中所有空闲段，可以结合到系统段表中3.简单段式管理的地址变换Base+dProgramSegmentationMainMemoryVirtualAddressRegisterSegmentTableSegmentdS#LengthBaseSegTablePtrSeg#Offset=dSegmentTable++段表起始地址段表地址寄存器虚拟地址11C4