【正文】 虛擬存儲(chǔ)技術(shù) 虛存 ：把內(nèi)存與外存有機(jī)的結(jié)合起來(lái)使用，從而得到一個(gè)容量很大的“內(nèi)存”，這就是虛存 實(shí)現(xiàn)思想 ：當(dāng)進(jìn)程運(yùn)行時(shí)，先將一部分程序裝入內(nèi)存，另一部分暫時(shí)留在外存，當(dāng)要執(zhí)行的指令不在內(nèi)存時(shí)，由系統(tǒng)自動(dòng)完成將它們從外存調(diào)入內(nèi)存工作 目的 ： 提高內(nèi)存利用率 虛擬存儲(chǔ)器的基本概念 虛擬頁(yè)式存儲(chǔ)管理 基本工作原理 在進(jìn)程開(kāi)始運(yùn)行之前，不是裝入全部頁(yè)面，而是裝入一個(gè)或零個(gè)頁(yè)面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁(yè)面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁(yè)面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁(yè)面，以便裝入新的頁(yè)面 虛擬存儲(chǔ)器的基本概念 頁(yè)表表項(xiàng) 中斷位（駐留位）： 表示該頁(yè)是在內(nèi)存還是在外存 訪問(wèn)位： 根據(jù)訪問(wèn)位來(lái)決定淘汰哪頁(yè)（由不同的算法決定） 修改位： 查看此頁(yè)是否在內(nèi)存中被修改過(guò) 頁(yè)號(hào) 中斷位 內(nèi)存塊號(hào) 外存地址 訪問(wèn)位 修改位 虛擬存儲(chǔ)器的基本概念 ?缺頁(yè)中斷（ Page Fault） ?在地址映射過(guò)程中，在頁(yè)表中發(fā)現(xiàn)所要訪問(wèn)的頁(yè)不在內(nèi)存，則產(chǎn)生缺頁(yè)中斷。操作系統(tǒng)接到此中斷信號(hào)后，就調(diào)出缺頁(yè)中斷處理程序，根據(jù)頁(yè)表中給出的外存地址，將該頁(yè)調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去 虛擬存儲(chǔ)器的基本概念 虛擬存儲(chǔ)器的基本概念 ?如果內(nèi)存中有空閑塊，則分配一頁(yè)，將新調(diào)入頁(yè)裝入內(nèi)存，并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號(hào) ?若此時(shí)內(nèi)存中沒(méi)有空閑塊，則要淘汰某頁(yè)，若該頁(yè)在內(nèi)存期間被 修改 過(guò)，則要將其 寫(xiě)回 外存 ?頁(yè)面淘汰算法 ?先進(jìn)先出頁(yè)面淘汰算法（ FIFO） 選擇在內(nèi)存中駐留時(shí)間最長(zhǎng)的頁(yè)并淘汰之 ?第二次機(jī)會(huì)淘汰算法 (SCR) 按照先進(jìn)先出算法選擇某一頁(yè)面，檢查其訪問(wèn)位，如果為 0，則淘汰該頁(yè)，如果為 1，則給第二次機(jī)會(huì)，并將訪問(wèn)位置 0 ?理想淘汰算法 — 最佳頁(yè)面算法（ OPT） 淘汰以后不再需要的或最遠(yuǎn)的將來(lái)才會(huì)用到的頁(yè)面 虛擬存儲(chǔ)器的基本概念 ?最近最少使用頁(yè)面淘汰算法（ LRU） 選擇最后一次訪問(wèn)時(shí)間距離當(dāng)前時(shí)間最長(zhǎng)的一頁(yè)并淘汰之 即淘汰沒(méi)有使用的時(shí)間最長(zhǎng)的頁(yè) 實(shí)現(xiàn)代價(jià)很高 時(shí)間戳或硬件方法 虛擬存儲(chǔ)器的基本概念 例子 1：計(jì)算缺頁(yè)次數(shù) 某程序在內(nèi)存中分配三個(gè)頁(yè)面，初始為空，頁(yè)面走向?yàn)?4， 3， 2， 1， 4， 3， 5， 4，3， 2， 1， 5 虛擬存儲(chǔ)器的基本概念 FIFO 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 3 2 1 4 3 5 5 5 2 1 1 頁(yè) 2 4 3 2 1 4 3 3 3 5 2 2 頁(yè) 3 4 3 2 1 4 4 4 3 5 5 x x x x x x x ? ? x x ? 共缺頁(yè)中斷 9次 虛擬存儲(chǔ)器的基本概念 LRU 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 2 4 3 2 1 4 3 5 4 3 2 1 頁(yè) 3 4 3 2 1 4 3 5 4 3 2 x x x x x x x ? ? x x x 共缺頁(yè)中斷 10次 虛擬存儲(chǔ)器的基本概念 OPT 4 3 2 1 4 3 5 4 3 2 1 5 頁(yè) 1 4 3 2 1 1 1 5 5 5 2 1 1 頁(yè) 2 4 3 3 3 3 3 3 3 5 5 5 頁(yè) 3 4 4 4 4 4 4 4 4 4 4 x x x x ? ? x ? ? x x ? 共缺頁(yè)中斷 7次 虛擬存儲(chǔ)器的基本概念 例子 2：計(jì)算缺頁(yè)次數(shù) 某程序在內(nèi)存中分配 m頁(yè)初始為空，頁(yè)面走向?yàn)?1， 2， 3， 4， 1， 2， 5， 1， 2， 3，4， 5。當(dāng) m=3， m=4時(shí)缺頁(yè)中斷分別為多少？用 FIFO算法 課堂練習(xí)： 分別用 LRU， OPT算法計(jì)算缺頁(yè)中斷次數(shù) 虛擬存儲(chǔ)器的基本概念 例子 2：計(jì)算缺頁(yè)次數(shù) m=3時(shí)，缺頁(yè)中斷 9次 m=4時(shí)，缺頁(yè)中斷 10次 注： FIFO頁(yè)面淘汰算法會(huì)產(chǎn)生異常現(xiàn)象（ Belady現(xiàn)象 :顛簸 ），即：當(dāng)分配給進(jìn)程的物理頁(yè)面數(shù)增加時(shí)，缺頁(yè)次數(shù)反而增加 虛擬存儲(chǔ)器的基本概念 影響缺頁(yè)次數(shù)的因素 (1) 分配給進(jìn)程的物理頁(yè)面數(shù) (2) 頁(yè)面本身的大小 (3) 程序的編制方法 (4) 頁(yè)面淘汰算法 虛擬存儲(chǔ)器的基本概念 性能問(wèn)題 顛簸（抖動(dòng)） 在虛存中，頁(yè)面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁(yè)面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動(dòng) 原因： ?頁(yè)面淘汰算法不合理 ?分配給進(jìn)程的物理頁(yè)面數(shù)太少 虛擬存儲(chǔ)器的基本概念 工作集（ Working Set）模型 基本思想 ： 根據(jù)程序的局部性原理，一般情況下，進(jìn)程在一段時(shí)間內(nèi)總是集中訪問(wèn)一些頁(yè)面，這些頁(yè)面稱為活躍頁(yè)面，如果分配給一個(gè)進(jìn)程的物理頁(yè)面數(shù)太少了，使該進(jìn)程所需的活躍頁(yè)面不能全部裝入內(nèi)存，則進(jìn)程在運(yùn)行過(guò)程中將頻繁發(fā)生中斷 如果能為進(jìn)程提供與活躍頁(yè)面數(shù)相等的物理頁(yè)面數(shù)，則可減少缺頁(yè)中斷次數(shù) 虛擬存儲(chǔ)器的基本概念 對(duì)于給定的訪問(wèn)序列選取定長(zhǎng)的區(qū)間，稱為工作集窗口，落在工作集窗口中的頁(yè)面集合稱為工作集 內(nèi)容取決于頁(yè)的三個(gè)因素： ? 訪頁(yè)序列特性 ? 時(shí)刻 Ti ? 窗口長(zhǎng)度 (△ ) 虛擬存儲(chǔ)器的基本概念 例： 26157775162341234443434441328674 | t1 | | t2 | ws(t1)={1,2,5,6,7} ws(t2)={3,4} 虛擬存儲(chǔ)器的基本概念 虛擬存儲(chǔ)器的基本概念 ? 課堂練習(xí) 上例中，采用工作集算法，總共需要分配多少頁(yè)面才能保證在程序執(zhí)行過(guò)程中不發(fā)生缺頁(yè)中斷。 如果采用 FIFO算法，初始頁(yè)面數(shù)為工作集長(zhǎng)度，計(jì)算缺頁(yè)中斷次數(shù)。 LRU與 OPT算法呢？ 虛擬段式存儲(chǔ)管理 段表內(nèi)容 增加：特征位（在 /不在內(nèi)存，是否可共享），存取權(quán)限位（讀，寫(xiě)，執(zhí)行），標(biāo)志位（是否修改過(guò)，能否移動(dòng)），擴(kuò)充位（固定長(zhǎng) /可擴(kuò)充 ） 虛擬存儲(chǔ)器的基本概念 越界中斷處理 進(jìn)程在執(zhí)行過(guò)程中，有時(shí)需要擴(kuò)大分段，如數(shù)據(jù)段。由于要訪問(wèn)的地址超出原有的段長(zhǎng)，所以有 越界中斷 。操作系統(tǒng)處理中斷時(shí) ，首先判斷該段的“擴(kuò)充位”，如可擴(kuò)充，則增加段的長(zhǎng)度；否則按出錯(cuò)處理 虛擬存儲(chǔ)器的基本概念 缺段中斷處理 檢查內(nèi)存中是否有足夠的空閑空間 ①若有，則裝入該段，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)，中斷返回 ②若沒(méi)有，檢查內(nèi)存中空閑區(qū)的總和是否滿足要求，是則應(yīng)采用緊縮技術(shù)，轉(zhuǎn)① ；否則，淘汰一（些）段，轉(zhuǎn)① 虛擬存儲(chǔ)器的基本概念 虛擬存儲(chǔ)器的特征 1. 多次性 2. 對(duì)換性 3. 虛擬性 虛擬存儲(chǔ)器的基本概念 交換技術(shù)與覆蓋技術(shù) 在多道環(huán)境下擴(kuò)充內(nèi)存的方法，用以解決在較小的存儲(chǔ)空間中運(yùn)行較大程序時(shí)遇到的矛盾 覆蓋技術(shù)主要用在早期的操作系統(tǒng)中 交換技術(shù)被廣泛用于小型分時(shí)系統(tǒng)中，交換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn) 交換技術(shù)與覆蓋技術(shù)共同點(diǎn)： 進(jìn)程的程序和數(shù)據(jù)主要放在外存，當(dāng)前需要執(zhí)行的部分放在內(nèi)存，內(nèi)外存之間進(jìn)行信息交換 不同點(diǎn)：如何控制交換？ 交換技術(shù)與覆蓋技術(shù) 虛擬存儲(chǔ)的實(shí)現(xiàn) 虛擬存儲(chǔ)空間 物理存儲(chǔ)空間 請(qǐng)求調(diào)頁(yè) 請(qǐng)求調(diào)段 交換與覆蓋