操作系統(tǒng)虛擬內存(編輯修改稿)
2025-03-22 17:42 本頁面
【文章內容簡介】 中分得的內存物理塊數(shù)不變。 – 局限在于為每個進程分配多少個物理塊難以確定。 34 請求分頁存儲管理 ? 可變分配局部置換 – 根據(jù)進程類型，或程序員的建議，開始為每個進程分配一定數(shù)目的物理塊。 – 當進程有頁面需要換入到內存時，只能從當前需要頁面的進程中選擇頁面換出到外存，該置換方法對其它進程沒有影響。 – 進程運行中頻繁發(fā)生缺頁，系統(tǒng)再為該進程分配若干附加的物理塊 ，直至其缺頁率減少到適當程度為止。 35 頁面置換 ? 虛擬存儲管理的一個設計問題是： – 需要一個空閑頁面時選擇哪個頁面來進行替換 ? 目標：減少缺頁中斷的次數(shù)，即減少 缺頁率 – 舉例：如果一個進程或一個作業(yè)在運行中成功的訪問次數(shù)為 S，即所訪問的頁面在內存中；不成功的訪問次數(shù)為 F，即訪問的頁面需要缺頁中斷并且需要調入內存；運行需要訪問的頁面的總次數(shù)為 A： A = S + F 則缺頁率 f為： f = F / A 36 ? 進程的內存物理塊數(shù) 進程分得的內存物理塊數(shù)越多，缺頁率越低。 ? 頁面大小 劃分的頁面越大，缺頁率越低。 ? 程序的局部性 如果編制的程序局部性好，則缺頁率低。 ? 頁面置換算法 如果選取的置換算法優(yōu)，則缺頁率低。 影響缺頁率的因素 37 置換算法 ? 最佳置換算法 ? FIFO (first in first out) 先進先出頁面置換算法 ? LRU (least recently used) 置換算法 ? 時鐘更換 ? 工作集法 38 最佳置換 ? 最佳置換算法 : – 選擇一個隨后最長時間不會被訪問的頁面進行替換 → 最長時間不被使用的頁 → 產(chǎn)生缺頁中斷的次數(shù)最小 → 要具備預知未來的能力 – 預測未來很困難 – 舉例：假如某進程的頁面號引用串為： 6 0 1 2 0 3 0 5 2 3 0 3 2 1 2 0 1 1 6 0 1，系統(tǒng)為進程分配三個內存物理塊。 如下圖所示。最佳頁面置換算法缺頁 6次，缺頁率為 6/21。 39 最佳頁面置換算法 最佳置換 40 FIFO 頁面置換 ? 更換最早進入內存的頁面 ? 維護一個所有頁面的鏈表 – 按照它們進入內存的次序 ? 替換鏈表頭部的頁面 ? 缺點：可能出現(xiàn)最先加載進來的頁面是經(jīng)常被訪問的頁面，這樣做很可能造成常被訪問的頁面替換到磁盤上，導致很快就需要再次發(fā)生缺頁中斷 41 ? 假如某進程的頁面號引用串為： 6 0 1 2 0 3 0 5 2 3 0 3 2 1 2 0 1 1 6 0 1，系統(tǒng)為進程分配三個內存物理塊。 FIFO頁面置換 FIFO頁面置換算法 42 最近最久未使用（ LRU）置換算法 ? LRU 代表最近使用最少 ? 使用過去的數(shù)據(jù)預測未來 – 時空局域性 ? 如果一個頁面長時間沒有被使用過 – 可能以后的一段時間也用不到 43 最近最久未使用 LRU置換算法 ? LRU 接近于 OPT ? 基本思想是替換一個舊頁面 – 不需要最舊的頁面 44 最近最久未使用 LRU置換算法 ? 舉例：在 LRU置換算法中引用串為： 6 0 1 2 0 3 0 5 2 3 0 3 2 1 2 0 1 1 6 0 1，為進程分配三個內存物理塊。置換過程如下圖所示。 缺頁 9次，缺頁率為 9/21。 LRU頁面置換算法 45 最近最久未使用 LRU置換算法 ? 使用一個頁面鏈表 – 最近被使用的頁面在鏈表頭 , 最近未被使用的在鏈表尾 – 每次頁面訪問時更新這個鏈表 ? 在每一個頁表項中使用計數(shù)器 – 選擇具有最小計數(shù)器值的頁面 – 周期性的將計數(shù)器清零 46 使用矩陣實現(xiàn) LRU ? 另一個選擇是使用 n n 矩陣 – 這里 n 是虛擬空間中的頁面數(shù) ? 開始矩陣被設置為 0 ? 當頁面 k 被訪問 : – 將 k行全部設置為 1, k列全部設置為 0 ? 需要替換頁面時 – 選擇矩陣里對應行值最小的頁面更換即可 47 使用矩陣實現(xiàn) LRU ? 頁面訪問順序： 0,1,2,3,2,1,0,3,2,3 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 Page 0 1 2 3 0 1 2 3 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 Page 0 1 2 3 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 Page 0 1 2 3 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 Page 0 1 2 3 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 Page 0 1 2 3 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1 2 3 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 48 使用移位寄存器實現(xiàn) LRU ? 給每個存放在內存的頁面配備一個移位寄存器 – 移位寄存器的初始值設為 0 ? 在每一個規(guī)定長度的時鐘周期 : – 將移位寄存器的值向右移動一位 – 并將對應頁面的訪問位的值加到該移位寄存器的最左位上 ? 當需要尋找一個頁面進行更換時 – 選擇對應移位寄存器值最小的頁面即可 49 使用移位寄存器實現(xiàn) LRU 50 時鐘算法 ? 為每個常駐頁維護訪問位 – 頁面被訪問過后訪問位自動設置 ? 訪問位可以被操作系統(tǒng)清零 ? 常駐頁面被組織到時鐘循環(huán)中 ? 針臂指向其中的一個頁面 51 時鐘算法 ? 查找一個要替換的頁面時 : – 查看正在被針臂指向的頁面 ? 訪問位 =0: – 較長時間內沒有被訪問 (自從上次輪詢 )，置換該頁 ? 訪問位 =1: – 自從上次輪詢后頁面被訪問過，重新置 0，暫不換出 52 時鐘算法 53 ? 除考慮頁面訪問情況外，還須考慮置換代價，即修改位 A：訪問位； M：修改位 改進型時鐘算法 A = 0M = 0A = 0M = 1A = 1M = 0A = 1M = 1NN N換 出54 工作集算法 ? 工作集是： – 最近的 k次訪問均涉及到的頁面集合 – 在最近的 T 秒或者 T 次中的所有頁面 ? w(k,t) 表示在時間 t 時 k 次訪問所涉及的頁面數(shù)量 55 工作集算法 工作集與最近訪問
高考資料相關推薦
鄂ICP備17016276號-1