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