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