当前位置:Gxlcms > html代码 > 页面置换算法_html/css_WEB-ITnose

页面置换算法_html/css_WEB-ITnose

时间:2021-07-01 10:21:17 帮助过:6人阅读

最佳(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予以淘汰。这是因为页面0将作为第5个被访问的页面,页面1是第14个被访问的页面,而页面7则要在第18次页面访问时才需调入。下次访问页面0时,因它已在内存而不必产生缺页中断。当进程访问页面3时,又将引起页面1被淘汰;因为,它在现有的1,2,0三个页面中,将是以后最晚才被访问的。图4-26示出了采用最佳置换算法时的置换图。由图可看出,采用最佳置换算法发生了 6次页面置换



先进先出(FIFO)页面置换算法


这是最早出现的置换算法。该算法总是 淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法与进程实际运行的规律不相适应,因为在进程中,有些页面经常被访问,FIFO算法并不能保证这些页面不被淘汰。

我们仍用上面的例子,但采用FIFO算法进行页面置换(如下图)。当进程第一次访问页面2时,将把第7页换出,因为它是最先被调入内存的;在第一次访问页面3时,又将把第0页换出,因为它在现有的2,0,1 三个页面中是最老的页。由图4-27 可以看出,利用FIFO算法时进行了 12次页面置换,比最佳置换算法正好多一倍。

注:当第一次将3置换进内存的时候,取而代之的是0而不是1(虽然0在3的前一位刚被访问,但是内存中的0仍旧是比1早到的内存页)






最近最久未使用(LRU)置换算法



最近最久未使用(LRU)的页面置换算法,是根据页面调入内存后的使用情况进行决策的。LRU置换算法是选择 最近最久未使用的页面予以淘汰。该算法赋予每个页面一个 访问字段,用来 记录一个页面自上次被访问以来所经历的时间t,当须淘汰一个页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。

利用LRU算法对上例进行页面置换的结果如图所示。当进程第一次对页面2进行访问时,由于页面7是最近最久未被访问的,故将它置换出去。当进程第一次对页面3进行访问时,第1页成为最近最久未使用的页,将它换出。最佳置换算法是从“向后看”的观点出发的,即它是依据以后各页的使用情况;而LRU算法则是“向前看”的,即根据各页以前的使用情况来判断,而页面过去和未来的走向之间并无必然的联系。













本文由Cout_Sev 搜集整理并修改

自《计算机操作系统(第三版)》(西安电子科技大学出版社),

转载注明出处。

谢谢!

人气教程排行