? ? ?在虛存管理中。當(dāng)發(fā)生缺頁(yè)中斷時(shí)，進(jìn)行頁(yè)面的換入操作。對(duì)于一些不能夠被換出的內(nèi)存，通常采用頁(yè)面鎖定的方式，在頁(yè)表中添加鎖定標(biāo)志位（lock? bit）以區(qū)分該頁(yè)是否是常駐內(nèi)存。當(dāng)內(nèi)存滿(mǎn)需要換出時(shí)，為了減少缺頁(yè)頻率通常由幾種頁(yè)面置換算法。例如、最優(yōu)頁(yè)面置換算法、先進(jìn)先出算法、最近最久未使用算法、時(shí)鐘頁(yè)面置換算法、二次機(jī)會(huì)法等。

目錄

一、最優(yōu)頁(yè)面置換算法（OPT）

二、先進(jìn)先出算法（FIFO）

三、最近最久未使用方法（LRU）

四、時(shí)鐘頁(yè)面置換算法。（Clock）

五、二次機(jī)會(huì)法

六、最不常用法（LFU）

七、Belady現(xiàn)象

---

一、最優(yōu)頁(yè)面置換算法（OPT）

? ? ?離下次訪(fǎng)問(wèn)最久的頁(yè)進(jìn)行置換。這是一個(gè)理想的置換算法。在現(xiàn)實(shí)系統(tǒng)中幾乎是無(wú)法實(shí)現(xiàn)的。它通過(guò)頁(yè)幀存放變量，用某個(gè)東西來(lái)計(jì)算出下次訪(fǎng)問(wèn)的時(shí)長(zhǎng)。替換“將來(lái)”最久未使用的頁(yè)。

?

二、先進(jìn)先出算法（FIFO）

? ? ? 判斷哪一個(gè)頁(yè)在內(nèi)存中存留的時(shí)間最長(zhǎng)，并淘汰掉。通常用隊(duì)列或者鏈表來(lái)實(shí)現(xiàn)。例如在隊(duì)列中記錄頁(yè)號(hào)，隊(duì)列頭的頁(yè)存放的時(shí)間最長(zhǎng)，最先淘汰，把置換進(jìn)來(lái)的頁(yè)面對(duì)應(yīng)的頁(yè)號(hào)加入近隊(duì)列尾。此方法性能較差并且有belady現(xiàn)象，被換出的頁(yè)面可能是被經(jīng)常訪(fǎng)問(wèn)的頁(yè)面。性能差，很少用于實(shí)際應(yīng)用中。替換“活”得最久的頁(yè)。

三、最近最久未使用方法（LRU）

? ? ? 當(dāng)需要頁(yè)面置換時(shí)，判斷哪一個(gè)頁(yè)號(hào)最近一次使用的時(shí)間離當(dāng)前最久，則該頁(yè)被換出。即哪一個(gè)頁(yè)“荒廢”的最久，則被換出。此方法，需要記錄每一個(gè)頁(yè)幀記入未被引用的次數(shù)，當(dāng)被引用時(shí)次數(shù)歸零?；蛘呖梢杂面湵韺?shí)現(xiàn)，把最近訪(fǎng)問(wèn)的頁(yè)號(hào)插入/移動(dòng)到鏈頭，置換時(shí)換出鏈尾。LRU算法也是一個(gè)性能比較差的算法。

?

四、時(shí)鐘頁(yè)面置換算法。（Clock）

? ? ? 是LRU的一個(gè)近似，FIFO的一種改進(jìn)。利用頁(yè)表項(xiàng)中的訪(fǎng)問(wèn)位 used bit，當(dāng)一個(gè)頁(yè)面被裝入內(nèi)存時(shí)，訪(fǎng)問(wèn)位會(huì)被初始化為0，當(dāng)CPU對(duì)該頁(yè)進(jìn)行訪(fǎng)問(wèn)時(shí)，CPU會(huì)把訪(fǎng)問(wèn)位置1。修改訪(fǎng)問(wèn)位可以由CPU硬件自動(dòng)操作，當(dāng)然訪(fǎng)問(wèn)位可以由操作系統(tǒng)主動(dòng)操作。具體實(shí)現(xiàn)邏輯為： 把所有頁(yè)號(hào)組成一個(gè)環(huán)形鏈表（像時(shí)鐘一樣），最初把指針指向“最老”的頁(yè)面，當(dāng)缺頁(yè)中斷時(shí)，如果指針?biāo)傅捻?yè)表項(xiàng)的訪(fǎng)問(wèn)位為0，則置換該頁(yè)，如果訪(fǎng)問(wèn)位為1，則將此頁(yè)的訪(fǎng)問(wèn)位置0后 。移動(dòng)指針到下一個(gè)頁(yè)表，判斷訪(fǎng)問(wèn)位是否為0，重復(fù)操作，直到有頁(yè)被換出。 可以說(shuō)，Clock算法由環(huán)形鏈表、FIFO、和訪(fǎng)問(wèn)位完成的。

五、二次機(jī)會(huì)法

? ? 在頁(yè)表項(xiàng)中有一個(gè)dirty bit，用來(lái)記錄是否進(jìn)行過(guò)寫(xiě)操作，CPU進(jìn)行寫(xiě)內(nèi)存操作時(shí)，會(huì)自動(dòng)將次位改1。而訪(fǎng)問(wèn)位，讀和寫(xiě)都會(huì)被CPU置1.當(dāng)然，這個(gè)位也可被操作系統(tǒng)修改。而二次機(jī)會(huì)法在Clock法上多了一個(gè)bit位，即dirtybit。如果兩個(gè)bit都是零就會(huì)被替換出去，先置訪(fǎng)問(wèn)位，后置臟位。

?

六、最不常用法（LFU）

? ? ? 最不常用并不是說(shuō)這個(gè)算法不常用，而是這個(gè)策略是置換最不常用的算法。把最少訪(fǎng)問(wèn)的頁(yè)給置換出去，需要一個(gè)計(jì)數(shù)器來(lái)記錄訪(fǎng)問(wèn)頁(yè)的次數(shù)。LRU是最久未訪(fǎng)問(wèn)，LFU為最少被訪(fǎng)問(wèn)。這個(gè)算法的缺陷是，當(dāng)執(zhí)行某一段新程序段時(shí)，老頁(yè)可能之前被頻繁訪(fǎng)問(wèn)，但是在未來(lái)中不去訪(fǎng)問(wèn)，LFU也很長(zhǎng)一段時(shí)間也不會(huì)被置換出去。

?

七、Belady現(xiàn)象

? ? ? ?即分配的物理頁(yè)越多，產(chǎn)生缺頁(yè)中斷的次數(shù)反而越多。例如FIFO。主要原因是，算法并不是為了保留將來(lái)即將訪(fǎng)問(wèn)的物理頁(yè)，算法與程序執(zhí)行邏輯無(wú)關(guān)。

看看LRU算法：

?

總結(jié)

以上是生活随笔為你收集整理的操作系统原理：页置换算法，FIFO，LRU，Clock，LFU，二次机会法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。