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

●請求頁式存儲管理

●請求段式存儲管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

●固定分配、局部置換●為每個進程分配固定頁數的內存空間、且運行過程中不變。●當進程缺頁時，只能從該進程在內存的幾個頁面中選出一頁換出，然后再調入一頁，保證進程的頁數不變?！窨勺兎峙洹⑷种脫Q●系統開始先為每個進程分配一定數目的物理塊。整個系統有一空閑物理塊鏈，當某進程缺頁時，系統從空閑鏈中選出一塊分配給進程?！窨臻e鏈為空時，OS從所有進程的頁面中權衡選擇一頁換出?！窨勺兎峙洹⒕植恐脫Q●分配同上，但進程缺頁時，只能從該進程在內存的頁面中選出一頁換出。請求頁式存儲管理的調入策略

●何時調入頁面●預調：預計進程要訪問的頁，提前調入內存。一次調入多頁比調入一頁更高效但預調頁的成功率僅約50％。●請調：進程發生缺頁中斷時將所缺頁面調入內存。實現簡單每次僅調入一頁，故須花費較大的系統開銷，增加了磁盤I／O的啟動頻率●從何處調入 請求頁式存儲管理系統中，把外存分為兩部分：文件區和對換區有以下三種實現方式：●進程的所有頁面都放在對換區?！裰粚⑿薷倪^的頁面放在對換區，未改的放在文件區?！馯NIX系統方式，首次從文件區調入，換出時放在對換區，以后從對換區調入?！窠Y論：

①在多道程序環境下，并非“多道程序度越高，系統吞吐量越大。”

②當CPU利用率達到某峰值后，若繼續增加道數，將產生抖動，使CPU利用率降低。●抖動預防方法①加載控制(只有駐留集足夠大的進程才能執行。這限制了進程數目)②

L=S準則（調整道數，使產生缺頁的平均時間L等于系統處理缺頁的平均時間

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

塊數少

缺頁嚴重

抖動

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

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

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

3請段式系統中的地址變換機構

4請段式系統中的內存管理

調入調出內存的單位是段。如果所需的段尚未調入內存，則產生缺段中斷信號。缺段中斷處理程序得到控制權侯，負責將所缺段調入內存。在段式系統的基礎上形成。在進行地址變換時，如果發現所要訪問的段不在內存，必須將所缺的段調入內存，并修改段表中的狀態位。段的調入策略和置換算法與請求頁式系統類似。物理內存的分配可以采取與可變分區管理相似的方案。不同的是分配的單位不是一個程序或進程，而是一個程序段或數據段。動態鏈接L