第4章存儲(chǔ)管理-上

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

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

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

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

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

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

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

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

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

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

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

12、存空間。實(shí)現(xiàn)時(shí)涉及到三個(gè)問題：分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)、分區(qū)時(shí)涉及到三個(gè)問題：分區(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起始地址長(zhǎng)度900K100K1700K300K2300K260K空閑分區(qū)表空閑分區(qū)表900K100K1700K300K2300K260KNULL空閑分區(qū)鏈空閑分區(qū)鏈可變分區(qū)模式的工作流程可變分區(qū)模式的工作流

13、程先看一個(gè)例子。一個(gè)計(jì)算機(jī)有先看一個(gè)例子。一個(gè)計(jì)算機(jī)有2560K2560K內(nèi)存，采用可變分區(qū)模式管理內(nèi)存，采用可變分區(qū)模式管理內(nèi)存，操作系統(tǒng)占用低地址的內(nèi)存，操作系統(tǒng)占用低地址的400K400K空間，剩余空間，剩余2160K2160K的空間為用戶區(qū)。的空間為用戶區(qū)。最初整個(gè)用戶區(qū)是空閑的，就一最初整個(gè)用戶區(qū)是空閑的，就一個(gè)分區(qū)。然后隨著用戶程序的創(chuàng)建個(gè)分區(qū)。然后隨著用戶程序的創(chuàng)建和撤銷。分區(qū)的個(gè)數(shù)和大小位置開和撤銷。分區(qū)的個(gè)數(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ū)分配算法 首次適應(yīng)算法首次適應(yīng)算法FF 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法 最佳適應(yīng)算法最佳適應(yīng)算法 最壞適應(yīng)算法最壞適應(yīng)算法 快速適應(yīng)算法快速適應(yīng)算法 首次適應(yīng)算法首次適應(yīng)算法 該算法要求空閑分區(qū)鏈按照空閑分區(qū)該算法要求空閑分區(qū)鏈按照空閑分區(qū)起始地址遞增起始地址遞增的次序排序。的次序排序。 在分配內(nèi)存時(shí)

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

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

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

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

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

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

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

23、配時(shí)，內(nèi)存空間利用率很低。動(dòng)態(tài)分區(qū)方式算法復(fù)雜，回收空時(shí)，內(nèi)存空間利用率很低。動(dòng)態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)時(shí)需要進(jìn)行分區(qū)合并等，系統(tǒng)開銷較大?；锇橄到y(tǒng)方閑分區(qū)時(shí)需要進(jìn)行分區(qū)合并等，系統(tǒng)開銷較大?；锇橄到y(tǒng)方式是對(duì)以上兩種內(nèi)存方式的一種折衷方案。式是對(duì)以上兩種內(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是整個(gè)是整個(gè)可分

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

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

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

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

28、為單位進(jìn)行交換對(duì)換空間的管理對(duì)換空間的管理 在外存上，系統(tǒng)管理著專門的空間用于存放從內(nèi)存換出的進(jìn)程，這空間稱為對(duì)換區(qū)。 為了能對(duì)對(duì)換區(qū)中的空閑盤塊進(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ū)的首址及其大小，它們的單位是盤塊號(hào)和盤塊數(shù)。進(jìn)程的換出與換入進(jìn)程的換出與換入 進(jìn)程的換出：每當(dāng)一進(jìn)程由于創(chuàng)建子進(jìn)程而需進(jìn)程的換出：每當(dāng)一進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等情況發(fā)生時(shí)，系統(tǒng)應(yīng)將

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

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

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

32、一個(gè)邏輯地址空間中的地址為輯地址空間中的地址為A，頁面的大小為，頁面的大小為L(zhǎng)，則頁號(hào)，則頁號(hào)P和頁內(nèi)和頁內(nèi)地址地址d可按下式求得：可按下式求得： AMODLdLAINTP其中，其中，INT是整除函數(shù)，是整除函數(shù)，MOD是取余函數(shù)。例如，其系統(tǒng)的是取余函數(shù)。例如，其系統(tǒng)的頁面大小為頁面大小為1 KB，設(shè)，設(shè)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)存物理頁的分配，則必須知道哪些物理頁空閑，哪些被占用。要用一個(gè)數(shù)據(jù)結(jié)構(gòu)來隨理頁空閑，哪些被占用。要用一個(gè)數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

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

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