首页 > 代码库 > 页面置换算法

页面置换算法

2024-07-03 05:54:03   225人阅读

最佳(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 搜集整理并修改

自《计算机操作系统（第三版）》（西安电子科技大学出版社），

转载注明出处。

谢谢！


联系
我们