15存儲管理4虛擬存儲請求頁式管理1(編輯修改稿)
2025-03-16 02:15 本頁面
【文章內(nèi)容簡介】 法46 頁面置換算法頁面置換算法 假定作業(yè) p共計(jì) n頁 ，而系統(tǒng)分配給它的主存塊只有 m塊 （ m,n均為正整數(shù)，１ ≤ m≤ n），即最多只能容納 m頁。 如果程序 p在運(yùn)行中成功的訪問次數(shù)為 s,不成功的訪問次數(shù)為 f,那么，其 總的訪問次數(shù) a=s+f，若定義 f ’=f/a， 稱 f ’為缺頁中斷率。缺頁中斷率 :47影響缺頁中斷次數(shù)的因素影響缺頁中斷次數(shù)的因素（ 1） 分配給進(jìn)程的物理頁面數(shù)物理頁面數(shù)多，缺頁中斷少，反之，則缺頁中斷多物理頁面數(shù)多，進(jìn)程數(shù)少（影響系統(tǒng)效率），反之，則進(jìn)程數(shù)多（缺頁中斷多）根據(jù)試驗(yàn)分析：對一共有 n頁的進(jìn)程來說，只要能分到n/2塊 內(nèi)存空間，就可使系統(tǒng)獲得最高效率；（ 2） 頁面本身的大小頁面大，進(jìn)程的頁數(shù)少，一頁的信息就大，缺頁中斷次數(shù)減少；不同的計(jì)算機(jī)系統(tǒng)，有不同頁面大?。?8例：程序要把例：程序要把 128128的數(shù)組初值置的數(shù)組初值置 “0”，數(shù)組中，數(shù)組中每一個(gè)元素為一個(gè)字，假定頁面大小為每一個(gè)元素為一個(gè)字，假定頁面大小為 128個(gè)字，個(gè)字，數(shù)組中的每一行元素存放一頁，能供該程序使用數(shù)組中的每一行元素存放一頁，能供該程序使用的主存塊只有的主存塊只有 1塊。初始時(shí)第一頁在內(nèi)存；塊。初始時(shí)第一頁在內(nèi)存；程序編制方法 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）程序的編制方法可見：缺頁中斷率與程序的局部化程度密切相關(guān)。希望編制的程序能經(jīng)常集中在幾個(gè)頁面上；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) 頁面淘汰算法理論的頁面淘汰算法應(yīng)該選擇的被淘汰頁面將是 以后永不使用的 ，或在最長 (未來 )時(shí)間內(nèi)不再被訪問的頁面。（ OPT算法 ）。實(shí)際上，可以用理論的頁面淘汰算法作 標(biāo)準(zhǔn)，選擇其它較好的頁面淘汰算法頁面淘汰算法選擇不合適，會使系統(tǒng) “抖動 ”51 剛被換出的頁很快又被訪問，需要重新調(diào)入，為此又需再選出一頁調(diào)出；而剛被換出的頁，很快又要被訪問，又需把它調(diào)入，如此頻繁地更換頁面，以致一個(gè)進(jìn)程在運(yùn)行中，把大部分時(shí)間花費(fèi)在完成頁面的置換工作上，使得 調(diào)度頁面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多 . 我們稱該進(jìn)程發(fā)生了 “抖動 ”。 抖動52 最佳置換算法是由 Relady在 1966年提出的，這種算法選擇的被淘汰頁面，將是 永不使用的，或在最長時(shí)間內(nèi)不再被訪問的頁面。 最佳 置換 算法是指對于任意的內(nèi)存固定空間 m和程序 p,有缺頁中斷率最小。它是一個(gè)理論上的算法。最佳置換算法（ OPT） 53 假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁面號引用串。 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先進(jìn)先出頁面置換算法（ FIFO） 這是最早出現(xiàn)的置換算法，這種算法總是淘汰最先進(jìn)入內(nèi)存的頁面 ，選擇在內(nèi)存中 駐留時(shí)間最久 的頁面予以淘汰。55 我們來看看采用 FIFO算法進(jìn)行頁面置換時(shí)的情況。 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的兩個(gè)實(shí)現(xiàn)方法 ： m(m是分配給該作業(yè)的存貯塊數(shù) )個(gè)元素的頁號表和一個(gè)替換指針。P[i](i=0,1,2,…,m1) 指示在一個(gè)內(nèi)存中的頁面的頁號。替換指針 K指向進(jìn)入主存最老的那一頁。每當(dāng)一頁新頁調(diào)入后，執(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ù)各個(gè)頁面調(diào)入內(nèi)存的時(shí)間來選擇被淘汰頁面，但 頁面調(diào)入的先后并不能反映頁面的使用情況 。 FIFO算法只是在 按線性順序訪問地址空間 才是理想的。 未考慮到程序的 動態(tài)特性 。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1