第4章存儲管理-上

1、第四章第四章 存儲器管理存儲器管理 存儲器管理內(nèi)容1.概述概述2.連續(xù)分配存儲管理方式連續(xù)分配存儲管理方式3. 不連續(xù)分配存儲管理方式不連續(xù)分配存儲管理方式頁式存儲管理頁式存儲管理段式存儲管理段式存儲管理段頁式存儲管理段頁式存儲管理4.虛擬存儲虛擬存儲一、概述存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) 內(nèi)存：無限容量大，速度內(nèi)存：無限容量大，速度無限快，永久性存儲器無限快，永久性存儲器金錢、技術金錢、技術存儲管理存儲管理寄存器高速緩存主存磁盤緩存磁盤可移動存儲介質(zhì)CPU寄存器主存輔存一、概述 存儲管理的目的存儲管理的目的主存的分配和管理主存的分配和管理提高主存儲器的利用率提高主存儲器的利用率“擴充擴充”

2、主存容量主存容量存儲保護存儲保護二、概述-程序的裝入和鏈接對用戶程序的處理步驟對用戶程序的處理步驟庫鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標模塊第一步:編譯第二步：鏈接第三步：裝入內(nèi)存地址映射地址映射Load A 1200 3456 。 。1200物理地址空間物理地址空間Load A data1data1 3456源程序源程序Load A 200 34560100200編譯編譯連接連接邏輯地址空間邏輯地址空間BA=1000名空間、地址空間、存儲空間2.1.2.1.程序的裝入程序的裝入絕對裝入方式 程序中所使用的絕對地址，可在編譯或匯編時給出，程序中所使用的絕對地址，可在編譯或匯編時給出， 也

3、可由程序員直接賦予。也可由程序員直接賦予。 但在由程序員直接給出絕對地但在由程序員直接給出絕對地址時，址時， 不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉(zhuǎn)換為絕對地址。或匯編時，再將這些符號地址轉(zhuǎn)換為絕對地址?？芍囟ㄎ谎b入方式動態(tài)運行時裝入方式 動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后，動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并

4、不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行。因是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行。因此此,裝入內(nèi)存后的所有地址都仍是相對地址。裝入內(nèi)存后的所有地址都仍是相對地址。絕對裝入方式絕對裝入方式MOV 1000,5CALL 100printf0100400a1000邏輯地址空間邏輯地址空間MOV 1000,5CALL 100printf0100400a1000物理地址空間物理地址空間可重定位裝入方式可重定位裝入方式MOV 1000,5CALL 100printf0100400a1000邏輯地址空間

5、邏輯地址空間MOV , 5CALLprintf400041004400a5000物理地址空間物理地址空間50004100MOV 1000 , 5CALL 100printf400041004400a5000CPU+4000重定位寄存器重定位寄存器MMUMOV 1000,51000邏輯地址邏輯地址5000物理地址物理地址動態(tài)運行時裝入方式動態(tài)運行時裝入方式2.2.2.2.程序的鏈接程序的鏈接靜態(tài)鏈接方式在程序運行之前，先將各目標模塊及它們所需的庫在程序運行之前，先將各目標模塊及它們所需的庫函數(shù)，鏈接成一個完整的裝配模塊，以后不再拆開。函數(shù)，鏈接成一個完整的裝配模塊，以后不再拆開。裝入時動態(tài)鏈接在

6、裝入內(nèi)存時是邊裝入內(nèi)存，邊裝入邊鏈接，即在在裝入內(nèi)存時是邊裝入內(nèi)存，邊裝入邊鏈接，即在裝入一個目標模塊時，若發(fā)生一個外部模塊調(diào)用，裝入一個目標模塊時，若發(fā)生一個外部模塊調(diào)用，將引起裝入程序去找出相應的外部目標模塊，并將將引起裝入程序去找出相應的外部目標模塊，并將它裝入內(nèi)存。它裝入內(nèi)存。運行時動態(tài)鏈接對某些目標模塊的鏈接，是在程序執(zhí)行中需要該對某些目標模塊的鏈接，是在程序執(zhí)行中需要該（目標）模塊時，才對它進行的鏈接。（目標）模塊時，才對它進行的鏈接。靜態(tài)鏈接方式 在將這幾個目標模在將這幾個目標模塊裝配成一個裝入塊裝配成一個裝入模塊時，須解決以模塊時，須解決以下兩個問題：下兩個問題： (1) (1

7、) 對相對地址進對相對地址進行修改。行修改。 (2) (2) 變換外部調(diào)用變換外部調(diào)用符號。符號。程序鏈接示意圖裝入時動態(tài)鏈接裝入時動態(tài)鏈接方式有以下優(yōu)點：裝入時動態(tài)鏈接方式有以下優(yōu)點： 便于修改和更新。便于修改和更新。 (2) 便于實現(xiàn)對目標模塊的共享。便于實現(xiàn)對目標模塊的共享。運行時動態(tài)鏈接運行時動態(tài)鏈接(Run-time Dynamic Linking) 近幾年流行起來的運行時動態(tài)鏈接方式，是對上述在裝入近幾年流行起來的運行時動態(tài)鏈接方式，是對上述在裝入時鏈接方式的一種改進。這種鏈接方式是時鏈接方式的一種改進。這種鏈接方式是將對某些模塊的將對某些模塊的鏈接推遲到執(zhí)行時才執(zhí)行鏈接推遲到執(zhí)行

8、時才執(zhí)行，亦即，在執(zhí)行過程中，當發(fā)現(xiàn)，亦即，在執(zhí)行過程中，當發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模去找到該模塊并將之裝入內(nèi)存，塊并將之裝入內(nèi)存， 把它鏈接到調(diào)用者模塊上。凡在執(zhí)把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標模塊，都不會被調(diào)入內(nèi)存和被鏈行過程中未被用到的目標模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間?？晒?jié)省大量的內(nèi)存空間。 三、連續(xù)內(nèi)存分配方式三、連續(xù)內(nèi)存分配方式單一連續(xù)分配單一連續(xù)分配 分區(qū)式分配分區(qū)式分配固定分區(qū)式

9、動態(tài)分區(qū)式動態(tài)重定位分配動態(tài)重定位分配3.1 單一連續(xù)分配單一連續(xù)分配（1 1）基本原理：基本原理： 內(nèi)存分為兩個區(qū)域：內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用于操作系統(tǒng)系統(tǒng)區(qū)，用于操作系統(tǒng);用戶區(qū)，用于用戶進程。用戶區(qū)某一時刻只能存放用戶區(qū)，用于用戶進程。用戶區(qū)某一時刻只能存放一個用戶進程，稱為一個用戶進程，稱為“單道，單一單道，單一”用戶程序用戶程序位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)0 xFFF.0位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序0ROM中的中的設備驅(qū)動程序設備驅(qū)動程序用戶程序用戶程序位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)0（2）內(nèi)存的分配和回收）內(nèi)存的分配和回收一般用戶單道

10、系統(tǒng)一般用戶單道系統(tǒng)用時分配，空閑回收用時分配，空閑回收（3）內(nèi)存的保護）內(nèi)存的保護為了防止用戶程序破壞操作系統(tǒng)的代碼為了防止用戶程序破壞操作系統(tǒng)的代碼和數(shù)據(jù)，要采取一些保護措施。和數(shù)據(jù)，要采取一些保護措施。采用動態(tài)重定位時加一些保護措施，用采用動態(tài)重定位時加一些保護措施，用到兩個寄存器：到兩個寄存器：重定位寄存器：用戶程序裝入內(nèi)存的起重定位寄存器：用戶程序裝入內(nèi)存的起始地址始地址界限寄存器：存放用戶程序的長度界限寄存器：存放用戶程序的長度物理地址物理地址CPU界限寄存器界限寄存器重定位寄存器重定位寄存器內(nèi)存內(nèi)存邏輯邏輯地址地址是是否否地址錯誤地址錯誤3.2.3.2.固定分區(qū)分配固定分區(qū)分配

11、1 基本原理基本原理分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)輸入隊列輸入隊列2 劃分分區(qū)的方法劃分分區(qū)的方法(1)分區(qū)大小相等分區(qū)大小相等,即使所有的即使所有的內(nèi)存分區(qū)大小相等。適用內(nèi)存分區(qū)大小相等。適用于控制多個相同對象。于控制多個相同對象。 (2) 分區(qū)大小不等。分區(qū)大小不等。 多個較小多個較小的分區(qū)，適量的中等分區(qū)的分區(qū)，適量的中等分區(qū)及少量的大分區(qū)及少量的大分區(qū)3.3.內(nèi)存分配內(nèi)存分配 固定分區(qū)使用表固定分區(qū)使用表 如何回收如何回收3.3 3.3 動態(tài)分區(qū)分配動態(tài)分區(qū)分配 1 基本原理基本原理 根據(jù)進程的需要動態(tài)地分配連續(xù)的內(nèi)存空間。實現(xiàn)根據(jù)進程的需要動態(tài)地分配連續(xù)的內(nèi)

12、存空間。實現(xiàn)時涉及到三個問題：分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)、分區(qū)時涉及到三個問題：分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配與回收。分配算法和分區(qū)的分配與回收。2 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表空閑分區(qū)表 空閑分區(qū)鏈空閑分區(qū)鏈0操作系統(tǒng)操作系統(tǒng)400K2560K11000KP3,300K2000K2300K260K300KP4，700K100KP5,500K900K1700K起始地址長度900K100K1700K300K2300K260K空閑分區(qū)表空閑分區(qū)表900K100K1700K300K2300K260KNULL空閑分區(qū)鏈空閑分區(qū)鏈可變分區(qū)模式的工作流程可變分區(qū)模式的工作流

13、程先看一個例子。一個計算機有先看一個例子。一個計算機有2560K2560K內(nèi)存，采用可變分區(qū)模式管理內(nèi)存，采用可變分區(qū)模式管理內(nèi)存，操作系統(tǒng)占用低地址的內(nèi)存，操作系統(tǒng)占用低地址的400K400K空間，剩余空間，剩余2160K2160K的空間為用戶區(qū)。的空間為用戶區(qū)。最初整個用戶區(qū)是空閑的，就一最初整個用戶區(qū)是空閑的，就一個分區(qū)。然后隨著用戶程序的創(chuàng)建個分區(qū)。然后隨著用戶程序的創(chuàng)建和撤銷。分區(qū)的個數(shù)和大小位置開和撤銷。分區(qū)的個數(shù)和大小位置開始變化。始變化。P1來，來，600K0操作系統(tǒng)操作系統(tǒng)400K2560K1P1，600K1000K1560K內(nèi)存的初始狀態(tài)內(nèi)存的初始狀態(tài)P2來，來，1000K

14、0操作系統(tǒng)操作系統(tǒng)400K2560K1P1，600K1000K560K2000KP2，1000K0操作系統(tǒng)操作系統(tǒng)400K2560K12160KP3來，來，300K0操作系統(tǒng)操作系統(tǒng)400K2560K1P1，600K1000KP3,300K2000KP2，1000K2300K260KP2結(jié)束結(jié)束0操作系統(tǒng)操作系統(tǒng)400K2560K1P1，600K1000KP3,300K2000K2300K260K1000KP4來來 700KP1結(jié)束結(jié)束P5來來 500K0操作系統(tǒng)操作系統(tǒng)400K2560K11000KP3,300K2000K2300K260K300KP4，700K600K1700K0操作系統(tǒng)操

15、作系統(tǒng)400K2560K11000KP3,300K2000K2300K260K300KP4，700K100KP5,500K900K1700K0操作系統(tǒng)操作系統(tǒng)400K2560K1P1，600K1000KP3,300K2000K2300K260K300KP4，700K1700K3.分區(qū)分配算法分區(qū)分配算法 首次適應算法首次適應算法FF 循環(huán)首次適應算法循環(huán)首次適應算法 最佳適應算法最佳適應算法 最壞適應算法最壞適應算法 快速適應算法快速適應算法 首次適應算法首次適應算法 該算法要求空閑分區(qū)鏈按照空閑分區(qū)該算法要求空閑分區(qū)鏈按照空閑分區(qū)起始地址遞增起始地址遞增的次序排序。的次序排序。 在分配內(nèi)存時

16、，每次都從鏈首開始查找，直至找到在分配內(nèi)存時，每次都從鏈首開始查找，直至找到一個長度大于用戶程序的分區(qū)，就進行分配。一個長度大于用戶程序的分區(qū)，就進行分配。 傾向于優(yōu)先利用內(nèi)存中低址部分的內(nèi)存，從而保留傾向于優(yōu)先利用內(nèi)存中低址部分的內(nèi)存，從而保留高址的大空閑區(qū)，但是低址部分會留下許多難以利高址的大空閑區(qū)，但是低址部分會留下許多難以利用的、很小的內(nèi)存空閑區(qū)，增加查找時間用的、很小的內(nèi)存空閑區(qū)，增加查找時間 循環(huán)首次適應算法循環(huán)首次適應算法 該算法是從首次適應算法演變而來的。在分配內(nèi)存該算法是從首次適應算法演變而來的。在分配內(nèi)存時，不再是每次都從鏈首開始找，而是從上次找到時，不再是每次都從鏈首開始

17、找，而是從上次找到的空閑分區(qū)的下一個節(jié)點開始找。到了鏈尾，再從的空閑分區(qū)的下一個節(jié)點開始找。到了鏈尾，再從鏈首開始找。鏈首開始找。 內(nèi)存中空閑區(qū)分布的比較均勻，減少查找時間，但內(nèi)存中空閑區(qū)分布的比較均勻，減少查找時間，但會缺乏大的空閑區(qū)。會缺乏大的空閑區(qū)。 最佳適應算法最佳適應算法 所謂所謂“最佳最佳”是指分配內(nèi)存時，總是把是指分配內(nèi)存時，總是把滿足要求的滿足要求的最小分區(qū)最小分區(qū)分配給用戶程序。分配給用戶程序。 為了加快分配速度，可以把空閑分區(qū)鏈按照空閑分為了加快分配速度，可以把空閑分區(qū)鏈按照空閑分區(qū)的大小遞增的順序排序，則找到的第一個滿足要區(qū)的大小遞增的順序排序，則找到的第一個滿足要求的分

18、區(qū)即是最佳的。求的分區(qū)即是最佳的。 每次分配剩下的內(nèi)存是最小的，導致存儲區(qū)留下許每次分配剩下的內(nèi)存是最小的，導致存儲區(qū)留下許多難以利用的小空閑區(qū)多難以利用的小空閑區(qū) 最壞適應法最壞適應法 將空閑區(qū)從大到小分配，每次都分配最大的空閑區(qū)。將空閑區(qū)從大到小分配，每次都分配最大的空閑區(qū)。 優(yōu)點是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的優(yōu)點是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，適合中小作業(yè)，同時分配算法查找效率幾率最小，適合中小作業(yè)，同時分配算法查找效率最高。最高。 缺點導致缺乏大空閑區(qū)缺點導致缺乏大空閑區(qū)。以上以上4種算法都為順序搜索法種算法都為順序搜索法 快速適應算法：又稱為分類搜索法快速

19、適應算法：又稱為分類搜索法 將空閑分區(qū)根據(jù)其容量大小進行分類，對于每一類具將空閑分區(qū)根據(jù)其容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設立一個空閑分區(qū)有相同容量的所有空閑分區(qū)，單獨設立一個空閑分區(qū)鏈表，在內(nèi)存中設立一張管理索引表，該表的每一表鏈表，在內(nèi)存中設立一張管理索引表，該表的每一表項對應了一個空閑分區(qū)類型并記錄了該類型空閑分區(qū)項對應了一個空閑分區(qū)類型并記錄了該類型空閑分區(qū)鏈表表頭的指針?？臻e分區(qū)的分類是根據(jù)進程常用的鏈表表頭的指針?？臻e分區(qū)的分類是根據(jù)進程常用的空間大小進行劃分，如空間大小進行劃分，如2KB，4KB，8KB等。等。 優(yōu)點：查找效率高，根據(jù)進程的長度，尋找到

20、能容納優(yōu)點：查找效率高，根據(jù)進程的長度，尋找到能容納它的最小空閑區(qū)鏈表，取下第一塊進行分配即可。能它的最小空閑區(qū)鏈表，取下第一塊進行分配即可。能保持大空間需要，也不會產(chǎn)生內(nèi)存碎片，保持大空間需要，也不會產(chǎn)生內(nèi)存碎片， 分區(qū)歸還主存時算法復雜，系統(tǒng)開銷較大。分區(qū)歸還主存時算法復雜，系統(tǒng)開銷較大。4.分區(qū)分配操作分區(qū)分配操作 分配內(nèi)存分配內(nèi)存 從頭開始查表檢索完否？m.size u.size?m.size u.sizesize?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請求者修改有關數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個表項將該分區(qū)從鏈中移出YNNYYN內(nèi)存分配流程回收內(nèi)存回收內(nèi)存 根據(jù)回收區(qū)的首

21、址，從空閑區(qū)鏈表中找到相應根據(jù)回收區(qū)的首址，從空閑區(qū)鏈表中找到相應的插入點，可能出現(xiàn)以下的插入點，可能出現(xiàn)以下4 4種情況：種情況：P2P1P3P1運行結(jié)束運行結(jié)束P2P1P3F1P3運行結(jié)束運行結(jié)束P1所占分區(qū)的上下都不空閑，在空閑分區(qū)所占分區(qū)的上下都不空閑，在空閑分區(qū)鏈中添加一項，填寫回收區(qū)的首址和大小鏈中添加一項，填寫回收區(qū)的首址和大小P3所占分區(qū)下邊的分區(qū)所占分區(qū)下邊的分區(qū)F1空閑，應進行空閑，應進行合并。在空閑分區(qū)鏈中找到合并。在空閑分區(qū)鏈中找到F1節(jié)點，修節(jié)點，修改其起始地址和長度改其起始地址和長度P2P1P3F1P2運行結(jié)束運行結(jié)束P2所占分區(qū)上邊的分區(qū)所占分區(qū)上邊的分區(qū)F1空閑

22、，應空閑，應進行合并。在空閑鏈表中找到進行合并。在空閑鏈表中找到F1節(jié)節(jié)點，修改其長度點，修改其長度P2P1P3F1F2P1運行結(jié)束運行結(jié)束P2P2所占分區(qū)上下邊的分區(qū)所占分區(qū)上下邊的分區(qū)F1和和F2都空都空閑，應進行合并。在空閑鏈表中找到閑，應進行合并。在空閑鏈表中找到F1節(jié)點，修改其長度為節(jié)點，修改其長度為F1、F2和和P2所所占分區(qū)的長度和。刪除占分區(qū)的長度和。刪除F2節(jié)點節(jié)點伙伴系統(tǒng)伙伴系統(tǒng)固定分區(qū)和動態(tài)分區(qū)方式都有不足之處。固定分區(qū)方式固定分區(qū)和動態(tài)分區(qū)方式都有不足之處。固定分區(qū)方式限制了活動進程的數(shù)目，當進程大小與空閑分區(qū)大小不匹配限制了活動進程的數(shù)目，當進程大小與空閑分區(qū)大小不匹

23、配時，內(nèi)存空間利用率很低。動態(tài)分區(qū)方式算法復雜，回收空時，內(nèi)存空間利用率很低。動態(tài)分區(qū)方式算法復雜，回收空閑分區(qū)時需要進行分區(qū)合并等，系統(tǒng)開銷較大。伙伴系統(tǒng)方閑分區(qū)時需要進行分區(qū)合并等，系統(tǒng)開銷較大?；锇橄到y(tǒng)方式是對以上兩種內(nèi)存方式的一種折衷方案。式是對以上兩種內(nèi)存方式的一種折衷方案。 伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為為2 2的的k k次冪，次冪，k k為整數(shù)，為整數(shù)，lkm，其中：，其中：21表示分配的最小表示分配的最小分區(qū)的大小，分區(qū)的大小，2m表示分配的最大分區(qū)的大小，通常表示分配的最大分區(qū)的大小，通常2m是整個是整個可分

24、配內(nèi)存的大小?？煞峙鋬?nèi)存的大小。 假設系統(tǒng)的可利用空間容量為假設系統(tǒng)的可利用空間容量為2m個字，則系統(tǒng)開始運行個字，則系統(tǒng)開始運行時，整個內(nèi)存區(qū)是一個大小為時，整個內(nèi)存區(qū)是一個大小為2m的空閑分區(qū)。在系統(tǒng)運行的空閑分區(qū)。在系統(tǒng)運行過程中，由于不斷的劃分，可能會形成若干個不連續(xù)的空閑過程中，由于不斷的劃分，可能會形成若干個不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)根據(jù)分區(qū)的大小進行分類，對于每一分區(qū)，將這些空閑分區(qū)根據(jù)分區(qū)的大小進行分類，對于每一類具有相同大小的所有空閑分區(qū)，單獨設立一個空閑分區(qū)雙類具有相同大小的所有空閑分區(qū)，單獨設立一個空閑分區(qū)雙向鏈表。這樣，不同大小的空閑分區(qū)形成了向鏈表。這樣，不同大

25、小的空閑分區(qū)形成了k(0km)個空個空閑分區(qū)鏈表。閑分區(qū)鏈表。 當需要為進程分配一個長度為當需要為進程分配一個長度為n的存儲空間時，首先計的存儲空間時，首先計算一個算一個i值，使值，使2i1緊湊-程序地址變化操作系統(tǒng)操作系統(tǒng)P110KP315KP730KP8操作系統(tǒng)操作系統(tǒng)P110KP315KP730KP8緊湊技術緊湊技術compaction2 2）動態(tài)重定位的實現(xiàn)）動態(tài)重定位的實現(xiàn) 動態(tài)重定位示意圖動態(tài)重定位示意圖 LOAD1,25003650100250050002500相對地址10000重定位寄存器LOAD1,250036510000101001250015000作業(yè)J處理機一側(cè) 存儲器

26、一側(cè)主存3 ）動態(tài)重定位分區(qū)分配算法）動態(tài)重定位分區(qū)分配算法 動態(tài)分區(qū)分配算法流程圖動態(tài)分區(qū)分配算法流程圖 請求分配u.size分區(qū)檢索空閑分區(qū)鏈(表)找到大于u.size的可用區(qū)否?按動態(tài)分區(qū)方式進行分配修改有關的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首批空閑分區(qū)總和u.size?進行緊湊形成連續(xù)空閑區(qū)修改有關的數(shù)據(jù)結(jié)構(gòu)否是無法分配返回否7、交換（、交換（Swapping）交換交換(Swapping)的引入的引入 為了提高內(nèi)存的利用率，出現(xiàn)了交換技術。為了提高內(nèi)存的利用率，出現(xiàn)了交換技術。 進程在運行過程中經(jīng)常因為進行進程在運行過程中經(jīng)常因為進行I/O操作和等待其他事操作和等待其他事件而阻塞，無法執(zhí)行。系統(tǒng)在

27、內(nèi)存緊張時把這些進程件而阻塞，無法執(zhí)行。系統(tǒng)在內(nèi)存緊張時把這些進程暫時換出內(nèi)存放入外存，騰出內(nèi)存分配給有條件運行暫時換出內(nèi)存放入外存，騰出內(nèi)存分配給有條件運行的進程。的進程。 所謂所謂“對換對換”， 是指把內(nèi)存中暫時不能運行的進程或是指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運行條件的進程或進程足夠的內(nèi)存空間，再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對換是提高內(nèi)存利所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對換是提高內(nèi)存利用率的有效措施。用率的有效措施。 以進程為單位進行交換以進程

28、為單位進行交換對換空間的管理對換空間的管理 在外存上，系統(tǒng)管理著專門的空間用于存放從內(nèi)存換出的進程，這空間稱為對換區(qū)。 為了能對對換區(qū)中的空閑盤塊進行管理，在系統(tǒng)中應配置相應的數(shù)據(jù)結(jié)構(gòu)，以記錄外存的使用情況。其形式與內(nèi)存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個表目中應包含兩項， 即對換區(qū)的首址及其大小，它們的單位是盤塊號和盤塊數(shù)。進程的換出與換入進程的換出與換入 進程的換出：每當一進程由于創(chuàng)建子進程而需進程的換出：每當一進程由于創(chuàng)建子進程而需要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等情況發(fā)生時，系統(tǒng)應將

29、某進程換出。情況發(fā)生時，系統(tǒng)應將某進程換出。 其過程是：其過程是：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，然后啟動盤塊，將該進程的程作為換出進程，然后啟動盤塊，將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送過程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送過程未出現(xiàn)錯誤，便可回收該進程所占用的內(nèi)存程未出現(xiàn)錯誤，便可回收該進程所占用的內(nèi)存空間，并對該進程的進程控制塊做相應的修改空間，并對該進程的進程控制塊做相應的修改 選擇阻塞、優(yōu)先級低選擇阻塞、優(yōu)先級低-將次進程保持到交換區(qū)將次進程保持到交換區(qū)-回收內(nèi)存回收內(nèi)存 進程的換入進程的換入交換區(qū)中選擇交

30、換區(qū)中選擇“就緒就緒”、時間最久、時間最久-換入到內(nèi)存。換入到內(nèi)存。四、基本分頁存儲管理四、基本分頁存儲管理 4.1 基本原理基本原理 把用戶的程序空間把用戶的程序空間(邏輯地址空間）劃分成大小相等的邏輯地址空間）劃分成大小相等的塊，稱為塊，稱為頁（面）、邏輯頁頁（面）、邏輯頁，從，從0開始給頁編號。開始給頁編號。 頁的大小應是頁的大小應是2的的n次冪，通常是次冪，通常是512B8KB 物理內(nèi)存按照頁的大小也劃分成大小相等的區(qū)域，稱物理內(nèi)存按照頁的大小也劃分成大小相等的區(qū)域，稱為為頁框、物理頁、物理塊頁框、物理頁、物理塊，從，從0開始編號開始編號 內(nèi)存分配：將進程空間中的邏輯頁面映射到物理空間

31、內(nèi)存分配：將進程空間中的邏輯頁面映射到物理空間中空閑的頁面中空閑的頁面.0123456程序邏輯空間程序邏輯空間內(nèi)存物理空間內(nèi)存物理空間01234567要求要把程序的要求要把程序的所有頁所有頁都裝入到內(nèi)存后，都裝入到內(nèi)存后，程序才能運行。程序才能運行。用戶程序分頁邏輯地址的結(jié)構(gòu)：用戶程序分頁邏輯地址的結(jié)構(gòu)： 32位位 011位頁內(nèi)地址（每頁大小為位頁內(nèi)地址（每頁大小為4KB=212KB）；）；1231頁號（地址空間最多允許有頁號（地址空間最多允許有1M=220頁）頁）頁號頁號 頁內(nèi)地址頁內(nèi)地址0111231對于某特定機器，其地址結(jié)構(gòu)是一定的。若給定一個邏對于某特定機器，其地址結(jié)構(gòu)是一定的。若給定

32、一個邏輯地址空間中的地址為輯地址空間中的地址為A，頁面的大小為，頁面的大小為L，則頁號，則頁號P和頁內(nèi)和頁內(nèi)地址地址d可按下式求得：可按下式求得： AMODLdLAINTP其中，其中，INT是整除函數(shù)，是整除函數(shù)，MOD是取余函數(shù)。例如，其系統(tǒng)的是取余函數(shù)。例如，其系統(tǒng)的頁面大小為頁面大小為1 KB，設，設A = 2170 B則由上式可以求得則由上式可以求得P = 2，d = 122。 2、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)（1）內(nèi)存頁表：）內(nèi)存頁表：要完成內(nèi)存物理頁的分配，則必須知道哪些物要完成內(nèi)存物理頁的分配，則必須知道哪些物理頁空閑，哪些被占用。要用一個數(shù)據(jù)結(jié)構(gòu)來隨理頁空閑，哪些被占用。要用一個數(shù)據(jù)結(jié)構(gòu)

33、來隨時記錄內(nèi)存的情況，這個數(shù)據(jù)結(jié)構(gòu)稱為時記錄內(nèi)存的情況，這個數(shù)據(jù)結(jié)構(gòu)稱為內(nèi)存頁表內(nèi)存頁表。01234n0，空閑，空閑1，被占用，被占用問題：內(nèi)存頁表有多少項？與問題：內(nèi)存頁表有多少項？與哪些因素有關？哪些因素有關？回答：回答： 內(nèi)存頁表的行數(shù)內(nèi)存頁表的行數(shù)內(nèi)存的大小內(nèi)存的大小 / 頁的大小頁的大?。?）進程頁表）進程頁表內(nèi)存頁表中的空閑物理頁是隨著不斷內(nèi)存頁表中的空閑物理頁是隨著不斷的分配與回收而隨機分布的。因此一個的分配與回收而隨機分布的。因此一個程序的所有頁裝入到哪些內(nèi)存物理頁也程序的所有頁裝入到哪些內(nèi)存物理頁也是隨機的。這就需要為是隨機的。這就需要為每一個進程每一個進程建立建立一張表，來

34、記錄該進程的每一頁都裝入一張表，來記錄該進程的每一頁都裝入到哪個物理頁去了，這張表稱為到哪個物理頁去了，這張表稱為進程頁進程頁表。表。 進程頁表進程頁表0123456用戶程序空間用戶程序空間內(nèi)存物理空間內(nèi)存物理空間01234567421311221824進程頁表進程頁表用戶程序0 頁1 頁2 頁3 頁4 頁5 頁n 頁頁表頁號塊號02132638495內(nèi)存012345678910問題：進程頁表放在哪兒？問題：進程頁表放在哪兒？回答：內(nèi)存回答：內(nèi)存問題：進程頁表的首地址放在哪兒？問題：進程頁表的首地址放在哪兒？回答：進程的回答：進程的PCB，頁表的長度也放，頁表的長度也放PCB 4.3分配與回收

35、分配與回收 分配過程分配過程用戶程序請求運行用戶程序請求運行查找內(nèi)存頁表有足夠查找內(nèi)存頁表有足夠的空閑物理頁嗎？的空閑物理頁嗎？系統(tǒng)根據(jù)程序長度計算所需的頁數(shù)系統(tǒng)根據(jù)程序長度計算所需的頁數(shù)否否是是等待等待修改內(nèi)存頁表，建立進程頁表，頁表始址和長度放修改內(nèi)存頁表，建立進程頁表，頁表始址和長度放PCB裝入用戶程序裝入用戶程序回收過程回收過程 根據(jù)進程頁表的內(nèi)容，把內(nèi)存頁表中對應的根據(jù)進程頁表的內(nèi)容，把內(nèi)存頁表中對應的物理頁改為空閑物理頁改為空閑 撤銷進程頁表撤銷進程頁表4.4地址轉(zhuǎn)換（重定位）問題地址轉(zhuǎn)換（重定位）問題 某系統(tǒng)邏輯地址某系統(tǒng)邏輯地址32位，頁的大小為位，頁的大小為4K04K8K12

36、K16KMOV 8193，200 用戶程序空間用戶程序空間13689進程頁表進程頁表0123456789物理內(nèi)存物理內(nèi)存8193應轉(zhuǎn)換的物理地址是什么？應轉(zhuǎn)換的物理地址是什么？81934K21邏輯頁號為邏輯頁號為2，頁內(nèi)地址，頁內(nèi)地址1由頁表得知由頁表得知2號邏輯頁裝入到號邏輯頁裝入到6號物號物理頁，所以物理地址為：理頁，所以物理地址為：64K1 24577P=INTA/L d=AMOD L1.基本的地址變換機構(gòu)基本的地址變換機構(gòu) b注意：要求頁表連續(xù)存放注意：要求頁表連續(xù)存放PTR00000000000100000000000000000010頁號頁號頁內(nèi)地址頁內(nèi)地址邏輯地址邏輯地址 819

37、33112110頁表寄存器頁表寄存器頁表始址頁表始址頁表長度頁表長度6+物理內(nèi)存區(qū)的映射物理內(nèi)存區(qū)的映射 段表存放在內(nèi)存，其起始地址和長度存入進程段表存放在內(nèi)存，其起始地址和長度存入進程的的PCB段號段號012段長度段長度基址基址58K20K100K110K260K540K操作系統(tǒng)操作系統(tǒng).B0SA0NY0LX0PM0K邏輯段號邏輯段號01234作業(yè)作業(yè)1的地址空間的地址空間10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000長度長度 段地址段地址01234操作系統(tǒng)操作系統(tǒng)邏輯地址邏輯地址00000000000000110000

38、000000000010，物理地址是多少？，物理地址是多少？ 地址轉(zhuǎn)換地址轉(zhuǎn)換-動態(tài)重定位動態(tài)重定位 Cl Cb+段號段號S S 段內(nèi)地址段內(nèi)地址d比較比較比較比較b + d比較比較段段表表S= Cl快表快表物理地址物理地址段表始址寄存器段表始址寄存器段表長度寄存器段表長度寄存器邏輯地址邏輯地址lb.Slb地址越界地址越界d=1d=l地址映射及存儲保護機制地址映射及存儲保護機制地址越界地址越界地址越界地址越界比較比較長度長度 始址始址5.1分段存儲基本原理 分頁與分段的區(qū)別 頁是信息的物理單位，段則是信息的邏輯單位 頁的大小固定且由系統(tǒng)決定，而段的長度卻不固定 分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，分段的作業(yè)地址空間則是二維的，程序員在標識一個地址時即需給出段名，又需給出段內(nèi)地址5.2