【正文】 稱 f為 “ 缺頁(yè)中斷率 ” 。 顯然 ， 缺頁(yè)中斷率與缺頁(yè)中斷的次數(shù)有密切的關(guān)系 。 分析起來(lái) ， 影響缺頁(yè)中斷次數(shù)的因素有以下幾種： （ 1）分配給作業(yè)的內(nèi)存塊數(shù)：由于分配給作業(yè)的內(nèi)存塊數(shù)多，因此同時(shí)能夠裝入內(nèi)存的作業(yè)頁(yè)面就多，缺頁(yè)的可能性下降，發(fā)生缺頁(yè)中斷的可能性也就下降。 （ 2）頁(yè)面尺寸：頁(yè)面尺寸是與塊尺寸相同的，因此塊大頁(yè)也就大。頁(yè)面增大了，在每個(gè)內(nèi)存塊里的信息相應(yīng)增加，缺頁(yè)的可能性下降。反之，頁(yè)面尺寸減少，每塊里的信息減少，缺頁(yè)的可能性上升。 （ 3）程序的實(shí)現(xiàn)：作業(yè)程序的編寫方法，對(duì)缺頁(yè)中斷產(chǎn)生的次數(shù)也會(huì)有影響。下面通過(guò)一個(gè)例子來(lái)說(shuō)明這個(gè)問題。 頁(yè)面淘汰算法 發(fā)生缺頁(yè)時(shí) ， 就要從輔存上把所需要的頁(yè)面調(diào)入到內(nèi)存 。 如果當(dāng)時(shí)內(nèi)存中有空閑塊 ， 那么頁(yè)面的調(diào)入問題就解決了；如果當(dāng)時(shí)內(nèi)存中已經(jīng)沒有空閑塊可供分配使用 ， 那么就必須在內(nèi)存中選擇一頁(yè) ， 然后把它調(diào)出內(nèi)存 ， 以便為即將調(diào)入的頁(yè)面讓出塊空間 。 這就是所謂的 “ 頁(yè)面淘汰 ” 問題 。 頁(yè)面淘汰首先要研究的是選擇誰(shuí)作為被淘汰的對(duì)象。雖然可以簡(jiǎn)單地隨機(jī)選擇一個(gè)內(nèi)存中的頁(yè)面淘汰出去，但顯然選擇將來(lái)不常使用的頁(yè)面出去，可能會(huì)使系統(tǒng)的性能更好一些。因?yàn)槿绻蕴粋€(gè)經(jīng)常要使用的頁(yè)面，那么很快由于又要用到它，需要把它再一次調(diào)入，從而增加了系統(tǒng)在處理缺頁(yè)中斷與頁(yè)面調(diào)出 /調(diào)入上的開銷。人們總是希望缺頁(yè)中斷少發(fā)生一些，如果出現(xiàn)這種情形，一個(gè)剛被淘汰（從內(nèi)存調(diào)出到輔存）出去的頁(yè)，時(shí)隔不久因?yàn)橛忠L問它，又把它從輔存調(diào)入。調(diào)入后不久再一次被淘汰，再訪問，再調(diào)入。 如此頻繁地反復(fù)進(jìn)行，使得整個(gè)系統(tǒng)一直陷于頁(yè)面的調(diào)入、調(diào)出，以致大部分 CPU時(shí)間都用于處理缺頁(yè)中斷和頁(yè)面淘汰上，很少能顧及到用戶作業(yè)的實(shí)際計(jì)算。這種現(xiàn)象被稱為“抖動(dòng)”或稱為“顛簸”。很明顯，抖動(dòng)使得整個(gè)系統(tǒng)效率低下，甚至趨于崩潰，是應(yīng)該極力避免和排除的。 要注意，頁(yè)面淘汰是由缺頁(yè)中斷引起的，但缺頁(yè)中斷不見得一定引起頁(yè)面淘汰。只有當(dāng)內(nèi)存中沒有空閑塊時(shí)，缺頁(yè)中斷才會(huì)引起頁(yè)面淘汰。 選擇淘汰對(duì)象有很多種方略可以采用，常見的有“先進(jìn)先出頁(yè)面淘汰算法”、“最久未使用頁(yè)面淘汰算法”、“最少使用頁(yè)面淘汰算法”以及“最優(yōu)頁(yè)面淘汰算法”等。下面將一一介紹它們。在介紹之前還需要說(shuō)明的是，在內(nèi)存里選中了一個(gè)淘汰的頁(yè)面，如果該頁(yè)面在內(nèi)存時(shí)未被修改過(guò)，那么就可以直接用調(diào)入的頁(yè)面將其覆蓋掉；但如果該頁(yè)面在內(nèi)存時(shí)被修改過(guò)，那么就必須把它回寫到磁盤，以便更新該頁(yè)在輔存上的副本。一個(gè)頁(yè)面的內(nèi)容在內(nèi)存時(shí)是否被修改過(guò)，這樣的信息可以通過(guò)頁(yè)表表目反映出來(lái)。前面，我們已經(jīng)給出過(guò)在請(qǐng)求分頁(yè)式存儲(chǔ)管理中頁(yè)表表目的簡(jiǎn)單構(gòu)成，更為實(shí)用的頁(yè)表表目包含的內(nèi)容如下。 前面 4項(xiàng)的解釋如前 ， 后面兩項(xiàng)的含義如下 。 引用位：在系統(tǒng)規(guī)定的時(shí)間間隔內(nèi) ， 該頁(yè)是否被引用過(guò)的標(biāo)志 （ 該位在頁(yè)面淘汰算法中將會(huì)用到 ） 。 改變位：該位為 “ 0”時(shí) ， 表示此頁(yè)面在內(nèi)存時(shí)數(shù)據(jù)未被修改過(guò)；為 “ 1”時(shí) ， 表示被修改過(guò) 。 當(dāng)此頁(yè)面被選中為淘汰對(duì)象時(shí) ， 根據(jù)此位的取值來(lái)確定是否要將該頁(yè)的內(nèi)容進(jìn)行磁盤回寫操作 。 頁(yè)號(hào) 塊號(hào) 缺頁(yè)中斷位 輔存地址 引用位 改變位 1．先進(jìn)先出頁(yè)面淘汰算法 先進(jìn)先出（ FIFO）是人們最容易想到的頁(yè)面淘汰算法。其做法是當(dāng)要進(jìn)行頁(yè)面淘汰時(shí)，總是把最早進(jìn)入內(nèi)存的頁(yè)面作為淘汰的對(duì)象。比如，給出一個(gè)作業(yè)運(yùn)行時(shí)的頁(yè)面走向?yàn)椋? 5 這就是說(shuō)，該作業(yè)運(yùn)行時(shí)，先要用到第 1頁(yè)，再用到第 2頁(yè)、第 3頁(yè)和第 4頁(yè)等。頁(yè)面走向中涉及到的頁(yè)面總數(shù)為 12。假定只分配給該作業(yè) 3個(gè)內(nèi)存塊使用。開始時(shí)作業(yè)程序全部在輔存， 3個(gè)內(nèi)存塊都為空。運(yùn)行后，通過(guò) 3次缺頁(yè)中斷，把第 第 第 3三個(gè)頁(yè)面分別從輔存調(diào)入內(nèi)存塊中。當(dāng)頁(yè)面走向到達(dá) 4時(shí)，用到第 4頁(yè)。由于 3個(gè)內(nèi)存塊中沒有第 4頁(yè)，因此仍然需要通過(guò)缺頁(yè)中斷將其調(diào)入。但供該作業(yè)使用的 3個(gè)內(nèi)存塊已經(jīng)全部分配完畢，必須進(jìn)行頁(yè)面淘汰才能夠騰空一個(gè)內(nèi)存塊，然后讓所需的第 4頁(yè)進(jìn)來(lái)?？梢钥闯?，前面 3個(gè)缺頁(yè)中斷沒有引起頁(yè)面淘汰，現(xiàn)在這個(gè)缺頁(yè)中斷引起了頁(yè)面淘汰。根據(jù) FIFO的淘汰原則，顯然應(yīng)該把第一個(gè)進(jìn)來(lái)的第 1頁(yè)淘汰出去。緊接著又用到第 1頁(yè)，它不在內(nèi)存的三個(gè)塊中，于是不得不把這一時(shí)刻為最先進(jìn)來(lái)的第 2頁(yè)淘汰出去，等等。圖 328(a)描述了整個(gè)進(jìn)展過(guò)程。 在圖中，最上面出示的是頁(yè)面走向，每一個(gè)頁(yè)號(hào)下面對(duì)應(yīng)著的 3個(gè)方框以及里面的數(shù)字，表示那一時(shí)刻3個(gè)內(nèi)存塊中當(dāng)時(shí)存放的頁(yè)面號(hào)。要注意的是，如果把某頁(yè)填入一個(gè)方框后，就理解為它只能在那一個(gè)方框里存在，直到被淘汰，如圖 328(b)所示（一個(gè)局部圖），那么被淘汰頁(yè)面在圖中出現(xiàn)的位置就是不確定的，讓人不易理解。為了清楚和能夠更好地說(shuō)明問題，圖 328(a)中的做法是讓每列中的頁(yè)號(hào)按淘汰算法的淘汰順序由下往上排列，排在最下面的是下一次的淘汰對(duì)象，排在最上面的是最后才會(huì)被淘汰的對(duì)象。 由于現(xiàn)在實(shí)行的是 FIFO頁(yè)面淘汰算法，因此排在最上面的頁(yè)號(hào)是剛剛調(diào)入內(nèi)存的頁(yè)面號(hào)，排在最下面的是進(jìn)入內(nèi)存最早的頁(yè)面號(hào)，它正是下一次頁(yè)面淘汰的對(duì)象，在圖中用圓圈把它圈起來(lái)，起到醒目提示的作用。圖 328(a)的最下面還有一方框行，它記錄了根據(jù)頁(yè)面走向往前邁進(jìn)時(shí)，每個(gè)所調(diào)用的頁(yè)面在當(dāng)時(shí)的內(nèi)存塊中是能夠找到的，還是要通過(guò)缺頁(yè)中斷調(diào)入。如果必須通過(guò)缺頁(yè)中斷調(diào)入，那么就在相應(yīng)的方框里打一個(gè)勾，以便最后能計(jì)算出相對(duì)于這個(gè)頁(yè)面走向，總共發(fā)生多少次缺頁(yè)中斷。比如對(duì)于所給的頁(yè)面走向，它涉及到的頁(yè)面總數(shù)為 12，通過(guò)缺頁(yè)中斷調(diào)入頁(yè)面的次數(shù)是 9（因?yàn)椤叭表?yè)計(jì)數(shù)”欄中有 9個(gè)勾），因此它的缺頁(yè)中斷率 f是： f=9/12=75% FIFO頁(yè)面淘汰算法的著眼點(diǎn)是 ， 認(rèn)為隨著時(shí)間的推移 ， 在內(nèi)存中呆得最長(zhǎng)的頁(yè)面 ， 被訪問的可能性最小 。 在實(shí)際中 ， 這就有可能把經(jīng)常要訪問的頁(yè)面淘汰出去 。 為了盡量避免出現(xiàn)這種情形 ， 提出了對(duì)它的改進(jìn)： “ 第二次機(jī)會(huì)頁(yè)面淘汰算法 ” 。 這種算法的基礎(chǔ)是先進(jìn)先出 。 它把進(jìn)入內(nèi)存的頁(yè)面按照進(jìn)入的先后次序組織成一個(gè)鏈表 。 在選擇淘汰對(duì)象時(shí) ， 總是把鏈表的第 1個(gè)頁(yè)面作為要淘汰的對(duì)象 ， 并檢查該頁(yè)面的 “ 引用位 （ R） ” 。 如果它的 R位為“ 0”，表示從上一次頁(yè)面淘汰以來(lái)，到現(xiàn)在它沒有被引用過(guò)。這就是說(shuō)，它既老又沒用，因此可以把它立即淘汰；如果它的 R位為“ 1”，表示從上一次頁(yè)面淘汰以來(lái)，它被引用過(guò)，因此暫時(shí)不淘汰它，再給它一次機(jī)會(huì)。于是將它的 R位修改為“ 0”，然后排到鏈表的最后，并繼續(xù)在鏈表上搜索符合條件的淘汰對(duì)象。圖 329給出了第二次機(jī)會(huì)頁(yè)面淘汰算法的示意。假定現(xiàn)在要進(jìn)行頁(yè)面淘汰，頁(yè)面鏈表的排隊(duì)情形如圖 329(a)所示，排在第 1個(gè)的頁(yè)面 A當(dāng)前的 R位為“ 1”，因此把它的 R位修改成“ 0”，并排到鏈表的最后。至于到底誰(shuí)是淘汰的對(duì)象，繼續(xù)從頁(yè)面 B往下搜索才能確定。 第二次機(jī)會(huì)頁(yè)面淘汰算法所做的是在頁(yè)面鏈表上尋找一個(gè)從上一次淘汰以來(lái)沒有被訪問過(guò)的頁(yè)面 。 如果所有的頁(yè)面都訪問過(guò)了 ， 那么這個(gè)算法就成為純粹的先進(jìn)先出頁(yè)面淘汰算法 。 極端地說(shuō) ， 假如圖 329(a)中所有的頁(yè)面的 R位都是 “ 1”， 那么該算法就會(huì)一個(gè)接一個(gè)地把每一個(gè)頁(yè)面移到鏈表的最后 ， 并且把它的R位修改成 “ 0”， 于是最后又會(huì)回到頁(yè)面 A。 此時(shí)它的R位已經(jīng)是 “ 0”， 因此被淘汰出去 。 所以 ， 這個(gè)算法總是能夠結(jié)束的 。 第二次機(jī)會(huì)頁(yè)面淘汰算法把在內(nèi)存中的頁(yè)面組織成一個(gè)鏈表來(lái)管理，頁(yè)面要在鏈表中經(jīng)常移動(dòng)，從而影響系統(tǒng)的效率?？梢园堰@些頁(yè)面組織成循環(huán)鏈表的形式，如圖 330所示。循環(huán)鏈表類似與時(shí)鐘，用一個(gè)指針指向當(dāng)前最先進(jìn)入內(nèi)存的頁(yè)面。當(dāng)發(fā)生缺頁(yè)中斷并要求頁(yè)面淘汰時(shí)，首先檢查指針指向的頁(yè)面的 R位。如果它的 R位為“ 0”，則就把它淘汰，讓新的頁(yè)面進(jìn)入它原來(lái)占用的內(nèi)存塊，并把指針按順時(shí)針方向向前移動(dòng)一個(gè)位置；如果它的 R位為“ 1”，則將其 R位清為“ 0”，然后把指針按順時(shí)針方向向前移動(dòng)一個(gè)位置，去重復(fù)這一過(guò)程，直到找到一個(gè) R位為“ 0”的頁(yè)面為止。它實(shí)際上是第二次機(jī)會(huì)頁(yè)面淘汰算法的變形，有時(shí)稱為“時(shí)鐘頁(yè)面淘汰算法”。 2． 最近最久未用頁(yè)面淘汰算法 最近最久未用 （ LRU） 頁(yè)面淘汰算法的著眼點(diǎn)是在要進(jìn)行頁(yè)面淘汰時(shí) ， 檢查這些淘汰對(duì)象的被訪問時(shí)間 ， 總是把最長(zhǎng)時(shí)間未被訪問過(guò)的頁(yè)面淘汰出去 。 這是一種基于程序局部性原理的淘汰算法 。 也就是說(shuō) ，該算法認(rèn)為如果一個(gè)頁(yè)面剛被訪問過(guò) ， 那么不久的將來(lái)被訪問的可能性就大；否則被訪問的可能性就小 。 仍以前面 FIFO中涉及的頁(yè)面走向 5為例，來(lái)看當(dāng)對(duì)它實(shí)行 LRU頁(yè)面淘汰算法時(shí)，缺頁(yè)中斷率是多少。 一切約定如前所述，圖 331(a)是 LRU的運(yùn)行過(guò)程，圖 331(b)是圖 328(a)的局部。對(duì)照著看它們，以比較出兩個(gè)算法思想的不同。 按照頁(yè)面走向，從第 1頁(yè)面開始直到第 5頁(yè)面（即 1，2， 3， 4， 1， 2， 5），這兩個(gè)圖表現(xiàn)的是一樣的。當(dāng)又進(jìn)到第 1頁(yè)時(shí)，由于該頁(yè)在內(nèi)存塊中有，因此不會(huì)引起缺頁(yè)中斷，但是兩個(gè)算法的處理就不相同了。 對(duì)于 FIFO， 關(guān)心的是這三頁(yè)進(jìn)入內(nèi)存的先后次序 。對(duì)第 1頁(yè)的訪問不會(huì)改變內(nèi)存中第 5三頁(yè)進(jìn)入內(nèi)存的先后次序 ， 因此它們之間的關(guān)系仍然保持前一列的關(guān)系 ， 如圖 331(b)所示 。 對(duì)于 LRU， 關(guān)心的是這三頁(yè)被訪問的時(shí)間 。 對(duì)第 1頁(yè)的訪問 ， 表明它是當(dāng)前剛被訪問過(guò)的頁(yè)面 ， 其次訪問的是頁(yè)面 5， 最早訪問的是頁(yè)面 2。 因此按照 LRU的原則 ， 它們?cè)趫D 331(a)中的排列順序應(yīng)該加以調(diào)整才對(duì) 。 即：第 1頁(yè)應(yīng)該在最上面 ， 第5頁(yè)應(yīng)該在中間 ， 第 2頁(yè)應(yīng)該在最下面 。 如果再進(jìn)到頁(yè)面 2，仍然不發(fā)生缺頁(yè)中斷，對(duì)于FIFO，不用調(diào)整在內(nèi)存中三頁(yè)的先后次序；對(duì)于 LRU，則又要調(diào)整這三頁(yè)的排列次序。 正是因?yàn)槿绱?，?dāng)進(jìn)到第 3頁(yè)、而第 3頁(yè)又不在內(nèi)存時(shí)，不僅發(fā)生缺頁(yè)中斷，而且引起頁(yè)面淘汰。在FIFO中，淘汰的對(duì)象是第 1頁(yè)；在 LRU中，淘汰的對(duì)象則是第 5頁(yè)，后面的處理過(guò)程與此類似。由于圖 331(a)中對(duì)缺頁(yè)的計(jì)數(shù)是 10，故它的缺頁(yè)中斷率 f是： f=10/12=83% 可以看出，對(duì)于同樣一個(gè)頁(yè)面走向，實(shí)行 FIFO頁(yè)面淘汰算法要比 LRU好。 3． 最近最少用頁(yè)面淘汰算法 最近最少用 （ LFU） 頁(yè)面淘汰算法的著眼點(diǎn)是考慮內(nèi)存塊中頁(yè)面的使用頻率 ， 它認(rèn)為在一段時(shí)間里使用得最多的頁(yè)面 ， 將來(lái)用到的可能性就大 。 因此 ， 當(dāng)要進(jìn)行頁(yè)面淘汰時(shí) ， 總是把當(dāng)前使用得最少的頁(yè)面淘汰出去 。 要實(shí)現(xiàn) LFU頁(yè)面淘汰算法 ， 應(yīng)該為每個(gè)內(nèi)存中的頁(yè)面設(shè)置一個(gè)計(jì)數(shù)器 。 對(duì)某個(gè)頁(yè)面訪問一次 ， 它的計(jì)數(shù)器就加 1。 經(jīng)過(guò)一個(gè)時(shí)間間隔 ， 把所有計(jì)數(shù)器都清 0。產(chǎn)生缺頁(yè)中斷時(shí) ， 比較每個(gè)頁(yè)面計(jì)數(shù)器的值 ， 把計(jì)數(shù)器取值最小的那個(gè)頁(yè)面淘汰出去 。 4．最優(yōu)頁(yè)面淘汰算法 如果已知一個(gè)作業(yè)的頁(yè)面走向，那么要進(jìn)行頁(yè)面淘汰時(shí)，應(yīng)該把以后不再使用的或在最長(zhǎng)時(shí)間內(nèi)不會(huì)用到的頁(yè)面淘汰出去，這樣所引起的缺頁(yè)中斷次數(shù)肯定最小，這就是所謂的“最優(yōu)（ OPT）頁(yè)面淘汰算法”。 比如，作業(yè) A的頁(yè)面走向?yàn)? 4，．．．，分給它 4個(gè)內(nèi)存塊使用。運(yùn)行一段時(shí)間后，頁(yè)面 3分別通過(guò)缺頁(yè)中斷進(jìn)入分配給它使用的 4個(gè)內(nèi)存塊。當(dāng)訪問頁(yè)面 6時(shí)， 4個(gè)內(nèi)存塊已無(wú)空閑的可以分配，于是要進(jìn)行頁(yè)面淘汰。按照 FIFO或LRU等算法，應(yīng)該淘汰第 2頁(yè)，因?yàn)樗钤邕M(jìn)入內(nèi)存，或最長(zhǎng)時(shí)間沒有調(diào)用到。但是，稍加分析可以看出，應(yīng)該淘汰第 7頁(yè)，因?yàn)樵陧?yè)面走向給出的可見的將來(lái)，根本沒有再訪問它！所以 OPT肯定要比別的淘汰算法產(chǎn)生的缺頁(yè)中斷次數(shù)少。 遺憾的是， OPT的前提是要已知作業(yè)運(yùn)行時(shí)的頁(yè)面走向，這是根本不可能做到的，所以 OPT頁(yè)面淘汰算法沒有實(shí)用價(jià)值，它只能用來(lái)做為一個(gè)標(biāo)桿（或尺度），與別的淘汰算法進(jìn)行比較。如果在相同頁(yè)面走向的前提下，某個(gè)淘汰算法產(chǎn)生的缺頁(yè)中斷次數(shù)接近與它，那么就說(shuō)這個(gè)淘汰算法不錯(cuò)；否則就屬較差。 前面提及，有若干因素會(huì)影響缺頁(yè)中斷的發(fā)生次數(shù)。因素之一是“分配給作業(yè)的內(nèi)存塊數(shù)”，并且“分配給作業(yè)的內(nèi)存塊數(shù)增多，發(fā)生缺頁(yè)中斷的可能性就下降”。這個(gè)結(jié)論對(duì)于 FIFO頁(yè)面淘汰算法來(lái)說(shuō)，有時(shí)卻會(huì)出現(xiàn)異常。也就是說(shuō)，對(duì)于 FIFO頁(yè)面淘汰算法，有時(shí)增加分配給作業(yè)的可用內(nèi)存塊數(shù)，它的缺頁(yè)次數(shù)反而上升，通常把這稱為“異?，F(xiàn)象”。 仍以前面涉及的頁(yè)面走向 5為例，實(shí)行 FIFO頁(yè)面淘汰算法，不同的是分配給該作業(yè) 4個(gè)內(nèi)存塊使用。圖 332是運(yùn)行的情形