【文章內容簡介】 法46 頁面置換算法頁面置換算法 假定作業(yè) p共計 n頁 ，而系統(tǒng)分配給它的主存塊只有 m塊 （ m,n均為正整數(shù)，１ ≤ m≤ n），即最多只能容納 m頁。 如果程序 p在運行中成功的訪問次數(shù)為 s,不成功的訪問次數(shù)為 f,那么，其 總的訪問次數(shù) a=s+f，若定義 f ’=f/a， 稱 f ’為缺頁中斷率。缺頁中斷率 :47影響缺頁中斷次數(shù)的因素影響缺頁中斷次數(shù)的因素（ 1） 分配給進程的物理頁面數(shù)物理頁面數(shù)多，缺頁中斷少，反之，則缺頁中斷多物理頁面數(shù)多，進程數(shù)少（影響系統(tǒng)效率），反之，則進程數(shù)多（缺頁中斷多）根據(jù)試驗分析：對一共有 n頁的進程來說，只要能分到n/2塊 內存空間，就可使系統(tǒng)獲得最高效率；（ 2） 頁面本身的大小頁面大，進程的頁數(shù)少，一頁的信息就大，缺頁中斷次數(shù)減少；不同的計算機系統(tǒng)，有不同頁面大小；48例：程序要把例：程序要把 128128的數(shù)組初值置的數(shù)組初值置 “0”，數(shù)組中，數(shù)組中每一個元素為一個字，假定頁面大小為每一個元素為一個字，假定頁面大小為 128個字，個字，數(shù)組中的每一行元素存放一頁，能供該程序使用數(shù)組中的每一行元素存放一頁，能供該程序使用的主存塊只有的主存塊只有 1塊。初始時第一頁在內存；塊。初始時第一頁在內存；程序編制方法 1： For j:=1 to 128 For i:=1 to 128 A[i][j]:=0。按列：缺頁中斷次數(shù)： 128128－ 1程序編制方法 2： For i:=1 to 128 For j:=1 to 128 A[i][j]:=0。按行：缺頁中斷次數(shù) 1281（ 3）程序的編制方法可見：缺頁中斷率與程序的局部化程度密切相關。希望編制的程序能經(jīng)常集中在幾個頁面上；491,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 1,102,13,14,15,16,17,18,19,110,150 (4) 頁面淘汰算法理論的頁面淘汰算法應該選擇的被淘汰頁面將是 以后永不使用的 ，或在最長 (未來 )時間內不再被訪問的頁面。（ OPT算法 ）。實際上，可以用理論的頁面淘汰算法作 標準，選擇其它較好的頁面淘汰算法頁面淘汰算法選擇不合適，會使系統(tǒng) “抖動 ”51 剛被換出的頁很快又被訪問，需要重新調入，為此又需再選出一頁調出；而剛被換出的頁，很快又要被訪問，又需把它調入，如此頻繁地更換頁面，以致一個進程在運行中，把大部分時間花費在完成頁面的置換工作上，使得 調度頁面所需時間比進程實際運行的時間還多 . 我們稱該進程發(fā)生了 “抖動 ”。 抖動52 最佳置換算法是由 Relady在 1966年提出的，這種算法選擇的被淘汰頁面，將是 永不使用的，或在最長時間內不再被訪問的頁面。 最佳 置換 算法是指對于任意的內存固定空間 m和程序 p,有缺頁中斷率最小。它是一個理論上的算法。最佳置換算法（ OPT） 53 假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串。 1 2 3 4 5 6 7 8 9 1011121314151617181920237 0 1 2 0 3 0 4 2 3 0 3 12 2 0 1 1 7 107700717014234 2 3021200230 3 21021 2 0 1 17017 0 130302 采用最佳置換算法，只發(fā)生了 6次頁面置換，發(fā)生了 9次缺頁中斷。缺頁率 =9/2154先進先出頁面置換算法（ FIFO） 這是最早出現(xiàn)的置換算法，這種算法總是淘汰最先進入內存的頁面 ，選擇在內存中 駐留時間最久 的頁面予以淘汰。55 我們來看看采用 FIFO算法進行頁面置換時的情況。 7170217031024 51236023743084209423100231113013140121518712197022070121一共發(fā)生了 12次頁面置換，比最佳置換算法多了 1倍。缺頁率 15/21=3/4， 15次頁面中斷。 1 2 3 4 5 6 7 8 9 1011121314151617181920237 0 1 2 0 3 0 4 2 3 0 3 12 2 0 1 1 7 1056FIFO的兩個實現(xiàn)方法 ： m(m是分配給該作業(yè)的存貯塊數(shù) )個元素的頁號表和一個替換指針。P[i](i=0,1,2,…,m1) 指示在一個內存中的頁面的頁號。替換指針 K指向進入主存最老的那一頁。每當一頁新頁調入后，執(zhí)行語句： p[k]=新的頁號； k=(k+1) mod m。替換指針指向最老的一頁2451頁 號57（該表以塊號為序，依次登記各塊的分配情況）。 0 1 2 4 6 3 4 2 ^ 5 6 5 7 7 1 4塊號 頁號 指針2替換指針 0 1 2 6 ^ 3 4 2 2 5 6 5 7 7 1 4塊號 頁號 指針6替換指針(a) 替換之前 (b) 替換之后58 FIFO是根據(jù)各個頁面調入內存的時間來選擇被淘汰頁面，但 頁面調入的先后并不能反映頁面的使用情況 。 FIFO算法只是在 按線性順序訪問地址空間 才是理想的。 未考慮到程序的 動態(tài)特性 。