地址映射過(guò)程中宙址，若在頁(yè)面中發(fā)現(xiàn)所要訪問(wèn)的頁(yè)面不再內(nèi)存中霎苗，則產(chǎn)生缺頁(yè)中斷。當(dāng)發(fā)生缺頁(yè)中斷時(shí)操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁(yè)面將其移出內(nèi)存，以便為即將調(diào)入的頁(yè)面讓出空間序苏。而用來(lái)選擇淘汰哪一頁(yè)的規(guī)則叫做頁(yè)面置換算法。常見(jiàn)的置換算法有：
- 最佳置換算法（OPT）（理想置換算法）
這是一種理想情況下的頁(yè)面置換算法捷凄，但實(shí)際上是不可能實(shí)現(xiàn)的忱详。該算法的基本思想是：發(fā)生缺頁(yè)時(shí)，有些頁(yè)面在內(nèi)存中跺涤，其中有一頁(yè)將很快被訪問(wèn)（也包含緊接著的下一條指令的那頁(yè)）匈睁，而其他頁(yè)面則可能要到10、100或者1000條指令后才會(huì)被訪問(wèn)桶错，每個(gè)頁(yè)面都可以用在該頁(yè)面首次被訪問(wèn)前所要執(zhí)行的指令數(shù)進(jìn)行標(biāo)記航唆。最佳頁(yè)面置換算法只是簡(jiǎn)單地規(guī)定：標(biāo)記最大的頁(yè)應(yīng)該被置換。這個(gè)算法唯一的一個(gè)問(wèn)題就是它無(wú)法實(shí)現(xiàn)院刁。當(dāng)缺頁(yè)發(fā)生時(shí)糯钙，操作系統(tǒng)無(wú)法知道各個(gè)頁(yè)面下一次是在什么時(shí)候被訪問(wèn)。雖然這個(gè)算法不可能實(shí)現(xiàn)退腥，但是最佳頁(yè)面置換算法可以用于對(duì)可實(shí)現(xiàn)算法的性能進(jìn)行衡量比較任岸。 - 先進(jìn)先出置換算法（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ì)尾上吴趴。
這種算法只是在按線性順序訪問(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)的。 - 最近最久未使用（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è)面予以置換净赴。這種算法就稱為最久未使用算法（Least Recently Used，LRU）罩润。 - Clock置換算法（LRU算法的近似實(shí)現(xiàn)）
簡(jiǎn)單的CLOCK算法是給每一幀關(guān)聯(lián)一個(gè)附加位玖翅，稱為使用位。當(dāng)某一頁(yè)首次裝入主存時(shí)哨啃，該幀的使用位設(shè)置為1;當(dāng)該頁(yè)隨后再被訪問(wèn)到時(shí)烧栋，它的使用位也被置為1。對(duì)于頁(yè)替換算法拳球，用于替換的候選幀集合看做一個(gè)循環(huán)緩沖區(qū)审姓，并且有一個(gè)指針與之相關(guān)聯(lián)。當(dāng)某一頁(yè)被替換時(shí)祝峻，該指針被設(shè)置成指向緩沖區(qū)中的下一幀魔吐。當(dāng)需要替換一頁(yè)時(shí)扎筒，操作系統(tǒng)掃描緩沖區(qū)，以查找使用位被置為0的一幀酬姆。每當(dāng)遇到一個(gè)使用位為1的幀時(shí)嗜桌，操作系統(tǒng)就將該位重新置為0；如果在這個(gè)過(guò)程開(kāi)始時(shí)辞色，緩沖區(qū)中所有幀的使用位均為0骨宠，則選擇遇到的第一個(gè)幀替換；如果所有幀的使用位均為1,則指針在緩沖區(qū)中完整地循環(huán)一周相满，把所有使用位都置為0层亿，并且停留在最初的位置上，替換該幀中的頁(yè)立美。由于該算法循環(huán)地檢查各頁(yè)面的情況匿又，故稱為CLOCK算法，又稱為最近未用(Not Recently Used, NRU)算法建蹄。 - 最少使用（LFU）置換算法
為每個(gè)頁(yè)面配置一個(gè)計(jì)數(shù)器碌更，一旦某頁(yè)被訪問(wèn)，則將其計(jì)數(shù)器的值加1洞慎，在需要選擇一頁(yè)置換時(shí)痛单，則將選擇其計(jì)數(shù)器值最小的頁(yè)面，即內(nèi)存中訪問(wèn)次數(shù)最少的頁(yè)面進(jìn)行淘汰拢蛋。
