16页面置换算法

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

页面置换算法第四章存储器管理4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法页面置换算法上节回顾1.虚拟存储器:定义:P126特征:多次性、对换性、虚拟性P1272.请求分页存储管理:硬件支持:页表机制、缺页中断机构、地址变换机构物理块分配策略与算法页面置换算法4.6.2内存分配策略和分配算法1.最小物理块数的确定页面置换算法2.物理块的分配策略在请求分页系统中,可采取两种内存分配策略,即固定和可变分配策略。在进行置换时,也可采取两种策略,即全局置换和局部置换。于是可组合出以下三种适用的策略。1)固定分配局部置换(FixedAllocation,LocalReplacement)2)可变分配全局置换(VariableAllocation,GlobalReplacement)3)可变分配局部置换(VariableAllocation,LocalReplacemen页面置换算法3.物理块分配算法1)这是将系统中所有可供分配的物理块,平均分配给各个进程。例如,当系统中有100个物理块,有5个进程在运行时,每个进程可分得20个物理块。这种方式貌似公平,但实际上是不公平的,因为它未考虑到各进程本身的大小。如有一个进程其大小为200页,只分配给它20个块,这样,它必然会有很高的缺页率;而另一个进程只有10页,却有10个物理块闲置未用。页面置换算法2)这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程,每个进程的页面数为Si,则系统中各进程页面数的总和为:又假定系统中可用的物理块总数为m,则每个进程所能分到的物理块数为bi,将有:b应该取整,它必须大于最小物理块数。niiSS1mSSbii页面置换算法3)在实际应用中,为了照顾到重要的、紧迫的作业能尽快地完成,应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分:一部分按比例地分配给各进程;另一部分则根据各进程的优先权,适当地增加其相应份额后,分配给各进程。在有的系统中,如重要的实时控制系统,则可能是完全按优先权来为各进程分配其物理块的。页面置换算法4.6.31.何时调入页面页面置换算法2.从何处调入页面在请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区。通常,由于对换区是采用连续分配方式,而事件是采用离散分配方式,故对换区的磁盘I/O速度比文件区的高。这样,每当发生缺页请求时,系统应从何处将缺页调入内存,页面置换算法页面置换算法3.页面调入过程I.页面未在内存时,向CPU发出缺页中断II.中断处理程序保留CPU环境,转入缺页中断处理程序。III.该程序通过查找页表,得到该页在外存的物理块IV.能容纳新页,启动磁盘I/O将缺页调入内存,修改页表。V.内存已满,选出准备换出的页面VI.如果此页已被修改,将它写回磁盘VII.把所缺的页调入内存,修改页表中的相应表项,存在位为“1”,并将此页表项写入快表中。VIII.形成所要访问数据的物理地址,再去访问内存数据。页面置换算法4.7页面置换算法1.2.先进先出算法3.LRU算法4.Clock算法5.其他算法页面置换算法页面置换算法的设计目标具有较低的页面更换频率换出以后不再访问的页面或者较长时间不再使用的页面页面置换算法4.7.11.最佳(Optimal)Belady于1966年提出的一种理论上的算法,思想是选择的被淘汰页面以后将永不使用,或者在最长(未来)时间内不再被访问。页面置换算法假定系统为某进程分配了三个物理块,并考虑有以下7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1进程运行时,先将7,0,1三个页面装入内存。以后,当进程要访问页面2时,将会产生缺页中断。此时OS根据最佳置换算法,将选择页面7予以淘汰。引用率70770170122010320304243230321201201770101页框(物理块)203页面置换算法1.最佳(Optimal)置换算法优缺点选择被置换的页面将是不再访问的或者较长时间不再使用的优点:可保证最低的缺页率缺点:不可能很真正实现,只可作为其他算法的评价参考特点:“往后看”,看未来,因此不可行页面置换算法2.先进先出(FIFO)引用率70770170122010323104430230321013201770201页框2304204230230127127011淘汰最先进入内存的页面,即选择内存驻留时间最长的页面。需要使用替换指针页面置换算法2.先进先出(FIFO)页面置换算法优缺点优点:算法简单缺点:性能不佳特点:只看“先后顺序”页面置换算法4.7.2最近最久未使用(LRU)置换算法1.算法描述选择最近最久未使用的页面。使用访问字段页面置换算法1.LRU置换算法引用率70770170122010320304403230321132201710701页框402432032102假定系统为某进程分配了三个物理块,并考虑有以下页面置换算法1.LRU置换算法优缺点优点:性能较好缺点:需要较多硬件支持特点:“向前看”,看过去的使用情况页面置换算法2.LRU置换算法的硬件支持LRU算法需要的元素1、进程各个页面有多久未被访问2、如何快速找到最近最久未使用的页面页面置换算法1)1、使用移位寄存器记录某进程在内存中每页的使用情况2、数据格式:R=Rn-1Rn-2Rn-3…R2R1R03、页面被访问一次,最高位Rn-1置1,每隔一定时间,寄存器右移一位4、R值最小的页面是被置换页面页面置换算法某进程具有8个页面时的LRU访问情况页面置换算法2)栈1、采用特殊的栈来保存当前使用的各个页面号2、栈顶保留的是最新被访问的页3、栈底保留的是最久未被访问的页,即置换目标页面置换算法4474707407047170410174010741210742120741210742621076页面置换算法练习在一个请求分页系统中,假定系统分配给一个进程的内存块数为3,进程的页面走向为2,3,2,1,5,2,4,5,3,2,5,2。试用最近最久未使用置换算法(LRU),请画图表示访问过程中发生的页面置换过程,并计算缺页次数。(假定开始时,物理块为空,每次调入页面都作为一次缺页处理)页面置换算法4.7.3Clock置换算法1.简单的Clock置换算法Clock置换算法是LRU算法的近似算法,也称为最近未用算法。在简单的Clock算法中,为每页设置一访问位,当被访问则设置为1,未访问为0。页面置换算法1.简单的Clock置换算法入口查寻指针前进一步,指向下一个表目页面访问位=0?选择该页面淘汰是返回置页面访问位=“0”否块号页号访问位指针0124034215650711替换指针页面置换算法1类(A=0,M=0):最近未被访问,又未被修改,最佳淘汰页。2类(A=0,M=1):最近未被访问,但已被修改页。3类(A=1,M=0):最近已被访问,但未被修改。4类(A=1,M=1):最近已被访问且被修改,最不应淘汰页。访问位A和修改位M可以组合成下面四种类型的页面页面置换算法1、从当前指针位置开始扫描循环队列,寻找第1类页面,不改变访问位A。2、第一步失败,寻找第2类页面,将所遇到的第一个这类页面作为淘汰页。将所有扫描过的页面的访问位A都置0。3、第二步也失败,重复第一步,如果仍失败,必要时再重复第二步,此时就一定能找到被淘汰的页。页面置换算法页面置换算法改进型Clock置换算法优缺点优点:减少了磁盘的I/O操作次数缺点:可能需要几轮扫描,增加了系统开销特点:使用两个指标判断,访问位+修改位页面置换算法练习已知某进程有4页在内存,页码为0,1,2,3,其A、M位分别为(1,1)(1,1),(0,1),(1,1),当前指针指向2号页,若采用改进型Clock置换算法,选择哪页淘汰?选择完成后,四个页的A、M位分别为多少?页面置换算法4.7.4其它置换算法1.最少使用(LFU:LeastFrequentlyUsed)置换算法对每个页面设置一个字段(移位寄存器),用来记录页面被访问的频率若用移位寄存器实现算法,LFU与LRU的访问图是完全相同的。页面置换算法2.页面缓冲算法(PBA:PageBufferingAlgorithm)采用可变分配和局部置换方式当一个进程换进换出频率很低时,选择页面淘汰,以备其他进程使用被淘汰页面若发生修改,放入已修改链表,否则放入空闲链表页面置换算法总结1、LRU算法、Clock算法2、了解各种算法的特点3、作业

1 / 37
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功