第四章 存儲(chǔ)器管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、適應(yīng)算法（分類(lèi)搜索法）,空閑區(qū)按容量大小分類(lèi)鏈接，每一類(lèi)中空閑區(qū)大小相當(dāng)。系統(tǒng)中有多個(gè)鏈。進(jìn)行分配時(shí)，找能容納進(jìn)程的最小空閑區(qū)鏈的鏈?zhǔn)卓臻e區(qū)進(jìn)行分配。沒(méi)有則不能分配。不需對(duì)分區(qū)進(jìn)行劃分。查找速度快不足：回收空閑區(qū)算法復(fù)雜，開(kāi)銷(xiāo)大,3. 分區(qū)的分配與回收,1） 分配內(nèi)存2） 回收內(nèi)存,1） 分配內(nèi)存,修改分區(qū)鏈/表劃分找一個(gè)足夠大的分區(qū),2） 回收內(nèi)存,檢查回收區(qū)(R)與空閑區(qū)(F)是否相鄰接（四種情形）,如鄰接，

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

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

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

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

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

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

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

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

29、段交替使用同一內(nèi)存區(qū)，這樣的內(nèi)存區(qū)稱(chēng)為覆蓋區(qū)/覆蓋段，這些程序段稱(chēng)為覆蓋。覆蓋區(qū)的大小由最大覆蓋決定一個(gè)進(jìn)程的地址空間大小是幾個(gè)覆蓋區(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)存空間的使用,對(duì)換（交換）技術(shù),1. 對(duì)換的引入2. 對(duì)換空間的管理進(jìn)程的換出進(jìn)程的換

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

51、空間,作業(yè)的地址空間劃分為若干個(gè)段，每個(gè)段為一組邏輯相關(guān)的信息（主程序段MAIN、子程序段X、數(shù)據(jù)段D、棧段S等），每個(gè)段有自己的名字。（段號(hào)/段名）每個(gè)段從0開(kāi)始編址，為一段連續(xù)的地址空間整個(gè)作業(yè)的地址空間：二維的訪問(wèn)地址的方式： [ 段名] | ,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)的實(shí)現(xiàn)原理,段式地址結(jié)構(gòu)段內(nèi)地址所占位數(shù)決定了段的最大長(zhǎng)度。段號(hào)所占位數(shù)決定了一個(gè)作業(yè)（進(jìn)程）的最大段數(shù)。,數(shù)據(jù)結(jié)構(gòu)段表（段映射表） 記錄段在內(nèi)存的起始地址和段長(zhǎng)等。,利用段表實(shí)現(xiàn)地址

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

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

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

56、tor程序（160k）,40k工作區(qū)，頁(yè)長(zhǎng)4k不共享: (160k+40k)*40=8000k共享: 160k+40k*40=1760k,頁(yè)式信息共享,,ed 1,,ed 2,,…,,ed 40,,data 1,,…,,data 10,進(jìn)程,1,,21,,22,,…,,60,,61,,…,,70,頁(yè)表,,ed 1,,ed 2,,…,,ed 40,,data 1,,…,,data 10,進(jìn)程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,,,,,,,,,,,,,,,,,,,,,頁(yè)表,分頁(yè)系統(tǒng)中共享editor的示意圖,段式信息共享,在需要共享的進(jìn)程段表中增加一項(xiàng)，使其指向已經(jīng)在內(nèi)存的共享段易于實(shí)現(xiàn)例：共享Editor,圖 4-19 分段系統(tǒng)中共享edit

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

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

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

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

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

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

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

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

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

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

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