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