第4章存储器管理(4)

12020/1/28最近最久未用（LRU）置换算法的着眼点是在要进行页面置换时，检查这些页面的被访问时间，总是把最长时间未被访问过的页面置换出去。这是一种基于程序局部性原理的置换算法。也就是说，该算法认为如果一个页面刚被访问过，那么不久的将来被访问的可能性就大；否则被访问的可能性就小。4.7.2最近最久未使用（LRU）置换算法22020/1/28引用率70770170122010320304403230321132201710701页框4024320321021.LRU(LeastRecentlyUsed)置换算法的描述4.7.2最近最久未使用（LRU）置换算法32020/1/284.7.2最近最久未使用（LRU）置换算法2.LRU置换算法的硬件支持1)为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3…R2R1R042020/1/28图4-28某进程具有8个页面时的LRU访问情况52020/1/282)栈图4-29用栈保存当前使用页面时栈的变化情况447470740704717041017401074121074212074121074262107662020/1/28课后习题23LRU算法：4,3,2,1,4,3,5,4,3,2,1,5,M=3时M=4时：页面走向434432432113243543215543243213142143页面走向43443243214324354321543543111243525312M=3时缺页次数为10，缺页率为10/12；M=4时缺页次数为8，缺页率为8/12。增加分配给作业的内存块数，减少了缺页次数，降低了缺页率。21572020/1/28练习在一个请求分页系统中，假定系统分配给一个作业的物理块数为3，并且此作业的页面走向为2,3,2,1,5,2,4,5,3,2,5,2。试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页次数。82020/1/284.7.3Clock置换算法1.简单的Clock置换算法图4-30简单Clock置换算法的流程和示例入口查寻指针前进一步，指向下一个表目页面访问位＝0?选择该页面淘汰是返回置页面访问位＝“0”否块号页号访问位指针0124034215650711替换指针92020/1/28如果它的R位为“0”，表示从上一次页面淘汰以来，到现在它没有被引用过。这就是说，它既老又没用，因此可以把它立即淘汰；如果它的R位为“1”，表示从上一次页面淘汰以来，它被引用过，因此暂时不淘汰它，再给它一次机会。于是将它的R位修改为“0”，然后继续在链表上搜索符合条件的淘汰对象。102020/1/28CLOCK算法的循环链表类似与时钟，用一个指针指向当前最先进入内存的页面。当发生缺页中断并要求页面淘汰时，首先检查指针指向的页面的R位。如果它的R位为“0”，则就把它淘汰，让新的页面进入它原来占用的内存块，并把指针按顺时针方向向前移动一个位置；如果它的R位为“1”，则将其R位清为“0”，然后把指针按顺时针方向向前移动一个位置，去重复这一过程，直到找到一个R位为“0”的页面为止。该算法又称为最近未用算法（NRU）112020/1/28122020/1/282.改进型Clock置换算法由访问位A和修改位M可以组合成下面四种类型的页面：1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。132020/1/28(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。142020/1/281、最少使用（LFU）置换算法最少使用（LFU）置换算法的着眼点是考虑内存块中页面的使用频率，它认为在一段时间里使用得最多的页面，将来用到的可能性就大。因此，当要进行页面淘汰时，总是把当前使用得最少的页面淘汰出去。要实现LFU页面淘汰算法，应该为每个内存中的页面设置一个计数器。对某个页面访问一次，它的计数器就加1。经过一个时间间隔，把所有计数器都清0。产生缺页中断时，比较每个页面计数器的值，把计数器取值最小的那个页面淘汰出去。4.7.2其它置换算法152020/1/282、页面缓冲置换算法（PBA）按照FIFO算法选择需要淘汰的页面，该被淘汰的页面将放入两个链表中的一个：若页面未被修改过，则将它放入空闲页面链表的末尾，否则放入已修改页面的链表的末尾。而这两个表都驻留在内存当中，当该进程以后再次访问这些页面时，只需花费较少的开销，便可使这些页面返回该进程的驻留集中。但当修改页面达一定数量时，再将它们一起(即成簇)写回到磁盘，以减少磁盘的I/O的操作次数，从而减少磁盘访问时间。4.7.2其它置换算法162020/1/28练习程序编制方法2：forj:=1to100fori:=1to100A[i,j]:=0;程序编制方法1：fori:=1to100forj:=1to100A[i,j]:=0;内存分配1个物理块装数据，初始时矩阵数据均不在内存；页面大小为100个整数；矩阵A100X100按行存放。这两个程序执行时分别会产生多少次缺页中断？172020/1/28解程序编制方法2：forj:=1to100fori:=1to100A[i,j]:=0;程序编制方法1：fori:=1to100forj:=1to100A[i,j]:=0;100*100100182020/1/28(1)分配给进程的物理块数(2)页本身的大小(3)程序的编制方法(4)页淘汰算法影响缺页次数的因素192020/1/28练习在页式虚存管理系统中，假定占有m块的进程(初始所有块均为空)，在长为p的页访问串中具有n个不同页号(nm)，试给出缺页次数的上限和下限。页故障数的上限是P，下限是n，因为FIFO淘汰掉最先进来的页，而不管其页面以后是否会用到。极端情况下，可能刚淘汰掉的页又接着要使用。故页故障上限为P；而不同的页至少有一次页故障，故下项为n。202020/1/284.8.1请求分段中的硬件支持1、段表内容存取方式（读，写，执行）修改位（是否修改过，能否移动）存在位（在/不在内存，是否可共享）增补位（是否做过动态增长）外存始址4.8请求分段存储管理方式段名段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址212020/1/28检查内存中是否有足够的空闲空间①若有，则装入该段，修改有关数据结构，中断返回②若没有，检查内存中空闲区的总和是否满足要求，是则应采用紧缩技术，转①；否则，淘汰一（些）段，转①2、缺段中断机构222020/1/283.地址变换机构访问[s][w]w≤段长?符合存取方式?段S在主存?修改访问字段,如写访问,置修改位＝1形成访问主存地址(A)＝(主存始址)＋(位移量w)返回分段越界中断处理分段保护中断处理缺段中断处理是是是否否否图4-32请求分段系统的地址变换过程232020/1/284.8.2分段的共享与保护1.共享段表图4-33共享段表项段名段长内存始址状态外存始址共享进程计数count状态进程名进程号段号存取控制………………共享段表242020/1/282.共享段的分配与回收1)在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count∶=count+1操作，以表明有两个进程共享该段。252020/1/282)当共享此段的某进程不再需要该段时，应将该段释放，包括撤在该进程段表中共享段所对应的表项，以及执行count∶=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，则只是取消调用者进程在共享段表中的有关记录。262020/1/283.分段保护1)越界检查2)存取控制检查(1)只读(2)只执行(3)读/写272020/1/28图4-34环保护机构调用返回调用返回环0环1环2(a)程序间的控制传输数据访问环0环1环2(b)数据访问数据访问3)环保护机构一个程序可以调用驻留在相同环或较高特权环中的服务。一个程序可以访问驻留在相同环或较低特权环中的数据。282020/1/28练习假如一个程序的段表如下，其中存在位为1表示段在内存，存取控制字段中w表示可写，R表示可读，E表示可执行。对下面的指令在执行时会产生什么样的结果段号存在位内存始址段长存取控制其他信息00500100W11100030R213000200E31800080R40500040R292020/1/28练习（1）STORER1,[0,70](2)STORER1,[1,20](3)LOADR1,[3,20](4)LOADR1,[3,100](5)JMP[2,100]段号存在位内存始址段长存取控制其他信息00500100W11100030R213000200E31800080R40500040R缺页中断保护性中断8020越界中断3100302020/1/28练习在内存管理中，“内零头”和“外零头”各指的是什么？在固定式分区分配、动态分区分配、页式虚拟存储系统、段式虚拟存储系统中，存在何种零头？为什么？内零头是指分配给作业的存储空间中未被利用的部分，外零头是指系统中无法利用的小存储块。在固定分区分配中，一个作业的大小并不一定与分区大小相等，因此分区中有一部分存储空间被浪费掉了。所以固定式分区分配中存在内零头。在动态分区分配中，按照一定的分配算法从系统中找出一个能满足作业需求的空闲分区分配给作业，如果这个空闲分区的容量比作业申请的空间大则将该区一分为二，一部分分配给作业，剩下的一部分仍然留作系统的空闲分区。由此可知动态分区存在外零头。312020/1/28练习在内存管理中，“内零头”和“外零头”各指的是什么？在固定式分区分配、动态分区分配、页式虚拟存储系统、段式虚拟存储系统中，存在何种零头？为什么？在页式虚拟存储系统中，用户作业的地址空间被划分为若干大小相等的页面，存储空间也分成与页大小相等的物理块，一般情况作业的大小不可能都是物理块大小的整数倍，因为作业的最后一页中角有部分空间被浪费掉，属内零头。在段式虚拟存储系统中，作业的地址空间由若干个逻辑分段组成，每段分配一个连续的内存区，但各段之间不要求连续，其内存的分配方式类似于动态分区分配。由此可知段式虚拟存储系统中存在外零头。