1、1 1第四章 存 儲(chǔ) 器 管 理第四章第四章 存存 儲(chǔ)儲(chǔ) 器器 管管 理理4.1 存儲(chǔ)器的層次結(jié)構(gòu)4.2 程序的裝入和鏈接4.3 連續(xù)分配存儲(chǔ)管理方式4.4 對(duì)換(Swapping)4.5 分頁存儲(chǔ)管理方式4.6 分段存儲(chǔ)管理方式習(xí)題2 2第四章 存 儲(chǔ) 器 管 理4.1 存儲(chǔ)器的層次結(jié)構(gòu)在計(jì)算機(jī)執(zhí)行時(shí)，幾乎每一條指令都涉及對(duì)存儲(chǔ)器的訪問，因此要求對(duì)存儲(chǔ)器的訪問速度能跟得上處理機(jī)的運(yùn)行速度。或者說，存儲(chǔ)器的速度必須非常快，能與處理機(jī)的速度相匹配，否則會(huì)明顯地影響到處理機(jī)的運(yùn)行。此外還要求存儲(chǔ)器具有非常大的容量，而且存儲(chǔ)器的價(jià)格還應(yīng)很便宜。 3 3第四章 存 儲(chǔ) 器 管 理4.1.1 多層結(jié)構(gòu)的

2、存儲(chǔ)器系統(tǒng)1. 存儲(chǔ)器的多層結(jié)構(gòu) 對(duì)于通用計(jì)算機(jī)而言，存儲(chǔ)層次至少應(yīng)具有三級(jí)：最高層為CPU寄存器，中間為主存，最底層是輔存。在較高檔的計(jì)算機(jī)中，還可以根據(jù)具體的功能細(xì)分為寄存器、高速緩存、主存儲(chǔ)器、磁盤緩存、固定磁盤、可移動(dòng)存儲(chǔ)介質(zhì)等6層。如圖4-1所示。 4 4第四章 存 儲(chǔ) 器 管 理圖4-1 計(jì)算機(jī)系統(tǒng)存儲(chǔ)層次示意5 5第四章 存 儲(chǔ) 器 管 理2. 可執(zhí)行存儲(chǔ)器在計(jì)算機(jī)系統(tǒng)的存儲(chǔ)層次中，寄存器和主存儲(chǔ)器又被稱為可執(zhí)行存儲(chǔ)器。對(duì)于存放于其中的信息，與存放于輔存中的信息相比較而言，計(jì)算機(jī)所采用的訪問機(jī)制是不同的，所需耗費(fèi)的時(shí)間也是不同的。進(jìn)程可以在很少的時(shí)鐘周期內(nèi)使用一條load或sto

3、re指令對(duì)可執(zhí)行存儲(chǔ)器進(jìn)行訪問。但對(duì)輔存的訪問則需要通過I/O設(shè)備實(shí)現(xiàn)，因此，在訪問中將涉及到中斷、設(shè)備驅(qū)動(dòng)程序以及物理設(shè)備的運(yùn)行，所需耗費(fèi)的時(shí)間遠(yuǎn)遠(yuǎn)高于訪問可執(zhí)行存儲(chǔ)器的時(shí)間，一般相差3個(gè)數(shù)量級(jí)甚至更多。6 6第四章 存 儲(chǔ) 器 管 理4.1.2 主存儲(chǔ)器與寄存器1. 主存儲(chǔ)器主存儲(chǔ)器簡(jiǎn)稱內(nèi)存或主存，是計(jì)算機(jī)系統(tǒng)中的主要部件，用于保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)，也稱可執(zhí)行存儲(chǔ)器。 7 7第四章 存 儲(chǔ) 器 管 理2. 寄存器寄存器具有與處理機(jī)相同的速度，故對(duì)寄存器的訪問速度最快，完全能與CPU協(xié)調(diào)工作，但價(jià)格卻十分昂貴，因此容量不可能做得很大。 8 8第四章 存 儲(chǔ) 器 管 理4.1.3 高速緩

4、存和磁盤緩存1. 高速緩存高速緩存是現(xiàn)代計(jì)算機(jī)結(jié)構(gòu)中的一個(gè)重要部件，它是介于寄存器和存儲(chǔ)器之間的存儲(chǔ)器，主要用于備份主存中較常用的數(shù)據(jù)，以減少處理機(jī)對(duì)主存儲(chǔ)器的訪問次數(shù)，這樣可大幅度地提高程序執(zhí)行速度。高速緩存容量遠(yuǎn)大于寄存器，而比內(nèi)存約小兩到三個(gè)數(shù)量級(jí)左右，從幾十KB到幾MB，訪問速度快于主存儲(chǔ)器。 9 9第四章 存 儲(chǔ) 器 管 理2. 磁盤緩存由于目前磁盤的I/O速度遠(yuǎn)低于對(duì)主存的訪問速度，為了緩和兩者之間在速度上的不匹配，而設(shè)置了磁盤緩存，主要用于暫時(shí)存放頻繁使用的一部分磁盤數(shù)據(jù)和信息，以減少訪問磁盤的次數(shù)。但磁盤緩存與高速緩存不同，它本身并不是一種實(shí)際存在的存儲(chǔ)器，而是利用主存中的部分

5、存儲(chǔ)空間暫時(shí)存放從磁盤中讀出(或?qū)懭?的信息。主存也可以看作是輔存的高速緩存，因?yàn)椋o存中的數(shù)據(jù)必須復(fù)制到主存方能使用，反之，數(shù)據(jù)也必須先存在主存中，才能輸出到輔存。10 10第四章 存 儲(chǔ) 器 管 理4.2 程序的裝入和鏈接用戶程序要在系統(tǒng)中運(yùn)行，必須先將它裝入內(nèi)存，然后再將其轉(zhuǎn)變?yōu)橐粋€(gè)可以執(zhí)行的程序，通常都要經(jīng)過以下幾個(gè)步驟：(1) 編譯，由編譯程序(Compiler)對(duì)用戶源程序進(jìn)行編譯，形成若干個(gè)目標(biāo)模塊(Object Module)；(2) 鏈接，由鏈接程序(Linker)將編譯后形成的一組目標(biāo)模塊以及它們所需要的庫函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊(Load Module)；(

6、3) 裝入，由裝入程序(Loader)將裝入模塊裝入內(nèi)存。圖4-2示出了這樣的三步過程。本節(jié)將扼要闡述程序(含數(shù)據(jù))的鏈接和裝入過程。11 11第四章 存 儲(chǔ) 器 管 理圖4-2對(duì)用戶程序的處理步驟12 12第四章 存 儲(chǔ) 器 管 理4.2.1 程序的裝入為了闡述上的方便，我們先介紹一個(gè)無需進(jìn)行鏈接的單個(gè)目標(biāo)模塊的裝入過程。該目標(biāo)模塊也就是裝入模塊。在將一個(gè)裝入模塊裝入內(nèi)存時(shí)，可以有如下三種裝入方式：1. 絕對(duì)裝入方式(Absolute Loading Mode)當(dāng)計(jì)算機(jī)系統(tǒng)很小，且僅能運(yùn)行單道程序時(shí)，完全有可能知道程序?qū)Ⅰv留在內(nèi)存的什么位置。此時(shí)可以采用絕對(duì)裝入方式。用戶程序經(jīng)編譯后，將產(chǎn)生

7、絕對(duì)地址(即物理地址)的目標(biāo)代碼。 13 13第四章 存 儲(chǔ) 器 管 理2. 可重定位裝入方式(Relocation Loading Mode)絕對(duì)裝入方式只能將目標(biāo)模塊裝入到內(nèi)存中事先指定的位置，這只適用于單道程序環(huán)境。而在多道程序環(huán)境下，編譯程序不可能預(yù)知經(jīng)編譯后所得到的目標(biāo)模塊應(yīng)放在內(nèi)存的何處。因此，對(duì)于用戶程序編譯所形成的若干個(gè)目標(biāo)模塊，它們的起始地址通常都是從0開始的，程序中的其它地址也都是相對(duì)于起始地址計(jì)算的。 14 14第四章 存 儲(chǔ) 器 管 理圖4-3作業(yè)裝入內(nèi)存時(shí)的情況15 15第四章 存 儲(chǔ) 器 管 理3. 動(dòng)態(tài)運(yùn)行時(shí)的裝入方式(Dynamic Run-time Loadi

8、ng)可重定位裝入方式可將裝入模塊裝入到內(nèi)存中任何允許的位置，故可用于多道程序環(huán)境。但該方式并不允許程序運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置。 16 16第四章 存 儲(chǔ) 器 管 理4.2.2 程序的鏈接1. 靜態(tài)鏈接(Static Linking)方式在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)鏈接成一個(gè)完整的裝配模塊，以后不再拆開。在圖4-4(a)中示出了經(jīng)過編譯后所得到的三個(gè)目標(biāo)模塊A、B、C，它們的長(zhǎng)度分別為L(zhǎng)、M和N。在模塊A中有一條語句CALL B，用于調(diào)用模塊B。在模塊B中有一條語句CALL C，用于調(diào)用模塊C。B和C都屬于外部調(diào)用符號(hào)，在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)

9、問題： (1) 對(duì)相對(duì)地址進(jìn)行修改。(2) 變換外部調(diào)用符號(hào)。 17 17第四章 存 儲(chǔ) 器 管 理圖4-4程序鏈接示意圖18 18第四章 存 儲(chǔ) 器 管 理2. 裝入時(shí)動(dòng)態(tài)鏈接(Load-time Dynamic Linking)這是指將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的鏈接方式。即在裝入一個(gè)目標(biāo)模塊時(shí)，若發(fā)生一個(gè)外部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存，還要按照?qǐng)D4-4所示的方式修改目標(biāo)模塊中的相對(duì)地址。裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)：(1) 便于修改和更新。(2) 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。 19 19第四章 存 儲(chǔ) 器

10、管 理3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-time Dynamic Linking)在許多情況下，應(yīng)用程序在運(yùn)行時(shí)，每次要運(yùn)行的模塊可能是不相同的。但由于事先無法知道本次要運(yùn)行哪些模塊，故只能是將所有可能要運(yùn)行到的模塊全部都裝入內(nèi)存，并在裝入時(shí)全部鏈接在一起。顯然這是低效的，因?yàn)橥鶗?huì)有部分目標(biāo)模塊根本就不運(yùn)行。比較典型的例子是作為錯(cuò)誤處理用的目標(biāo)模塊，如果程序在整個(gè)運(yùn)行過程中都不出現(xiàn)錯(cuò)誤，則顯然就不會(huì)用到該模塊。2020第四章 存 儲(chǔ) 器 管 理4.3 連續(xù)分配存儲(chǔ)管理方式4.3.1 單一連續(xù)分配在單道程序環(huán)境下，當(dāng)時(shí)的存儲(chǔ)器管理方式是把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，它通常

11、是放在內(nèi)存的低址部分。而在用戶區(qū)內(nèi)存中，僅裝有一道用戶程序，即整個(gè)內(nèi)存的用戶空間由該程序獨(dú)占。這樣的存儲(chǔ)器分配方式被稱為單一連續(xù)分配方式。21 21第四章 存 儲(chǔ) 器 管 理4.3.2 固定分區(qū)分配1. 劃分分區(qū)的方法可用下述兩種方法將內(nèi)存的用戶空間劃分為若干個(gè)固定大小的分區(qū)： (1) 分區(qū)大小相等(指所有的內(nèi)存分區(qū)大小相等)。(2) 分區(qū)大小不等。2222第四章 存 儲(chǔ) 器 管 理2. 內(nèi)存分配為了便于內(nèi)存分配，通常將分區(qū)按其大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，其中各表項(xiàng)包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)(是否已分配)，如圖4-5所示。 2323第四章 存 儲(chǔ) 器 管 理圖4-5 固定分

12、區(qū)使用表2424第四章 存 儲(chǔ) 器 管 理4.3.3 動(dòng)態(tài)分區(qū)分配1. 動(dòng)態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 常用的數(shù)據(jù)結(jié)構(gòu)有以下兩種形式： 空閑分區(qū)表，在系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個(gè)空閑分區(qū)的情況。每個(gè)空閑分區(qū)占一個(gè)表目，表目中包括分區(qū)號(hào)、分區(qū)大小和分區(qū)始址等數(shù)據(jù)項(xiàng)，如圖4-6所示。 空閑分區(qū)鏈。為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，在每個(gè)分區(qū)的起始部分設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)所用的前向指針，在分區(qū)尾部則設(shè)置一后向指針。通過前、后向鏈接指針，可將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈，如圖4-7所示。 2525第四章 存 儲(chǔ) 器 管 理 圖4-6 空閑分區(qū)表 2626第四章 存 儲(chǔ)

13、 器 管 理 圖4-7 空閑鏈結(jié)構(gòu) 2727第四章 存 儲(chǔ) 器 管 理2. 動(dòng)態(tài)分區(qū)分配算法為把一個(gè)新作業(yè)裝入內(nèi)存，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。由于內(nèi)存分配算法對(duì)系統(tǒng)性能有很大的影響，故人們對(duì)它進(jìn)行了較為廣泛而深入的研究，于是產(chǎn)生了許多動(dòng)態(tài)分區(qū)分配算法。 2828第四章 存 儲(chǔ) 器 管 理3. 分區(qū)分配操作1) 分配內(nèi)存系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈(表)中找到所需大小的分區(qū)。設(shè)請(qǐng)求的分區(qū)大小為u.size，表中每個(gè)空閑分區(qū)的大小可表示為m.size。 2929第四章 存 儲(chǔ) 器 管 理圖4-8內(nèi)存分配流程3030第四章 存 儲(chǔ) 器 管 理2)

14、 回收內(nèi)存 當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈(表)中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)以下四種情況之一： (1) 回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)F1相鄰接，見圖4-9(a)。此時(shí)應(yīng)將回收區(qū)與插入點(diǎn)的前一分區(qū)合并，不必為回收分區(qū)分配新表項(xiàng)，而只需修改其前一分區(qū)F1的大小。(2) 回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)F2相鄰接，見圖4-9(b)。此時(shí)也可將兩分區(qū)合并，形成新的空閑分區(qū)，但用回收區(qū)的首址作為新空閑區(qū)的首址，大小為兩者之和。31 31第四章 存 儲(chǔ) 器 管 理(3) 回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接，見圖4-9(c)。此時(shí)將三個(gè)分區(qū)合并，使用F1的表項(xiàng)和F1的首址

15、，取消F2的表項(xiàng)，大小為三者之和。(4) 回收區(qū)既不與F1鄰接，又不與F2鄰接。這時(shí)應(yīng)為回收區(qū)單獨(dú)建立一個(gè)新表項(xiàng)，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。圖4-10示出了內(nèi)存回收時(shí)的流程。3232第四章 存 儲(chǔ) 器 管 理圖4-9 內(nèi)存回收時(shí)的情況3333第四章 存 儲(chǔ) 器 管 理圖4-10 內(nèi)存回收流程3434第四章 存 儲(chǔ) 器 管 理4.3.4 基于順序搜索的動(dòng)態(tài)分區(qū)分配算法1. 首次適應(yīng)(first fit，F(xiàn)F)算法我們以空閑分區(qū)鏈為例來說明采用FF算法時(shí)的分配情況。FF算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿

16、足要求的空閑分區(qū)為止。然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間，分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中。若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿足要求的分區(qū)，則表明系統(tǒng)中已沒有足夠大的內(nèi)存分配給該進(jìn)程，內(nèi)存分配失敗，返回。3535第四章 存 儲(chǔ) 器 管 理2. 循環(huán)首次適應(yīng)(next fit，NF)算法為避免低址部分留下許多很小的空閑分區(qū)，以及減少查找可用空閑分區(qū)的開銷，循環(huán)首次適應(yīng)算法在為進(jìn)程分配內(nèi)存空間時(shí)，不再是每次都從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直至找到一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。 3636第四章 存

17、 儲(chǔ) 器 管 理3. 最佳適應(yīng)(best fit，BF)算法所謂“最佳”是指，每次為作業(yè)分配內(nèi)存時(shí)，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用”。為了加速尋找，該算法要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈。 3737第四章 存 儲(chǔ) 器 管 理4. 最壞適應(yīng)(worst fit，WF)算法由于最壞適應(yīng)分配算法選擇空閑分區(qū)的策略正好與最佳適應(yīng)算法相反：它在掃描整個(gè)空閑分區(qū)表或鏈表時(shí)，總是挑選一個(gè)最大的空閑區(qū)，從中分割一部分存儲(chǔ)空間給作業(yè)使用，以至于存儲(chǔ)器中缺乏大的空閑分區(qū)，故把它稱為是最壞適應(yīng)算法。 3838第四章 存 儲(chǔ) 器 管 理4.3.5 基于索引搜

18、索的動(dòng)態(tài)分區(qū)分配算法1. 快速適應(yīng)(quick fit)算法該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對(duì)于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，這樣系統(tǒng)中存在多個(gè)空閑分區(qū)鏈表。同時(shí)，在內(nèi)存中設(shè)立一張管理索引表，其中的每一個(gè)索引表項(xiàng)對(duì)應(yīng)了一種空閑分區(qū)類型，并記錄了該類型空閑分區(qū)鏈表表頭的指針。 3939第四章 存 儲(chǔ) 器 管 理2. 伙伴系統(tǒng)(buddy system)該算法規(guī)定，無論已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪(k為整數(shù)，lkm)。通常2m是整個(gè)可分配內(nèi)存的大小(也就是最大分區(qū)的大小)。假設(shè)系統(tǒng)的可利用空間容量為2m 個(gè)字，則系統(tǒng)開始運(yùn)行時(shí)

19、，整個(gè)內(nèi)存區(qū)是一個(gè)大小為2m的空閑分區(qū)。在系統(tǒng)運(yùn)行過程中，由于不斷地劃分，將會(huì)形成若干個(gè)不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)按分區(qū)的大小進(jìn)行分類。對(duì)于具有相同大小的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表，這樣，不同大小的空閑分區(qū)形成了k個(gè)空閑分區(qū)鏈表。4040第四章 存 儲(chǔ) 器 管 理在伙伴系統(tǒng)中，對(duì)于一個(gè)大小為2k，地址為x的內(nèi)存塊，其伙伴塊的地址則用buddyk(x)表示，其通式為：)22 xMOD(若2x0)2xMOD(若2x(x)buddyk1kk1kkk 41 41第四章 存 儲(chǔ) 器 管 理3. 哈希算法在上述的分類搜索算法和伙伴系統(tǒng)算法中，都是將空閑分區(qū)根據(jù)分區(qū)大小進(jìn)行分類，對(duì)于每

20、一類具有相同大小的空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表。在為進(jìn)程分配空間時(shí)，需要在一張管理索引表中查找到所需空間大小所對(duì)應(yīng)的表項(xiàng)，從中得到對(duì)應(yīng)的空閑分區(qū)鏈表表頭指針，從而通過查找得到一個(gè)空閑分區(qū)。如果對(duì)空閑分區(qū)分類較細(xì)，則相應(yīng)索引表的表項(xiàng)也就較多，因此會(huì)顯著地增加搜索索引表的表項(xiàng)的時(shí)間開銷。4242第四章 存 儲(chǔ) 器 管 理4.3.6 動(dòng)態(tài)可重定位分區(qū)分配 1. 緊湊連續(xù)分配方式的一個(gè)重要特點(diǎn)是，一個(gè)系統(tǒng)或用戶程序必須被裝入一片連續(xù)的內(nèi)存空間中。當(dāng)一臺(tái)計(jì)算機(jī)運(yùn)行了一段時(shí)間后，它的內(nèi)存空間將會(huì)被分割成許多小的分區(qū)，而缺乏大的空閑空間。即使這些分散的許多小分區(qū)的容量總和大于要裝入的程序，但由于這些分

21、區(qū)不相鄰接，也無法把該程序裝入內(nèi)存。 4343第四章 存 儲(chǔ) 器 管 理圖4-11 緊湊的示意4444第四章 存 儲(chǔ) 器 管 理2. 動(dòng)態(tài)重定位在4.2.1節(jié)中所介紹的動(dòng)態(tài)運(yùn)行時(shí)裝入的方式中，作業(yè)裝入內(nèi)存后的所有地址仍然都是相對(duì)(邏輯)地址。而將相對(duì)地址轉(zhuǎn)換為絕對(duì)(物理)地址的工作被推遲到程序指令要真正執(zhí)行時(shí)進(jìn)行。為使地址的轉(zhuǎn)換不會(huì)影響到指令的執(zhí)行速度，必須有硬件地址變換機(jī)構(gòu)的支持，即須在系統(tǒng)中增設(shè)一個(gè)重定位寄存器，用它來存放程序(數(shù)據(jù))在內(nèi)存中的起始地址。程序在執(zhí)行時(shí)，真正訪問的內(nèi)存地址是相對(duì)地址與重定位寄存器中的地址相加而形成的。 4545第四章 存 儲(chǔ) 器 管 理圖4-12動(dòng)態(tài)重定位示意

22、圖4646第四章 存 儲(chǔ) 器 管 理3. 動(dòng)態(tài)重定位分區(qū)分配算法動(dòng)態(tài)重定位分區(qū)分配算法與動(dòng)態(tài)分區(qū)分配算法基本上相同，差別僅在于：在這種分配算法中，增加了緊湊的功能。通常，當(dāng)該算法不能找到一個(gè)足夠大的空閑分區(qū)以滿足用戶需求時(shí)，如果所有的小的空閑分區(qū)的容量總和大于用戶的要求，這時(shí)便須對(duì)內(nèi)存進(jìn)行“緊湊”，將經(jīng)“緊湊”后所得到的大空閑分區(qū)分配給用戶。如果所有的小的空閑分區(qū)的容量總和仍小于用戶的要求，則返回分配失敗信息。 4747第四章 存 儲(chǔ) 器 管 理圖4-13 動(dòng)態(tài)分區(qū)分配算法流程圖4848第四章 存 儲(chǔ) 器 管 理4.4 對(duì)換(Swapping)對(duì)換技術(shù)也稱為交換技術(shù)，最早用于麻省理工學(xué)院的單用

23、戶分時(shí)系統(tǒng)CTSS中。由于當(dāng)時(shí)計(jì)算機(jī)的內(nèi)存都非常小，為了使該系統(tǒng)能分時(shí)運(yùn)行多個(gè)用戶程序而引入了對(duì)換技術(shù)。系統(tǒng)把所有的用戶作業(yè)存放在磁盤上，每次只能調(diào)入一個(gè)作業(yè)進(jìn)入內(nèi)存，當(dāng)該作業(yè)的一個(gè)時(shí)間片用完時(shí)，將它調(diào)至外存的后備隊(duì)列上等待，再從后備隊(duì)列上將另一個(gè)作業(yè)調(diào)入內(nèi)存。這就是最早出現(xiàn)的分時(shí)系統(tǒng)中所用的對(duì)換技術(shù)。現(xiàn)在已經(jīng)很少使用。4949第四章 存 儲(chǔ) 器 管 理4.4.1 多道程序環(huán)境下的對(duì)換技術(shù)1. 對(duì)換的引入在多道程序環(huán)境下，一方面，在內(nèi)存中的某些進(jìn)程由于某事件尚未發(fā)生而被阻塞運(yùn)行，但它卻占用了大量的內(nèi)存空間，甚至有時(shí)可能出現(xiàn)在內(nèi)存中所有進(jìn)程都被阻塞，而無可運(yùn)行之進(jìn)程，迫使CPU停止下來等待的情況

24、；另一方面，卻又有著許多作業(yè)，因內(nèi)存空間不足，一直駐留在外存上，而不能進(jìn)入內(nèi)存運(yùn)行。顯然這對(duì)系統(tǒng)資源是一種嚴(yán)重的浪費(fèi)，且使系統(tǒng)吞吐量下降。 5050第四章 存 儲(chǔ) 器 管 理2. 對(duì)換的類型在每次對(duì)換時(shí)，都是將一定數(shù)量的程序或數(shù)據(jù)換入或換出內(nèi)存。根據(jù)每次對(duì)換時(shí)所對(duì)換的數(shù)量，可將對(duì)換分為如下兩類：(1) 整體對(duì)換。(2) 頁面(分段)對(duì)換。 51 51第四章 存 儲(chǔ) 器 管 理4.4.2 對(duì)換空間的管理 1. 對(duì)換空間管理的主要目標(biāo)在具有對(duì)換功能的OS中，通常把磁盤空間分為文件區(qū)和對(duì)換區(qū)兩部分。1) 對(duì)文件區(qū)管理的主要目標(biāo)2) 對(duì)對(duì)換空間管理的主要目標(biāo)5252第四章 存 儲(chǔ) 器 管 理2. 對(duì)換

25、區(qū)空閑盤塊管理中的數(shù)據(jù)結(jié)構(gòu)為了實(shí)現(xiàn)對(duì)對(duì)換區(qū)中的空閑盤塊的管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用于記錄外存對(duì)換區(qū)中的空閑盤塊的使用情況。其數(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ù)表示。5353第四章 存 儲(chǔ) 器 管 理3. 對(duì)換空間的分配與回收由于對(duì)換分區(qū)的分配采用的是連續(xù)分配方式，因而對(duì)換空間的分配與回收與動(dòng)態(tài)分區(qū)方式時(shí)的內(nèi)存分配與回收方法雷同。其分配算法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算法或最佳適應(yīng)算法等。具體的分配操作也與圖4-8中內(nèi)存的分配過程相同。 54

26、54第四章 存 儲(chǔ) 器 管 理4.4.3 進(jìn)程的換出與換入1. 進(jìn)程的換出對(duì)換進(jìn)程在實(shí)現(xiàn)進(jìn)程換出時(shí)，是將內(nèi)存中的某些進(jìn)程調(diào)出至對(duì)換區(qū)，以便騰出內(nèi)存空間。換出過程可分為以下兩步：(1) 選擇被換出的進(jìn)程。(2) 進(jìn)程換出過程。 5555第四章 存 儲(chǔ) 器 管 理2. 進(jìn)程的換入對(duì)換進(jìn)程將定時(shí)執(zhí)行換入操作，它首先查看PCB集合中所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程。當(dāng)有許多這樣的進(jìn)程時(shí)，它將選擇其中已換出到磁盤上時(shí)間最久(必須大于規(guī)定時(shí)間，如2s)的進(jìn)程作為換入進(jìn)程，為它申請(qǐng)內(nèi)存。如果申請(qǐng)成功，可直接將進(jìn)程從外存調(diào)入內(nèi)存；如果失敗，則需先將內(nèi)存中的某些進(jìn)程換出，騰出足夠的內(nèi)存空間后，

27、再將進(jìn)程調(diào)入。5656第四章 存 儲(chǔ) 器 管 理4.5 分頁存儲(chǔ)管理方式(1) 分頁存儲(chǔ)管理方式。(2) 分段存儲(chǔ)管理方式。(3) 段頁式存儲(chǔ)管理方式。 5757第四章 存 儲(chǔ) 器 管 理4.5.1 分頁存儲(chǔ)管理的基本方法1. 頁面和物理塊(1) 頁面。(2) 頁面大小。 5858第四章 存 儲(chǔ) 器 管 理2. 地址結(jié)構(gòu)分頁地址中的地址結(jié)構(gòu)如下：5959第四章 存 儲(chǔ) 器 管 理對(duì)某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為A，頁面的大小為L(zhǎng)，則頁號(hào)P和頁內(nèi)地址d可按下式求得：6060第四章 存 儲(chǔ) 器 管 理3. 頁表在分頁系統(tǒng)中，允許將進(jìn)程的各個(gè)頁離散地存儲(chǔ)在內(nèi)存的任一

28、物理塊中，為保證進(jìn)程仍然能夠正確地運(yùn)行，即能在內(nèi)存中找到每個(gè)頁面所對(duì)應(yīng)的物理塊，系統(tǒng)又為每個(gè)進(jìn)程建立了一張頁面映像表，簡(jiǎn)稱頁表。 61 61第四章 存 儲(chǔ) 器 管 理圖4-14 頁表的作用6262第四章 存 儲(chǔ) 器 管 理4.5.2 地址變換機(jī)構(gòu)1. 基本的地址變換機(jī)構(gòu)進(jìn)程在運(yùn)行期間，需要對(duì)程序和數(shù)據(jù)的地址進(jìn)行變換，即將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址，由于它執(zhí)行的頻率非常高，每條指令的地址都需要進(jìn)行變換，因此需要采用硬件來實(shí)現(xiàn)。頁表功能是由一組專門的寄存器來實(shí)現(xiàn)的。一個(gè)頁表項(xiàng)用一個(gè)寄存器。 6363第四章 存 儲(chǔ) 器 管 理圖4-15 分頁系統(tǒng)的地址變換機(jī)構(gòu)6464第四章

29、存 儲(chǔ) 器 管 理2. 具有快表的地址變換機(jī)構(gòu)由于頁表是存放在內(nèi)存中的，這使CPU在每存取一個(gè)數(shù)據(jù)時(shí)，都要兩次訪問內(nèi)存。第一次是訪問內(nèi)存中的頁表，從中找到指定頁的物理塊號(hào)，再將塊號(hào)與頁內(nèi)偏移量W拼接，以形成物理地址。第二次訪問內(nèi)存時(shí)，才是從第一次所得地址中獲得所需數(shù)據(jù)(或向此地址中寫入數(shù)據(jù))。因此，采用這種方式將使計(jì)算機(jī)的處理速度降低近1/2。可見，以此高昂代價(jià)來換取存儲(chǔ)器空間利用率的提高，是得不償失的。6565第四章 存 儲(chǔ) 器 管 理圖4-16 具有快表的地址變換機(jī)構(gòu)6666第四章 存 儲(chǔ) 器 管 理4.5.3 訪問內(nèi)存的有效時(shí)間從進(jìn)程發(fā)出指定邏輯地址的訪問請(qǐng)求，經(jīng)過地址變換，到在內(nèi)存中找

30、到對(duì)應(yīng)的實(shí)際物理地址單元并取出數(shù)據(jù)，所需要花費(fèi)的總時(shí)間，稱為內(nèi)存的有效訪問時(shí)間(Effective Access Time，EAT)。假設(shè)訪問一次內(nèi)存的時(shí)間為t，在基本分頁存儲(chǔ)管理方式中，有效訪問時(shí)間分為第一次訪問內(nèi)存時(shí)間(即查找頁表對(duì)應(yīng)的頁表項(xiàng)所耗費(fèi)的時(shí)間t)與第二次訪問內(nèi)存時(shí)間(即將頁表項(xiàng)中的物理塊號(hào)與頁內(nèi)地址拼接成實(shí)際物理地址所耗費(fèi)的時(shí)間t)之和：EAT=t+t=2t6767第四章 存 儲(chǔ) 器 管 理在引入快表的分頁存儲(chǔ)管理方式中，通過快表查詢，可以直接得到邏輯頁所對(duì)應(yīng)的物理塊號(hào)，由此拼接形成實(shí)際物理地址，減少了一次內(nèi)存訪問，縮短了進(jìn)程訪問內(nèi)存的有效時(shí)間。但是，由于快表的容量限制，不可能

31、將一個(gè)進(jìn)程的整個(gè)頁表全部裝入快表，所以在快表中查找到所需表項(xiàng)存在著命中率的問題。所謂命中率，是指使用快表并在其中成功查找到所需頁面的表項(xiàng)的比率。這樣，在引入快表的分頁存儲(chǔ)管理方式中，有效訪問時(shí)間的計(jì)算公式即為： EAT=+(t+)(1)+t=2t+t上式中，表示查找快表所需要的時(shí)間，表示命中率，t表示訪問一次內(nèi)存所需要的時(shí)間。6868第四章 存 儲(chǔ) 器 管 理可見，引入快表后的內(nèi)存有效訪問時(shí)間分為查找到邏輯頁對(duì)應(yīng)的頁表項(xiàng)的平均時(shí)間+(t+)(1-)，以及對(duì)應(yīng)實(shí)際物理地址的內(nèi)存訪問時(shí)間t。假設(shè)對(duì)快表的訪問時(shí)間為20ns(納秒)，對(duì)內(nèi)存的訪問時(shí)間t為100ns，則下表中列出了不同的命中率與有效訪問

32、時(shí)間的關(guān)系：6969第四章 存 儲(chǔ) 器 管 理4.5.4 兩級(jí)和多級(jí)頁表1. 兩級(jí)頁表(Two-Level Page Table)針對(duì)難于找到大的連續(xù)的內(nèi)存空間來存放頁表的問題，可利用將頁表進(jìn)行分頁的方法，使每個(gè)頁面的大小與內(nèi)存物理塊的大小相同，并為它們進(jìn)行編號(hào)，即依次為0#頁、1#頁，n#頁，然后離散地將各個(gè)頁面分別存放在不同的物理塊中。同樣，也要為離散分配的頁表再建立一張頁表，稱為外層頁表(Outer Page Table)，在每個(gè)頁表項(xiàng)中記錄了頁表頁面的物理塊號(hào)。 7070第四章 存 儲(chǔ) 器 管 理圖4-17兩級(jí)頁表結(jié)構(gòu)71 71第四章 存 儲(chǔ) 器 管 理為了方便實(shí)現(xiàn)地址變換，在地址變換

33、機(jī)構(gòu)中，同樣需要增設(shè)一個(gè)外層頁表寄存器，用于存放外層頁表的始址，并利用邏輯地址中的外層頁號(hào)作為外層頁表的索引，從中找到指定頁表分頁的始址，再利用P2作為指定頁表分頁的索引，找到指定的頁表項(xiàng)，其中即含有該頁在內(nèi)存的物理塊號(hào)，用該塊號(hào)P和頁內(nèi)地址d即可構(gòu)成訪問的內(nèi)存物理地址。圖4-18示出了兩級(jí)頁表時(shí)的地址變換機(jī)構(gòu)。7272第四章 存 儲(chǔ) 器 管 理圖4-18具有兩級(jí)頁表的地址變換機(jī)構(gòu)7373第四章 存 儲(chǔ) 器 管 理2. 多級(jí)頁表對(duì)于32位的機(jī)器，采用兩級(jí)頁表結(jié)構(gòu)是合適的，但對(duì)于64位的機(jī)器，采用兩級(jí)頁表是否仍然合適，須做以下簡(jiǎn)單分析。如果頁面大小仍采用4 KB即212 B，那么還剩下52位，假

34、定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號(hào)。此時(shí)在外層頁表中可能有4096G個(gè)頁表項(xiàng)，要占用16384 GB的連續(xù)內(nèi)存空間。 7474第四章 存 儲(chǔ) 器 管 理4.5.5 反置頁表(Inverted Page Table)1. 反置頁表的引入在分頁系統(tǒng)中，為每個(gè)進(jìn)程配置了一張頁表，進(jìn)程邏輯地址空間中的每一頁，在頁表中都對(duì)應(yīng)有一個(gè)頁表項(xiàng)。在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，通常允許一個(gè)進(jìn)程的邏輯地址空間非常大，因此就需要有許多的頁表項(xiàng)，而因此也會(huì)占用大量的內(nèi)存空間。 7575第四章 存 儲(chǔ) 器 管 理2. 地址變換在利用反置頁表進(jìn)行地址變換時(shí)，是根據(jù)進(jìn)程標(biāo)識(shí)符和頁號(hào)，去檢索反置頁表。

35、如果檢索到與之匹配的頁表項(xiàng)，則該頁表項(xiàng)(中)的序號(hào)i便是該頁所在的物理塊號(hào)，可用該塊號(hào)與頁內(nèi)地址一起構(gòu)成物理地址送內(nèi)存地址寄存器。若檢索了整個(gè)反置頁表仍未找到匹配的頁表項(xiàng)，則表明此頁尚未裝入內(nèi)存。對(duì)于不具有請(qǐng)求調(diào)頁功能的存儲(chǔ)器管理系統(tǒng)，此時(shí)則表示地址出錯(cuò)。對(duì)于具有請(qǐng)求調(diào)頁功能的存儲(chǔ)器管理系統(tǒng)，此時(shí)應(yīng)產(chǎn)生請(qǐng)求調(diào)頁中斷，系統(tǒng)將把此頁調(diào)入內(nèi)存。7676第四章 存 儲(chǔ) 器 管 理4.6 分段存儲(chǔ)管理方式存儲(chǔ)管理方式隨著OS的發(fā)展也在不斷地發(fā)展。當(dāng)OS由單道向多道發(fā)展時(shí)，存儲(chǔ)管理方式便由單一連續(xù)分配發(fā)展為固定分區(qū)分配。 7777第四章 存 儲(chǔ) 器 管 理4.6.1 分段存儲(chǔ)管理方式的引入1. 方便編程通

36、常，用戶把自己的作業(yè)按照邏輯關(guān)系劃分為若干個(gè)段，每個(gè)段都從0開始編址，并有自己的名字和長(zhǎng)度。因此，程序員們都迫切地需要訪問的邏輯地址是由段名(段號(hào))和段內(nèi)偏移量(段內(nèi)地址)決定的，這不僅可以方便程序員編程，也可使程序非常直觀，更具可讀性。例如，下述的兩條指令便使用段名和段內(nèi)地址： LOAD 1，A |D； STORE 1，B |C；7878第四章 存 儲(chǔ) 器 管 理2. 信息共享在實(shí)現(xiàn)對(duì)程序和數(shù)據(jù)的共享時(shí)，是以信息的邏輯單位為基礎(chǔ)的。比如，為了共享某個(gè)過程、函數(shù)或文件。分頁系統(tǒng)中的“頁”只是存放信息的物理單位(塊)，并無完整的邏輯意義，這樣，一個(gè)可被共享的過程往往可能需要占用數(shù)十個(gè)頁面，這為實(shí)

37、現(xiàn)共享增加了困難。 7979第四章 存 儲(chǔ) 器 管 理3. 信息保護(hù)信息保護(hù)同樣是以信息的邏輯單位為基礎(chǔ)的，而且經(jīng)常是以一個(gè)過程、函數(shù)或文件為基本單位進(jìn)行保護(hù)的。 8080第四章 存 儲(chǔ) 器 管 理4. 動(dòng)態(tài)增長(zhǎng) 在實(shí)際應(yīng)用中，往往存在著一些段，尤其是數(shù)據(jù)段，在它們的使用過程中，由于數(shù)據(jù)量的不斷增加，而使數(shù)據(jù)段動(dòng)態(tài)增長(zhǎng)，相應(yīng)地它所需要的存儲(chǔ)空間也會(huì)動(dòng)態(tài)增加。然而，對(duì)于數(shù)據(jù)段究竟會(huì)增長(zhǎng)到多大，事先又很難確切地知道。對(duì)此，很難采取預(yù)先多分配的方法進(jìn)行解決。 81 81第四章 存 儲(chǔ) 器 管 理5. 動(dòng)態(tài)鏈接在4.2.2節(jié)中我們已對(duì)運(yùn)行時(shí)動(dòng)態(tài)鏈接做了介紹。為了提高內(nèi)存的利用率，系統(tǒng)只將真正要運(yùn)行的目

38、標(biāo)程序裝入內(nèi)存，也就是說，動(dòng)態(tài)鏈接在作業(yè)運(yùn)行之前，并不是把所有的目標(biāo)程序段都鏈接起來。當(dāng)程序要運(yùn)行時(shí)，首先將主程序和它立即需要用到的目標(biāo)程序裝入內(nèi)存，即啟動(dòng)運(yùn)行。而在程序運(yùn)行過程中，當(dāng)需要調(diào)用某個(gè)目標(biāo)程序時(shí)，才將該段(目標(biāo)程序)調(diào)入內(nèi)存并進(jìn)行鏈接。 8282第四章 存 儲(chǔ) 器 管 理4.6.2 分段系統(tǒng)的基本原理 1. 分段在分段存儲(chǔ)管理方式中，作業(yè)的地址空間被劃分為若干個(gè)段，每個(gè)段定義了一組邏輯信息。例如，有主程序段MAIN、子程序段X、數(shù)據(jù)段D及棧段S等，如圖4-19所示。 分段地址中的地址具有如下結(jié)構(gòu)：8383第四章 存 儲(chǔ) 器 管 理2. 段表在前面所介紹的動(dòng)態(tài)分區(qū)分配方式中，系統(tǒng)為整

39、個(gè)進(jìn)程分配一個(gè)連續(xù)的內(nèi)存空間。而在分段式存儲(chǔ)管理系統(tǒng)中，則是為每個(gè)分段分配一個(gè)連續(xù)的分區(qū)。進(jìn)程中的各個(gè)段，可以離散地裝入內(nèi)存中不同的分區(qū)中。為保證程序能正常運(yùn)行，就必須能從物理內(nèi)存中找出每個(gè)邏輯段所對(duì)應(yīng)的位置。 8484第四章 存 儲(chǔ) 器 管 理圖4-19 利用段表實(shí)現(xiàn)地址映射8585第四章 存 儲(chǔ) 器 管 理3. 地址變換機(jī)構(gòu)為了實(shí)現(xiàn)進(jìn)程從邏輯地址到物理地址的變換功能，在系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址和段表長(zhǎng)度TL。在進(jìn)行地址變換時(shí)，系統(tǒng)將邏輯地址中的段號(hào)與段表長(zhǎng)度TL進(jìn)行比較。若STL，表示段號(hào)太大，是訪問越界，于是產(chǎn)生越界中斷信號(hào)。若未越界，則根據(jù)段表的始址和該段的段號(hào)，計(jì)算出

40、該段對(duì)應(yīng)段表項(xiàng)的位置，從中讀出該段在內(nèi)存的起始地址。然后，再檢查段內(nèi)地址d是否超過該段的段長(zhǎng)SL。若超過，即dSL，同樣發(fā)出越界中斷信號(hào)。若未越界，則將該段的基址d與段內(nèi)地址相加，即可得到要訪問的內(nèi)存物理地址。圖4-20示出了分段系統(tǒng)的地址變換過程。8686第四章 存 儲(chǔ) 器 管 理圖4-20 分段系統(tǒng)的地址變換過程8787第四章 存 儲(chǔ) 器 管 理4. 分頁和分段的主要區(qū)別(1) 頁是信息的物理單位。(2) 頁的大小固定且由系統(tǒng)決定。(3) 分頁的用戶程序地址空間是一維的。 8888第四章 存 儲(chǔ) 器 管 理4.6.3 信息共享1. 分頁系統(tǒng)中對(duì)程序和數(shù)據(jù)的共享在分頁系統(tǒng)中，雖然也能實(shí)現(xiàn)對(duì)程

41、序和數(shù)據(jù)的共享，但遠(yuǎn)不如分段系統(tǒng)來得方便。我們通過一個(gè)例子來說明這個(gè)問題。 8989第四章 存 儲(chǔ) 器 管 理圖4-21 分頁系統(tǒng)中共享editor的示意圖9090第四章 存 儲(chǔ) 器 管 理2. 分段系統(tǒng)中程序和數(shù)據(jù)的共享在分段系統(tǒng)中，由于是以段為基本單位的，不管該段有多大，我們都只需為該段設(shè)置一個(gè)段表項(xiàng)，因此使實(shí)現(xiàn)共享變得非常容易。我們?nèi)砸怨蚕韊ditor為例，此時(shí)只需在(每個(gè))進(jìn)程1和進(jìn)程2的段表中，為文本編輯程序設(shè)置一個(gè)段表項(xiàng)，讓段表項(xiàng)中的基址(80)指向editor程序在內(nèi)存的起始地址。圖4-22是分段系統(tǒng)中共享editor的示意圖。91 91第四章 存 儲(chǔ) 器 管 理圖4-22 分段系統(tǒng)中共享editor的示意圖9292第四章 存 儲(chǔ) 器 管 理4.6.4 段頁式存儲(chǔ)管理方式1. 基本原理段頁式系統(tǒng)的基本原理是分段和分頁原理的結(jié)合，即先將用戶程序分成若干個(gè)段，再把每個(gè)段分成若干個(gè)頁，并為每一個(gè)段賦予一個(gè)段名。圖4-23(a)示出了一個(gè)作業(yè)地址空間的結(jié)構(gòu)。該作業(yè)有三個(gè)段：主程序段、子程序段和數(shù)據(jù)段；頁面大小為 4