第四章存储器管理4.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,上节内容回顾,虚拟存储器的引入,局部性原理,虚拟存储器的实现方法,虚拟存储器的特征,多次性 对换性 虚拟性,请求分页存储方式,4.7,页面置换算法,一、问题的引入,内存不足的时候，要进行页面的对换,抖动,当某一页需要调入内存，而内存空间不足时，需将内存中的一页置换到外存上，而被换出的页很快又要被访问，须再次换入。当频繁发生上述情况时，称作抖动。,不能盲目的对换，要设计一定的算法,页面使用顺序,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,第一块,第二块,第三块,缺页中断,7,7,0,7,0,1,二、最佳置换算法,2,0,1,2,0,1,2,0,3,2,0,3,2,4,3,2,0,3,2,0,1,7,0,1,算法发生页面置换的次数是,6,次,算法只是一个理论上的方法，没法具体实现，因为进程访问内存序列未知,作为其他算法衡量的一个依据,三、先进先出置换算法（,FIFO,）,页面使用,顺序,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,第一物理块,7,7,7,2,2,2,2,4,4,4,0,0,0,0,0,0,0,7,7,7,第二物理块,0,0,0,0,3,3,3,2,2,2,2,2,1,1,1,1,1,0,0,第三物理块,1,1,1,1,0,0,0,3,3,3,3,3,2,2,2,2,2,1,页面置换次数,12,次,比较差的一种方法,三、最近最久未使用置换算法（,LRU,）,根据局部性原理，近来未用的，将来也可能不使用,利用,访问字段,，记录页面上次访问的时间,替换当前最长时间内没有被访问的页面,页面使用,顺序,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,第一物理块,7,7,7,2,2,2,2,4,4,4,0,0,0,1,1,1,1,1,1,1,第二物理块,0,0,0,0,0,0,0,0,3,3,3,3,3,3,0,0,0,0,0,第三物理块,1,1,1,3,3,3,2,2,2,2,2,2,2,2,2,7,7,7,2.LRU,置换算法的硬件支持,1),寄存器,为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器,，可表示为,R=R,n-1,R,n-2,R,n-3,R,2,R,1,R,0,图,4-28,某进程具有,8,个页面时的,LRU,访问情况,2),栈,图,4-29,用栈保存当前使用页面时栈的变化情况,四、,Clock,置换算法,1.,简单的,Clock,置换算法,图,4-30,简单,Clock,置换算法的流程和示例,2.,改进型,Clock,置换算法,由访问位,A,和修改位,M,可以组合成下面四种类型的页面：,1,类,(A=0,M=0):,表示该页最近既未被访问，又未被修改，是最佳淘汰页。,2,类,(A=0,M=1),：,表示该页最近未被访问，但已被修改，并不是很好的淘汰页。,3,类,(A=1,M=0),：,最近已被访问，但未被修改，该页有可能再被访问。,4,类,(A=1,M=1):,最近已被访问且被修改，该页可能再被访问。,其执行过程可分成以下三步：,(1),从指针所指示的当前位置开始，扫描循环队列，寻找,A=0,且,M=0,的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位,A,。,(2),如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找,A=0,且,M=1,的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置,0,。,(3),如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复,0,。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能,找到被淘汰的页。,4.7.4,其它置换算法,最少使用,(LFU,：,Least Frequently Used),置换算法,2.,页面缓冲算法,(PBA,：,Page Buffering Algorithm),作业,按列连续存放呢？,思考：增加内存块数，一定会减少缺页率吗？,