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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、區(qū)空閑盤塊管理中的數(shù)據(jù)結(jié)構(gòu)為了實現(xiàn)對對換區(qū)中的空閑盤塊的管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用于記錄外存對換區(qū)中的空閑盤塊的使用情況。其數(shù)據(jù)結(jié)構(gòu)的形式與內(nèi)存在動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表的每個表目中，應(yīng)包含兩項：對換區(qū)的首址及其大小，分別用盤塊號和盤塊數(shù)表示。5353第四章 存 儲 器 管 理3. 對換空間的分配與回收由于對換分區(qū)的分配采用的是連續(xù)分配方式，因而對換空間的分配與回收與動態(tài)分區(qū)方式時的內(nèi)存分配與回收方法雷同。其分配算法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算法或最佳適應(yīng)算法等。具體的分配操作也與圖4-8中內(nèi)存的分配過程相同。 54

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

41、序和數(shù)據(jù)的共享，但遠(yuǎn)不如分段系統(tǒng)來得方便。我們通過一個例子來說明這個問題。 8989第四章 存 儲 器 管 理圖4-21 分頁系統(tǒng)中共享editor的示意圖9090第四章 存 儲 器 管 理2. 分段系統(tǒng)中程序和數(shù)據(jù)的共享在分段系統(tǒng)中，由于是以段為基本單位的，不管該段有多大，我們都只需為該段設(shè)置一個段表項，因此使實現(xiàn)共享變得非常容易。我們?nèi)砸怨蚕韊ditor為例，此時只需在(每個)進(jìn)程1和進(jìn)程2的段表中，為文本編輯程序設(shè)置一個段表項，讓段表項中的基址(80)指向editor程序在內(nèi)存的起始地址。圖4-22是分段系統(tǒng)中共享editor的示意圖。91 91第四章 存 儲 器 管 理圖4-22 分段

42、系統(tǒng)中共享editor的示意圖9292第四章 存 儲 器 管 理4.6.4 段頁式存儲管理方式1. 基本原理段頁式系統(tǒng)的基本原理是分段和分頁原理的結(jié)合，即先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每一個段賦予一個段名。圖4-23(a)示出了一個作業(yè)地址空間的結(jié)構(gòu)。該作業(yè)有三個段：主程序段、子程序段和數(shù)據(jù)段；頁面大小為 4 KB。在段頁式系統(tǒng)中，其地址結(jié)構(gòu)由段號、段內(nèi)頁號及頁內(nèi)地址三部分所組成，如圖4-23(b)所示。9393第四章 存 儲 器 管 理圖4-23 作業(yè)地址空間和地址結(jié)構(gòu)9494第四章 存 儲 器 管 理在段頁式系統(tǒng)中，為了實現(xiàn)從邏輯地址到物理地址的變換，系統(tǒng)中需要同時配置段表和頁表。段表的內(nèi)容與分段系統(tǒng)略有不同，它不再是內(nèi)存始址和段長，而是頁表始址和頁表長度。圖4-2