可能是最全的頁面置換算法總結(jié)了

1、最佳置換法（OPT）

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

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

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

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

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

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

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

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

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

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

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

4、時鐘置換算法（CLOCK）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6、總結(jié)

算法規(guī)則優(yōu)缺點OPT優(yōu)先淘汰最長時間內(nèi)不會被訪問的頁面缺頁率最小，性能最好；但無法實現(xiàn)FIFO優(yōu)先淘汰最先進入內(nèi)存的頁面實現(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文檔下載方式公眾號后臺回復(fù)逆襲進大廠即可拿到最新版的 PDF 啦，我會不斷堅持更新第 3 版、第 4 版，直到第 N 版的。