第6章 虛擬存儲管理課件

第6章虛擬存儲管理本章要點●虛擬存儲器的引入

●請求頁式存儲管理

●請求段式存儲管理

●6.1虛擬存儲器的引入前面介紹的存儲管理方案要求作業(yè)全部裝入內(nèi)存才可運(yùn)行。但這會出現(xiàn)兩種情況：●有的作業(yè)因太大，內(nèi)存裝不下而無法運(yùn)行?！裣到y(tǒng)中作業(yè)數(shù)太多，因系統(tǒng)容量有限只能讓少數(shù)作業(yè)先運(yùn)行。問題：能否不把作業(yè)的全部信息同時裝入主存儲器，而讓作業(yè)開始執(zhí)行？如果這個問題能夠解決的話，當(dāng)主存空間小于作業(yè)需求量時，作業(yè)也能執(zhí)行，這就使得主存空間能被充分地利用，進(jìn)而用戶編制程序時可以不必考慮主存儲器的實際容量，允許用戶的邏輯地址空間大于主存儲器的絕對地址空間，對用戶來說，好像計算機(jī)系統(tǒng)具有一個容量很大的主存儲器，稱為虛擬存儲器。虛擬存儲器的容量由計算機(jī)的地址結(jié)構(gòu)和輔助存儲器（如磁盤）的容量決定，與實際主存儲器的容量無關(guān)。所以，虛擬存儲器實際上是為擴(kuò)大主存容量而采用的一種管理技巧。工作原理：以大容量的輔助存儲器（如磁盤）做后盾。把作業(yè)信息保留在磁盤上，當(dāng)要求裝入時，只將其中一部分先裝入主存儲器，另一部分暫時存放在磁盤上，作業(yè)執(zhí)行過程中要用到那些不在主存儲器中的信息時，再把它們裝到主存儲器中。問題：在作業(yè)信息不全部裝入主存的情況下能否保證作業(yè)的正確執(zhí)行?局部性原理（理論基礎(chǔ)）1968年P(guān).Denning提出●程序執(zhí)行時，大多數(shù)情況下是順序執(zhí)行的?！襁^程調(diào)用會使程序的執(zhí)行軌跡從一部分內(nèi)存區(qū)域轉(zhuǎn)至另一部分區(qū)域，但過程調(diào)用的深度不會超過5?！癯绦蛑杏性S多循環(huán)語句，這些語句會重復(fù)多次執(zhí)行?！癯绦蛑袑?shù)據(jù)結(jié)構(gòu)的操作，往往局限在很小的范圍內(nèi)。局部性原理局限性的表現(xiàn)●時間局限性程序中的的某條指令一旦執(zhí)行，不久后會再次執(zhí)行。●空間局限性程序一旦訪問某存儲單元，不久后會訪問其附近的存儲單元。虛擬存儲器的定義所謂虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲器系統(tǒng)?！耠x散性作業(yè)不裝入連續(xù)的存儲空間，內(nèi)存分配采用離散分配方式。●多次性一個作業(yè)被分割，被多次調(diào)入內(nèi)存?！駥Q性作業(yè)在運(yùn)行過程中換進(jìn)、換出內(nèi)存?！裉摂M性從邏輯上擴(kuò)充了內(nèi)存的容量。虛擬存儲器的特征實現(xiàn)虛擬存儲管理必須解決三個關(guān)鍵問題：怎樣知道當(dāng)前哪些信息已在主存儲器中，哪些信息尚未裝入主存儲器中？如果作業(yè)要訪問的信息不在主存儲器中，怎樣去找到這些信息且把它們裝入到主存儲器中？在把欲訪問的信息裝入主存儲器時，發(fā)現(xiàn)主存儲器中已無空閑區(qū)域，又該怎么辦？●6.2請求頁式存儲管理對采用頁式管理的存儲器來說，能被方便地改造成虛擬存儲器。改造的方法很簡單，只需將作業(yè)的全部信息作為副本存放在磁盤上，作業(yè)調(diào)度選中一個作業(yè)時，至少把作業(yè)的第一頁信息裝入主存儲器，在作業(yè)執(zhí)行過程中欲訪問不在主存儲器中的頁時，再把它們裝入。為此需要對頁表進(jìn)行改造。首先應(yīng)在頁表中指出哪些頁已在主存儲器中，哪些頁還沒裝入主存儲器，并且指出每一頁副本在磁盤上的位置。●狀態(tài)位P：記錄該頁是否在內(nèi)存。P=1該頁在內(nèi)存； P=0該頁不在內(nèi)存?！裨L問字段A：記錄該頁在一段時間內(nèi)被訪問的次數(shù)?！裥薷奈籑：記錄該頁在內(nèi)存期間是否被修改過。 M=1該頁調(diào)入內(nèi)存后被修改過；M=0該頁調(diào)入內(nèi)存后未被修改過?！裢獯娴刂罚涸擁撛谕獯娴牡刂贰ｍ摫淼臄U(kuò)充●6.2請求頁式存儲管理缺頁中斷機(jī)構(gòu)主要表現(xiàn)在：●在指令執(zhí)行期間產(chǎn)生和處理中斷信號。而普通中斷是在每條指令結(jié)束后去檢查是否有中斷到達(dá)?！褚粭l指令執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。一條雙操作數(shù)的指令在執(zhí)行時，指令本身和操作數(shù)可能都不在內(nèi)存。缺頁中斷是一種特殊的中斷movax,[2500]…………incax地址變換機(jī)構(gòu)頁面調(diào)度如果欲調(diào)入一頁時，主存儲器中已沒有空閑塊，怎么辦？則必須先調(diào)出已在主存儲器中的某一頁，再將當(dāng)前所需的頁調(diào)入，同時對頁表作相應(yīng)的修改。采用某種算法選擇一頁暫時調(diào)出，把它存放到磁盤上去，讓出主存空間，用來存放當(dāng)前要使用的頁面，這一過程稱為頁面調(diào)度。若被頁面調(diào)度選中調(diào)出的頁又要被訪問，則可用類似的方法調(diào)出另一些頁面而將其調(diào)入。頁面調(diào)度算法的選擇是很重要的。如果選用了一個不合適的調(diào)度算法就會出現(xiàn)這樣的現(xiàn)象：剛被調(diào)出的頁又立即要用，因而又要把它調(diào)入；而調(diào)入不久又被調(diào)出；調(diào)出不久又再次被調(diào)入。如此反復(fù)，使調(diào)度非常頻繁，以至于使大部分時間都花費(fèi)在來回調(diào)度上，這種現(xiàn)象稱為抖動，又稱顛簸。因而應(yīng)該選擇一種好的調(diào)度算法，以減少和避免抖動現(xiàn)象。

請求頁式存儲管理的頁面置換算法

●最佳置換算法OPT●先進(jìn)先出置換算法FIFO●最近最久未使用置換算法LRU●CLOCK置換算法Optimal算法系統(tǒng)為某個進(jìn)程分配了3個物理塊，假設(shè)進(jìn)程按照以下頁號的順序來訪問頁面;7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,170120120324320320170170120304230321201701共發(fā)生幾次缺頁中斷？9次。頁面換出6次，這是最理想的情況，置換的次數(shù)最少思想——置換那些不再使用，或最長時間不使用的頁。僅僅是一個理論算法而已。因為在實際應(yīng)用中，我們無法判斷哪一頁是以后不再訪問的頁或距離現(xiàn)在最長時間以后再訪問的頁770先進(jìn)先出算法系統(tǒng)為某個進(jìn)程分配了3個物理塊，假設(shè)進(jìn)程按照以下頁號的順序來訪問頁面;7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,170120123123043042042302301301271270270170120304230321201701思想——先進(jìn)入內(nèi)存的頁被先置換出去。OPT與FIFO的比較結(jié)果： OPT頁面換出6次，缺頁9次。 FIFO頁面換出12次，缺頁15次。7701072103024032403240321232137107012030423031201701LRU算法3022301022021032021置換置換置換置換LRU頁面換出9次，缺頁12次。707思想——用“過去”的行為預(yù)測將來，置換哪些“最近最久未使用”的頁。CLOCK頁面置換算法●

LRU性能較好，但實現(xiàn)困難！因此可用CLOCK算法。

●為每頁設(shè)一訪問位，再將內(nèi)存中的所有頁面鏈接成一循環(huán)隊列。●當(dāng)某頁被訪問時，其訪問位置1?！裰脫Q算法在選擇一頁淘汰時，只需檢查其訪問位。 如果是0，就選擇該頁換出； 如果是1，則重新將其置為0，暫不換出。CLOCK頁面置換算法●除了考慮頁面的使用情況外，還要考慮該頁是否被修改過。●由訪問位A和修改位M組合成下面四種情況的組合：●

<1>A=0，M=0該頁既未被訪問過、又未被修改過，是最佳淘汰頁?！?/p>

<2>A=0，M=1該頁最近未被訪問、但已被修改，可以被淘汰。●

<3>A=1，M=0最近已被訪問，但未被修改，該頁有可能再被訪問?！?/p>

<4>A=1，M=1最近已被訪問且被修改，該頁可能再被訪問。CLOCK算法執(zhí)行過程1>從當(dāng)前位置掃描循環(huán)隊列，尋找〈1〉類頁面。2>若1>失敗，開始第二輪掃描，尋找<2>類頁面，并將所經(jīng)過的頁面的訪問位置0。3>若2>也失敗，返回到開始位置，將所有的訪問位復(fù)0，goto1>。補(bǔ)充：UNIX的頁面調(diào)度UNIX采用的措施：（1）正在與外設(shè)交換信息的頁面或者正在被裝入的頁面是不能被替換的。（2）頁面調(diào)度采用二次機(jī)會頁面替換算法。實現(xiàn)要點如下：①把除了內(nèi)核部分的所有物理頁登錄在一張總頁面表中。②設(shè)置一個時鐘指針，掃描總頁面表。當(dāng)時鐘指針到達(dá)一個表項時，如果該物理頁是空閑的或正在與外設(shè)交換信息，則繼續(xù)掃描下一表項，否則找出占用該物理頁的進(jìn)程頁表。③按物理頁號從進(jìn)程頁表中找出對應(yīng)的表項。若該頁的有效位已經(jīng)被置成了0，則對該頁所占的物理頁置上“空閑”標(biāo)志。若該頁有效位為1，則把有效位改置成0。④產(chǎn)生缺頁中斷后，可找一個有空閑標(biāo)志的物理頁，將該物理頁中的信息調(diào)出到磁盤上，然后再來裝入新頁。⑤對有效位被置成0的頁，頁中的信息仍保留在所占的物理頁中，只要這個物理頁沒有空閑標(biāo)志，那么就不會被用來裝入新頁。這樣，一旦進(jìn)程又要訪問該頁時，只要把有效位重新置成1，使該頁信息成為二次有效，進(jìn)程就可立即訪問該頁信息。這樣就減少了大量的輸入/輸出傳送。（3）為了裝入一個新頁而要調(diào)出一頁時，要檢查被調(diào)出頁的修改位標(biāo)志。若該頁被修改過，則調(diào)出時必須把該頁的內(nèi)容寫回磁盤上，否則就不必寫回磁盤，以減少I/O（4）系統(tǒng)中有一個2號進(jìn)程，UNIX把它稱為頁面守護(hù)進(jìn)程，它的作用是保證有足夠的空閑物理頁可供使用。一般它處于睡眠狀態(tài)，每當(dāng)有空閑標(biāo)志的物理頁總數(shù)量低于一個限值時被喚醒。其職責(zé)如下：①控制二次機(jī)會算法中的時鐘指針，當(dāng)時鐘指針?biāo)傅哪澄锢眄摽沙蔀榭臻e頁時，把空閑物理頁數(shù)加1。②讓時鐘繼續(xù)掃描，使空閑物理頁不斷增加。③當(dāng)空閑物理頁數(shù)達(dá)到限值后，讓時鐘指針停止掃描。時鐘指針停止掃描時，頁面守護(hù)進(jìn)程就進(jìn)入睡眠狀態(tài)，直到被喚醒后再工作。缺頁中斷率

假定作業(yè)p共計n頁，系統(tǒng)分配給它的物理塊只有m塊（１≤m≤n）。如果作業(yè)p在運(yùn)行中成功的訪問次數(shù)為s（訪問的地址都在內(nèi)存中），不成功的訪問次數(shù)為F（訪問的地址在外存），則總的訪問次數(shù)Ａ為：A=S+F

則缺頁中斷率為：f=F/A請求頁式存儲管理系統(tǒng)的性能實現(xiàn)虛擬存儲器時應(yīng)盡可能降低缺頁中斷率。影響缺頁中斷率f的因素有：

(1)分配給作業(yè)的主存塊數(shù)----塊數(shù)n↑f↓(2)頁面大小----頁面大小↑f↓(3)程序的編制方法----局部化程度↑f↓(4)頁面替換算法駐留集●正確選擇駐留集窗口大?。?●窗口大小Δ選擇得過小，頻繁產(chǎn)生缺頁中斷。 ●窗口大小Δ選擇得很大，失去了虛擬存儲器的意義。●駐留集：即在某段時間間隔內(nèi)，進(jìn)程實際要訪問的頁面的集合。請求頁式存儲管理駐留集管理駐留集管理包括以下內(nèi)容：●保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)是多少？●為每個進(jìn)程分配物理塊時，其數(shù)目是固定的、還是可變的？●如何為進(jìn)程置換物理塊，是局部置換？還是全局置換？缺頁率與物理塊數(shù)（窗口大小）的關(guān)系●當(dāng)進(jìn)程獲得的物理塊數(shù)達(dá)到臨界值，繼續(xù)增加塊數(shù)，缺頁率不能顯著降低●進(jìn)程獲得的塊數(shù)達(dá)到臨界值，缺頁率穩(wěn)定在上下限之間臨界值(窗口大小)塊數(shù)過少，頻繁缺頁，降低了系統(tǒng)吞吐率塊數(shù)太多，必然有些頁面屬于浪費(fèi)。內(nèi)存不能充分利用，失去了虛擬存儲器的意義拐點●物理塊越多越好！——虛擬？●隨著為進(jìn)程分配的物理塊數(shù)目的減少，將使進(jìn)程執(zhí)行中的缺頁率提高，從而降低進(jìn)程的執(zhí)行速度。●能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)是多少？●這與計算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。最少物理塊數(shù)進(jìn)程正常運(yùn)行需要多少物理塊?能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)是多少？這與計算機(jī)硬件結(jié)構(gòu)有關(guān)，取決于指令格式、功能和尋址方式。例如：①對于某些簡單機(jī)器，若是單地址指令且采用直接尋址方式，最小物理塊數(shù)應(yīng)為2。即，指令所在頁和數(shù)據(jù)頁。 incbyteptr[30H]

②若該機(jī)器允許間接尋址，則至少要3個物理塊 MOVA,[B]③現(xiàn)代計算機(jī)，指令長度可能是兩個或兩個以上字節(jié)，至少要為進(jìn)程分配6個物理塊。因為指令本身可能跨越2個頁，源地址和目標(biāo)地址所涉及的區(qū)域也都可能跨兩個頁面

最小物理塊數(shù) …… jelabel ……label: incax ……if(序列號!=x){…}else{…}0000:…… ……2A00: 745A2A02: ………… ……2A5A: 1C…… ……5A…………74駐留集管理

●固定分配、局部置換●為每個進(jìn)程分配固定頁數(shù)的內(nèi)存空間、且運(yùn)行過程中不變?！癞?dāng)進(jìn)程缺頁時，只能從該進(jìn)程在內(nèi)存的幾個頁面中選出一頁換出，然后再調(diào)入一頁，保證進(jìn)程的頁數(shù)不變。●可變分配、全局置換●系統(tǒng)開始先為每個進(jìn)程分配一定數(shù)目的物理塊。整個系統(tǒng)有一空閑物理塊鏈，當(dāng)某進(jìn)程缺頁時，系統(tǒng)從空閑鏈中選出一塊分配給進(jìn)程?！窨臻e鏈為空時，OS從所有進(jìn)程的頁面中權(quán)衡選擇一頁換出。●可變分配、局部置換●分配同上，但進(jìn)程缺頁時，只能從該進(jìn)程在內(nèi)存的頁面中選出一頁換出。請求頁式存儲管理的調(diào)入策略

●何時調(diào)入頁面●預(yù)調(diào)：預(yù)計進(jìn)程要訪問的頁，提前調(diào)入內(nèi)存。一次調(diào)入多頁比調(diào)入一頁更高效但預(yù)調(diào)頁的成功率僅約50％。●請調(diào)：進(jìn)程發(fā)生缺頁中斷時將所缺頁面調(diào)入內(nèi)存。實現(xiàn)簡單每次僅調(diào)入一頁，故須花費(fèi)較大的系統(tǒng)開銷，增加了磁盤I／O的啟動頻率●從何處調(diào)入 請求頁式存儲管理系統(tǒng)中，把外存分為兩部分：文件區(qū)和對換區(qū)有以下三種實現(xiàn)方式：●進(jìn)程的所有頁面都放在對換區(qū)。●只將修改過的頁面放在對換區(qū)，未改的放在文件區(qū)?！馯NIX系統(tǒng)方式，首次從文件區(qū)調(diào)入，換出時放在對換區(qū)，以后從對換區(qū)調(diào)入?！窠Y(jié)論：

①在多道程序環(huán)境下，并非“多道程序度越高，系統(tǒng)吞吐量越大?！?/p>

②當(dāng)CPU利用率達(dá)到某峰值后，若繼續(xù)增加道數(shù)，將產(chǎn)生抖動，使CPU利用率降低。●抖動預(yù)防方法①加載控制(只有駐留集足夠大的進(jìn)程才能執(zhí)行。這限制了進(jìn)程數(shù)目)②

L=S準(zhǔn)則（調(diào)整道數(shù)，使產(chǎn)生缺頁的平均時間L等于系統(tǒng)處理缺頁的平均時間

S）③采用局部置換(某進(jìn)程抖動，不影響其它進(jìn)程)④當(dāng)?shù)罃?shù)偏高，盡快掛起若干進(jìn)程圖6-6CPU利用率與多道程序道數(shù)的關(guān)系2抖動和加載控制抖動(顛簸)的含義：剛剛被調(diào)出的頁面又立即要用，因而又要把它裝入，而裝入不久又被選中調(diào)出，調(diào)出不久又要裝入使用，如此反復(fù)，使調(diào)度非常頻繁。抖動的原因：置換算法不好；缺頁嚴(yán)重缺頁的原因：內(nèi)存不足；道數(shù)多道數(shù)多

塊數(shù)少

缺頁嚴(yán)重

抖動

進(jìn)程的時間浪費(fèi)在換進(jìn)換出，CPU利用率低【練習(xí)】在一個頁式虛擬存儲管理的系統(tǒng)中，有一用戶作業(yè)，它依次要訪問的字地址序列是：115,228,120,88,446,102,321,432,260,167，若該作業(yè)的第0頁已經(jīng)裝入主存，現(xiàn)分配給該作業(yè)的主存共300字，頁的大小為100字，請回答下列問題：（1）按FIFO算法將產(chǎn)生_________次缺頁中斷，依次淘汰的頁號為___________________.缺頁中斷率為__________.

0000044444411111133332222222210、1、2它依次要訪問的字地址序列是：115,228,120,88,446,102,321,432,260,167（2）按LRU調(diào)度算法將產(chǎn)生___________次缺頁中斷，依次淘汰的頁號為___________________.缺頁中斷率為_________.0121041342101210413420021041342、0、1、3●1請段式系統(tǒng)中段表的擴(kuò)充

6.3請求段式存儲管理除段號、段長和段始址這些段式系統(tǒng)已有的基本表項之外，增加了以下表項：●存取方式：用于標(biāo)識本段的存取屬性是只執(zhí)行、只讀，還是允許讀/寫●狀態(tài)位：指示該段是否已進(jìn)駐內(nèi)存●訪問字段：用于記錄本段有多長時間沒有被訪問。置換算法在選擇換出段時參考●修改位：表示該段調(diào)入內(nèi)存后是否被修改過●增補(bǔ)位：這是請求段式存儲管理系統(tǒng)中特有的字段，用于表示本段在運(yùn)行過程中是否進(jìn)行過動態(tài)增長●外存地址：用于指出該段在外存的地址，供調(diào)入該段時使用2請段式系統(tǒng)中的缺段中斷

3請段式系統(tǒng)中的地址變換機(jī)構(gòu)

4請段式系統(tǒng)中的內(nèi)存管理

調(diào)入調(diào)出內(nèi)存的單位是段。如果所需的段尚未調(diào)入內(nèi)存，則產(chǎn)生缺段中斷信號。缺段中斷處理程序得到控制權(quán)侯，負(fù)責(zé)將所缺段調(diào)入內(nèi)存。在段式系統(tǒng)的基礎(chǔ)上形成。在進(jìn)行地址變換時，如果發(fā)現(xiàn)所要訪問的段不在內(nèi)存，必須將所缺的段調(diào)入內(nèi)存，并修改段表中的狀態(tài)位。段的調(diào)入策略和置換算法與請求頁式系統(tǒng)類似。物理內(nèi)存的分配可以采取與可變分區(qū)管理相似的方案。不同的是分配的單位不是一個程序或進(jìn)程，而是一個程序段或數(shù)據(jù)段。動態(tài)鏈接L