進(jìn)程運(yùn)行時(shí)，若其訪問(wèn)的頁(yè)面不在內(nèi)存而需將其調(diào)入，但內(nèi)存已無(wú)空閑空間時(shí)，就需要從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送入磁盤的對(duì)換區(qū)中。

通常，將選擇調(diào)出頁(yè)面的算法稱為頁(yè)面置換算法。置換算法的好壞將直接影響操作系統(tǒng)的性能。下面介紹幾種常見(jiàn)的置換算法：

1 最佳置換算法(OPT)

最佳(Optimal, OPT)置換算法所選擇的被淘汰頁(yè)面是以后永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面，這樣可以保證獲得最低的缺頁(yè)率。但由于人們無(wú)法預(yù)知進(jìn)程頁(yè)面未來(lái)的使用情況，因而該算法無(wú)法實(shí)現(xiàn)。

最佳置換算法可以用來(lái)評(píng)價(jià)其他算法。假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下頁(yè)面號(hào)引用串：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

進(jìn)程運(yùn)行時(shí)，先將7, 0, 1三個(gè)頁(yè)面依次裝入內(nèi)存。進(jìn)程要訪問(wèn)頁(yè)面2時(shí)，產(chǎn)生缺頁(yè)中斷，根據(jù)最佳置換算法，選擇第18次訪問(wèn)才需調(diào)入的頁(yè)面7予以淘汰。然后，訪問(wèn)頁(yè)面0時(shí)，因?yàn)橐言趦?nèi)存中所以不必產(chǎn)生缺頁(yè)中斷。訪問(wèn)頁(yè)面3時(shí)又會(huì)根據(jù)最佳置換算法將頁(yè)面1淘汰，依此類推。

從圖可知，發(fā)生缺頁(yè)中斷的次數(shù)為9，頁(yè)面置換的次數(shù)為6。

2 先進(jìn)先出(FIFO)頁(yè)面置換算法

優(yōu)先淘汰最早進(jìn)入內(nèi)存的頁(yè)面，亦即在內(nèi)存中駐留時(shí)間最久的頁(yè)面。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把調(diào)入內(nèi)存的頁(yè)面根據(jù)先后次序鏈接成隊(duì)列，設(shè)置一個(gè)指針總指向最早的頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行時(shí)的規(guī)律不適應(yīng)，因?yàn)樵谶M(jìn)程中，有的頁(yè)面經(jīng)常被訪問(wèn)。

仍用上面的實(shí)例，釆用FIFO算法進(jìn)行頁(yè)面置換。進(jìn)程訪問(wèn)頁(yè)面2時(shí)，把最早進(jìn)入內(nèi)存的頁(yè)面7換出。然后訪問(wèn)頁(yè)面3時(shí)，再把2, 0, 1中最先進(jìn)入內(nèi)存的頁(yè)換出。由圖可知，利用FIFO算法時(shí)進(jìn)行了 12次頁(yè)面置換，比最佳置換算法正好多一倍。

FIFO算法還會(huì)產(chǎn)生當(dāng)所分配的物理塊數(shù)增大而頁(yè)故障數(shù)不減反增的異?，F(xiàn)象，這是由 Belady于1969年發(fā)現(xiàn)，故稱為Belady異常，如下圖所示。只有FIFO算法可能出現(xiàn)Belady 異常，而LRU和OPT算法永遠(yuǎn)不會(huì)出現(xiàn)Belady異常。

3 最近最久未使用(LRU)置換算法

選擇最近最長(zhǎng)時(shí)間未訪問(wèn)過(guò)的頁(yè)面予以淘汰，它認(rèn)為過(guò)去一段時(shí)間內(nèi)未訪問(wèn)過(guò)的頁(yè)面，在最近的將來(lái)可能也不會(huì)被訪問(wèn)。該算法為每個(gè)頁(yè)面設(shè)置一個(gè)訪問(wèn)字段，來(lái)記錄頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間，淘汰頁(yè)面時(shí)選擇現(xiàn)有頁(yè)面中值最大的予以淘汰。

再對(duì)上面的實(shí)例釆用LRU算法進(jìn)行頁(yè)面置換，如下圖所示。進(jìn)程第一次對(duì)頁(yè)面2訪問(wèn)時(shí)，將最近最久未被訪問(wèn)的頁(yè)面7置換出去。然后訪問(wèn)頁(yè)面3時(shí)，將最近最久未使用的頁(yè)面1換出。

圖中前5次置換的情況與最佳置換算法相同，但兩種算法并無(wú)必然聯(lián)系。實(shí)際上，LRU算法根據(jù)各頁(yè)以前的情況，是“向前看”的，而最佳置換算法則根據(jù)各頁(yè)以后的使用情況，是“向后看”的。

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

4 時(shí)鐘(Clock)置換算法

LRU算法的性能接近于OPT，但是實(shí)現(xiàn)起來(lái)比較困難，且開(kāi)銷大；FIFO算法實(shí)現(xiàn)簡(jiǎn)單，但性能差。所以操作系統(tǒng)的設(shè)計(jì)者嘗試了很多算法，試圖用比較小的開(kāi)銷接近LRU的性能，這類算法都是Clock算法的變體。

簡(jiǎn)單的Clock算法是給每一頁(yè)設(shè)置一個(gè)訪問(wèn)位，再將內(nèi)存中所有頁(yè)面都通過(guò)鏈接指針鏈接成一個(gè)循環(huán)隊(duì)列。當(dāng)某頁(yè)被訪問(wèn)時(shí)，其訪問(wèn)位置1。置換算法在選擇一頁(yè)淘汰時(shí)，只需要檢查頁(yè)的訪問(wèn)位。若是0，則將該頁(yè)換出；若是1，則重新將它置為0，暫時(shí)不換出，給該頁(yè)二次駐留內(nèi)存的機(jī)會(huì)，接著按照FIFO的算法檢查下一個(gè)頁(yè)面。當(dāng)檢查到隊(duì)列中最后一個(gè)頁(yè)面時(shí)，其訪問(wèn)位仍為1，則再放回隊(duì)首區(qū)檢查下一個(gè)頁(yè)面。由于該算法循環(huán)地檢查各頁(yè)面的情況，故稱為Clock算法，又稱為最近未用(Not Recently Used, NRU)算法。

Clock算法的性能比較接近LRU，而通過(guò)增加使用的位數(shù)目，可以使得Clock算法更加高效。在使用位的基礎(chǔ)上再增加一個(gè)修改位M（訪問(wèn)位為設(shè)為A），則得到改進(jìn)型的Clock置換算法。這樣，每一頁(yè)都處于以下四種情況之一：

• 最近未被訪問(wèn)，也未被修改(A=0, M=0)。
• 最近被訪問(wèn)，但未被修改(A=1, M=0)。
• 最近未被訪問(wèn)，但被修改(A=0, M=1)。
• 最近被訪問(wèn)，被修改(A=1, M=1)。

算法執(zhí)行如下操作步驟：

• 從指針的當(dāng)前位置開(kāi)始，掃描循環(huán)隊(duì)列。在這次掃描過(guò)程中，對(duì)使用位不做任何修改。選擇遇到的第一個(gè)(A=0, M=0)頁(yè)，則進(jìn)行置換。
• 如果第1步失敗，則重新掃描，查找(A=0, M=1)頁(yè)。選擇遇到的第一個(gè)這樣的頁(yè)則置換。在這個(gè)掃描過(guò)程中，對(duì)每個(gè)跳過(guò)的頁(yè)，把它的使用位設(shè)置成0。
• 如果第2步失敗，指針將回到它的最初位置，并且集合中所有頁(yè)的使用位均為0。重復(fù)第1步，并且如果有必要，重復(fù)第2步。這樣將可以找到供置換的頁(yè)。

改進(jìn)型的Clock算法優(yōu)于簡(jiǎn)單Clock算法之處在于：替換時(shí)首選沒(méi)有變化的頁(yè)。由于修改過(guò)的頁(yè)在被替換之前必須寫(xiě)回，因而這樣做會(huì)節(jié)省時(shí)間。

5 其他置換算法

還有許多其他進(jìn)行頁(yè)面置換的算法。例如：最少使用置換算法(LFU)、頁(yè)面緩沖算法(PBA)等。

最少使用置換算法(LFU)采用移位寄存器來(lái)記錄頁(yè)面訪問(wèn)頻率，置換一段時(shí)間內(nèi)最少使用的頁(yè)。頁(yè)面緩沖算法(PBA)則通過(guò)空閑物理塊鏈表，使得頁(yè)面在內(nèi)存中不做物理上的移動(dòng)，已修改和未修改的頁(yè)面仍在內(nèi)存中備用。