【正文】 頁面置換算法頁面置換算法 假定作業(yè) p共計(jì) n頁 ，而系統(tǒng)分配給它的主存塊只有 m塊 （ m,n均為正整數(shù)，１ ≤ m≤ n），即最多只能容納 m頁。此時，由系統(tǒng)調(diào)度另一作業(yè)運(yùn)行。25請求分頁系統(tǒng)中，頁表項(xiàng)如下：請求分頁系統(tǒng)中，頁表項(xiàng)如下： 頁號 物理塊號 狀態(tài)位 P訪問字段 A 修改位 M外存地址(1)狀態(tài)位 （駐留位） P:該頁是在內(nèi)存還是在外存(2)訪問字段位 A：記錄本頁在一段時間內(nèi)被訪問的次數(shù) 。 15硬件支持： (1) 請求分頁 的頁表機(jī)制。 在一段時間內(nèi)，程序?qū)痪窒抻谶@些過程的范圍內(nèi)運(yùn)行。l 程序地址空間 （邏輯地址空間、虛地址空間） :用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從 0開始的，可以是一維線性空間，也可以是多維空間。 支持這種現(xiàn)象的是： a、數(shù)組遍歷； b、代碼的順序執(zhí)行； c、程序員傾向于將相關(guān)的變量定義相互靠近存放。 (2) 缺段中斷 機(jī)構(gòu)。 31 在進(jìn)行地址變換時， 首先 去檢索快表； 如果快表中沒有這一頁的頁表項(xiàng)，再到內(nèi)存中找頁表，根據(jù) 狀態(tài)位 P來判斷該頁 是否在內(nèi)存中。問題 : 多少個物理塊合適 ?物理塊太多 :資源空閑 .物理塊太少 :頻繁中斷 采取固定和可變分配策略 362)、 可變分配全局置換空閑物理塊隊(duì)列先為每個進(jìn)程分配一定數(shù)目的物理塊 ,OS也保持一個 空閑物理塊隊(duì)列 ,當(dāng)進(jìn)程缺頁時 ,由系統(tǒng)從空閑物理塊隊(duì)列取出一個物理塊分配給該進(jìn)程 ,并將要調(diào)入的 (缺 )頁裝入內(nèi)存 .僅當(dāng)空閑物理塊隊(duì)列中的物理塊用完時 ,OS才從內(nèi)存中 任一進(jìn)程的一頁 調(diào)出 .問題 : 會使被調(diào)出頁的進(jìn)程缺頁 ,進(jìn)而使缺頁率增加 ,影響其它進(jìn)程的執(zhí)行 .373)、 可變分配局部置換要求保持適當(dāng)?shù)娜表撀? 基于進(jìn)程的類型 ,為每個進(jìn)程分配一定數(shù)目的物理塊 , 進(jìn)程如缺頁 : 只從該進(jìn)程在內(nèi)存中的頁面中換出一頁 ,這樣不會影響其它進(jìn)程 。希望編制的程序能經(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) 頁面淘汰算法理論的頁面淘汰算法應(yīng)該選擇的被淘汰頁面將是 以后永不使用的 ，或在最長 (未來 )時間內(nèi)不再被訪問的頁面。替換指針指向最老的一頁2451頁 號57（該表以塊號為序，依次登記各塊的分配情況）。67 CLock置換算法置換算法 CLock算法就是用得較多的一種 LRU近似算法。74改進(jìn)型改進(jìn)型 Clock算法的特點(diǎn)算法的特點(diǎn)該算法與簡單 Clock算法比較，可 減少磁盤的 I/O操作次數(shù) ，但為了找到要淘汰的頁面，可能需要經(jīng)過幾輪掃描，使該算法本身的開銷有所增加。采取局部置換策略 在 CPU調(diào)度程序中引入工作集算法 掛起若干進(jìn)程 216。 85工作集 W(t,△ )是二元函數(shù)，它與時間 t有關(guān)，在不同時間 t的工作集的大小不同，所包含的頁面數(shù)也不相同；工作集又與窗口尺寸 △ 有關(guān)，工 作集 W是工作集窗口的非降函數(shù)。開始時， CPU的利用率隨著程序度的提高而提高，達(dá)到某一峰值后，如果繼續(xù)增加多道程序度，將產(chǎn)生抖動，從而導(dǎo)致 CPU的利用率急劇下降。 根據(jù)訪問位 A和修改位 M的組合來確定72改進(jìn)型改進(jìn)型 CLock算法，執(zhí)行過程可分為以下三步算法，執(zhí)行過程可分為以下三步：： （ 1）從指針的當(dāng)前位置開始，掃描按先進(jìn)先出循環(huán)隊(duì)列，尋找 A=0且 M=0的第一類頁面，將符合條件的第一個頁面作為淘汰頁，在第一次掃描期間 A不改變。64棧 LRU置換算法可用堆棧的方法來實(shí)現(xiàn)。 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的兩個實(shí)現(xiàn)方法 ： m(m是分配給該作業(yè)的存貯塊數(shù) )個元素的頁號表和一個替換指針。初始時第一頁在內(nèi)存；塊。34最小物理塊數(shù)的確定 最小的物理塊數(shù)，是指保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)。27缺頁中斷機(jī)構(gòu) 在請求分頁系統(tǒng)中，當(dāng)要訪問的頁面不在內(nèi)存時，硬件發(fā)一個 缺頁中斷 ，轉(zhuǎn)交OS處理。 軟件支持： (1) 實(shí)現(xiàn) 請求調(diào)頁 的軟件。（ 4）程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，它們往往都局限于很小的范圍內(nèi)。1內(nèi)存的物理組織內(nèi)存的物理組織l 物理地址： 把內(nèi)存分成若干個大小相等的存儲單元，每個單元給一個編號，這個編號稱為 內(nèi)存地址（物理地址 ,絕對地址 ,實(shí)地址） ,存儲單元占 8位，稱作字節(jié)（ byte）。9局限性的表現(xiàn)：時間，空間（ 1） 時間局限性 時間局限性 是指最近被訪問的存儲位置，很可能不久的將來還要被訪問。 (2) 實(shí)現(xiàn) 頁面置換 的軟件。28(1)在指令 執(zhí)行期間 產(chǎn)生和處理中斷信號。 最少物理塊數(shù)與指令的格式、功能和尋址方式有關(guān)，也就是說與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)。初始時第一頁在內(nèi)存；程序編制方法 1： For j:=1 to 128 For i:=1 to 128 A[i][j]:=0。P[i](i=0,1,2,…,m1) 指示在一個內(nèi)存中的頁面的頁號。 棧中存放當(dāng)前內(nèi)存中的頁面號，每當(dāng)訪問一頁時就調(diào)整一次堆棧，總是 使最近訪問的那頁的頁面號保持在棧頂 ，然后根據(jù)當(dāng)前被訪問時間的近遠(yuǎn)，依次排列， 棧底 總是最近最久未使用的那頁的頁面號。 73（ 2）第一步失敗，開始第二輪掃描，尋找 A=0且 M=1的第二類頁面，將符合條件的第一個頁面作為淘汰頁。81抖動的預(yù)防 核心問題 :選擇合適的頁面置換算法 。程序尺寸工作集86第一個工作集工作集之間的轉(zhuǎn)換第二個工作集第三個工