操作系統(tǒng)課件os04存儲管理.ppt

操作系統(tǒng) Operating Systems WINDOWSWINDOWS UNIXUNIX LINUXLINUX OS2OS2 VxWorksVxWorks Mac OSMac OS 4.7 請求分頁存儲管理方式 4.7.1 請求分頁中的硬件支持 1頁表機制 狀態(tài)位P：用于指示該頁是否已調(diào)入內(nèi)存。 供程序訪問時參考。 訪問字段A：供選擇換出頁面時參考。 用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或記錄本 頁最近已有多長時間未被訪問。 4.7 請求分頁存儲管理方式 4.7.1 請求分頁中的硬件支持 1頁表機制 修改位M：供置換頁面時參考。 表示該頁在調(diào)入內(nèi)存后是否被修改過。 外存地址 用于指出該頁在外存上的地址，通常是物理塊號 供調(diào)入該頁時參考。 2缺頁中斷機構(gòu) 在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時，便 產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存。 缺頁中斷同樣需要經(jīng)歷： 1. 保護CPU環(huán)境 2. 分析中斷原因 3. 轉(zhuǎn)入缺頁中斷處理程序進行處理 4. 恢復(fù)CPU環(huán)境 多次缺頁中斷的指令 如：在執(zhí)行一條指令 COPY A TO B時，可能要產(chǎn) 生6次缺頁中斷： l指令本身跨了兩個頁面 lA和B又分別各是一個數(shù) 據(jù)塊，也都跨了兩個頁 面。 缺頁中斷 缺頁中斷與一般的中斷區(qū)別： (1)缺頁中斷是在指令執(zhí)行期間產(chǎn)生和處理中斷信號。 一般中斷都是在CPU一條指令執(zhí)行完后，才檢查是否有 中斷請求到達。 (2) 一指令在執(zhí)行期間，可產(chǎn)生多次缺頁中斷。 系統(tǒng)中硬件機構(gòu)應(yīng)能保存多次中斷時的狀態(tài)，并保證 最后返回到中斷前產(chǎn)生缺頁中斷的指令處繼續(xù)執(zhí)行。 3地址變換機構(gòu) 4.7.2 內(nèi)存分配策略和分配算法 1最小物理塊數(shù) 是指能保證進程正常運行所需的最小物理塊數(shù)。 2物理塊的分配策略 3物理塊分配算法 最小物理塊數(shù) 當(dāng)系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運 行。 進程應(yīng)獲得的最少物理塊數(shù)與計算機的硬件結(jié)構(gòu)有關(guān)，取 決于指令的格式、功能和尋址方式。 對于某些功能較強的機器，其指令長度可能是兩個或 多于兩個字節(jié)。 對于這種機器，至少要為每個進程分配6個物理塊，以 裝入6個頁面。 物理塊的分配策略 內(nèi)存分配策略： 固定分配 可變分配 置換策略 全局置換 局部置換 固定分配局部置換 可變分配全局置換 可變分配局部置換 3物理塊分配算法 1) 平均分配算法 將系統(tǒng)中所有可供分配的物理塊平均分配給各個進程 2) 按比例分配算法 根據(jù)進程的大小按比例分配物理塊的算法。 3) 考慮優(yōu)先權(quán)的分配算法 把內(nèi)存中可供分配的所有物理塊分成兩部分： 一部分按比例地分配給各進程； 另一部分則根據(jù)各進程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng) 份額后，分配給各進程。 4.7.3 調(diào)頁策略 1) 預(yù)調(diào)頁策略 可采用一種以預(yù)測為基礎(chǔ)的預(yù)調(diào)頁策略 將那些預(yù)計在不久之后便會被訪問的頁面預(yù)先調(diào)入內(nèi)存 主要用于進程的首次調(diào)入時，由程序員指出應(yīng)該先調(diào) 入哪些頁。 2) 請求調(diào)頁策略 若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便立即提出請求，由OS將 其所需頁面調(diào)入內(nèi)存。 在目前的虛擬存儲器中大多采用此策略。 4.8 頁面置換算法 1) 最佳頁面替換算法OPT 通常可保證獲得最低的缺頁率。 該算法是無法實現(xiàn)的 2) 先進先出頁面替換算法FIFO 3) 最近最久未使用置換算法LRU 4) 時鐘頁面替換算法 缺頁率(缺頁中斷率) 如果作業(yè)p在運行中成功的訪問次數(shù)為s， 不成功的訪問 次數(shù)為F，則總的訪問次數(shù)為：A = s + F 缺頁中斷率：f = F / A 。 最佳替換算法OPT 所淘汰的頁應(yīng)該是： 以后不再訪問的頁 或在最長（未來）時間內(nèi)不再訪問的頁。 發(fā)生了5次頁面置換，缺頁次數(shù)=8；缺頁率=8/17 7 0 1 7 722 2 2 0 00 4 0 333 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 11 2 0 0 1 先進先出頁面替換算法 基于程序總是按線性順序來訪問物理空間這一假設(shè)。 淘汰最先調(diào)入主存的頁，或在主存中駐留時間最長的頁。 只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個 隊列，并設(shè)置一個指針，它總是指向最老的頁面 7 0 2 2 47701 2 3 0 0 12 3042 3 0 32 4 0 3 7 0 1 2 0 3 0 4 2 3 0 3 2 1 11 3 0 發(fā)生了8次頁面置換，缺頁次數(shù)=11；缺頁率=11/14 最 老 的 頁 最近最久未使用頁面替換算法LRU 該算法的主要出發(fā)點是： 用“最近的過去”作為“最近的將來”的近似 如果某頁被訪問了，則它可能馬上還要被訪問。 當(dāng)需要淘汰某一頁時，選擇離當(dāng)前時間最近的一段時間內(nèi)最 久沒有使用過的頁先淘汰。 或者反過來說，如果某頁很長時間未被訪問，則它在最近一 段時間也不會被訪問。 2硬件支持 須有寄存器或棧的支持： 1) 寄存器 須為每個在內(nèi)存中的頁面配置一個移位寄存器： 進程訪問某物理塊時，先將寄存器的Rn1位設(shè)成1。 定時信號將每隔一定時間將寄存器右移一位。 若將n位寄存器的數(shù)看做是一整數(shù)，那么，具有最小數(shù)值 的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面。 R7R6R5R4R3R2R1R0 000000000 100000000 1 LRU算法實現(xiàn)：棧 最 新 被 訪 問 的 頁 例子-計算缺頁中斷次數(shù)和被淘汰頁面(1) 假設(shè)采用固定分配策略，進程分得三個頁框,執(zhí)行中按下列次 序引用5個獨立的頁面: 2 3 2 1 5 2 4 5 3 2 5 2。 2 3 2 1 5 2 4 5 3 2 5 2 2 3 4 51 2222 33 33 55 3 3 2 4 23 222152 5 2 5 3 3 215 2453 2 5 3 54 2 5 1 OPT LRU 發(fā)生了3次頁面置換，缺頁次數(shù)=6；缺頁率=6/12 發(fā)生了4次頁面置換，缺頁次數(shù)=7；缺頁率=7/12 最 新 被 訪 問 的 頁 例子-計算缺頁中斷次數(shù)和被淘汰頁面(2) 2 3 2 1 5 2 4 5 3 2 5 2 2 2 3 5 51 2 231 4 32 315 24 3 5 5 34 2 FIFO 發(fā)生了6次頁面置換，缺頁次數(shù)=9；缺頁率=9/12 最 老 的 頁 時鐘頁面替換算法 1、簡單的Clock置換算法 簡單的Clock置換算法（1） 1. 主存中的任何頁面被訪問時， 其 “訪問位”置1。 2. 淘汰頁面時， 從指針當(dāng)前指向的頁面開始 掃描循環(huán)隊列，把所遇到的 “訪問位”是1的頁面的“訪問 位”清0，跳過這個頁面; 把所遇到的“訪問位”是0的 頁面淘汰掉，指針推進一步 。 Page9 use=1 Page19 Use=1Page1 Use=0 Page45 Use=1 Page191 Use=1 Page556 Use=0 Page13 Use=0 Page67 Use=1 Page33 Use=1 Page222 Use=0 查尋指 針 n-1 0 1 2 3 4 5 6 7 8 Page45 Use=0 Page191 Use=0 簡單的Clock置換算法（2） 4. 掃描循環(huán)隊列時，如果 遇到的所有頁面的“訪問 位”為1，指針就會繞整 個循環(huán)隊列一圈，把碰 到的所有頁面的“訪問位 ”清0; 指針停在起始位置，并 淘汰掉這一頁， 然后，指針推進一步。 Page1 Use=0 Page45 Use=1 Page191 Use=1 Page556 Use=0 查尋指 針 n-1 0 1 2 3 4 Page45 Use=0 Page191 Use=0 Page556 Use=1 Page1 Use=1 例子-計算缺頁中斷次數(shù)和被淘汰頁面(1) 假設(shè)采用固定分配策略，進程分得三個頁框,執(zhí)行中按下列次 序引用5個獨立的頁面: 2 3 2 1 5 2 4 5 3 2 5 2。 2* 3* 5* 11* 2* 2*5* 5*3*3* 3*32* 2*2 2 5* 44* 1 CLOCK *號表示相應(yīng)的訪問位等于1 2 3 2 1 5 2 4 5 3 2 5 2 發(fā)生了5次頁面置換，缺頁次數(shù)=8；缺頁率=8/12 3* 2* 4 3* 2* 5* 4.9 請求分段存儲管理方式 與基本分段的最大區(qū)別： 允許部分段運行前不裝入 可以在運行過程中按需動態(tài)調(diào)入。 硬件支持 1. 段表機制 2. 缺段中斷機構(gòu) 3. 地址變換機構(gòu) 1. 段表機制 (1) 存取方式：標(biāo)識本段存取屬性(讀,執(zhí)行,讀/寫)。 (2) 訪問字段A：用于記錄該段被訪問的頻繁程度。 (3) 修改位M：供置換頁面時參考。 (4) 存在位P：供程序訪問時參考。 (5) 增補位：用于表示本段在運行過程中是否做過動態(tài)增長 。 (6) 外存始址：指示本段在外存中起始盤塊號。 段名 段長 段的 基址 存取 方式 訪問 字段A 修改 位M 存在 位P 增補 位 外存 始址 2缺段中斷機構(gòu) 3地址變換機構(gòu) 小結(jié)（1） 內(nèi)存管理概念 程序裝入與鏈接；邏輯地址與物理地址空間； 交換 連續(xù)分配管理方式 單一連續(xù)分配、固定分區(qū)分配、動態(tài)分區(qū)分配 伙伴系統(tǒng)、可重定位分配分配 非連續(xù)分配管理方式 分頁管理方式；分段管理方式；段頁式管理方式。 小結(jié)（2） 虛擬內(nèi)存管理 虛擬內(nèi)存基本概念 請求分頁管理方式 頁面分配策略 頁面置換算法 OPT；FIFO；LRU；CLOCK。 請求分段管理方式 作業(yè) 1.在一個分頁虛存系統(tǒng)中，用戶編程空間32個頁面，頁長 1KB，主存為16KB。如果用戶程序有10頁長