虛擬存儲管理

操作系統(tǒng)第三講虛擬存儲管理前面所介紹的各種存儲器管理方式有一個(gè)共同的特點(diǎn)，即它們都要求將一個(gè)作業(yè)全部裝入內(nèi)存后方能運(yùn)行，于是，出現(xiàn)了下面這樣兩種情況：(1)有的作業(yè)很大，其所要求的內(nèi)存空間超過了內(nèi)存總?cè)萘浚鳂I(yè)不能全部被裝入內(nèi)存，致使該作業(yè)無法運(yùn)行。(2)有大量作業(yè)要求運(yùn)行，但由于內(nèi)存容量不足以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們先運(yùn)行，而將其它大量的作業(yè)留在外存上等待。虛擬存儲器的引入1．常規(guī)存儲器管理方式的特征(1)一次性。在前面所介紹的幾種存儲管理方式中，都要求將作業(yè)全部裝入內(nèi)存后方能運(yùn)行，即作業(yè)在運(yùn)行前需一次性地全部裝入內(nèi)存，而正是這一特征導(dǎo)致了上述兩種情況的發(fā)生。此外，還有許多作業(yè)在每次運(yùn)行時(shí)，并非其全部程序和數(shù)據(jù)都要用到。如果一次性地裝入其全部程序，也是一種對內(nèi)存空間的浪費(fèi)。(2)駐留性。作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。盡管運(yùn)行中的進(jìn)程會因I/O而長期等待，或有的程序模塊在運(yùn)行過一次后就不再需要(運(yùn)行)了，但它們都仍將繼續(xù)占用寶貴的內(nèi)存資源?，F(xiàn)在要研究的問題是：一次性及駐留性在程序運(yùn)行時(shí)是否是必需的？程序局部性原理在一段時(shí)間內(nèi)一個(gè)程序的執(zhí)行往往呈現(xiàn)出高度的局部性，表現(xiàn)在時(shí)間與空間兩方面時(shí)間局部性一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行空間局部性若某一存儲單元被使用，則在一定時(shí)間內(nèi)，與該存儲單元相鄰的單元可能被使用七、虛擬存儲連續(xù)性；駐留性；一次性；離散性交換性多次性

以CPU時(shí)間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)1、概述問題的提出程序大于內(nèi)存程序暫時(shí)不執(zhí)行或運(yùn)行完是否還要占用內(nèi)存

虛擬存儲器的基本思想是？虛擬存儲器支持多道程序設(shè)計(jì)技術(shù)

程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時(shí)在內(nèi)存和磁盤之間動(dòng)態(tài)交換虛擬存儲技術(shù)虛存：把內(nèi)存與外存有機(jī)的結(jié)合起來使用，從而得到一個(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)存工作；當(dāng)沒有足夠的內(nèi)存空間時(shí)，系

統(tǒng)自動(dòng)選擇部分內(nèi)存空間，將其中原有的內(nèi)容

交換到磁盤上，并釋放這些內(nèi)存空間供其它進(jìn)

程使用。（虛擬存儲技術(shù)的概念）目的：提高內(nèi)存利用率概述（續(xù)2）內(nèi)存

磁盤控制器MMU

總線

虛擬地址CPU物理地址MMU：內(nèi)存管理單元虛擬存儲器的特征1．多次性多次性是指一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行。多次性是虛擬存儲器最重要的特征，任何其它的存儲管理方式都不具有這一特征。因此，我們也可以認(rèn)為虛擬存儲器是具有多次性特征的存儲器系統(tǒng)。2．對換性對換性是指允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)(從外存調(diào)至內(nèi)存)、換出(至外存的對換區(qū))；甚至還允許將暫時(shí)不運(yùn)行的進(jìn)程調(diào)至外存，待它們重又具備運(yùn)行條件時(shí)再調(diào)入內(nèi)存。3．虛擬性虛擬性是指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。這是虛擬存儲器所表現(xiàn)出來的最重要的特征，也是實(shí)現(xiàn)虛擬存儲器的最重要的目標(biāo)。2、虛擬擬頁式式存儲儲管理理（1）基本思思想在進(jìn)程程開始始運(yùn)行行之前前，不不是裝裝入全全部頁頁面，而是裝裝入一個(gè)或或零個(gè)頁面面，之后根根據(jù)進(jìn)程運(yùn)行行的需要，，動(dòng)態(tài)裝入入其它頁面；當(dāng)內(nèi)存存空間已滿滿，而又需需要裝入新新的頁面時(shí)，，則根據(jù)某某種算法淘淘汰某個(gè)頁頁面，以便裝裝入新的頁頁面頁號、駐留留位、內(nèi)存存塊號、保保護(hù)位、訪訪問位、修改位位駐留位（中中斷位）：：表示該頁頁是在內(nèi)存存還是在外外存訪問位：根根據(jù)訪問位位來決定淘淘汰哪頁（（由不同的的算法決定）修改位：查查看此頁是是否在內(nèi)存存中被修改改過保護(hù)位：：讀/寫/執(zhí)行禁止緩存存位：采采用內(nèi)存存映射I/O的機(jī)器中中需要頁號中斷位內(nèi)內(nèi)存塊號號保保護(hù)位位禁止緩存存位訪問位修修改改位（2）頁表表表項(xiàng)設(shè)計(jì)計(jì)XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K物理地址空空間虛地址空間間}虛頁頁框28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K000000000000000011110000101100000000000001111001000111010011010115141312111098765432100010000000000100110000000000100110在/不在在內(nèi)內(nèi)存存頁表表虛地地址址8196物理理地地址址24580（3）缺缺頁頁中中斷斷（（PageFault）處處理理在地地址址映映射射過過程程中中，，在在頁頁表表中中發(fā)發(fā)現(xiàn)現(xiàn)所所要要訪訪問問的的頁不不在在內(nèi)內(nèi)存存，，則則產(chǎn)產(chǎn)生生缺缺頁頁中中斷斷。。操操作作系系統(tǒng)統(tǒng)接接到到此中中斷斷信信號號后后，，就就調(diào)調(diào)出出缺缺頁頁中中斷斷處處理理程程序序，，根根據(jù)頁頁表表中中給給出出的的外外存存地地址址，，將將該該頁頁調(diào)調(diào)入入內(nèi)內(nèi)存存，，使作作業(yè)業(yè)繼繼續(xù)續(xù)運(yùn)運(yùn)行行下下去去如果果內(nèi)內(nèi)存存中中有有空空閑閑塊塊，，則則分分配配一一頁頁，，將將新新調(diào)調(diào)入入頁裝裝入入內(nèi)內(nèi)存存，，并并修修改改頁頁表表中中相相應(yīng)應(yīng)頁頁表表項(xiàng)項(xiàng)目目的的駐駐留位及相相應(yīng)的內(nèi)內(nèi)存塊號號若此時(shí)內(nèi)內(nèi)存中沒沒有空閑閑塊，則則要淘汰汰某頁，，若該頁在內(nèi)內(nèi)存期間間被修改改過，則則要將其其寫回外外存（4）頁面淘汰汰算法理想淘汰汰算法—最佳頁面面算法（（OPT：：Optimal）淘汰以后后不再需需要的或或最遠(yuǎn)的將來來才會用到的頁頁面實(shí)現(xiàn)？作用？先進(jìn)先出出頁面淘淘汰算法法（FIFO）選擇在內(nèi)內(nèi)存中駐駐留時(shí)間間最長的的頁并淘淘汰之策略模型型：超市市撤換商商品頁面淘汰汰算法（（續(xù)1）最近未使使用頁面面淘汰算算法（NRU———NotRecentlyUsed）選擇在最最近一段段時(shí)間內(nèi)內(nèi)未使用用過的一一頁并淘淘汰之實(shí)現(xiàn)：設(shè)設(shè)置兩位位訪問位（（R），修修改位（（M）啟動(dòng)一個(gè)個(gè)進(jìn)程時(shí)時(shí)，R、M置0R被定期清清零發(fā)生缺頁頁中斷時(shí)時(shí)，操作作系統(tǒng)檢檢查R，M：第0類：無訪問問，無修修改第1類：無訪訪問，有有修改第2類：有訪訪問，無無修改第3類：有訪訪問，有有修改操作系統(tǒng)統(tǒng)隨機(jī)從從編號最最小的非非空類中中選擇一一頁淘汰頁面淘汰汰算法（（續(xù)2）是最佳淘淘汰頁并不是很很好的淘淘汰頁該頁有可可能再被被訪問該頁可可能再再被訪訪問在將一一個(gè)頁頁面換換出時(shí)時(shí)，如如果該該頁已已被修修改過過，便便須將將該頁頁重新新寫回回到磁磁盤上上；但但如果果該頁頁未被被修改改過，，則不不必將將它拷拷回磁磁盤。。在該該算法法中，，除須須考慮慮頁面面的使使用情情況外外，還還須再再增加加一個(gè)個(gè)因素素，即即置換換代價(jià)價(jià)，這這樣，，選擇擇頁面面換出出時(shí)，，既要要是未未使用用過的的頁面面，又又要是是未被被修改改過的的頁面面。把把同時(shí)時(shí)滿足足這兩兩個(gè)條條件的的頁面面作為為首選選淘汰汰的頁頁面。。頁面淘汰算法法（續(xù)3）第二次機(jī)會淘淘汰算法(SCR-SecondChance)按照先進(jìn)先出出算法選擇某某一頁面，檢檢查其訪問位，如果果為0，則淘汰該頁頁，如果為1，則給第二次次機(jī)會，并將將訪問位置0實(shí)現(xiàn)：時(shí)鐘（（Clock）算法LKJIHGFEDCBA頁面淘汰算法法（續(xù)4）最近最久未使使用頁面淘汰汰算法（LRU——LeastRecentlyUsed）選擇最后一次次訪問時(shí)間距距離當(dāng)前時(shí)間間最長的一頁并淘淘汰之即淘汰沒有使使用的時(shí)間最最長的頁實(shí)現(xiàn)代價(jià)很高高時(shí)間戳或硬件件方法硬件方法：在一個(gè)有n個(gè)個(gè)頁框的機(jī)器器中，LRU硬件可以維維持一個(gè)n*n位的矩陣陣，開始時(shí)所所有位都是0。當(dāng)訪問到到頁K時(shí)，硬硬件首先把k行的位都設(shè)設(shè)置成1，再再把k列的位位都設(shè)置成0.任何時(shí)刻刻，二進(jìn)制值值最小的行就就是最久未使使用的，第二二小的行是下下一個(gè)最久未未使用的，以以此類推。頁面淘汰算法法（續(xù)5）LRU的軟件解決方方案：最不經(jīng)常使用用（NFU-NotFrequentlyUsed）選擇訪問次數(shù)數(shù)最少的頁面面淘汰之實(shí)現(xiàn)：軟件計(jì)計(jì)數(shù)器，一頁頁一個(gè)，初值值為0。每次時(shí)鐘中斷時(shí)時(shí)，計(jì)數(shù)器加加R。發(fā)生缺頁中中斷時(shí)，選擇計(jì)數(shù)數(shù)器值最小的一一頁淘汰改進(jìn)（模擬LRU）：計(jì)數(shù)器在在加R前先右移一位位R位加到計(jì)數(shù)器器的最左端稱為老化算法發(fā)生缺頁時(shí)，，淘汰計(jì)數(shù)器器值最小的頁頁面頁0~5的R位

時(shí)鐘周周期為0101011101011101011101011101011頁012345頁0~5的R位

時(shí)鐘周周期為2頁0~5的R位

時(shí)鐘周周期為4例1：某程序在內(nèi)內(nèi)存中分配三三個(gè)頁面，初初始為空，頁面面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5，按照FIFO、LRU、

OPT計(jì)算缺頁次次數(shù)頁面淘汰算法法（續(xù)6）FIFO4321

頁14321

頁2432

頁343 xxxx4 4 1 2 x3 3 4 1 x5 5 3 4 x43 55 33 44

√√

2 2 5 3x15 11 22 55 x√共缺頁中斷9次LRU4321頁14321頁2432頁343xxxx4412x3341x543543354435x√√215215321432xxx共缺頁中斷10次頁面淘汰算法法（續(xù)8）OPT4321頁14321頁2433頁344xxxx4134√3134√5534x4534√3534√2254x15115544x√共缺頁中斷7次頁面淘汰算法法（續(xù)9）例2：某程序在內(nèi)內(nèi)存中分配m頁初始為空，，頁面走向?yàn)?，2，3，4，1，2，5，1，2，3，4，5。當(dāng)m=3，m=4時(shí)缺頁中斷分分別為多少？用用FIFO算法計(jì)算缺頁頁次數(shù)頁面淘汰算法法（續(xù)10）注：FIFO頁面淘汰算法法會產(chǎn)生異常?，F(xiàn)象（Belady現(xiàn)象），即：：當(dāng)分配給進(jìn)程的物理頁頁面數(shù)增加時(shí)時(shí)，缺頁次數(shù)反而增加頁面淘汰算法法（續(xù)11）m=3時(shí)，缺頁中斷斷9次m=4時(shí)，缺頁中斷斷10次分配給進(jìn)程的的物理頁面數(shù)數(shù)頁面本身的大大小程序的編制方方法頁面淘汰算法法（5）影響缺頁次數(shù)數(shù)的因素試分析上述因因素如何影響響缺頁次數(shù)？？程序編制方法法1：Forj:=1to128Fori:=1to128A[i,j]:=0;程序編制方法法2：Fori:=1to128Forj:=1to128A[i,j]:=0;影響缺頁次數(shù)數(shù)的因素（續(xù)續(xù)1）例子3：內(nèi)存分配一一頁，初始時(shí)第一一頁在內(nèi)存；；頁面大小為128個(gè)整數(shù)；矩陣陣A128X128按行存放你能看出兩種種程序編制方方法有什么區(qū)區(qū)別么？試分分析哪種方法法較好？（1）顛簸（抖動(dòng)））在虛存中，頁頁面在內(nèi)存與與外存之間頻頻繁調(diào)度，以至于調(diào)調(diào)度頁面所需需時(shí)間比進(jìn)程程實(shí)際運(yùn)行的時(shí)間還還多，此時(shí)系系統(tǒng)效率急劇劇下降，甚至導(dǎo)致致系統(tǒng)崩潰。。這種現(xiàn)象稱稱為顛簸或抖動(dòng)原因：頁面淘汰算法法不合理分配給進(jìn)程的的物理頁面數(shù)數(shù)太少3、性能問題基本思想：根根據(jù)程序的局局部性原理，，一般情況下，進(jìn)進(jìn)程在一段時(shí)時(shí)間內(nèi)總是集集中訪問一些頁面，，這些頁面稱稱為活躍頁面面，如果分配給一個(gè)個(gè)進(jìn)程的物理理頁面數(shù)太少少了，使該進(jìn)程所需需的活躍頁面面不能全部裝裝入內(nèi)存，則進(jìn)程在在運(yùn)行過程中中將頻繁發(fā)生生中斷如果能為進(jìn)程程提供與活躍躍頁面數(shù)相等等的物理頁面數(shù)，，則可減少缺缺頁中斷次數(shù)數(shù)（2）工作集（WorkingSet）模型對于給定的訪訪問序列選取取定長的區(qū)間間，稱為工作集窗口口，落在工作作集窗口中的的頁面集合稱為工作集內(nèi)容取決于頁頁的三個(gè)因素素：訪頁序列特性性時(shí)刻Ti窗口長度()工作集（WorkingSet）模模型型（（續(xù)續(xù)1）||t2||t1ws(t1)={1,2,5,6,7}ws(t2)={3,4}工作作集集（（WorkingSet）模模型型（（續(xù)續(xù)2）例：：（1）段表表內(nèi)內(nèi)容容增加加：：特征征位位（（在在/不在在內(nèi)內(nèi)存存，，是否否可可共共享享））存取權(quán)限位（（讀，寫，執(zhí)執(zhí)行）標(biāo)志位（是否否修改過，能能否移動(dòng)）擴(kuò)充位（固定定長/可擴(kuò)充）4、虛擬段式存存儲管理進(jìn)程在執(zhí)行過過程中，有時(shí)時(shí)需要擴(kuò)大分分段，如數(shù)據(jù)段段。由于要訪訪問的地址超超出原有的段長長，所以發(fā)越越界中斷。操操作系統(tǒng)處理中中斷時(shí)，首首先判斷該段段的“擴(kuò)充位””，如可擴(kuò)充充，則增加段段的長度；否則則按出錯(cuò)處理理（2）越界中斷處理理檢查內(nèi)存中是是否有足夠的的空閑空間①若有，則裝裝入該段，修修改有關(guān)數(shù)據(jù)據(jù)結(jié)構(gòu)，中斷返回回②若沒有，檢檢查內(nèi)存中空空閑區(qū)的總和和是否滿足要求，是是則應(yīng)采用緊緊縮技術(shù)，轉(zhuǎn)轉(zhuǎn)①；否則，，淘汰一（些些）段，轉(zhuǎn)①①（3）缺段中斷處理理大型程序：若干程序段，，若干數(shù)據(jù)段段一些熟知的事事實(shí)：進(jìn)程的某些程程序段在進(jìn)程程運(yùn)行期間可可能根本不用互斥執(zhí)行的程程序段沒有必必要同時(shí)駐留留內(nèi)存有些程序段執(zhí)執(zhí)行一次后不不再用到（4）段的動(dòng)態(tài)鏈接接靜態(tài)鏈接：為為了程序正確確執(zhí)行，必須須由連接裝配配程序把它們連連接成一個(gè)可可運(yùn)行的目標(biāo)標(biāo)程序，并在程序運(yùn)行前前都裝入內(nèi)存存。問題：花費(fèi)時(shí)時(shí)間，浪費(fèi)空空間動(dòng)態(tài)鏈接：在程序開始運(yùn)運(yùn)行時(shí)，只將將主程序段裝裝配好并調(diào)入入內(nèi)存，其它各各段的裝配是是在主程序段段的運(yùn)行過程中逐步完成成。每當(dāng)需要要調(diào)用一個(gè)新新段時(shí)，再將這個(gè)新段裝裝配好，并與與主程序段鏈鏈接段的動(dòng)態(tài)鏈接接（續(xù)1）LOAD100LOAD100600600800直接尋址間接尋址100100數(shù)據(jù)間接字?jǐn)?shù)據(jù)段的動(dòng)態(tài)鏈接接（續(xù)2）鏈接間接字和鏈接中中斷機(jī)器指令：直直接尋址，間間接尋址L直接地址段的動(dòng)態(tài)鏈接接（續(xù)3）采用間接尋址址時(shí)，間接地地址指示的單單元的內(nèi)容稱為間接接字，在間接接字中，包含含了直接地址，還包包含了附加的的狀態(tài)位。格格式為：L：鏈接標(biāo)志位位L=0：該段已經(jīng)建建立了鏈接L=1：該段尚未鏈鏈接處理機(jī)在執(zhí)行行間接指令時(shí)時(shí)，其硬件能能自動(dòng)對鏈接字中連連接標(biāo)志位進(jìn)進(jìn)行判斷。當(dāng)當(dāng)L=1時(shí)，硬件自動(dòng)動(dòng)發(fā)鏈接中斷斷，并停止執(zhí)執(zhí)行該間接指令，轉(zhuǎn)轉(zhuǎn)去執(zhí)行鏈接接中斷處理程程序。處理完后（L已被中斷處理理程序改為0），再重新執(zhí)行該該間接指令；；若L=0，則根據(jù)間接字中的直直接地址去取取數(shù)據(jù)編譯程序的準(zhǔn)準(zhǔn)備工作：段的動(dòng)態(tài)鏈接接（續(xù)4）............編譯前LOAD1,[A]|<B>LOAD*1,3|100100136786787“[A]|<B>”編譯后鏈接前段的動(dòng)態(tài)鏈接接（續(xù)5）100鏈接后6787“[A]|<B>04120段的動(dòng)態(tài)鏈接接（續(xù)6）3段LOAD*1,3|100120<Y>：12345678段的動(dòng)態(tài)態(tài)鏈接（（續(xù)7）4段鏈接中斷斷處理根據(jù)鏈接接間接字字找出要要訪問段段的符號號名和段內(nèi)地址址分配段號號，檢查查該段是是否在內(nèi)內(nèi)存，若若不在，則從從外存調(diào)調(diào)入，并并登記段段表，修修改內(nèi)存分配表表修改間接接字：修修改連接接標(biāo)志位位為0，修改直接地址址重新啟動(dòng)動(dòng)被中斷斷的指令令執(zhí)行段的動(dòng)態(tài)態(tài)鏈接（（續(xù)8）頁面尺寸寸TLB的大小、、位置、、訪問方方式局部與全全局分配配策略裝入策略略與清清除策策略多級頁表表內(nèi)存鎖定定（5）其他有關(guān)關(guān)設(shè)計(jì)問問題頁面尺寸寸確定頁面面大小對對于分頁頁的硬件件設(shè)計(jì)非非常重要要要考慮的的因素：：內(nèi)部碎片片頁表長度度缺頁次數(shù)數(shù)（缺頁頁率）Intel80x86/Pentium：4096或4M多頁面大大小的研研究與使使用其他有關(guān)關(guān)設(shè)計(jì)問問題（續(xù)續(xù)1）快表TLB（TranslationLookasideBuffers）為加快地地址映射射速度，，改善系系統(tǒng)性能能采用聯(lián)