頁(yè)面置換算法
當(dāng)發(fā)生缺頁(yè)中斷時(shí)摘能，如果操作系統(tǒng)內(nèi)存中沒有空閑頁(yè)面沪饺，則操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁(yè)面將其移出內(nèi)存者甲，以便為即將調(diào)入的頁(yè)面讓出空間。而用來選擇淘汰哪一頁(yè)的規(guī)則叫做頁(yè)面置換算法
缺頁(yè)中斷
指的是當(dāng)軟件試圖訪問已映射在虛擬地址空間中慎冤，但是目前并未被加載在物理內(nèi)存中的一個(gè)分頁(yè)時(shí)疼燥，由中央處理器的內(nèi)存管理單元所發(fā)出的中斷。
簡(jiǎn)而言之蚁堤，缺頁(yè)中斷就是要訪問的頁(yè)不在主存醉者，需要操作系統(tǒng)將其調(diào)入主存后再進(jìn)行訪問。
最優(yōu)頁(yè)面置換算法
最理想的狀態(tài)下披诗，我們給頁(yè)面做個(gè)標(biāo)記撬即，挑選一個(gè)最遠(yuǎn)才會(huì)被再次用到的頁(yè)面。當(dāng)然呈队，這樣的算法不可能實(shí)現(xiàn)剥槐，因?yàn)椴淮_定一個(gè)頁(yè)面在何時(shí)會(huì)被用到。
FIFO 及其改進(jìn)
這種算法的思想和隊(duì)列是一樣的宪摧，OS維護(hù)一個(gè)當(dāng)前在內(nèi)存中的所有頁(yè)面的鏈表粒竖，最新進(jìn)入的頁(yè)面在尾部，最久的在頭部几于，每當(dāng)發(fā)生缺頁(yè)中斷蕊苗，就替換掉表頭的頁(yè)面并且把新調(diào)入的頁(yè)面加入到鏈表末尾。
這個(gè)算法的問題沿彭，顯然是太過于“公正了”朽砰，沒有考慮到實(shí)際的頁(yè)面使用頻率。
一種合理的改進(jìn)：即給每個(gè)頁(yè)面增加一個(gè)R位喉刘，每次先從鏈表頭開始查找瞧柔，如果R置位，清除R位并且把該頁(yè)面節(jié)點(diǎn)放到鏈表結(jié)尾饱搏；如果R是0非剃，那么就是又老又沒用到，替換掉推沸。
時(shí)鐘頁(yè)面置換算法（clock）
這種算法只是模型像時(shí)鐘，其實(shí)就是一個(gè)環(huán)形鏈表的第二次機(jī)會(huì)算法券坞，表針指向最老的頁(yè)面鬓催。缺頁(yè)中斷時(shí)，執(zhí)行相同的操作恨锚，包括檢查R位等宇驾。
LRU
Least Recently Used的縮寫，即最近最少使用猴伶，常用于頁(yè)面置換算法和緩存淘汰算法
實(shí)現(xiàn)：
最常見的實(shí)現(xiàn)是使用一個(gè)鏈表保存緩存數(shù)據(jù)课舍；
新數(shù)據(jù)插入到鏈表頭部
每當(dāng)緩存命中（即緩存數(shù)據(jù)被訪問）塌西，則將數(shù)據(jù)移到鏈表頭部
當(dāng)鏈表滿的時(shí)候，將鏈表尾部的數(shù)據(jù)丟棄
