缺頁(yè)中斷：在請(qǐng)求分頁(yè)系統(tǒng)中，可以通過(guò)查詢頁(yè)表中的狀態(tài)位來(lái)確定所要訪問(wèn)的頁(yè)面是否存在于內(nèi)存中。每當(dāng)所要訪問(wèn)的頁(yè)面不在內(nèi)存是，會(huì)產(chǎn)生一次缺頁(yè)中斷，此時(shí)操作系統(tǒng)會(huì)根據(jù)頁(yè)表中的外存地址在外存中找到所缺的一頁(yè)，將其調(diào)入內(nèi)存。

缺頁(yè)本身是一種中斷，與一般的中斷一樣，需要經(jīng)過(guò)4個(gè)處理步驟：

1、保護(hù)CPU現(xiàn)場(chǎng)

2、分析中斷原因

3、轉(zhuǎn)入缺頁(yè)中斷處理程序進(jìn)行處理

4、恢復(fù)CPU現(xiàn)場(chǎng)，繼續(xù)執(zhí)行

但是缺頁(yè)中斷是由于所要訪問(wèn)的頁(yè)面不存在于內(nèi)存時(shí)，由硬件所產(chǎn)生的一種特殊的中斷，因此，與一般的中斷存在區(qū)別：

1、在指令執(zhí)行期間產(chǎn)生和處理缺頁(yè)中斷信號(hào)

2、一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁(yè)中斷

3、缺頁(yè)中斷返回是，執(zhí)行產(chǎn)生中斷的一條指令，而一般的中斷返回是，執(zhí)行下一條指 ???令。

?

最佳（Optimal）置換算法是指其所選擇的淘汰頁(yè)面，將是以后永不使用的，或許是在最長(zhǎng)（未來(lái)）時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通常可保證獲得最低的缺頁(yè)率。但由于人們目前還無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法是無(wú)法實(shí)現(xiàn)的，但可以利用該算法去評(píng)價(jià)其他算法。?

?

?

先進(jìn)先出（FIFO）置換算法是最簡(jiǎn)單的頁(yè)面置換算法。這種算法的基本思想：當(dāng)需要淘汰一個(gè)頁(yè)面是，總是選擇主流駐村時(shí)間最長(zhǎng)的頁(yè)面進(jìn)行淘汰，即先進(jìn)入主存的頁(yè)面先淘汰。其理由是最早調(diào)入主存的頁(yè)面不在被使用的可能性最大。該算法會(huì)淘汰經(jīng)常訪問(wèn)的頁(yè)面，不直營(yíng)進(jìn)程實(shí)際運(yùn)行的規(guī)律，目前已很少使用。

?

個(gè)人認(rèn)為第二張表比較好理解。

?

?

?

Belady異常：一般來(lái)說(shuō)，分配給進(jìn)程的物理塊越多，運(yùn)行時(shí)的缺頁(yè)次數(shù)應(yīng)該越少，使用FIFO是，存在相反情況，分配4個(gè)物理塊的缺頁(yè)竟然比3個(gè)物理塊的缺頁(yè)次數(shù)還多。不過(guò)LRU和OPT算法永遠(yuǎn)不會(huì)出現(xiàn)Belady異常。

?

?

?

?

最近最久未使用（LRU）置換算法：利用局部性原理，根據(jù)一個(gè)作業(yè)在執(zhí)行過(guò)程中過(guò)去的頁(yè)面訪問(wèn)歷史來(lái)推測(cè)未來(lái)的行為。它認(rèn)為過(guò)去一段時(shí)間里不曾被訪問(wèn)過(guò)的頁(yè)面，在最近的將來(lái)可能也不會(huì)再被訪問(wèn)。所以，這種算法的實(shí)質(zhì)是當(dāng)需要淘汰一個(gè)頁(yè)面時(shí)，總選擇在最近一段時(shí)間內(nèi)最久不用的頁(yè)面予以淘汰。LRU算法普遍地適用于各種類型的程序，但是系統(tǒng)要時(shí)時(shí)刻刻對(duì)各頁(yè)的訪問(wèn)歷史情況加以記錄和更新，開(kāi)銷太大，因此LRU算法必須要有硬件支持。

?

個(gè)人認(rèn)為第二張表比較好理解。

?

?

?

?

?

時(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算法是給每一幀關(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)算法。

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

1、最近未被訪問(wèn)，也未被修改（u=0, m=0）

2、最近被訪問(wèn)，但未被修改（u=1, m=0）

3、最近未被訪問(wèn)，但被修改（u=0, m=1）

4、最近被訪問(wèn)，被修改（u=1, m=1）

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

1、從指針的當(dāng)前位置開(kāi)始，掃描幀緩沖區(qū)。在這次掃描過(guò)程中，對(duì)使用為不做任何修改。選擇遇到的第一個(gè)幀（u=0, m=0）用于替換。

2、如果第一步失敗，則重新掃描，查找（u=0, m=1）的幀。選擇遇到的第一個(gè)這樣的幀用于替換。在這個(gè)掃描過(guò)程中，對(duì)每個(gè)跳過(guò)的幀，把它的使用位設(shè)置成0。

3、如果第二步失敗，指針將回到它的最初位置，并且集合中所有幀的使用位均為0.重復(fù)第一步，并且如果有必要，重復(fù)第二步。這樣將可以找到供替換的幀。

?

改進(jìn)型的CLOCK算法由于簡(jiǎn)單CLOCK算法之處在于替換時(shí)首選沒(méi)有變化的頁(yè)。由于修改的頁(yè)在被替換之前必須寫回。

?

?

?

?

??????????????

時(shí)鐘置換算法（CLOCK）例題：

?

?一個(gè)作業(yè)的物理塊數(shù)為3，此作業(yè)的頁(yè)面走向?yàn)?#xff1a;3,4,2,6,4,3,7,4,3,6,3,4,8,4,6

內(nèi)存及控制信息			輸入串	指針移動(dòng)情況及幀替換信息	是否缺頁(yè)？
內(nèi)存	訪問(wèn)位	指針	3	內(nèi)存中沒(méi)有3，需要找到一個(gè)幀放入3， 指針?biāo)傅奈恢们『糜性L問(wèn)位為0的， 于是就淘汰這個(gè)幀，指針下移	√
?	0	←
?	0	?
?	0	?
內(nèi)存	訪問(wèn)位	指針	4	內(nèi)存中沒(méi)有4，需要找到一個(gè)幀放入4， 指針?biāo)傅奈恢们『糜性L問(wèn)位為0的， 于是就淘汰這個(gè)幀，指針下移	√
3	1	?
?	0	←
?	0	?
內(nèi)存	訪問(wèn)位	指針	2	內(nèi)存中沒(méi)有2，需要找到一個(gè)幀放入2， 指針?biāo)傅奈恢们『糜性L問(wèn)位為0的， 于是就淘汰這個(gè)幀，指針下移	√
3	1	?
4	1	?
?	0	←
內(nèi)存	訪問(wèn)位	指針	6	內(nèi)存中沒(méi)有6，需要找到一個(gè)幀放入6， 指針?biāo)傅奈恢玫脑L問(wèn)位為1， 將其變成0，再下移	√
3	1	←
4	1	?
2	1	?
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢玫脑L問(wèn)位仍為1， 將其變成0，再下移
3	0	?
4	1	←
2	1	?
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢玫脑L問(wèn)位仍為1， 將其變成0，再下移（回到開(kāi)頭）
3	0	?
4	0	?
2	1	←
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢们『糜性L問(wèn)位為0的， 于是就淘汰這個(gè)幀，指針下移
3	0	←
4	0	?
2	0	?
內(nèi)存	訪問(wèn)位	指針	4	內(nèi)存中有4，于是4所在幀的訪問(wèn)位變?yōu)?， 指針下移	×
6	1	?
4	0	←
2	0	?
內(nèi)存	訪問(wèn)位	指針	3	內(nèi)存中沒(méi)有3，需要找到一個(gè)幀放入3， 指針?biāo)傅奈恢们『糜性L問(wèn)位為0的， 于是就淘汰這個(gè)幀，指針下移	√
6	1	?
4	1	?
2	0	←
內(nèi)存	訪問(wèn)位	指針	7	內(nèi)存中沒(méi)有7，需要找到一個(gè)幀放入7， 指針?biāo)傅奈恢玫脑L問(wèn)位為1， 將其變成0，再下移	√
6	1	←
4	1	?
3	1	?
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢玫脑L問(wèn)位仍為1， 將其變成0，再下移
6	0	?
4	1	←
3	1	?
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢玫脑L問(wèn)位仍為1， 將其變成0，再下移（回到開(kāi)頭）
6	0	?
4	0	?
3	1	←
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢们『糜性L問(wèn)位為0的， 于是就淘汰這個(gè)幀，指針下移
6	0	←
4	0	?
3	0	?
內(nèi)存	訪問(wèn)位	指針	4	內(nèi)存中有4，于是4所在幀的訪問(wèn)位變?yōu)?， 指針下移	×
7	1	?
4	0	←
3	0	?
內(nèi)存	訪問(wèn)位	指針	3	內(nèi)存中有3，于是3所在幀的訪問(wèn)位變?yōu)?， 指針下移（回到開(kāi)頭）	×
7	1	?
4	1	?
3	0	←
內(nèi)存	訪問(wèn)位	指針	6	內(nèi)存中沒(méi)有6，需要找到一個(gè)幀放入6， 指針?biāo)傅奈恢玫脑L問(wèn)位為1， 將其變成0，再下移	√
7	1	←
4	1	?
3	1	?
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢玫脑L問(wèn)位仍為1， 將其變成0，再下移
7	0	?
4	1	←
3	1	?
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢玫脑L問(wèn)位仍為1， 將其變成0，再下移（回到開(kāi)頭）
7	0	?
4	0	?
3	1	←
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢们『糜性L問(wèn)位為0的， 于是就淘汰這個(gè)幀，指針下移
7	0	←
4	0	?
3	0	?
內(nèi)存	訪問(wèn)位	指針	3	內(nèi)存中有3，于是3所在幀的訪問(wèn)位變?yōu)?， 指針下移	×
6	1	?
4	0	←
3	0	?
內(nèi)存	訪問(wèn)位	指針	4	內(nèi)存中有4，于是4所在幀的訪問(wèn)位變?yōu)?， 指針下移	×
6	1	←
4	0	?
3	1	?
內(nèi)存	訪問(wèn)位	指針	8	內(nèi)存中沒(méi)有8，需要找到一個(gè)幀放入8， 指針?biāo)傅奈恢玫脑L問(wèn)位為1， 將其變成0，再下移（回到開(kāi)頭）	√
6	1	?
4	1	?
3	1	←
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢玫脑L問(wèn)位仍為1， 將其變成0，再下移
6	1	←
4	1	?
3	0	?
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢玫脑L問(wèn)位仍為1， 將其變成0，再下移
6	0	?
4	1	←
3	0	?
內(nèi)存	訪問(wèn)位	指針		指針?biāo)傅奈恢们『糜性L問(wèn)位為0的， 于是就淘汰這個(gè)幀，指針下移（回到開(kāi)頭）
6	0	?
4	0	?
3	0	←
內(nèi)存	訪問(wèn)位	指針	4	內(nèi)存中有4，于是4所在幀的訪問(wèn)位變?yōu)?， 指針下移	×
6	0	←
4	0	?
8	1	?
內(nèi)存	訪問(wèn)位	指針	6	內(nèi)存中有6，于是6所在幀的訪問(wèn)位變?yōu)?， 指針下移	×
6	0	?
4	1	?
8	1	←
內(nèi)存	訪問(wèn)位	指針	結(jié)束	完成	缺頁(yè)8次
6	1	?
4	1	←
8	1

?

?

總結(jié)

以上是生活随笔為你收集整理的缺页中断处理算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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