第四章 存儲器管理

1、第四章 存儲器管理,4.1 存儲器的層次結(jié)構(gòu)4.2 程序的裝入和鏈接 4.3 連續(xù)分配方式 4.4 基本分頁存儲管理方式 4.5 基本分段存儲管理方式 4.6 虛擬存儲器的基本概念 4.7 請求分頁存儲管理方式 4.8 頁面置換算法 4.9 請求分段存儲管理方式,存儲管理的目的和功能,主要任務為多道程序的運行提供良好的環(huán)境，方便用戶使用存儲器，提高存儲器的利用率，以及從邏輯上擴充內(nèi)存。功能主

2、存的分配和管理提高主存利用率存儲保護地址映射內(nèi)存擴充,4.1 存儲器的層次結(jié)構(gòu),4.1.1 多級存儲器結(jié)構(gòu)4.1.2 主存儲器與寄存器4.1.3 高速緩存和磁盤緩存,4.1.1 多級存儲器結(jié)構(gòu),存儲器系統(tǒng)：支持OS運行硬件環(huán)境的一個重要方面，作業(yè)必須把它的程序和數(shù)據(jù)存放在內(nèi)存中才能運行多道程序系統(tǒng)中，若干個程序和相關的數(shù)據(jù)要放入內(nèi)存，操作系統(tǒng)要管理、保護程序和數(shù)據(jù)，使它們不至于受到破壞操作系統(tǒng)本身也要存放在內(nèi)存

3、中并運行,4.1.1 多級存儲器結(jié)構(gòu),存儲系統(tǒng)設計三個問題： 容量、速度和成本容量：需求永無止境速度：能匹配處理器的速度成本問題：成本和其他部件相比應在合適范圍之內(nèi),4.1.1 多級存儲器結(jié)構(gòu),容量、速度和成本三個目標不可能同時達到最優(yōu)，要作權(quán)衡存取速度快，每bit價格高容量大，每bit價格越低，同時存取速度也越慢解決方案：采用層次化的存儲體系結(jié)構(gòu)當沿著層次下降時每bit的價格將下降，容量將增大，速度將變

4、慢，處理器的訪問頻率也將下降,4.1.1 多級存儲器結(jié)構(gòu),,,CPU寄存器,,主存,,輔存,速度越來越快造價越來越高容量越來越小,,4.1.1 多級存儲器結(jié)構(gòu),CPU寄存器：CPU的組成部分主存： CPU運行時訪問，存取指令、數(shù)據(jù) 要求訪問速度快輔存：I/O設備，訪問涉及中斷、設備驅(qū)動 物理設備運行等，訪問速度慢不同層次的存儲介質(zhì)，由OS統(tǒng)一管理。存儲管理負責主存的管理設

5、備管理負責輔存的管理,4.1.2 主存儲器與寄存器,主存儲器可執(zhí)行存儲器、內(nèi)存、主存保存進程運行時的程序和數(shù)據(jù)，CPU運行時只能從主存取指令和數(shù)據(jù)速度遠低于CPU執(zhí)行指令速度，引入寄存器、高速緩存寄存器CPU組成部分，訪問速度最快，造價昂貴，容量小,4.1.3 高速緩存和磁盤緩存,高速緩存（CACHE）介于寄存器和主存之間，可分為兩級、多級暫存主存中頻繁訪問的信息，減少訪問主存的次數(shù)（如頁表、段表）磁盤緩存暫存需要

6、頻繁訪問的磁盤數(shù)據(jù)，減少磁盤訪問次數(shù),4.2 程序的裝入和鏈接,4.2.1 程序的處理步驟4.2.2 程序的裝入4.2.3 程序的鏈接4.2.4 重定位,4.2.1 程序的處理步驟,程序,圖 4-1 對用戶程序的處理步驟,4.2.2 程序的裝入,1. 絕對裝入方式(Absolute Loading Mode)2. 可重定位裝入方式(Relocatable Loading Mode)3. 動態(tài)運行

7、時裝入方式(Dynamic Run-time Loading),1. 絕對裝入方式(Absolute Loading Mode),直接指定方式程序中所使用的絕對地址，既可在編譯或匯編時給出， 也可由程序員直接賦予。 由程序員直接給出絕對地址時，不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉(zhuǎn)換為絕對地址。,2.

8、 可重定位裝入方式(Relocatable Loading Mode),作業(yè)地址空間,內(nèi)存空間,作業(yè)裝入內(nèi)存的情況,2. 可重定位裝入方式,每個程序從0號地址開始編程，使用邏輯地址程序裝入內(nèi)存后，所有指令中的邏輯地址已經(jīng)調(diào)整為實際內(nèi)存的物理地址（圖中2500→12500）不允許程序在內(nèi)存中移動位置,3. 動態(tài)運行時裝入方式(Dynamic Run-time Loading),動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后

9、，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行。因此， 裝入內(nèi)存后的所有地址都仍是相對地址。 運行時可以申請附加空間，裝入需要的程序和數(shù)據(jù)。 裝入內(nèi)存的程序可以移動位置。,4.2.3 程序的鏈接,1. 靜態(tài)鏈接方式(Static Linking)2. 裝入時動態(tài)鏈接(Load time Dynamic Linking) 3. 運行時動態(tài)鏈接(Run-time Dyn

10、amic Linking),1. 靜態(tài)鏈接方式(Static Linking),圖 4-3 程序鏈接示意圖,程序運行之前事先進行鏈接，以后不再拆開?？蓤?zhí)行文件,2. 裝入時動態(tài)鏈接(Loadingtime Dynamic Linking),目標模塊在裝入內(nèi)存時，邊裝入邊鏈接。便于軟件版本的修改和更新便于實現(xiàn)目標模塊共享,3. 運行時動態(tài)鏈接(Run-time Dynamic Linking),目標模塊的鏈接可以推遲到執(zhí)行時才

11、進行。程序執(zhí)行過程中，發(fā)現(xiàn)被調(diào)用模塊尚未裝入內(nèi)存，由OS找到該模塊，將它裝入內(nèi)存，并進行鏈接。凡在執(zhí)行過程中未被用到的目標模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。,4.2.4 重定位,地址空間（每個作業(yè)/目標程序一個，從0開始編址）邏輯地址/相對地址/虛地址/有效地址：地址空間中單元編號；存儲空間（整個計算機系統(tǒng)一個，從0開始編址）物理地址/絕對地址/實地址：存儲

12、空間中單元編號。,4.2.4 重定位（續(xù)）,重定位由于作業(yè)裝入到與其地址空間不一致的存儲空間所引起的對有關地址部分的調(diào)整過程稱為重定位（地址映射/地址調(diào)整/地址變換/地址轉(zhuǎn)換）。重定位的類型靜態(tài)重定位：作業(yè)裝入過程中由裝配程序一次性進行動態(tài)重定位：作業(yè)執(zhí)行過程中訪問指令或數(shù)據(jù)時，由附加的硬件地址變換機構(gòu)進行的地址變換。,4.3 連續(xù)分配方式（分區(qū)存儲管理）,4.3.1 單一連續(xù)分配4.3.2 固定分區(qū)分配 4.

13、3.3 動態(tài)分區(qū)分配4.3.4 伙伴系統(tǒng)*4.3.5 哈希算法*4.3.6 可重定位分區(qū)分配4.3.7 分區(qū)的存儲保護4.3.8 覆蓋與對換(Swapping),4.3.1 單一連續(xù)分配 單用戶單任務系統(tǒng)的存儲管理,最簡單的一種存儲管理方式，但只能用于單用戶、單任務的操作系統(tǒng)中。采用這種存儲管理方式時，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低

14、址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間， 提供給用戶使用。 存儲分配：系統(tǒng)區(qū)，用戶區(qū)存儲保護：對OS加以保護即可。（界限寄存器 / 目態(tài)、管態(tài)）地址映射：靜態(tài)重定位,4.3.2 固定分區(qū)分配 最早使用的多道程序存儲管理方式,內(nèi)存空間固定劃分為若干個固定大小的分區(qū)，每個分區(qū)可裝入一道作業(yè)。分區(qū)的劃分分區(qū)大小相等， 即:使所有的內(nèi)存分區(qū)大小相等分區(qū)大小不等內(nèi)存分配(分區(qū)說明表)找大小合適的分區(qū)

15、找到，分配，修改分區(qū)表未找到，拒絕分配缺點：道數(shù)固定，主存利用率低（零頭/碎片）,固定分區(qū)(大小相同),固定分區(qū)(多種大小),分區(qū)說明表和內(nèi)存分配,0,4.3.3 動態(tài)分區(qū)分配（可變式分區(qū)）,存儲空間的劃分是在作業(yè)裝入時進行的，使分區(qū)大小適應作業(yè)的需要，分區(qū)個數(shù)不固定。數(shù)據(jù)結(jié)構(gòu)分區(qū)分配算法分區(qū)的分配與回收地址變換,,空閑分區(qū)表 (2) 空閑分區(qū)鏈 空白區(qū)鏈 在內(nèi)存實現(xiàn),空閑分區(qū)鏈結(jié)構(gòu)圖,1.

16、分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu),,2. 分區(qū)分配算法,分區(qū)分配算法：尋找某個空閑分區(qū)，其大小需大于或等于程序的要求。若是大于要求，則將該分區(qū)分割成兩個分區(qū)，其中一個分區(qū)為要求的大小并標記為“占用”，而另一個分區(qū)為余下部分并標記為“空閑”。分區(qū)劃分的先后次序通常是從內(nèi)存低端到高端。分區(qū)釋放算法：需要將相鄰的空閑分區(qū)合并成一個空閑分區(qū)。(這時要解決的問題是：合并條件的判斷和合并時機的選擇),2. 分區(qū)分配算法,首次適應算法FF(First F

17、it) 最先匹配法循環(huán)首次適應算法(Next Fit) 下次匹配法 該算法是由首次適應算法演變而成的。最佳適應算法(Best Fit) 最壞適應算法(Worst Fit)快速適應算法(Quick Fit),（1） 首次適應算法FF,空閑區(qū)鏈按首地址遞增的次序鏈接。進行分配時，從鏈首開始查找，找到第一個能滿足作業(yè)地址空間大小要求的空閑區(qū)即進行分配。對分區(qū)進行劃分實質(zhì)：優(yōu)先使用內(nèi)存中低地址部分的空閑區(qū)不足：運

18、行一段時間后，空閑區(qū)鏈前端碎片多，查找費時,（2） 循環(huán)首次適應算法,空閑區(qū)鏈按首地址遞增的次序鏈接。進行分配時，從上一次找到空閑區(qū)的下一個分區(qū)開始查找，直至找到第一個能滿足作業(yè)地址空間大小要求的空閑區(qū)即進行分配。設置起始查尋指針，并循環(huán)查找。對分區(qū)進行劃分實質(zhì)：使內(nèi)存中的空閑區(qū)分布比較均勻不足：運行一段時間后，缺乏大的空閑區(qū)。,（3） 最佳適應算法,空閑區(qū)鏈按大小遞增的次序鏈接。進行分配時，從鏈首開始查找，找到第一個能滿足

19、作業(yè)地址空間大小要求的空閑區(qū)即進行分配。第一個能滿足作業(yè)地址空間大小要求的空閑區(qū)是最適合的。對分區(qū)進行劃分(常數(shù)G)實質(zhì)：避免“大材小用”性能不一定最佳,（4） 最壞適應算法,空閑區(qū)鏈按大小遞減的次序鏈接。進行分配時，直接比較鏈首空閑區(qū)，如大小合適即進行分配。否則不能分配。第一個空閑區(qū)可能是與進程需求最不匹配的。對分區(qū)進行劃分(常數(shù)G)性能不一定最壞不足：會使鏈中缺少大的空閑區(qū)以上四種算法稱為順序搜索法,（5） 快速

20、適應算法（分類搜索法）,空閑區(qū)按容量大小分類鏈接，每一類中空閑區(qū)大小相當。系統(tǒng)中有多個鏈。進行分配時，找能容納進程的最小空閑區(qū)鏈的鏈首空閑區(qū)進行分配。沒有則不能分配。不需對分區(qū)進行劃分。查找速度快不足：回收空閑區(qū)算法復雜，開銷大,3. 分區(qū)的分配與回收,1） 分配內(nèi)存2） 回收內(nèi)存,1） 分配內(nèi)存,修改分區(qū)鏈/表劃分找一個足夠大的分區(qū),2） 回收內(nèi)存,檢查回收區(qū)(R)與空閑區(qū)(F)是否相鄰接（四種情形）,如鄰接，

21、則合并。修改數(shù)據(jù)結(jié)構(gòu),與F1合并修改F1大小,與F2合并，修改F2始址與大小,與F1、F2合并成一個分區(qū)，使用F1在鏈中位置 ， F2刪除,單獨分區(qū)插入空閑區(qū)鏈,例：按首次適應算法分配和回收內(nèi)存,T0時刻：系統(tǒng)中有進程J1,J2,J3內(nèi)存分配情況如圖a空閑區(qū)鏈如圖bT1時刻： J4(50K)到達T2時刻： J5(16K)到達T3時刻： J2、J3完成畫出每個時刻內(nèi)存分配情況圖和空閑區(qū)鏈的變化情況,圖a,圖b,

22、例：按首次適應算法分配和回收內(nèi)存,T1時刻： J4(50K)到達內(nèi)存分配情況如圖c空閑區(qū)鏈如圖d,圖c,圖d,例：按首次適應算法分配和回收內(nèi)存,T2時刻： J5(16K)到達內(nèi)存分配情況如圖e空閑區(qū)鏈如圖f,圖e,圖f,例：按首次適應算法分配和回收內(nèi)存,T3時刻： J2、J3完成內(nèi)存分配情況如圖g空閑區(qū)鏈如圖h,圖g,圖h,思考與練習,如果T3之后，一10K作業(yè)到達，怎么處理？按最佳適應算法，如何處理本例？,108K,23

23、2K,256K,OS,J1(8K),J2(16K),64K,J3(124K),24K,0,20K,28K,44K,0,例：分區(qū)分配與回收(首次適應算法),T0時刻：J1,J2,J3,T1時刻：J4(50K),T2時刻：J5(16K),T3時刻：J2,J3完成,,,,Head,44K64k,,,232K24k,,,,,T0時刻,T1時刻,T2時刻,T3時刻,T3之后，一10K作業(yè)到達，怎么處理？按最佳適應算法，如何處理本例？,4

24、. 分區(qū)的地址變換,靜態(tài)重定位，裝入時一次進行分區(qū)的起始地址+邏輯地址=物理地址,4.3.4 伙伴系統(tǒng)* 4.3.5 哈希算法*,固定分區(qū)，利用率低動態(tài)分區(qū)，算法復雜，開銷較大伙伴系統(tǒng)是一種折中方案哈希算法查找空閑分區(qū)鏈表,4.3.4 伙伴系統(tǒng)*,類似于快速適應算法分區(qū)大小：2K （1≦K≦m）K個空閑分區(qū)鏈表分配：先找2l（ 2l-1<n ≦ 2l ）大的分區(qū)進行分配，找不到，則找2l+1大的分區(qū)

25、，進行劃分，一個分配，另一個放到2l分區(qū)鏈（一對伙伴）；……可能多次劃分回收時進行合并；可能多次合并多處理機系統(tǒng)采用,4.3.5 哈希算法*,分類搜索、伙伴系統(tǒng)算法，空閑區(qū)按大小分類鏈接，多個鏈，如果分類細，鏈表多，搜索索引表找合適的鏈表開銷大，可能導致性能下降哈希算法利用哈希函數(shù)，在分類索引表中查找空閑分區(qū)鏈,4.3.6 可重定位分區(qū)分配 動態(tài)重定位分區(qū)分配,1. 動態(tài)重定位的引入2.

26、動態(tài)重定位的實現(xiàn)3. 動態(tài)重定位分區(qū)分配算法,1. 動態(tài)重定位的引入,可變式分區(qū)的“零頭/碎片”問題 小的、分散的空閑區(qū)，總?cè)萘坎恍?，但不能容納用戶作業(yè)，得不到充分利用用戶作業(yè)適應內(nèi)存大小拼接、緊湊技術(shù) 將內(nèi)存中作業(yè)進行移動，使所有的空白區(qū)合并成一個大的空白區(qū)。通過移動，將多個分散的小空白區(qū)拼接成大空白區(qū)的方法稱為“拼接”或“緊湊”。地址如何轉(zhuǎn)換？采用動態(tài)重定位技術(shù),拼

27、接、緊湊示意圖,拼接時機回收分區(qū)時找不到足夠大的分區(qū)來滿足用戶要求時,2. 動態(tài)重定位的實現(xiàn),訪問指令或數(shù)據(jù)時由附加的地址變換機構(gòu)進行地址變換機構(gòu)：重定位寄存器RR拼接時，不做地址變換，只記錄位置多道程序運行時，只需一個RR，存放當前運行作業(yè)的內(nèi)存起始地址,2. 動態(tài)重定位的實現(xiàn),圖 4-9 動態(tài)重定位示意圖,MOV AX,[2500],3. 動態(tài)重定位分區(qū)分配算法,與動態(tài)分區(qū)分配算法基本相同差別：找不到合適的

28、空閑區(qū)時進行拼接,動態(tài)重定位分區(qū)分配算法流程圖,,4.3.7 分區(qū)的存儲保護,界限寄存器(只需要一對)上、下界寄存器 下界≤物理地址≤上界基址、限長寄存器 邏輯地址≤限長寄存器 分區(qū)存儲管理又稱為界地址存儲管理存儲保護鍵每個分區(qū)配一個單獨的保護鍵（鎖）PSW中有保護鍵字段（鑰匙）,,匹配,4.3.8 覆蓋與對換(Swapping),覆蓋技術(shù)對換技術(shù),覆蓋技術(shù),覆蓋區(qū)與覆蓋覆蓋技術(shù)讓同一程序的不同程序

29、段交替使用同一內(nèi)存區(qū)，這樣的內(nèi)存區(qū)稱為覆蓋區(qū)/覆蓋段，這些程序段稱為覆蓋。覆蓋區(qū)的大小由最大覆蓋決定一個進程的地址空間大小是幾個覆蓋區(qū)容量之和。,覆蓋的劃分,A(4K),B(5K),C(8K),D(5K),E(4K),F(6K),,4K,8K,6k,,,,,,作業(yè)的常駐部分,覆蓋區(qū)0（8K）,覆蓋區(qū)1（6K）,程序的模塊結(jié)構(gòu),內(nèi)存空間的使用,對換（交換）技術(shù),1. 對換的引入2. 對換空間的管理進程的換出進程的換

30、入,定義 所謂“對換”，是指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。 目的： 提高內(nèi)存利用率，利用外存來解決主存容量不夠大的問題。 對換的功能 對換空間的管理 進程的換出 進程的換入 Unix 對換進程 / Windows,1. 對換的引入（MIT C

31、TSS）,外存：文件區(qū)、對換區(qū) 文件區(qū)：存放文件對換區(qū)：存放換出的進程（速度，連續(xù)分配）數(shù)據(jù)結(jié)構(gòu)為了能對對換區(qū)中的空閑盤塊進行管理，在系統(tǒng)中應配置相應的數(shù)據(jù)結(jié)構(gòu)，以記錄外存的使用情況。其形式與內(nèi)存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個表目中應包含兩項， 即對換區(qū)的首址及其大小，它們的單位是盤塊號和盤塊數(shù)。 對換空間的分配與回收：與動態(tài)分區(qū)內(nèi)存分配與回收方法類似。

32、分配：算法回收：鄰接情形與合并,2. 對換空間的管理,每當一進程由于創(chuàng)建子進程而需要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等情況發(fā)生時，系統(tǒng)應將某進程換出。 系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，然后啟動盤塊I/O，將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送過程未出現(xiàn)錯誤，便可回收該進程所占用的內(nèi)存空間，并對該進程的進程控制塊做相應的修改。,3. 進程的換出,系統(tǒng)定時地查看所有進程的狀態(tài)，從中找出“就

33、緒”狀態(tài)但已換出的進程，將其中換出時間(換出到磁盤上)最久的進程作為換入進程，將其換入。,,4. 進程的換入,4.4 基本分頁存儲管理方式（單純分頁）,4.4.1 引入4.4.2 分頁存儲管理的基本方法4.4.3 頁式地址變換機構(gòu)4.4.4 兩級和多級頁表4.4.5 反置頁表,4.4.1 引入,分區(qū)分配的不足連續(xù)分配碎片問題，拼接代價尋求解決碎片問題的新途徑：讓程序的地址空間適應存儲

34、器的現(xiàn)狀？多重分區(qū)→分頁離散分配方式頁式段式段頁式,4.4.2 分頁存儲管理的基本方法,1. 分頁存儲管理的基本原理2. 地址結(jié)構(gòu)3. 分頁存儲管理的數(shù)據(jù)結(jié)構(gòu)頁面大小的選擇,1. 分頁存儲管理的基本原理,分頁存儲管理，是將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號，從0開始，如第0頁、第1頁等。相應地，也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或

35、頁框(frame)， 也同樣為它們加以編號，如0＃塊、1＃塊等等。在為進程分配內(nèi)存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。頁內(nèi)碎片（可以忽略不計）由于進程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內(nèi)碎片”。,分頁存儲管理的優(yōu)缺點（單純）,優(yōu)點：沒有外零頭（碎片），每個內(nèi)零頭不超過頁大小。一個程序不必連續(xù)存放。便于改變程序占用空間的大小。即隨著程序運行而動態(tài)生成的數(shù)據(jù)增多，地址空間

36、可相應增長。缺點：程序仍然需要全部裝入內(nèi)存。,2. 頁式地址結(jié)構(gòu)（邏輯地址）,分頁地址中的地址結(jié)構(gòu)如下：,31,12,11,0,對某特定機器，其地址結(jié)構(gòu)的長度是一定的。若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內(nèi)地址W可按下式求得：,,,3. 分頁存儲管理的數(shù)據(jù)結(jié)構(gòu),進程頁表：每個進程有一個頁表，描述該進程占用的物理頁面（塊號）及邏輯排列順序（頁號）；邏輯頁號（本進程的地址空間）→物理塊號（實際內(nèi)存空間）

37、；物理頁面表(存儲分塊表)：整個系統(tǒng)有一個物理頁面表，描述物理內(nèi)存空間的分配使用狀況。數(shù)據(jù)結(jié)構(gòu)（實現(xiàn)）：位示圖，空閑頁面鏈表；請求表：整個系統(tǒng)有一個請求表，描述系統(tǒng)內(nèi)各個進程頁表的位置和大小，用于地址轉(zhuǎn)換，也可以結(jié)合到各進程的PCB里；,頁表的作用示意圖,進程頁表,4. 頁面大小的選擇,在分頁系統(tǒng)中的頁面其大小應適中。頁面若太小，一方面雖然可使內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間， 有利于提高內(nèi)存利用率，但另一方面也會使每個進

38、程占用較多的頁面，從而導致進程的頁表過長，占用大量內(nèi)存； 此外，還會降低頁面換進換出的效率。然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進換出的速度，但卻又會使頁內(nèi)碎片增大。因此，頁面的大小應選擇得適中，且頁面大小應是2的冪，通常為512 B~8 KB。,4.4.3 頁式地址變換機構(gòu),1. 基本的地址變換機構(gòu)2. 地址變換過程3. 具有快表的地址變換機構(gòu),1. 基本的地址變換機構(gòu),頁表實現(xiàn)頁表駐留內(nèi)存

39、頁表寄存器PTR：頁表在內(nèi)存的始址和長度PCB中存放進程的頁表在內(nèi)存的始址和長度，進程被調(diào)度運行時裝入PTR單CPU系統(tǒng)，只需一個PTR,地址變換過程,分頁系統(tǒng)的地址變換機構(gòu)與過程,b,塊內(nèi)地址,,頁式地址變換,,,地址變換例,邏輯地址結(jié)構(gòu)：15位，頁面大小為1k頁表： 頁號 塊號 0 2 1 3 2

40、 8 ….邏輯地址：2500P=2 (2500 div 1024) W=452 (2500 mod 1024)物理地址：塊號：8，塊內(nèi)位移：452 8*1024+452=8644,,,2 452,8 452,,,,,,地址變換例,邏輯地址結(jié)構(gòu)：15位，頁面大小為1k頁表： 頁號 塊號

41、 0 2 1 3 2 8 ….邏輯地址：02A7HO2A7H 0000001010100111B P=0 W=1010100111B物理地址：塊號：2(00010) 塊內(nèi)位移：1010100111B 0001

42、01010100111B 0AA7H,,,頁式地址變換舉例(頁長4K),3. 具有快表的地址變換機構(gòu),引入頁表駐留內(nèi)存訪問指令或數(shù)據(jù)：至少2次訪問內(nèi)存影響運行速度快表：聯(lián)想寄存器，超高速緩存Cache具有并行查尋能力引入快表的目的減少二次訪問內(nèi)存地址變換時先查Cache，查不到，再查頁表具有快表的地址變換,圖 4-13 具有快表的地址變換機構(gòu),頁表寄存器,,頁表始址,,頁表長度,,＞,,頁號,,頁內(nèi)

43、地址,,＋,,,,,,,,,邏輯地址L,越界中斷,,塊號,,b,,,,頁表,,,,,,,,頁號,,,,,,,頁號,,輸,入,寄,存,器,,,塊號,,b,,,,,b,快表,,d,,,,,,物理地址,,,,,,,,,,,,,,,頁表寄存器,,頁表始址,,頁表長度,,＞,,頁號,(3),,頁,內(nèi)地址,,＋,,,,,,,,,,邏輯地址L,越界中斷,,塊號,,,,b,,頁表,頁號,0,1,2,,,,物理地址,3,輸入寄存器,,,,,,塊號,頁號,

44、,,,,,,,,,快表,具有快表的地址變換機構(gòu)與過程,4.4.4 兩級和多級頁表,地址空間大，頁表長，占內(nèi)存例：邏輯地址32位，頁長4K，則頁表項可達220個，頁表占空間4M字節(jié)(每項4個字節(jié))，要求連續(xù)。對頁表進行分頁兩級頁表多級頁表,P1 p2 d,,,外層頁號 外層頁內(nèi)地址

45、頁內(nèi)地址,31 22 21 12 11 0,兩級頁表,現(xiàn)代的大多數(shù)計算機系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當大的內(nèi)存空間。例如，對于一個具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4 KB即212 B，則在每個進程頁表中的頁表項可達1兆個之多。又因

46、為如果每個頁表項占用一個字節(jié)， 則每個進程僅僅其頁表就要占用1兆的內(nèi)存空間，而且還要求是連續(xù)的。 可以采用這樣兩個方法來解決這一問題：① 采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題：② 只將當前需要的部分頁表項調(diào)入內(nèi)存， 其余的頁表項仍駐留在磁盤上，需要時再調(diào)入。,采用兩級頁表，邏輯地址結(jié)構(gòu)可描述如下：,圖 4-14 兩級頁表結(jié)構(gòu),圖 4-15 具有兩級頁表的地址變換機構(gòu),對于32位的機器，采用兩級頁表結(jié)構(gòu)是合適的；但對于

47、64位的機器，如果頁面大小仍采用4 KB即212 B，那么還剩下52位， 假定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號。此時在外層頁表中可能有4096 G個頁表項， 要占用16384 GB的連續(xù)內(nèi)存空間。 必須采用多級頁表，將外層頁表再進行分頁，也是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關系。 對于64位的計算機，如果要求它能支持2６４(=1844744

48、 TB)規(guī)模的物理存儲空間，則即使是采用三級頁表結(jié)構(gòu)也是難以辦到的；而在當前的實際應用中也無此必要。,,多級頁表,4.4.5 反置頁表 Inverted Page Table,進程的邏輯地址空間大，頁表大，占空間反置頁表是為每一個物理塊設置一個頁表項，按物理塊號排序，其內(nèi)容為頁號及其隸屬進程的標識符（只包含已在內(nèi)存的頁面）。利用進程號和頁號，去檢索反置頁表。,反置頁表示意圖,CPU,pid,p,d,i,d,物理存儲器,pid

49、 p,,,,,,,,,,,,,,物理地址,邏輯地址,,頁表,i,4.5 基本分段存儲管理方式,4.5.1 分段存儲管理方式的引入4.5.2 分段地址空間4.5.3 分段系統(tǒng)的基本原理4.5.4 信息共享,4.5.1 分段存儲管理方式的引入,分區(qū)、分頁方案：地址空間是一維線性的，分頁由OS自動進行，不考慮程序的邏輯結(jié)構(gòu)。程序員希望把邏輯上相關的內(nèi)容放在一起。引入分段存儲管理方式，主要是為了滿足用戶和程序員的下述一

50、系列需要： 1) 方便編程 2) 信息共享 3) 信息保護 4) 動態(tài)增長 5) 動態(tài)鏈接,分段存儲管理方式的引入,分段的概念所謂分段存儲管理，就是管理由若干分段組成的作業(yè)，且按分段來進行存儲分配。(每個段的存儲分配與回收類似于動態(tài)分區(qū)方案)關鍵問題：如何保證分段（二維）地址空間中的作業(yè)，在線性的存儲空間中正確地運行。,4.5.2 分段地址

51、空間,作業(yè)的地址空間劃分為若干個段，每個段為一組邏輯相關的信息（主程序段MAIN、子程序段X、數(shù)據(jù)段D、棧段S等），每個段有自己的名字。（段號/段名）每個段從0開始編址，為一段連續(xù)的地址空間整個作業(yè)的地址空間：二維的訪問地址的方式： [ 段名] | ,Call [X]|Mov AX [A]|Mov AX,[B]|,Y:,D:,C:,段Main 段X

52、段A 段B,分段地址中的地址具有如下結(jié)構(gòu)：,31 16 15 0,4.5.3 分段系統(tǒng)的實現(xiàn)原理,段式地址結(jié)構(gòu)段內(nèi)地址所占位數(shù)決定了段的最大長度。段號所占位數(shù)決定了一個作業(yè)（進程）的最大段數(shù)。,數(shù)據(jù)結(jié)構(gòu)段表（段映射表） 記錄段在內(nèi)存的起始地址和段長等。,利用段表實現(xiàn)地址

53、映射,4.5.3 分段系統(tǒng)的實現(xiàn)原理（續(xù)1）,段式地址變換機構(gòu)與過程段表實現(xiàn)段表駐留內(nèi)存段表(控制)寄存器：段表在內(nèi)存的始址和長度PCB中存放進程的段表在內(nèi)存的始址和長度，進程被調(diào)度運行時裝入段表寄存器單CPU系統(tǒng)，只需一個段表寄存器,分段系統(tǒng)的地址變換過程,相似之處：離散分配，控制寄存器，地址變換過程 (1) 頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率。或者說， 分頁僅僅是由于

54、系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對完整的信息。 分段的目的是為了能更好地滿足用戶的需要。,4. 分頁和分段的主要區(qū)別,(2) 頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機器硬件實現(xiàn)的，對用戶透明，因而在系統(tǒng)中只能有一種大小的頁面；而段的長度卻不固定， 決定于用戶所編寫的程序，通常由編譯程序在對源程序進行編譯時，根據(jù)信息的性質(zhì)來劃分。 (3) 分頁

55、的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個記憶符，即可表示一個地址； 而分段的作業(yè)地址空間則是二維的，程序員在標識一個地址時，既需給出段名， 又需給出段內(nèi)地址。,4. 分頁和分段的主要區(qū)別（續(xù)）,4.5.4 信息共享,可重入代碼（純代碼）允許多個進程同時訪問的代碼，不允許任何進程對其進行修改。共享程序段+局部數(shù)據(jù)區(qū),頁式信息共享,被共享的頁面在所有進程中必須存在且具有相同的頁號不方便例：40用戶共享Edi

56、tor程序（160k）,40k工作區(qū)，頁長4k不共享: (160k+40k)*40=8000k共享: 160k+40k*40=1760k,頁式信息共享,,ed 1,,ed 2,,…,,ed 40,,data 1,,…,,data 10,進程,1,,21,,22,,…,,60,,61,,…,,70,頁表,,ed 1,,ed 2,,…,,ed 40,,data 1,,…,,data 10,進程2,,21,,22,,…

57、,,60,,71,,…,,80,,,…,,ed 1,,ed 2,,…,,ed 40,,data 1,,…,,data 10,,data 1,,…,,data 10,主存,0,21,22,60,61,70,71,80,,,,,,,,,,,,,,,,,,,,,頁表,分頁系統(tǒng)中共享editor的示意圖,段式信息共享,在需要共享的進程段表中增加一項，使其指向已經(jīng)在內(nèi)存的共享段易于實現(xiàn)例：共享Editor,圖 4-19 分段系統(tǒng)中共享edit

58、or的示意圖,段式信息共享,4.5.5 段頁式存儲管理方式,基本思想實現(xiàn)原理段頁式地址結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)地址變換過程,1. 基本思想,分段方式與分頁方式的結(jié)合，各取所長采用分段方法來分配和管理用戶作業(yè)的地址空間，而采用分頁方法來分配和管理物理存儲器。優(yōu)點：既可以保持分段地址空間邏輯相關的優(yōu)點（分段動態(tài)鏈接、分段共享、分段保護），又可以避免主存分區(qū)的拼接，保持分頁系統(tǒng)管理物理存儲空間的優(yōu)點。,2. 實現(xiàn)原理,程序分段，每一

59、分段又被分成大小固定的頁。每一分段有段名（號）頁面裝入存儲空間中與頁面大小相等的物理塊。,,,,0,4K,8K,12K,,,,,,,,,,,,15K,16K,,子程序段B,0,4K,,8K,數(shù)據(jù)段C,,,0,4K,,,,,,,,,,,8K,10K,12K,主程序段A,3. 段頁式地址結(jié)構(gòu),分段由程序員或編譯程序根據(jù)程序的邏輯結(jié)構(gòu)劃分；分頁由OS自動進行，與程序員無關，與程序內(nèi)部的邏輯結(jié)構(gòu)無關。目標地址空間仍是二維的。（S,W

60、’）OS將W’分為（P,W）,,段號(S),,段內(nèi)頁號(P),,頁內(nèi)地址(W),4. 數(shù)據(jù)結(jié)構(gòu),段表：段號，狀態(tài)，頁表大小，頁表始址頁表：頁號，狀態(tài)，存儲塊號段表寄存器：段表大小，段表始址,利用段表和頁表實現(xiàn)地址映射,5. 地址變換過程,段頁式系統(tǒng)中的地址變換機構(gòu),4.6 虛擬存儲器的基本概念,4.6.1 虛擬存儲器的引入4.6.2 虛擬存儲器的實現(xiàn)方法4.6.3 虛擬存儲器的特征,,4.6.1

61、 虛擬存儲器的引入,1. 常規(guī)存儲器管理方式的特征一次性（程序一次裝入內(nèi)存）駐留性（程序運行期間駐留內(nèi)存）2. 局部性原理 1968年， Denning.P指出，程序在執(zhí)行時呈現(xiàn)局部性規(guī)律，即在一個較短的時間內(nèi)，程序執(zhí)行僅限于某個部分，相應地，它所訪問的存儲空間也局限于某個區(qū)域。,局部性原理的論點：程序執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外， 在大多數(shù)情況下仍是順序執(zhí)行的。過程調(diào)用將會使程序的執(zhí)行軌

62、跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5。程序中存在許多循環(huán)結(jié)構(gòu)， 這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行。程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對數(shù)組進行操作，它們往往都局限于很小的范圍內(nèi)。,局限性原理的表現(xiàn)：時間局限性。如果程序中的某條指令一旦執(zhí)行， 則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過， 則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時間局限性的典型原因，是由于在程序中存

63、在著大量的循環(huán)操作。空間局限性。一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。,3. 虛擬存儲器定義,所謂虛擬存儲器，是指具有請求調(diào)入功能和置換功能， 能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。 虛擬存儲器的邏輯容量（實際容量）由內(nèi)存容量和外存容量之和所決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于

64、外存。可見，虛擬存儲技術(shù)是一種性能非常優(yōu)越的存儲器管理技術(shù)，故被廣泛地應用于大、 中、 小型機器和微型機中。   虛擬存儲器的最大容量是由計算機的地址結(jié)構(gòu)決定的 。,4.6.2 虛擬存儲器的實現(xiàn)方法,1. 請求分頁系統(tǒng)硬件支持：一定容量的內(nèi)、外存① 請求分頁的頁表機制，它是在純分頁的頁表機制上增加若干項而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)；② 缺頁中斷機構(gòu)，即每當用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時 便產(chǎn)

65、生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存；③ 地址變換機構(gòu)， 它同樣是在純分頁地址變換機構(gòu)的基礎上發(fā)展形成的。實現(xiàn)請求分頁的軟件。2. 請求分段系統(tǒng)3. 請求段頁式系統(tǒng) 離散分配！,,4.6.3 虛擬存儲器的特征,離散性多次性對換性虛擬性,4.7 請求分頁存儲管理方式,4.7.1 請求分頁中的硬件支持4.7.2 內(nèi)存分配策略和分配算法4.7.3 調(diào)頁策略,4.7.1 請求分頁中的硬

66、件支持,基本：一定容量的內(nèi)存、外存1. 頁表機制2. 缺頁中斷機制3. 地址變換機構(gòu),1. 頁表機制,頁式地址變換的主要數(shù)據(jù)結(jié)構(gòu)記錄更多信息,是否在內(nèi)存,訪問次數(shù)或未被訪問時間,是否被修改過,2. 缺頁中斷,缺頁中斷的概念所訪問頁面不在內(nèi)存（狀態(tài)位為0），則產(chǎn)生缺頁中斷，請求OS將所訪問頁面調(diào)入內(nèi)存。一般中斷的處理過程(執(zhí)行完一條指令才接受)保護CPU現(xiàn)場分析中斷原因中斷處理恢復CPU現(xiàn)場缺頁中斷的特

67、殊性在指令執(zhí)行期間產(chǎn)生與處理一條指令執(zhí)行時可能產(chǎn)生多次缺頁中斷例： COPY A TO B (MOVSB A ,B ),涉及6次缺頁中斷的指令,3. 地址變換機構(gòu)與過程,地址變換機構(gòu)快表頁表外存（缺頁中斷）地址變換過程,請求分頁中的地址變換過程,P170,4.7.2 內(nèi)存分配策略和分配算法,三個問題：為保證進程正常運行所需的最小物理塊數(shù)的確定每個進程的塊數(shù)固定還是可變平均分配還是按大小比例分配最小物理塊

68、數(shù)的確定頁面分配與置換策略物理塊分配算法,1. 最小物理塊數(shù)的確定,指能保證進程正常運行所需的最小物理塊數(shù)。當系統(tǒng)為進程分配的物理塊數(shù)少于此值時，進程將無法運行。進程應獲得的最少物理塊數(shù)與計算機的硬件結(jié)構(gòu)有關，取決于指令的格式、功能和尋址方式。對于某些簡單的機器，若是單地址指令且采用直接尋址方式，則所需的最少物理塊數(shù)為2。其中，一塊是用于存放指令的頁面，另一塊則是用于存放數(shù)據(jù)的頁面。如果該機器允許間接尋址時，則至少要求有三個物