第七章虛擬存儲管理

1、第七章 虛擬存儲管理具有主存“擴(kuò)充”功能的存儲管理系統(tǒng)OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚1 虛擬存儲器概念一、局部性原理幾乎所有的程序在執(zhí)行時都呈現(xiàn)出局部性規(guī)律。即在一較短時間內(nèi)，程序執(zhí)行總是局限于地址空間的某個局部區(qū)域，呈現(xiàn)出地址訪問聚集成群的傾向時間局部性:一旦程序的某個位置數(shù)據(jù)或指令被訪問，它常常再次被訪問空間局部性：一旦程序的某個位置數(shù)據(jù)或指令被訪問，它附近的位置很快被訪問OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚10+20+30+40+50+60+70=280K(0,0 )(0,1 )(1,0 )(1,1 )(1,2 )(1,3 )覆蓋技術(shù)：10+30+70=110K1 虛擬存儲

2、器概念二、(自動)覆蓋技術(shù)任何程序均由若干功能相對獨立的程序段組成,在運行中無需將全部程序段同時裝入內(nèi)存?？梢园闯绦虻倪壿嫿Y(jié)構(gòu)將那些不會同時執(zhí)行的程序段組成覆蓋,使它們共享主存同一區(qū)域,從而達(dá)到邏輯上“擴(kuò)充”主存的目的。OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚1 虛擬存儲器概念三、虛擬存儲器1.虛存定義早期定義：把內(nèi)存與外存有機(jī)的結(jié)合起來使用，從而得到一個容量很大的“內(nèi)存”，這就是虛存。一般性定義：系統(tǒng)通過軟硬件技術(shù)的結(jié)合，為每個作業(yè)提供的地址空間是一個虛擬存儲器。2.虛存容量 由CPU地址結(jié)構(gòu)決定eg:總線尋址能力為20位，CPU有效地址為18位【分析】實存=1M，虛存=256K，虛存 實存

3、3.虛擬存儲管理：具有主存“擴(kuò)充”功能的存儲管理系統(tǒng)OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚例1：虛擬存儲器的容量是由計算機(jī)地址結(jié)構(gòu)決定的，若CPU的地址為32位，則對于一個進(jìn)程來說，其最大的虛擬存儲空間為B。A. 2G B. 4G C. 0.5G D. 1G例2：設(shè)主存容量為8MB,輔存容量為50MB，計算機(jī)地址寄存器是24位，則虛存的最大容量為。A.8MB B.50MB+8MB C.50MB+224B D.224B例3：判斷題。(1) 覆蓋和交換都需要從外存讀入信息，所以覆蓋是交換 的別名。( )(2) 虛擬存儲器是一個假想的地址空間，因而這個地址的大小沒有限制的。( )(3)虛擬存儲技術(shù)

4、是一種拿時間換空間的技術(shù)。( )1 虛擬存儲器概念OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚1.地址空間等分為虛頁，存儲空間等分為實頁2.運行過程中，只裝入作業(yè)的部分頁面3.何時調(diào)入頁面：有兩種不同的調(diào)頁策略2 請求分頁一、基本原理請求調(diào)頁一次可調(diào)入多個頁面,調(diào)頁效率高預(yù)調(diào)頁需智能技術(shù)支持、預(yù)測準(zhǔn)確率問題調(diào)頁策略方法簡單,易于實現(xiàn)每次只能調(diào)入一頁,系統(tǒng)開銷大OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚1.地址空間等分為虛頁，存儲空間等分為實頁2.運行過程中，只裝入作業(yè)的部分頁面2 請求分頁一、基本原理3.何時調(diào)入頁面：有兩種不同的調(diào)頁策略4.如何判某頁是否在主存？ 擴(kuò)充頁表狀態(tài)位、有效位、中斷位：指

5、示對應(yīng)虛頁是否在主存輔存地址：指示頁面副本在輔存的位置OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚1.地址空間等分為虛頁，存儲空間等分為實頁2.運行過程中，只裝入作業(yè)的部分頁面3.何時調(diào)入頁面：有兩種不同的調(diào)頁策略2 請求分頁一、基本原理擴(kuò)充頁表5.如何處理頁面不在主存的情況？4.如何判某頁在主存否？硬件變址機(jī)構(gòu)發(fā)出缺頁(頁面故障)中斷信號OS處理缺頁中斷2.內(nèi)存無空閑塊,缺頁中斷處理程序需進(jìn)行頁面置換1.內(nèi)存有空閑塊,根據(jù)缺頁的輔存地址將其調(diào)入主存OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚1.地址空間等分為虛頁，存儲空間等分為實頁2.運行過程中，只裝入作業(yè)的部分頁面3.何時調(diào)入頁面：有兩種不同的調(diào)

6、頁策略2 請求分頁一、基本原理擴(kuò)充頁表5.如何處理頁面不在主存的情況？4.如何判某頁在主存否？固定分配局部置換進(jìn)程駐留集大小不變，從進(jìn)程內(nèi)部置換頁面可變分配全局置換可向OS申請新的主存塊，否則從任一進(jìn)程駐留集中置換可變分配局部置換在進(jìn)程內(nèi)部置換，若頁面故障頻繁，則追加主存OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚1.地址空間等分為虛頁，存儲空間等分為實頁2.運行過程中，只裝入作業(yè)的部分頁面3.何時調(diào)入頁面：有兩種不同的調(diào)頁策略2 請求分頁一、基本原理擴(kuò)充頁表5.如何處理頁面不在主存的情況？4.如何判某頁在主存否？6.擴(kuò)充的頁表：頁面近期被訪問的次數(shù)，或最近被訪問的時間頁面裝入主存是被修改過OS原

7、理第7章 虛擬存儲揚州大學(xué) 鄒姝稚例1:在請求分頁存儲管理中,當(dāng)所訪問的頁面不在內(nèi)存時,便產(chǎn)生缺頁中斷,缺頁中斷是屬于。A. I/O中斷B.程序中斷C.訪管中斷D.外中斷例2：作業(yè)在執(zhí)行中發(fā)生缺頁中斷，經(jīng)操作系統(tǒng)處理后，應(yīng)讓其執(zhí)行指令。A.被中斷的前一條B.被中斷的后一條C.被中斷的那一條D.啟動時的第一條例3 ：在請求分頁系統(tǒng)中，凡未裝入過的頁都應(yīng)從調(diào)入主存。A. 系統(tǒng)區(qū)B. 文件區(qū)C. 交換區(qū)D.頁面緩沖區(qū)2 請求分頁例4：在虛擬內(nèi)存管理中，地址變換機(jī)構(gòu)將邏輯地址變換為物理地址，形成該邏輯地址的階段是。A.編輯B.編譯C.鏈接D.裝載OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚例6 ：在缺頁處

8、理過程中，操作系統(tǒng)執(zhí)行的操作可能是。I修改頁表 II磁盤I/O III分配頁框A. 僅I、II B.僅II C.僅III D.I、II和III2 請求分頁例5：為了支持請求式分頁內(nèi)存管理，通常頁表項內(nèi)存有一標(biāo)志位，用來記錄相應(yīng)頁是否被寫過，請解釋該標(biāo)志位的操作者及其作用。OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚例1：已知進(jìn)程訪問如下頁面，窗口尺寸=6，試求t時刻的工作集。W(t, 6)=1,2,7,8一頁面剛換出不久又需調(diào)入,為此選擇一頁調(diào)出,而這一剛換出的頁,很快又要訪問又需將其調(diào)入如此頻繁的更換頁面,使得大部分機(jī)器時間都花費在頁面置換上。二、工作集Working set進(jìn)程運行中距時刻t最

9、近的次訪問所涉及的頁面集,稱作進(jìn)程的工作集,記為W(t, )。其中數(shù)字稱為工作集窗口。3 頁面置換算法及性能一、抖動(顛簸)OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚3 頁面置換算法及性能一、抖動(顛簸)一頁面剛換出不久又需調(diào)入,為此選擇一頁調(diào)出,而這一剛換出的頁,很快又要訪問又需將其調(diào)入如此頻繁的更換頁面,使得大部分機(jī)器時間都花費在頁面置換上。二、工作集Working set進(jìn)程運行中距時刻t最近的次訪問所涉及的頁面集,稱作進(jìn)程的工作集,記為W(t, )。其中數(shù)字稱為工作集窗口。例2：=9，試求w(t1, ) 和w(t2, )W(t1, )=1,2,3,6,7,8,9W(t2, )=3,4OS

10、原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚三、缺頁中斷率f固定分配局部置換設(shè)作業(yè)共計n頁,系統(tǒng)分配給該作業(yè)的主存塊為m塊,且1mn若作業(yè)運行中成功訪問次數(shù)為S;若作業(yè)運行中不成功訪問次數(shù)為F;則總訪問次數(shù) A=S+F;定義：f=F/A為作業(yè)的缺頁中斷率四、影響f的因素分配給作業(yè)的主存塊數(shù) m頁面的尺寸大小程序編制方法頁面置換算法性能優(yōu)劣go3 頁面置換算法及性能OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚例：一程序?qū)?56256矩陣A置初值0。該矩陣定義為：VAR A:ARRAY1.256,1.256 of INTEGER;假定分配給該矩陣的內(nèi)存塊為1塊，頁面大小為每頁256個整數(shù)字，矩陣按行存放，開始

11、內(nèi)存為空。若程序和有關(guān)變量已存放主存。問：程序運行時共發(fā)生多少次缺頁中斷？A. 256-1 B.256 C. 2562-1 D.2562【程序1】FOR J:=1 to 256FOR I:=1 to 256AI,J:=0;【程序2】FOR I:=1 to 256FOR J:=1 to 256AI,J:=0;DB3 頁面置換算法及性能OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚例:一作業(yè)在執(zhí)行中的頁面引用串為7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1分配給該作業(yè)的主存塊m=3,試計算基于OPT的缺頁中斷率f。解：預(yù)調(diào)頁后，內(nèi)存頁面號：7,0,1f=6/20=30%

12、1.最佳置換算法OPT（Optimal）選擇以后不再訪問的頁或距現(xiàn)在最長時間后才需再訪問的頁進(jìn)行置換3 頁面置換算法及性能五、常用頁面置換算法OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚例1：已知一作業(yè)獲得3塊主存，其頁面訪問次序為：4,3,0,4,1,1,2,3,2。試計算基于FIFO的缺頁中斷次數(shù)。解：預(yù)調(diào)頁后初始頁面：4，3，0第幾次缺頁中斷調(diào)進(jìn)/出頁內(nèi)存頁面號1 1/42 2/33 3/03,0,10,1,21,2,3淘汰鏈?zhǔn)醉撁?，將新調(diào)入的頁面號結(jié)點插至鏈尾2.先進(jìn)先出算法FIFO (First-in, First-out) Belady現(xiàn)象3 頁面置換算法及性能建立一個存放內(nèi)存頁面號的

13、鏈表,最老頁在鏈?zhǔn)?最新頁在鏈尾思想：淘汰最早進(jìn)入主存，在主存駐留時間最長的頁面。OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚例2 ：什么是Belady現(xiàn)象？舉例說明。Belady現(xiàn)象是指：在請求分頁系統(tǒng)中,若采用FIFO算法進(jìn)行頁面置換,有可能出現(xiàn)隨著分配給進(jìn)程的主存塊增加,缺頁中斷次數(shù)也隨之增加的異?，F(xiàn)象。3 頁面置換算法及性能OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚例2 ：什么是Belady現(xiàn)象？舉例說明。3 頁面置換算法及性能舉例：頁面走向為4,3,2,1,4,3,5,4,3,2,1,5。初始內(nèi)存為空。分別以主存駐留集為3和4塊計算。OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚3. LRU算法

14、(Least Recently Used)3 頁面置換算法及性能思想：淘汰最近一段時間最久未使用的頁面實現(xiàn)：建立堆棧存放進(jìn)程當(dāng)前在主存的頁面號每訪問一頁，調(diào)整棧一次：將所訪頁調(diào)至棧頂淘汰棧底指示的頁面，新進(jìn)頁壓入棧頂例1：某程序在內(nèi)存中分配三個頁面，初始為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5。在LRU頁面置換策略下，該程序執(zhí)行中共產(chǎn)生幾次缺頁中斷？OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚(1) FOR I:=1 to 100 DOFOR J:=1 to 100 DOAI,J:=0;(2) FOR J:=1 to 100 DOFOR I:=1 to 100 DOAI,J:

15、=0;當(dāng)采用先來先服務(wù)的算法時，兩種情況各產(chǎn)生多少次缺頁中斷？【分析】在缺頁中斷時，調(diào)進(jìn)/調(diào)出的基本單位是1頁程序（1）按行處理，共產(chǎn)生100/2=50次缺頁中斷。程序（2）按列處理，共產(chǎn)生100*100/2=5000次缺頁中斷。3 頁面置換算法及性能例2：有一矩陣：VAR A:ARRAY1.100,1.100 OF integer;按先行后列次序存放。在一虛擬存儲系統(tǒng)中，采用LRU淘汰算法，一個進(jìn)程獲得3塊內(nèi)存，每頁可放200個整數(shù)。其中第1頁存放程序，且假定程序已在內(nèi)存，另二塊存放數(shù)據(jù)，初始狀態(tài)為空。程序編制如下：OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚頁號 頁框號有效位(存在位)0101

16、H1102254H13 頁面置換算法及性能例3：請求分頁管理系統(tǒng)中，假設(shè)某進(jìn)程頁表：頁面大小4KB,一次內(nèi)存訪問時間是100ns，一次快表(TLB)的訪問時間是10ns,處理一次缺頁的平均時間為108ns(已含更新TLB和頁表的時間),進(jìn)程的駐留集大小固定為2,采用LRU和局部淘汰策略。假設(shè)TLB初始為空；地址轉(zhuǎn)換時先訪問TLB,若TLB未命中,再訪問頁表(忽略訪問頁表之后的TLB更新時間)；有效位為0表示頁面不在內(nèi)存,產(chǎn)生缺頁中斷,處理后返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，試問：(1) 依次訪問上述三個虛地址各需多少時間？給出計算過程。(

17、2)基于上述訪問序列，虛地址1565H的物理地址是多少？說明理由。OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚3 頁面置換算法及性能為每頁設(shè)置頁面訪問位A，當(dāng)訪問該頁時置A1將作業(yè)的主存頁面鏈成循環(huán)鏈表設(shè)查詢指針，初始指向最老頁例：某時刻，一作業(yè)有4, 2, 5, 1頁按序進(jìn)入主存42514. 最近未用算法NRU(Not Recently Used) clock算法OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚例:設(shè)某計算機(jī)的邏輯地址空間和物理地址空間均為64K,按字節(jié)編址。某進(jìn)程最多需要6頁數(shù)據(jù)存儲空間，頁的大小為1KB，OS采用固定分配局部置換策略為此進(jìn)程分配4個頁框。當(dāng)進(jìn)程執(zhí)行到時刻260時要訪問

18、邏輯地址為17CAH的數(shù)據(jù)，請回答下列問題：(1)該邏輯地址對應(yīng)的頁號是多少？(2)若采用FIFO置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。(3)若采用Clock算法，該邏輯地址對應(yīng)的物理地址是多少？設(shè)搜索下一頁的指針沿順時針方向移動，且當(dāng)前指向2號頁框，示意圖如下。3 頁面置換算法及性能OS原理第7章 虛擬存儲揚州大學(xué) 鄒姝稚段號狀態(tài) 段長段始址存取方式訪問 修改位 位增補(bǔ)位外存地址狀態(tài)：該段是否在主存及可否共享整補(bǔ)位：該段可否在最大段長范圍內(nèi)動態(tài)增長4 段式虛擬存儲系統(tǒng)一、基本原理作業(yè)地址空間中所有段的副本均保存于輔存上。在作業(yè)運行前，只裝入當(dāng)前所需部分段。在運行過程中，以缼段中斷處理方式調(diào)入所需的段。