評(píng)價(jià)一個(gè)算法的優(yōu)劣,可通過(guò)在一個(gè)特定的存儲(chǔ)訪問(wèn)序列（頁(yè)面走向）上運(yùn)行它，并計(jì)算缺頁(yè)數(shù)量來(lái)實(shí)現(xiàn)。

1 先入先出法（FIFO）

最簡(jiǎn)單的頁(yè)面置換算法是先入先出（FIFO）法。這種算法的實(shí)質(zhì)是，總是選擇在主存中停留時(shí)間最長(zhǎng)（即最老）的一頁(yè)置換，即先進(jìn)入內(nèi)存的頁(yè)，先退出內(nèi)存。理由是：最早調(diào)入內(nèi)存的頁(yè)，其不再被使用的可能性比剛調(diào)入內(nèi)存的可能性大。建立一個(gè)FIFO隊(duì)列，收容所有在內(nèi)存中的頁(yè)。被置換頁(yè)面總是在隊(duì)列頭上進(jìn)行。當(dāng)一個(gè)頁(yè)面被放入內(nèi)存時(shí)，就把它插在隊(duì)尾上。
這種算法只是在按線(xiàn)性順序訪問(wèn)地址空間時(shí)才是理想的，否則效率不高。因?yàn)槟切┏１辉L問(wèn)的頁(yè)，往往在主存中也停留得最久，結(jié)果它們因變“老”而不得不被置換出去。
FIFO的另一個(gè)缺點(diǎn)是，它有一種異常現(xiàn)象，即在增加存儲(chǔ)塊的情況下，反而使缺頁(yè)中斷率增加了。當(dāng)然，導(dǎo)致這種異常現(xiàn)象的頁(yè)面走向?qū)嶋H上是很少見(jiàn)的。

2 最優(yōu)置換算法（OPT）

最優(yōu)置換（Optimal Replacement）是在理論上提出的一種算法。其實(shí)質(zhì)是：當(dāng)調(diào)入新的一頁(yè)而必須預(yù)先置換某個(gè)老頁(yè)時(shí)，所選擇的老頁(yè)應(yīng)是將來(lái)不再被使用，或者是在最遠(yuǎn)的將來(lái)才被訪問(wèn)。采用這種頁(yè)面置換算法，保證有最少的缺頁(yè)率。
但是最優(yōu)頁(yè)面置換算法的實(shí)現(xiàn)是困難的，因?yàn)樗枰藗冾A(yù)先就知道一個(gè)進(jìn)程整個(gè)運(yùn)行過(guò)程中頁(yè)面走向的全部情況。不過(guò)，這個(gè)算法可用來(lái)衡量（如通過(guò)模擬實(shí)驗(yàn)分析或理論分析）其他算法的優(yōu)劣。

用最佳頁(yè)面置換法計(jì)算缺頁(yè)次數(shù)

6 5 4 3 5 4 3 6 5 4 5 

－－－－－－－－－－－

6 6 6 3 3 3 3 6 6 6 6 

5 5 5 5 5 5 5 5 5 5 

4 4 4 4 4 4 4 4 4 


僅僅第四列3和第八列6處,缺頁(yè).

第四列處:

opt算法中，頁(yè)面發(fā)生沖突時(shí)，被替換的頁(yè)面是未來(lái)訪問(wèn)最靠后的頁(yè)面。

例子中，第4列處，6的再次訪問(wèn)最靠后，因而6被替換。

之后，第8列處，3被替換是因?yàn)?，4，5中未來(lái)被訪問(wèn)的頁(yè)是4，5。

所以，3被替換。

3 最久未使用算法（LRU）

FIFO算法和OPT算法之間的主要差別是，F(xiàn)IFO算法利用頁(yè)面進(jìn)入內(nèi)存后的時(shí)間長(zhǎng)短作為置換依據(jù)，而OPT算法的依據(jù)是將來(lái)使用頁(yè)面的時(shí)間。如果以最近的過(guò)去作為不久將來(lái)的近似，那么就可以把過(guò)去最長(zhǎng)一段時(shí)間里不曾被使用的頁(yè)面置換掉。它的實(shí)質(zhì)是，當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間里最久沒(méi)有使用過(guò)的頁(yè)面予以置換。這種算法就稱(chēng)為最久未使用算法（Least Recently Used，LRU）。
LRU算法是與每個(gè)頁(yè)面最后使用的時(shí)間有關(guān)的。當(dāng)必須置換一個(gè)頁(yè)面時(shí)，LRU算法選擇過(guò)去一段時(shí)間里最久未被使用的頁(yè)面。
LRU算法是經(jīng)常采用的頁(yè)面置換算法，并被認(rèn)為是相當(dāng)好的，但是存在如何實(shí)現(xiàn)它的問(wèn)題。LRU算法需要實(shí)際硬件的支持。其問(wèn)題是怎么確定最后使用時(shí)間的順序，對(duì)此有兩種可行的辦法：
（1）計(jì)數(shù)器。最簡(jiǎn)單的情況是使每個(gè)頁(yè)表項(xiàng)對(duì)應(yīng)一個(gè)使用時(shí)間字段，并給CPU增加一個(gè)邏輯時(shí)鐘或計(jì)數(shù)器。每次存儲(chǔ)訪問(wèn)，該時(shí)鐘都加1。每當(dāng)訪問(wèn)一個(gè)頁(yè)面時(shí)，時(shí)鐘寄存器的內(nèi)容就被復(fù)制到相應(yīng)頁(yè)表項(xiàng)的使用時(shí)間字段中。這樣我們就可以始終保留著每個(gè)頁(yè)面最后訪問(wèn)的“時(shí)間”。在置換頁(yè)面時(shí)，選擇該時(shí)間值最小的頁(yè)面。這樣做，不僅要查頁(yè)表，而且當(dāng)頁(yè)表改變時(shí)（因CPU調(diào)度）要維護(hù)這個(gè)頁(yè)表中的時(shí)間，還要考慮到時(shí)鐘值溢出的問(wèn)題。
（2）棧。用一個(gè)棧保留頁(yè)號(hào)。每當(dāng)訪問(wèn)一個(gè)頁(yè)面時(shí)，就把它從棧中取出放在棧頂上。這樣一來(lái)，棧頂總是放有目前使用最多的頁(yè)，而棧底放著目前最少使用的頁(yè)。由于要從棧的中間移走一項(xiàng)，所以要用具有頭尾指針的雙向鏈連起來(lái)。在最壞的情況下，移走一頁(yè)并把它放在棧頂上需要改動(dòng)6個(gè)指針。每次修改都要有開(kāi)銷(xiāo)，但需要置換哪個(gè)頁(yè)面卻可直接得到，用不著查找，因?yàn)槲仓羔樦赶驐５祝渲杏斜恢脫Q頁(yè)。
因?qū)崿F(xiàn)LRU算法必須有大量硬件支持，還需要一定的軟件開(kāi)銷(xiāo)。所以實(shí)際實(shí)現(xiàn)的都是一種簡(jiǎn)單有效的LRU近似算法。
一種LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存儲(chǔ)分塊表的每一表項(xiàng)中增加一個(gè)引用位，操作系統(tǒng)定期地將它們置為0。當(dāng)某一頁(yè)被訪問(wèn)時(shí)，由硬件將該位置1。過(guò)一段時(shí)間后，通過(guò)檢查這些位可以確定哪些頁(yè)使用過(guò)，哪些頁(yè)自上次置0后還未使用過(guò)。就可把該位是0的頁(yè)淘汰出去，因?yàn)樵谧罱欢螘r(shí)間里它未被訪問(wèn)過(guò)。

4 第二次機(jī)會(huì)算法（SCR）

第二次機(jī)會(huì)算法的基本思想是與FIFO相同的，但是有所改進(jìn)，避免把經(jīng)常使用的頁(yè)面置換出去。當(dāng)選擇置換頁(yè)面時(shí)，檢查它的訪問(wèn)位。如果是0，就淘汰這頁(yè)；如果訪問(wèn)位是1，就給它第二次機(jī)會(huì)，并選擇下一個(gè)FIFO頁(yè)面。當(dāng)一個(gè)頁(yè)面得到第二次機(jī)會(huì)時(shí)，它的訪問(wèn)位就清為0，它的到達(dá)時(shí)間就置為當(dāng)前時(shí)間。如果該頁(yè)在此期間被訪問(wèn)過(guò)，則訪問(wèn)位置1。這樣給了第二次機(jī)會(huì)的頁(yè)面將不被淘汰，直至所有其他頁(yè)面被淘汰過(guò)（或者也給了第二次機(jī)會(huì)）。因此，如果一個(gè)頁(yè)面經(jīng)常使用，它的訪問(wèn)位總保持為1，它就從來(lái)不會(huì)被淘汰出去。
第二次機(jī)會(huì)算法可視為一個(gè)環(huán)形隊(duì)列。用一個(gè)指針指示哪一頁(yè)是下面要淘汰的。當(dāng)需要一個(gè)存儲(chǔ)塊時(shí)，指針就前進(jìn)，直至找到訪問(wèn)位是0的頁(yè)。隨著指針的前進(jìn)，把訪問(wèn)位就清為0。在最壞的情況下，所有的訪問(wèn)位都是1，指針要通過(guò)整個(gè)隊(duì)列一周，每個(gè)頁(yè)都給第二次機(jī)會(huì)。這時(shí)就退化成FIFO算法了。

頁(yè)面置換算法還有很多變種，如考慮到被置換頁(yè)是否修改過(guò)、按FIFO算法選中的頁(yè)正在使用等情況，都需要硬件、軟件協(xié)同實(shí)現(xiàn)。