第四章存儲器管理

1、計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院第四章存儲器管理 4.1 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) 4.2程序的裝入和鏈接程序的裝入和鏈接 4.3連續(xù)分配方式連續(xù)分配方式4.4基本分頁存儲管理方式基本分頁存儲管理方式4.5基本分段存儲管理方式基本分段存儲管理方式4.6虛擬存儲器的基本概念虛擬存儲器的基本概念4.7請求分頁存儲管理方式請求分頁存儲管理方式4.8頁面置換算法頁面置換算法4.9請求分段存儲管理方式請求分段存儲管理方式 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算

2、機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.1 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) 4.1.1 4.1.1 多級存儲器結(jié)構(gòu)多級存儲器結(jié)構(gòu)對于通用計算機而言，存儲層次至少應(yīng)具有三級：最高層為CPU寄存器，中間為主存，最底層是輔存。在較高檔的計算機中，還可以根據(jù)具體的功能分工細(xì)劃為寄存器、高速緩存、主存儲器、磁盤緩存、固定磁盤、可移動存儲介質(zhì)等6層。如圖4-1所示，在存儲層次中越往上，存儲介質(zhì)的訪問速度越快，價格也越高，相對存儲容量也越小。其中，寄存器、高速緩存、主存儲器和磁盤緩存均屬于操作系統(tǒng)存儲管理的管轄范疇，掉電后它們存儲的信息不再存在。固定磁盤和可移動存儲介質(zhì)屬于設(shè)備管理的管轄范疇，它們存儲的信息將被長期保存。

3、 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院圖4-1 計算機系統(tǒng)存儲層次示意 寄存器高速緩存主存磁盤緩存磁盤可移動存儲介質(zhì)CPU寄存器主存輔存計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.1.2 4.1.2 主存儲器與寄存器主存儲器與寄存器1 1主存儲器主存儲器主存儲器(簡稱內(nèi)存或主存)是計算機系統(tǒng)中一個主要部件，用于保存進程運行時的程序和數(shù)據(jù)，也稱可執(zhí)行存儲器，其容量對于當(dāng)前的微機系統(tǒng)和大中型機，可能一般為數(shù)十MB到數(shù)GB，而且容量還在不斷增加，而嵌

4、入式計算機系統(tǒng)一般僅有幾十KB到幾MB。CPU的控制部件只能從主存儲器中取得指令和數(shù)據(jù)，數(shù)據(jù)能夠從主存儲器讀取并將它們裝入到寄存器中，或者從寄存器存入到主存儲器。CPU與外圍設(shè)備交換的信息一般也依托于主存儲器地址空間。由于主存儲器的訪問速度遠(yuǎn)低于CPU執(zhí)行指令的速度，為緩和這一矛盾，在計算機系統(tǒng)中引入了寄存器和高速緩存。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院2 2寄存器寄存器寄存器訪問速度最快，完全能與CPU協(xié)調(diào)工作，但價格卻十分昂貴，因此容量不可能做得很大。寄存器的長度一般以字(word)為單位。寄存器的數(shù)目，對于

5、當(dāng)前的微機系統(tǒng)和大中型機，可能有幾十個甚至上百個；而嵌入式計算機系統(tǒng)一般僅有幾個到幾十個。寄存器用于加速存儲器的訪問速度，如用寄存器存放操作數(shù)，或用作地址寄存器加快地址轉(zhuǎn)換速度等。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.1.3 4.1.3 高速緩存和磁盤緩存高速緩存和磁盤緩存1 1高速緩存高速緩存高速緩存是現(xiàn)代計算機結(jié)構(gòu)中的一個重要部件，其容量大于或遠(yuǎn)大于寄存器，而比內(nèi)存約小兩到三個數(shù)量級左右，從幾十KB到幾MB，訪問速度快于主存儲器。根據(jù)程序執(zhí)行的局部性原理(即程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，在一較短的時間內(nèi)，程

6、序的執(zhí)行僅局限于某個部分)，將主存中一些經(jīng)常訪問的信息存放在高速緩存中，減少訪問主存儲器的次數(shù)，可大幅度提高程序執(zhí)行速度。計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院2 2磁盤緩存磁盤緩存由于目前磁盤的I/O速度遠(yuǎn)低于對主存的訪問速度，因此將頻繁使用的一部分磁盤數(shù)據(jù)和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數(shù)。磁盤緩存本身并不是一種實際存在的存儲介質(zhì)，它依托于固定磁盤，提供對主存儲器存儲空間的擴充，即利用主存中的存儲空間，來暫存從磁盤中讀出(或?qū)懭?的信息。主存也可以看做是輔存的高速緩存，因為，輔存中的數(shù)據(jù)必須復(fù)制到主

7、存方能使用；反之，數(shù)據(jù)也必須先存在主存中，才能輸出到輔存。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院一個文件的數(shù)據(jù)可能出現(xiàn)在存儲器層次的不同級別中，例如，一個文件數(shù)據(jù)通常被存儲在輔存中(如硬盤)，當(dāng)其需要運行或被訪問時，就必須調(diào)入主存，也可以暫時存放在主存的磁盤高速緩存中。大容量的輔存常常使用磁盤，磁盤數(shù)據(jù)經(jīng)常備份到磁帶或可移動磁盤組上，以防止硬盤故障時丟失數(shù)據(jù)。有些系統(tǒng)自動地把老文件數(shù)據(jù)從輔存轉(zhuǎn)儲到海量存儲器中，如磁帶上，這樣做還能降低存儲價格。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器

8、管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.2程序的裝入和鏈接程序的裝入和鏈接 在多道程序環(huán)境下，要使程序運行，必須先為之創(chuàng)建進程。而創(chuàng)建進程的第一件事，便是將程序和數(shù)據(jù)裝入內(nèi)存。如何將一個用戶源程序變?yōu)橐粋€可在內(nèi)存中執(zhí)行的程序，通常都要經(jīng)過以下幾個步驟：首先是要編譯，由編譯程序(Compiler)將用戶源代碼編譯成若干個目標(biāo)模塊(Object Module)；其次是鏈接，由鏈接程序(Linker)將編譯后形成的一組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊(Load Module)；最后是裝入，由裝入程序(Loader)將裝入模塊裝入內(nèi)存。圖4-2示出了這樣的三步過

9、程。本節(jié)將扼要闡述程序(含數(shù)據(jù))的鏈接和裝入過程。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院圖4-2對用戶程序的處理步驟 庫鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院Goto L1L1：源程序編譯Goto 2目標(biāo)代碼0123名空間地址空間裝入Goto a2內(nèi)存(運行程序)

10、aa1存儲空間a2 【作業(yè)的名空間、邏輯地址空間和物理空間】【作業(yè)的名空間、邏輯地址空間和物理空間】計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.2.14.2.1程序的裝入程序的裝入1 1絕對裝入方式絕對裝入方式(Absolute Loading Mode)(Absolute Loading Mode)在編譯時，如果知道程序?qū)Ⅰv留在內(nèi)存的什么位置，那么，編譯程序?qū)a(chǎn)生絕對地址的目標(biāo)代碼。例如，事先已知用戶程序(進程)駐留在從R處開始的位置，則編譯程序所產(chǎn)生的目標(biāo)模塊(即裝入模塊)便從R處開始向上擴展。絕對裝入程序按照裝入模

11、塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。裝入模塊被裝入內(nèi)存后，由于程序中的邏輯地址與實際內(nèi)存地址完全相同，故不須對程序和數(shù)據(jù)的地址進行修改。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院程序中所使用的絕對地址，既可在編譯或匯編時給出，也可由程序員直接賦予。但在由程序員直接給出絕對地址時，不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉(zhuǎn)換為絕對地址。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章

12、存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院2可重定位裝入方式可重定位裝入方式(Relocation Loading Mode) 絕對裝入方式只能將目標(biāo)模塊裝入到內(nèi)存中事先指定的位置。在多道程序環(huán)境下，編譯程序不可能預(yù)知所編譯的目標(biāo)模塊應(yīng)放在內(nèi)存的何處，因此，絕對裝入方式只適用于單道程序環(huán)境。在多道程序環(huán)境下，所得到的目標(biāo)模塊的起始地址通常是從0開始的，程序中的其它地址也都是相對于起始地址計算的。此時應(yīng)采用可重定位裝入方式，根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到內(nèi)存的適當(dāng)位置。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院

13、圖4-3作業(yè)裝入內(nèi)存時的情況LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作業(yè)地址空間內(nèi)存空間計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院例如，在用戶程序的1000號單元處有一條指令LOAD 1，2500，該指令的功能是將2500單元中的整數(shù)365取至寄存器1。但若將該用戶程序裝入到內(nèi)存的1000015000號單元而不進行地址變換，則在執(zhí)行11000號單元中的指令時，它將仍從2500號單元中把數(shù)據(jù)取至寄存器1而導(dǎo)致數(shù)據(jù)錯誤。由圖4-3可見，正確的方法

14、應(yīng)該是將取數(shù)指令中的地址2500修改成12500，即把指令中的相對地址2500與本程序在內(nèi)存中的起始地址10000相加，才得到正確的物理地址12500。除了數(shù)據(jù)地址應(yīng)修改外，指令地址也須做同樣的修改，即將指令的相對地址1000與起始地址10000相加，得到絕對地址11000。通常是把在裝入時對目標(biāo)程序中指令和數(shù)據(jù)的修改過程稱為重定位。又因為地址變換通常是在裝入時一次完成的，以后不再改變，故稱為靜態(tài)重定位。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院靜態(tài)地址重定位靜態(tài)地址重定位 靜態(tài)地址重定位是在程序執(zhí)行之前由操作系靜態(tài)地址

15、重定位是在程序執(zhí)行之前由操作系統(tǒng)的重定位裝入程序完成的。統(tǒng)的重定位裝入程序完成的。在裝入一個作業(yè)時，在裝入一個作業(yè)時，把作業(yè)中的指令地址全部轉(zhuǎn)換為絕對地址把作業(yè)中的指令地址全部轉(zhuǎn)換為絕對地址（地址（地址轉(zhuǎn)換工作是在作業(yè)執(zhí)行前集中一次完成的）在作轉(zhuǎn)換工作是在作業(yè)執(zhí)行前集中一次完成的）在作業(yè)執(zhí)行過程中就無須再進行地址轉(zhuǎn)換工作。業(yè)執(zhí)行過程中就無須再進行地址轉(zhuǎn)換工作。計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院Load ah,781078 3651000Load ah,10781001相對地址裝入裝入模塊內(nèi)存絕對地址1078365靜

16、態(tài)地址重定位的優(yōu)點是容易實現(xiàn)，無需硬件支持，它只要求程序本身是可重定位的，即對那些要修改的地址部分具有某種標(biāo)識，地址重定位由專門設(shè)計的程序來完成。在早期的操作系統(tǒng)中大多數(shù)都采用這種方法。其主要缺點是程序經(jīng)地址重定位后就不能移動了，因而不能重新分配內(nèi)存，不利于內(nèi)存的有效利用。計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院3 3動態(tài)運行時裝入方式動態(tài)運行時裝入方式(Dynamic Run-time Loading)(Dynamic Run-time Loading)可重定位裝入方式可將裝入模塊裝入到內(nèi)存中任何允許的位置，故可用于多

17、道程序環(huán)境；但這種方式并不允許程序運行時在內(nèi)存中移動位置。因為，程序在內(nèi)存中的移動，意味著它的物理位置發(fā)生了變化，這時必須對程序和數(shù)據(jù)的地址(是絕對地址)進行修改后方能運行。然而，實際情況是，在運行過程中它在內(nèi)存中的位置可能經(jīng)常要改變，此時就應(yīng)采用動態(tài)運行時裝入的方式。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院動態(tài)地址重定位動態(tài)地址重定位 動態(tài)地址重定位是在動態(tài)地址重定位是在程序執(zhí)行期間進行程序執(zhí)行期間進行的的。在在CPUCPU訪問內(nèi)存之前訪問內(nèi)存之前, ,將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地

18、址。成內(nèi)存地址。 通過基地址寄存器、變址寄存器計算出指令的有通過基地址寄存器、變址寄存器計算出指令的有效地址，再利用硬件機構(gòu)實現(xiàn)地址映射，這樣的硬效地址，再利用硬件機構(gòu)實現(xiàn)地址映射，這樣的硬件設(shè)備稱為件設(shè)備稱為存儲管理單元存儲管理單元MMU(Memory-Management MMU(Memory-Management Unit)Unit)。 通常采用的辦法是通常采用的辦法是利用一個重定位寄存器，對利用一個重定位寄存器，對每一個有效地址都要加上重定位寄存器中的內(nèi)容，每一個有效地址都要加上重定位寄存器中的內(nèi)容，以形成絕對地址。以形成絕對地址。計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲

19、器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院130 動態(tài)地址重定位的動態(tài)地址重定位的優(yōu)點是程序在內(nèi)存中的搬移不會對程序的正確執(zhí)優(yōu)點是程序在內(nèi)存中的搬移不會對程序的正確執(zhí)行造成影響，使內(nèi)存得以被充分利用，行造成影響，使內(nèi)存得以被充分利用，其缺點是需要附加的硬件支持，其缺點是需要附加的硬件支持，實現(xiàn)存儲管理的軟件算法比較復(fù)雜。實現(xiàn)存儲管理的軟件算法比較復(fù)雜。計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.2.24.2.2程序的鏈接程序的鏈接根據(jù)鏈接時間的不同，可把鏈接分成如下三種：(1) 靜態(tài)鏈接靜態(tài)鏈接。在程序

20、運行之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)，鏈接成一個完整的裝配模塊，以后不再拆開。我們把這種事先進行鏈接的方式稱為靜態(tài)鏈接方式。(2) 裝入時動態(tài)鏈接裝入時動態(tài)鏈接。這是指將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時，采用邊裝入邊鏈接的鏈接方式。(3) 運行時動態(tài)鏈接運行時動態(tài)鏈接。這是指對某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該(目標(biāo))模塊時，才對它進行的鏈接。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院1 1靜態(tài)鏈接方式靜態(tài)鏈接方式(Static Linking)(Static Linking)(1) 對相對

21、地址進行修改。在由編譯程序所產(chǎn)生的所有目標(biāo)模塊中，使用的都是相對地址，其起始地址都為0，每個模塊中的地址都是相對于起始地址計算的。在鏈接成一個裝入模塊后，原模塊B和C在裝入模塊的起始地址不再是0，而分別是L和L+M，所以此時須修改模塊B和C中的相對地址，即把原B中的所有相對地址都加上L，把原C中的所有相對地址都加上L+M。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院(2) 變換外部調(diào)用符號。將每個模塊中所用的外部調(diào)用符號也都變換為相對地址，如把B的起始地址變換為L，把C的起始地址變換為L+M，如圖4-4(b)所示。這種先進

22、行鏈接所形成的一個完整的裝入模塊，又稱為可執(zhí)行文件。通常都不再拆開它，要運行時可直接將它裝入內(nèi)存。這種事先進行鏈接，以后不再拆開的鏈接方式，稱為靜態(tài)鏈接方式。靜態(tài)鏈接方式。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院圖 4-4程序鏈接示意圖 模塊 ACALL B；Return；0L-1模塊 BCALL C；Return；0M-1模塊 CReturn；0N-10模塊 AJSR“L”Return；L-1模塊 BJSR“LM”Return；LL+M-1L+ML+M+N-1模塊 CReturn；(a) 目標(biāo)模塊(b) 裝入模塊計計

23、算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院2 2裝入時動態(tài)鏈接裝入時動態(tài)鏈接(Load-time Dynamic Linking)(Load-time Dynamic Linking)用戶源程序經(jīng)編譯后所得的目標(biāo)模塊，是在裝入內(nèi)存時裝入內(nèi)存時邊裝入邊鏈接邊裝入邊鏈接的，即在裝入一個目標(biāo)模塊時，若發(fā)生一個外外部模塊調(diào)用事件部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存，還要按照圖按照圖4-44-4所示的方式來修改目所示的方式來修改目標(biāo)模塊中的相對地址標(biāo)模塊中的相對地址。裝入時動態(tài)鏈接方式有以下優(yōu)點：(1)

24、 便于修改和更新。對于經(jīng)靜態(tài)鏈接裝配在一起的裝入模塊，如果要修改或更新其中的某個目標(biāo)模塊，則要求重新打開裝入模塊。這不僅是低效的，而且有時是不可能的。若采用動態(tài)鏈接方式，由于各目標(biāo)模塊是分開存放的，所以要修改或更新各目標(biāo)模塊是件非常容易的事。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院(2) 便于實現(xiàn)對目標(biāo)模塊的共享。在采用靜態(tài)鏈接方式時，每個應(yīng)用模塊都必須含有其目標(biāo)模塊的拷貝，無法實現(xiàn)對目標(biāo)模塊的共享。但采用裝入時動態(tài)鏈接方式，OS則很容易將一個目標(biāo)模塊鏈接到幾個應(yīng)用模塊上，實現(xiàn)多個應(yīng)用程序?qū)υ撃K的共享。 計計算機操作

25、系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院3 3運行時動態(tài)鏈接運行時動態(tài)鏈接(Run-time Dynamic Linking)(Run-time Dynamic Linking)在許多情況下，應(yīng)用程序在運行時，每次要運行的模塊可能是不相同的。但由于事先無法知道本次要運行哪些模塊，故只能是將所有可能要運行到的模塊都全部裝入內(nèi)存，并在裝入時全部鏈接在一起。顯然這是低效的，因為往往會有些目標(biāo)模塊根本就不運行。比較典型的例子是作為錯誤處理用的目標(biāo)模塊，如果程序在整個運行過程中都不出現(xiàn)錯誤，則顯然就不會用到該模塊。 計計算機操作系算機操作系統(tǒng)

26、電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院近幾年流行起來的運行時動態(tài)鏈接方式，是對上述在裝入時鏈接方式的一種改進。這種鏈接方式是將對某些模塊的鏈接推遲到程序執(zhí)行時才進行鏈接，亦即，在執(zhí)行過在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。 計計算機操作系算機操作系

27、統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院存儲管理方式一覽表存儲管理方式一覽表實存實存虛存虛存虛擬頁式虛擬頁式虛擬段式虛擬段式虛擬段頁式虛擬段頁式單連續(xù)區(qū)單連續(xù)區(qū)固定分區(qū)固定分區(qū)可變分區(qū)可變分區(qū)存儲方式存儲方式連續(xù)存儲方式（實存）連續(xù)存儲方式（實存）離散離散分頁分頁分段分段段頁式段頁式計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.3連續(xù)分配方式連續(xù)分配方式 4.3.14.3.1單一連續(xù)分配單一連續(xù)分配這是最簡單的一種存儲管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。采用這種

28、存儲管理方式時，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院雖然在早期的單用戶、單任務(wù)操作系統(tǒng)中，有不少都配置了存儲器保護機構(gòu)，用于防止用戶程序?qū)Σ僮飨到y(tǒng)的破壞，但近年來常見的幾種單用戶操作系統(tǒng)中，如CP/M、MS-DOS及RT11等，都未采取存儲器保護措施。這是因為，一方面可以節(jié)省硬件，另一方面也因為這是可行的。在單用戶環(huán)境下，機器由一用戶獨占，不可能存在其他用戶干擾的問題；這時可能出現(xiàn)

29、的破壞行為也只是用戶程序自己去破壞操作系統(tǒng)，其后果并不嚴(yán)重，只是會影響該用戶程序的運行，且操作系統(tǒng)也很容易通過系統(tǒng)的再啟動而重新裝入內(nèi)存。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院單一連續(xù)分配方案的優(yōu)缺點單一連續(xù)分配方案的優(yōu)缺點優(yōu)點：方法簡單，易于實現(xiàn)；優(yōu)點：方法簡單，易于實現(xiàn)；缺點：它僅適用于單道程序，因而不能使處理機和缺點：它僅適用于單道程序，因而不能使處理機和內(nèi)存得到充分利用。內(nèi)存得到充分利用。計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.3.

30、24.3.2固定分區(qū)分配固定分區(qū)分配1 1劃分分區(qū)的方法劃分分區(qū)的方法可用下述兩種方法將內(nèi)存的用戶空間劃分為若干個固定大小的分區(qū)：(1) 分區(qū)大小相等分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。其缺點是缺乏靈活性，即當(dāng)程序太小時，會造成內(nèi)存空間的浪費；當(dāng)程序太大時，一個分區(qū)又不足以裝入該程序，致使該程序無法運行。盡管如此，這種劃分方式仍被用于利用一臺計算機去控制多個相同對象的場合，因為這些對象所需的內(nèi)存空間是大小相等的。例如，爐溫群控系統(tǒng)，就是利用一臺計算機去控制多臺相同的冶煉爐。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院

31、(2) 分區(qū)大小不等分區(qū)大小不等。為了克服分區(qū)大小相等而缺乏靈活性的這個缺點，可把內(nèi)存區(qū)劃分成含有多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。這樣，便可根據(jù)程序的大小為之分配適當(dāng)?shù)姆謪^(qū)。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院2 2內(nèi)存分配內(nèi)存分配為了便于內(nèi)存分配，通常將分區(qū)按大小進行排隊，并為之建立一張分區(qū)使用表，其中各表項包括每個分區(qū)的起始地址、大小及狀態(tài)(是否已分配)，見圖4-5(a)所示。當(dāng)有一用戶程序要裝入時，由內(nèi)存分配程序檢索該表，從中找出一個能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，然后將該表項中

32、的狀態(tài)置為“已分配”；若未找到大小足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。存儲空間分配情況如圖4-5(b)所示。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院圖 4-5固定分區(qū)使用表 操作系統(tǒng)作業(yè)A作業(yè)B作業(yè)C24 KB32 KB64 KB128 KB256 KB分區(qū)號大小/KB起址/KB狀態(tài)11220已分配23232已分配36464已分配4128128未分配(b) 存儲空間分配情況(a) 分區(qū)說明表計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院計計算機操作

33、系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院內(nèi)存空間利用率低，內(nèi)存空間利用率低，如圖。如圖。5 5道進程大小道進程大小總和為總和為250 KB250 KB，但，但是所占是所占5 5個分區(qū)總?cè)輦€分區(qū)總?cè)萘繀s達到量卻達到1000 KB1000 KB，內(nèi)存空間利用率僅內(nèi)存空間利用率僅達到達到25%25%。分區(qū)1 100 KB分區(qū)2 150 KB分區(qū)3 250 KB分區(qū)4 250 KB分區(qū)5 250 KB程序4 100 KB程序5 50 KB程序1 20 KB程序2 30 KB程序3 50 KB解決辦法：解決辦法：采用動態(tài)分區(qū)存儲管理采用動態(tài)分

34、區(qū)存儲管理計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.3.34.3.3動態(tài)分區(qū)分配動態(tài)分區(qū)分配動態(tài)分區(qū)分配是根據(jù)進程的實際需要根據(jù)進程的實際需要，動態(tài)地為之分配內(nèi)存空間。它是在進程裝入和處理過程中建立分區(qū)，并要使分區(qū)的容量能正好適應(yīng)進程的大小。而整個內(nèi)存分區(qū)數(shù)目隨著進程數(shù)目的變化而動態(tài)改變，各個分區(qū)的大小隨著各個進程的大小各有不同，所以稱之為動態(tài)分區(qū)分配。動態(tài)分區(qū)又稱之為可變分區(qū)可變分區(qū)，或變長分區(qū)變長分區(qū)模式，主要克服固定分區(qū)管理的“內(nèi)碎片”問題。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲

35、器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院OSP1P3OSP1P3OSP4例子：一計算機系統(tǒng)有例子：一計算機系統(tǒng)有2560KB內(nèi)存，采用可變分區(qū)模式管內(nèi)存，采用可變分區(qū)模式管理，理，OS占低地址的占低地址的400KB空間，用戶內(nèi)存為空間，用戶內(nèi)存為2160KB。P1OSP1P2OSP1P2P3P2計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院 在實現(xiàn)可變分區(qū)分配時，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法分區(qū)分配算法和分區(qū)分區(qū)的分配與回收的分配與回收操作這樣三個問題。1分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)為

36、了實現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來描述空閑分區(qū)空閑分區(qū)和已分配分已分配分區(qū)區(qū)的情況，為分配提供依據(jù)。常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式：計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院(1)空閑分區(qū)表。在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個空閑分區(qū)的情況。每個空閑分區(qū)占一個表目，表目中包括分區(qū)序號、分區(qū)始址及分區(qū)的大小等數(shù)據(jù)項。(2) 空閑分區(qū)鏈。為了實現(xiàn)對空閑分區(qū)的分配和鏈接，在每個分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針；在分區(qū)尾部則設(shè)置一后向指針，通過前、后向鏈接指針，可

37、將所有的空閑分區(qū)鏈接成一個雙向鏈，如圖4-6所示。為了檢索方便，在分區(qū)尾部重復(fù)設(shè)置狀態(tài)位和分區(qū)大小表目。當(dāng)分區(qū)被分配出去以后，把狀態(tài)位由“0”改為“1”，此時，前、后向指針已無意義。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院 Freelist 圖 4.15 可變存儲中空閑區(qū)鏈表 28k 2k 45k 15k 80k 60k NULL 表 4-3 可變分區(qū)存儲中已分區(qū)表 表 4-4 可變分區(qū)存儲中空閑分區(qū)表 分區(qū)號 起始地址 長度 占用標(biāo)志位 1 20k 8k 1 2 30k 15k 1 3 60k 20k 1 4 0 5

38、 0 分區(qū)號 起始地址 長度 占用標(biāo)志位 1 28k 2k 1 2 45k 15k 1 3 80k 60k 1 4 0 5 0 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院前向指針0N 個字節(jié)可用后向指針0N+2N+2圖4-6空閑鏈結(jié)構(gòu) 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院2 2分區(qū)分配算法分區(qū)分配算法1) 首次適應(yīng)算法首次適應(yīng)算法(first fit)(first fit)我們以空閑分區(qū)鏈為例來說明采用FF算法時的分配情況。FF算法要求算法要求空

39、閑分區(qū)鏈以地址遞增的次序鏈接空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時，從鏈?zhǔn)组_始順序查找，直至找到一個大小能滿足要求的空閑分從鏈?zhǔn)组_始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)為止區(qū)為止；然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€能滿足要求的分區(qū)，則此次內(nèi)存分配失敗，返回。該算法傾向于優(yōu)先利用內(nèi)存中低址部分的空閑分區(qū)，從而保留了高址部分的大空閑區(qū)。這給為以后到達的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。其缺點是低址部分不斷被劃分，會留下許多難以利用的、很小的空閑分區(qū)，而每次查找又都是從低址部分開始，這無疑會增加查

40、找可用空閑分區(qū)時的開銷。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院2) 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法(next fit)(next fit)該算法是由首次適應(yīng)算法演變而成的。在為進程分配內(nèi)存空間時，不再是每次都從鏈?zhǔn)组_始查找，而是從上次不再是每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直至找到一個能滿足要求的空閑分區(qū)，從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)。為實現(xiàn)該算法，應(yīng)設(shè)置一起始查尋指針，用于指示下一次起始查尋的空閑分區(qū)，并采用循環(huán)查找方

41、式，即如果最后一個(鏈尾)空閑分區(qū)的大小仍不能滿足要求，則應(yīng)返回到第一個空閑分區(qū)，比較其大小是否滿足要求。找到后，應(yīng)調(diào)整起始查尋指針。該算法能使內(nèi)存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)時的開銷，但這樣會缺乏大的空閑分區(qū)。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院3) 最佳適應(yīng)算法最佳適應(yīng)算法(best fit)(best fit)所謂“最佳”是指每次為作業(yè)分配內(nèi)存時，總是把能滿把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為了加速尋找，該算法要求將所有的空閑

42、分區(qū)按其容要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈量以從小到大的順序形成一空閑分區(qū)鏈。這樣，第一次找到的能滿足要求的空閑區(qū)，必然是最佳的。孤立地看，最佳適應(yīng)算法似乎是最佳的，然而在宏觀上卻不一定。因為每次分配后所切割下來的剩余部分總是最小的，這樣，在存儲器中會留下許多難以利用的小空閑區(qū)。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4) 最壞適應(yīng)算法最壞適應(yīng)算法(worst fit)(worst fit)最壞適應(yīng)分配算法要掃描整個空閑分區(qū)表或鏈表，總是挑選一個最大的空閑區(qū)分割給作業(yè)使用挑選一個最大的空閑區(qū)

43、分割給作業(yè)使用，其優(yōu)點是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對中、小作業(yè)有利，同時最壞適應(yīng)分配算法查找效率很高。該算法要求將要求將所有的空閑分區(qū)按其容量以從大到小的順序形成一空閑分區(qū)所有的空閑分區(qū)按其容量以從大到小的順序形成一空閑分區(qū)鏈，鏈，查找時只要看第一個分區(qū)能否滿足作業(yè)要求。但是該算法的缺點也是明顯的，它會使存儲器中缺乏大的空閑分區(qū)。最壞適應(yīng)算法與前面所述的首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法一起，也稱為順序搜索法。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院5) 快速適應(yīng)算法快速適應(yīng)算法(qui

44、ck fit)(quick fit)該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量將空閑分區(qū)根據(jù)其容量大小進行分類大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表，這樣，系統(tǒng)中存在多個空閑分區(qū)鏈表，同時在內(nèi)存中設(shè)立一張管理索引表，該表的每一個表項對應(yīng)了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針?？臻e分區(qū)的分類是根據(jù)進程常用的空間大小進行劃分，如2 KB、4 KB、8 KB等，對于其它大小的分區(qū)，如7 KB這樣的空閑區(qū)，既可以放在8 KB的鏈表中，也可以放在一個特殊的空閑區(qū)鏈表中。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管

45、理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院該算法的優(yōu)點優(yōu)點是查找效率高，僅需要根據(jù)進程的長度，尋找到能容納它的最小空閑區(qū)鏈表，并取下第一塊進行分配即可。另外該算法在進行空閑分區(qū)分配時，不會對任何分區(qū)產(chǎn)生分割，所以能保留大的分區(qū)，滿足對大空間的需求，也不會產(chǎn)生內(nèi)存碎片。該算法的缺點缺點是在分區(qū)歸還主存時算法復(fù)雜，系統(tǒng)開銷較大。此外，該算法在分配空閑分區(qū)時是以進程為單位，一個分區(qū)只屬于一個進程，因此在為進程所分配的一個分區(qū)中，或多或少地存在一定的浪費?？臻e分區(qū)劃分越細(xì)，浪費則越嚴(yán)重，整體上會造成可觀的存儲空間浪費，這是典型的以空間換時間的作法。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲

46、器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院3 3分區(qū)分配操作分區(qū)分配操作1) 分配內(nèi)存分配內(nèi)存系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)。設(shè)請求的分區(qū)大小為u.size，表中每個空閑分區(qū)的大小可表示為m.size。若m.size-u.sizesize(size是事先規(guī)定的不再切割的剩余分區(qū)的大小)，說明多余部分太小，可不再切割，將整個分區(qū)分配給請求者；否則(即多余部分超過size)，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)鏈(表)中。然后，將分配區(qū)的首址返回給調(diào)用者。圖4-7示出了分配流程。 計計算機操作系算機操作系統(tǒng)電統(tǒng)

47、電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院圖 4-7內(nèi)存分配流程 從頭開始查表檢索完否？m.sizeu.size?m.size-u.sizesize?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個表項將該分區(qū)從鏈中移出YNNYYN計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院2) 回收內(nèi)存回收內(nèi)存當(dāng)進程運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈(表)中找到相應(yīng)的插入點，此時可能出現(xiàn)以下四種情況之一：(1) 回收區(qū)與插入點的前一個

48、空閑分區(qū)F1相鄰接，見圖4-8(a)。此時應(yīng)將回收區(qū)與插入點的前一分區(qū)合并，不必為回收分區(qū)分配新表項，而只需修改其前一分區(qū)F1的大小。(2) 回收分區(qū)與插入點的后一空閑分區(qū)F2相鄰接，見圖4-8(b)。此時也可將兩分區(qū)合并，形成新的空閑分區(qū)，但用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院(3) 回收區(qū)同時與插入點的前、后兩個分區(qū)鄰接，見圖4-8(c)。此時將三個分區(qū)合并，使用F1的表項和F1的首址，取消F2的表項，大小為三者之和。(4) 回收區(qū)既不與F1鄰接，又不與F2鄰接

49、。這時應(yīng)為回收區(qū)單獨建立一新表項，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院圖 4-8內(nèi)存回收時的情況 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院M1回收區(qū)M2回收M1空白區(qū)M2(a)M1回收區(qū)M2回收M1M2(b)M1回收區(qū)M2回收M1M2(c)M1回收區(qū)M2回收M1(d)內(nèi)存回收時的情況 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科

50、學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.3.44.3.4伙伴系統(tǒng)伙伴系統(tǒng)固定分區(qū)和動態(tài)分區(qū)方式都有不足之處。固定分區(qū)方式限制了活動進程的數(shù)目，當(dāng)進程大小與空閑分區(qū)大小不匹配時，內(nèi)存空間利用率很低。動態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)時需要進行分區(qū)合并等，系統(tǒng)開銷較大?；锇橄到y(tǒng)方式是對以上兩種內(nèi)存方式的一種折衷方案?；锇橄到y(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪，k為整數(shù)，lkm，其中：21表示分配的最小分區(qū)的大小，2m表示分配的最大分區(qū)的大小，通常2m是整個可分配內(nèi)存的大小。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院假設(shè)系統(tǒng)的可

51、利用空間容量為2m個字，則系統(tǒng)開始運行時，整個內(nèi)存區(qū)是一個大小為2m的空閑分區(qū)。在系統(tǒng)運行過程中，由于不斷的劃分，可能會形成若干個不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)根據(jù)分區(qū)的大小進行分類，對于每一類具有相同大小的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)雙向鏈表。這樣，不同大小的空閑分區(qū)形成了k(0km)個空閑分區(qū)鏈表。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院當(dāng)需要為進程分配一個長度為n的存儲空間時，首先計算一個i值，使2i1TL，表示段號太大，是訪問越界，于是產(chǎn)生越界中斷信號；若未越界，則根據(jù)段表的始址和該段的段號，計算出該段

52、對應(yīng)段表項的位置，從中讀出該段在內(nèi)存的起始地址，然后，再檢查段內(nèi)地址d是否超過該段的段長SL。若超過，即dSL，同樣發(fā)出越界中斷信號；若未越界，則將該段的基址d與段內(nèi)地址相加，即可得到要訪問的內(nèi)存物理地址。圖4-18示出了分段系統(tǒng)的地址變換過程。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院圖4-18分段系統(tǒng)的地址變換過程 控制寄存器段表始址段表長度2100段號S越界1 K段長600段號01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址計計算機操作系算機操作系統(tǒng)電統(tǒng)電子

53、教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院像分頁系統(tǒng)一樣，當(dāng)段表放在內(nèi)存中時，每要訪問一個數(shù)據(jù)，都須訪問兩次內(nèi)存訪問兩次內(nèi)存，從而極大地降低了計算機的速率。解決的方法也和分頁系統(tǒng)類似，再增設(shè)一個聯(lián)想存儲器，用于保存最近常用的段表項。由于一般情況是段比頁大，因而段表項的數(shù)目比頁表項的數(shù)目少，其所需的聯(lián)想存儲器也相對較小，便可以顯著地減少存取數(shù)據(jù)的時間，比起沒有地址變換的常規(guī)存儲器的存取速度來僅慢約10%15%。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院 段表始址 段表長度 段號 段內(nèi)地

54、址 寄存器 寄存器 邏輯地址 no 快 表 yes 越界 越界中斷 地址越界 yes 段表 段號 no S 物理地址 圖 4.25 段式存儲管理地址映射 S D B L + SL? 段首址 段長度 Sb Sl 段 段 段 號 首址 長度 S Sb Sl DSl Sb+D 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院段表始址段表長度段表寄存器段號3段內(nèi)地址723越界中斷邏輯地址段號段長2000段基址16 K400154 K15025 K90038 K8 K7233658 K8915物理地址內(nèi)存中的段表內(nèi)存3號段計計算機操作系算

55、機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4 4分頁和分段的主要區(qū)別分頁和分段的主要區(qū)別由上所述不難看出，分頁和分段系統(tǒng)有許多相似之處。比如，兩者都采用離散分配方式，且都要通過地址映射機構(gòu)來實現(xiàn)地址變換。但在概念上兩者完全不同，主要表現(xiàn)在下述三個方面。(1) 頁是信息的物理單位頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率?；蛘哒f，分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電

56、子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院(2) 頁的大小固定且由系統(tǒng)決定頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機器硬件實現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面；而段的長度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進行編譯時，根據(jù)信息的性質(zhì)來劃分。(3) 分頁的作業(yè)地址空間是一維的分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個記憶符，即可表示一個地址；而分段的作業(yè)地址空間則是二維的，程序員在標(biāo)識一個地址時，既需給出段名，又需給出段內(nèi)地址。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教

57、案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院4.5.34.5.3信息共享信息共享分段系統(tǒng)的一個突出優(yōu)點，是易于實現(xiàn)段的共享，即允許若干個進程共享一個或多個分段，且對段的保護也十分簡單易行。在分頁系統(tǒng)中，雖然也能實現(xiàn)程序和數(shù)據(jù)的共享，但遠(yuǎn)不如分段系統(tǒng)來得方便。我們通過一個例子來說明這個問題。例如，有一個多用戶系統(tǒng)，可同時接納40個用戶，他們都執(zhí)行一個文本編輯程序(Text Editor)。如果文本編輯程序有160 KB的代碼和另外40 KB的數(shù)據(jù)區(qū)，則總共需有 8 MB的內(nèi)存空間來支持40個用戶。如果160 KB的代碼是可重入的(Reentrant)，則無論是在分頁系

58、統(tǒng)還是在分段系統(tǒng)中，該代碼都能被共享，在內(nèi)存中只需保留一份文本編輯程序的副本，此時所需的內(nèi)存空間僅為1760 KB(4040+160)，而不是8000 KB。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院假定每個頁面的大小為4 KB，那么，160 KB的代碼將占用40個頁面，數(shù)據(jù)區(qū)占10個頁面。為實現(xiàn)代碼的共享，應(yīng)在每個進程的頁表中都建立40個頁表項，它們的物理塊號都是21#60#。在每個進程的頁表中，還須為自己的數(shù)據(jù)區(qū)建立頁表項，它們的物理塊號分別是61#70#、71#80#、81#90#，等等。圖4-19是分頁系統(tǒng)中共享

59、editor的示意圖。 計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院圖4-19分頁系統(tǒng)中共享editor的示意圖 ed 1ed 2ed 40data 1data 10進程12122606170頁表ed 1ed 2ed 40data 1data 10進程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180頁表計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院在分段系統(tǒng)中，實現(xiàn)共享則容

60、易得多，只需在每個進程的段表中為文本編輯程序設(shè)置一個段表項。圖4-20是分段系統(tǒng)中共享editor的示意圖。 圖 4-20分段系統(tǒng)中共享editor的示意圖 editor進程1data 1進程2editordata 2段表段長基址16080402401608040380editordata 1data 280240280380420計計算機操作系算機操作系統(tǒng)電統(tǒng)電子教案子教案第四章存儲器管理第四章存儲器管理 計計算機科學(xué)技算機科學(xué)技術(shù)術(shù)學(xué)院學(xué)院可重入代碼可重入代碼(Reentrant Code)又稱為又稱為“純代碼純代碼”(Pure Code)，是一種允許多個進程同時訪問的代碼。，是一種允許多