頁面置換算法

頁面置換算法：

1、 最佳置換算法：這是一種理想化的算法，既選擇哪些是永不使用或者最長時間内不會被通路的頁面置換出去。這種方法性能好，但是難于實作。

例題：假定系統為程序p1配置設定了3個實體塊，該程序通路頁面的順序為“0,7,6,5,7,4,7,3,5,4,7,4,5,6,5,7,6,0,7,6”，利用最佳置換算法的結果如圖所示，圖中x辨別産生缺頁終端，求缺頁次數、頁面隻換次數和缺頁率

根據題意，系統為程序配置設定了3個實體塊，開始為空，是以前三次通路均産生缺頁中斷，第4次通路時需要找到一個實體塊進行清除，根據最佳置換算法的要求，找到0,7，6三個頁面中往後最近一次被通路最晚的，即0，進行替換，以此計算共計産生9次缺頁中斷，缺頁率為9/20=45%

2、 先進先出算法：該算法總是淘汰最先進入主存的頁面，既選擇在主存中駐留時間最久的頁面予以淘汰，概算發實作簡單，隻需把一個程序調入主存的頁面，按先後順序連接配接成一個隊列，并設定一個指針即可，是最直覺性能最差的算法

3、 最近最少未使用置換算法：該算法是選擇最近最少未使用的頁面予以淘汰，系統每個頁面設定一個通路字段，用于記錄這個頁面自上次被通路以來所經曆的時間t，當要淘汰一個頁面時，選擇t最大的頁面，但在是現實需要硬體的支援（寄存器或棧）

4、最近未用置換算法：将最近一段時間未引用過的頁面換出，該算法為每個頁面設定一位通路位，将主存中的所有頁面都通過連結指針連成一個循環隊列，當某頁被通路時，其通路位置1，在選擇一頁淘汰時，檢查其通路位，如果是0，則選擇該頁換出，若為1置為0暫不換出，再循環隊列中檢查下一個頁面，直到通路位為0的頁面為止，由于該算法隻有一位通路位，隻能用它便是該頁是否已經使用過，而置換時是将未使用過的頁面換出去，是以該算法稱為最近未用算法

————————————————

版權聲明：本文為CSDN部落客「不吃帶葉的」的原創文章，遵循CC 4.0 BY-SA版權協定，轉載請附上原文出處連結及本聲明。

原文連結：

https://blog.csdn.net/baidu_38610980/article/details/108238333