可能是最全的頁面置換算法總結了

1、最佳置換法（OPT）

最佳置換算法（OPT，Optimal） ：每次選擇淘汰的頁面將是以后永不使用，或者在最長時間內不再被訪問的頁面，這樣可以保證最低的缺頁率。

最佳置換算法可以保證最低的缺頁率，但實際上，只有在進程執(zhí)行的過程中才能知道接下來會訪問到的是哪個頁面。操作系統(tǒng)無法提前預判頁面訪問序列。因此，最佳置換算法是無法實現(xiàn)的

2、先進先出置換算法（FIFO）

先進先出置換算法（FIFO） ：每次選擇淘汰的頁面是最早進入內存的頁面實現(xiàn)方法：把調入內存的頁面根據(jù)調入的先后順序排成一個隊列，需要換出頁面時選擇隊頭頁面隊列的最大長度取決于系統(tǒng)為進程分配了多少個內存塊。

Belady 異�！�當為進程分配的物理塊數(shù)增大時，缺頁次數(shù)不減反增的異常現(xiàn)象。

只有 FIFO 算法會產(chǎn)生 Belady 異常，而 LRU 和 OPT 算法永遠不會出現(xiàn)Belady異常。另外，F(xiàn)IFO算法雖然實現(xiàn)簡單，但是該算法與進程實際運行時的規(guī)律不適應，因為先進入的頁面也有可能最經(jīng)常被訪問。因此，算法性能差

FIFO的性能較差，因為較早調入的頁往往是經(jīng)常被訪問的頁，這些頁在 FIFO 算法下被反復調入和調出，并且有Belady現(xiàn)象。所謂Belady現(xiàn)象是指：采用 FIFO 算法時，如果對—個進程未分配它所要求的全部頁面，有時就會出現(xiàn)分配的頁面數(shù)增多但缺頁率反而提高的異常現(xiàn)象。

3、最近最久未使用置換算法（LRU）

最近最久未使用置換算法（LRU，least recently used） ：每次淘汰的頁面是最近最久未使用的頁面實現(xiàn)方法：賦予每個頁面對應的頁表項中，用訪問字段記錄該頁面自．上次被訪問以來所經(jīng)歷的時間t（該算法的實現(xiàn)需要專門的硬件支持，雖然算法性能好，但是實現(xiàn)困難，開銷大）。當需要淘汰一個頁面時，選擇現(xiàn)有頁面中t值最大的，即最近最久未使用的頁面。

LRU性能較好，但需要寄存器和棧的硬件支持。LRU是堆棧類算法，理論上可以證明，堆棧類算法不可能出現(xiàn)Belady異常。

在手動做題時，若需要淘汰頁面，可以逆向檢查此時在內存中的幾個頁面號。在逆向掃描過程中最后一個出現(xiàn)的頁號就是要淘汰的頁面。

4、時鐘置換算法（CLOCK）

最佳置換算法性 OPT 能最好，但無法實現(xiàn)；先進先出置換算法實現(xiàn)簡單，但算法性能差；最近最久未使用置換算法性能好，是最接近 OPT 算法性能的，但是實現(xiàn)起來需要專門的硬件支持，算法開銷大。

所以操作系統(tǒng)的設計者嘗試了很多算法，試圖用比較小的開銷接近 LRU 的性能，這類算法都是 CLOCK 算法的變體，因為算法要循環(huán)掃描緩沖區(qū)像時鐘一樣轉動。所以叫clock算法。

時鐘置換算法是一種性能和開銷較均衡的算法，又稱 CLOCK 算法，或最近未用算法（NRU，Not Recently Used）

簡單的 CLOCK 算法實現(xiàn)方法：為每個頁面設置一個訪問位，再將內存中的頁面都通過鏈接指針鏈接成一個循環(huán)隊列。

當某頁被訪問時，其訪問位置為1，當需要淘汰一個頁面時，只需檢查頁的訪問位。如果是0，就選擇該頁換出；如果是1，則將它置為0，暫不換出，繼續(xù)檢查下一個頁面，若第一輪掃描中所有頁面都是1，則將這些頁面的訪問位依次置為0后，再進行第二輪掃描（第二輪掃描中一定會有訪問位為0的頁面，因此簡單的CLOCK算法選擇一個淘汰頁面最多會經(jīng)過兩輪掃描）

5、改進型的時鐘置換算法

簡單的時鐘置換算法僅考慮到一個頁面最近是否被訪問過。事實上，如果被淘汰的頁面沒有被修改過，就不需要執(zhí)行I／O操作寫回外存。只有被淘汰的頁面被修改過時，才需要寫回外存。

因此，除了考慮一個頁面最近有沒有被訪問過之外，操作系統(tǒng)還應考慮頁面有沒有被修改過。在其他條件都相同時，應優(yōu)先淘汰沒有修改過的頁面，避免I／O操作。這就是改進型的時鐘置換算法的思想。修改位＝0，表示頁面沒有被修改過；修改位＝1，表示頁面被修改過。

為方便討論，用（訪問位，修改位）的形式表示各頁面狀態(tài)。如（1， 1）表示一個頁面近期被訪問過，且被修改過。

改進型的Clock算法需要綜合考慮某一內存頁面的訪問位和修改位來判斷是否置換該頁面。在實際編寫算法過程中，同樣可以用一個等長的整型數(shù)組來標識每個內存塊的修改狀態(tài)。訪問位A和修改位M可以組成一下四種類型的頁面。

算法規(guī)則：將所有可能被置換的頁面排成一個循環(huán)隊列

第一輪：從當前位置開始掃描到第一個（A ＝0， M ＝ 0）的幀用于替換。表示該頁面最近既未被訪問，又未被修改，是最佳淘汰頁第二輪：若第一輪掃描失敗，則重新掃描，查找第一個（A ＝0， M ＝ 1）的幀用于替換。本輪將所有掃描過的幀訪問位設為0。表示該頁面最近未被訪問，但已被修改，并不是很好的淘汰頁。第三輪：若第二輪掃描失敗，則重新掃描，查找第一個（A ＝1， M ＝ 0）的幀用于替換。本輪掃描不修改任何標志位。表示該頁面最近已被訪問，但未被修改，該頁有可能再被訪問。第四輪：若第三輪掃描失敗，則重新掃描，查找第一個A ＝1， M ＝ 1）的幀用于替換。表示該頁最近已被訪問且被修改，該頁可能再被訪問。

由于第二輪已將所有幀的訪問位設為0，因此經(jīng)過第三輪、第四輪掃描一定會有一個幀被選中，因此改進型CLOCK置換算法選擇－ －個淘汰頁面最多會進行四輪掃描

算法規(guī)則：將所有可能被置換的頁面排成一個循環(huán)隊列第一輪：從當前位置開始掃描到第－一個（0， 0）的幀用于替換。本輪掃描不修改任何標志位。（第一優(yōu)先級：最近沒訪問，且沒修改的頁面）第二輪：若第一輪掃描失敗，則重新掃描，查找第一個（0， 1）的幀用于替換。本輪將所有掃描過的幀訪問位設為0（第二優(yōu)先級： 最近沒訪問，但修改過的頁面）第三輪：若第二輪掃描失敗，則重新掃描，查找第一個（0， 0）的幀用于替換。本輪掃描不修改任何標志位（第三優(yōu)先級：最近訪問過，但沒修改的頁面）第四輪：若第三輪掃描失敗，則重新掃描，查找第一個（0， 1）的幀用于替換。（第四優(yōu)先級：最近訪問過，且修改過的頁面）由于第二輪已將所有幀的訪問位設為0，因此經(jīng)過第三輪、第四輪掃描一定會有一個幀被選中，因此改進型CLOCK置換算法選擇一個淘汰頁面最多會進行四輪掃描。

6、總結

算法規(guī)則優(yōu)缺點OPT優(yōu)先淘汰最長時間內不會被訪問的頁面缺頁率最小，性能最好；但無法實現(xiàn)FIFO優(yōu)先淘汰最先進入內存的頁面實現(xiàn)簡單；但性能很差，可能出現(xiàn)Belady異常LRU優(yōu)先淘汰最近最久沒訪問的頁面性能很好；但需要硬件支持，算法開銷大CLOCK （NRU）循環(huán)掃描各頁面 第一輪淘汰訪問位＝0的，并將掃描過的頁面訪問位改為1。若第－輪沒選中，則進行第二輪掃描。實現(xiàn)簡單，算法開銷��；但未考慮頁面是否被修改過。改進型CLOCK （改進型NRU）若用（訪問位，修改位）的形式表述，則 第一輪：淘汰（0，0） 第二輪：淘汰（O，1），并將掃描過的頁面訪問位都置為0 第三輪：淘汰（O， 0） 第四輪：淘汰（0， 1）算法開銷較小，性能也不錯PDF文檔下載方式公眾號后臺回復逆襲進大廠即可拿到最新版的 PDF 啦，我會不斷堅持更新第 3 版、第 4 版，直到第 N 版的。