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

1、最佳置換法（OPT）

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

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

2、先進(jìn)先出置換算法（FIFO）

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

Belady 異�！�當(dāng)為進(jìn)程分配的物理塊數(shù)增大時(shí)，缺頁(yè)次數(shù)不減反增的異�，F(xiàn)象。

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

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

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

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

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

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

4、時(shí)鐘置換算法（CLOCK）

最佳置換算法性 OPT 能最好，但無(wú)法實(shí)現(xiàn)；先進(jìn)先出置換算法實(shí)現(xiàn)簡(jiǎn)單，但算法性能差；最近最久未使用置換算法性能好，是最接近 OPT 算法性能的，但是實(shí)現(xiàn)起來(lái)需要專(zhuān)門(mén)的硬件支持，算法開(kāi)銷(xiāo)大。

所以操作系統(tǒng)的設(shè)計(jì)者嘗試了很多算法，試圖用比較小的開(kāi)銷(xiāo)接近 LRU 的性能，這類(lèi)算法都是 CLOCK 算法的變體，因?yàn)樗惴ㄒ�循環(huán)掃描緩沖區(qū)像時(shí)鐘一樣轉(zhuǎn)動(dòng)。所以叫clock算法。

時(shí)鐘置換算法是一種性能和開(kāi)銷(xiāo)較均衡的算法，又稱(chēng) CLOCK 算法，或最近未用算法（NRU，Not Recently Used）

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

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

5、改進(jìn)型的時(shí)鐘置換算法

簡(jiǎn)單的時(shí)鐘置換算法僅考慮到一個(gè)頁(yè)面最近是否被訪問(wèn)過(guò)。事實(shí)上，如果被淘汰的頁(yè)面沒(méi)有被修改過(guò)，就不需要執(zhí)行I／O操作寫(xiě)回外存。只有被淘汰的頁(yè)面被修改過(guò)時(shí)，才需要寫(xiě)回外存。

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

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

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

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

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

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

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

6、總結(jié)

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