1、 本章學(xué)習(xí)目標 本章主要講解了存儲器管理的基本方式，剖析了Linux 操作系統(tǒng)對內(nèi)存的管理模式。通過對本章學(xué)習(xí)，讀者應(yīng)該達到以下學(xué)習(xí)目標：重點掌握本章的基本概念，分頁式存儲管理技術(shù)和分段式存儲管理技術(shù)，虛擬存儲器的概念。理解段頁式存儲管理技術(shù)，虛存中的置換算法。了解Linux操作系統(tǒng)的存儲管理技術(shù)。第第4章章 存儲器管理存儲器管理1教學(xué)內(nèi)容4.1 存儲器管理概述4.2 連續(xù)分配存儲管理方式4.3 分頁存儲管理方式 4.4 分段存儲管理方式4.5 虛擬存儲器的基本概念4.6 請求分頁4.7 請求分段存儲管理4.8 LINUX系統(tǒng)的內(nèi)存管理方法 本章小結(jié)24.1 存儲器管理概述存儲器管理概述 4.

2、1.1 存儲器的層次存儲器的層次圖4.1所示就是存儲器的體系結(jié)構(gòu)。高速緩沖存儲器主存儲器輔助存儲器存儲容量遞增存取速度遞增圖4. 1 多級存儲器體系示意圖第第4章章 存儲器管理存儲器管理34.1.2 用戶程序的處理過程用戶程序的處理過程用戶程序處理分以下幾個階段：（1）編譯。由編譯程序?qū)⒂脩粼创a編譯成若干個目標模塊。（2）鏈接。有鏈接程序?qū)⒕幾g后形成的目標代碼以及它們所需的庫函數(shù)，鏈接在一起，形成一個裝入模塊。（3）裝入。有裝入程序?qū)⒀b入模塊裝入內(nèi)存。處理過程示意圖見4.2第第4章章 存儲器管理存儲器管理4編譯程序產(chǎn)生的目標模塊程序數(shù)據(jù)庫函數(shù)鏈接程序裝入模塊裝入程序圖.2 對用戶程序的處理步

3、驟第第4章章 存儲器管理存儲器管理51目標程序裝入內(nèi)存的方式目標程序裝入內(nèi)存的方式 程序只有裝入到內(nèi)存后才能運行。裝入方式分絕對裝入方式、可重定位裝入方式和動態(tài)運行時裝入方式。（1）絕對裝入方式 在編譯時，如果知道程序?qū)Ⅰv留在內(nèi)存什么位置，那么編譯程序?qū)a(chǎn)生絕對地址的目標代碼。絕對裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)裝入內(nèi)存。裝入模塊被裝入內(nèi)存后，不須對程序和數(shù)據(jù)的地址進行修改，程序中所使用的絕對地址，即可以在編譯或匯編中給出，也可以有程序員直接給予。一般不讓程序員給予地址，通常情況是在程序中采用符號地址，然后在編譯或匯編時，將這些符號地址再轉(zhuǎn)化為絕對地址。第第4章章 存儲器管理存儲器管

4、理6（2）可重定位裝入方式 又稱靜態(tài)重定位。是在程序執(zhí)行之前，有操作系統(tǒng)的重定位裝入程序完成。一般用于多道程序環(huán)境中，編譯程序不能預(yù)知所編譯的目標模塊在內(nèi)存什么地方。重定位程序根據(jù)裝入程序的內(nèi)存起始地址，直接修改所涉及到的邏輯地址，將內(nèi)存的起始地址加上邏輯地址得到正確的內(nèi)存地址。第第4章章 存儲器管理存儲器管理7100001200013500360Load 1,350015000內(nèi)存空間020003500360Load 1,35005000作業(yè)地址空間圖4.3 作業(yè)裝入內(nèi)存時的情況第第4章章 存儲器管理存儲器管理8（3）動態(tài)運行時的裝入方式）動態(tài)運行時的裝入方式 又稱動態(tài)重定位。是在程序執(zhí)行期

5、間進行的。一般說來，這種轉(zhuǎn)換有專門的硬件機構(gòu)來完成，通常采用一個重定位寄存器 ，每次進行存儲訪問時，對取出的邏輯地址加上重定位寄存器的內(nèi)容，形成正確的內(nèi)存地址。如圖4.4所示.第第4章章 存儲器管理存儲器管理9100001200013500360Load 1,350015000內(nèi)存空間物理地址10000350013500+圖4.4 采用動態(tài)重定位時內(nèi)存空間及地址重定位示意圖第第4章章 存儲器管理存儲器管理102目標程序鏈接目標程序鏈接 鏈接程序的功能，是將經(jīng)過編譯或匯編后得到的一組目標模塊以及它們所需要的庫函數(shù)，裝配成一個完整的裝入模塊。實現(xiàn)鏈接的方法有三種：靜態(tài)鏈接、裝入時動態(tài)鏈接和運行時動

6、態(tài)鏈接。（1）靜態(tài)鏈接 設(shè)編譯后得到的三個目標模塊A、B、C，它們的長度分別為L、M和N。 程序鏈接示意圖如圖4.5所示。需要完成的工作是對相對地址進行修改，同時變換外部調(diào)用符號，將每個CALL語句改為跳轉(zhuǎn)到某個相對地址，從而形成一個完整的裝入模塊，又稱可執(zhí)行文件。通常不再拆開，運行時可直接裝入內(nèi)存。這種事先進行鏈接，以后不再拆開的方式稱為靜態(tài)鏈接。第第4章章 存儲器管理存儲器管理11（2）裝入時動態(tài)鏈接 用戶源程序經(jīng)編譯后得到目標模塊，是在裝入內(nèi)存時邊裝入邊鏈接的。即在裝入一個目標模塊時，若發(fā)生一個外部模塊調(diào)用時，將引起裝入程序去找相應(yīng)的外部目標模塊，并將它裝入內(nèi)存。（3）運行時動態(tài)鏈接 裝

7、入時進行的鏈接雖然可以將整個模塊裝入到內(nèi)存的任何地方，但裝入摸塊的結(jié)構(gòu)是靜態(tài)的。在程序執(zhí)行期間裝入模塊是不可改變的，因為無法預(yù)知本次要運行哪個模塊，只能將所有可能要運行的模塊，在裝入時全部鏈接在一起，使得每次執(zhí)行的模塊都相同。這樣效率很低，因此采用運行時動態(tài)鏈接。在這種鏈接方式中，可將某些目標模塊的鏈接，推遲到執(zhí)行時才進行。即在執(zhí)行過程中，若發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，有OS去找該模塊，將它裝入內(nèi)存，并把它鏈接到調(diào)用模塊上。第第4章章 存儲器管理存儲器管理120L-1模塊ACALL BReturn ;模塊BCALL CReturn ;模塊CReturn ;0M-1N-10目標模塊裝入模塊

8、0L-1模塊AJSR “L”Return ;模塊BJSR”L+M” Return模塊CReturnLL+M-1L+ML+M+N-1圖4.5 程序鏈接示意圖第第4章章 存儲器管理存儲器管理134.2連續(xù)分配存儲管理方式連續(xù)分配存儲管理方式 連續(xù)分配是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間，連續(xù)分配有兩種：單道程序的連續(xù)分配和多道程序的連續(xù)分配。多道程序的連續(xù)分配又稱為分區(qū)分配方式，它包括固定分區(qū)、動態(tài)分區(qū)和動態(tài)重定位分區(qū)三種。下面就是對各種連續(xù)存儲管理的研究。第第4章章 存儲器管理存儲器管理144.2.1 單道程序的連續(xù)分配單道程序的連續(xù)分配 這是一種最簡單的存儲方式，只能用于單用戶、單任務(wù)的操

9、作系統(tǒng)。在這種存儲方式中，內(nèi)存分為兩個分區(qū)：系統(tǒng)區(qū)和用戶區(qū)。1系統(tǒng)區(qū)。 僅供操作系統(tǒng)使用，一般駐留在低址部分，其中包括中斷向量。第第4章章 存儲器管理存儲器管理152用戶區(qū) 操作系統(tǒng)以外的全部空間。其結(jié)構(gòu)圖如圖4.6所示。操作系統(tǒng)用戶程序0a+1na圖4.6所示第第4章章 存儲器管理存儲器管理16 為了避免用戶程序執(zhí)行時訪問了操作系統(tǒng)所占空間，應(yīng)將用戶程序的執(zhí)行嚴格控制在用戶區(qū)域。稱之為存儲保護，保護措施主要是有硬件實現(xiàn)。硬件提供界地址寄存器和越界檢查機構(gòu)。將操作系統(tǒng)所在空間的下界a存放在界地址寄存器中，用戶程序執(zhí)行時，每訪問一次主存，越界檢查機構(gòu)便將訪問主存的地址和界地址寄存器的值進行比較，

10、若出界則報地址錯。第第4章章 存儲器管理存儲器管理17界限寄存器重定位寄存器CPU+邏輯地址物理地址地址錯內(nèi)存圖4.7 地址映射和地址保護第第4章章 存儲器管理存儲器管理184.2.2 固定分區(qū)分配方式固定分區(qū)分配方式 固定分區(qū)管理比較簡單，本節(jié)僅以舉例的方式說明其原理。設(shè)一個容量為32k的實際內(nèi)存，分割成如下若干區(qū)域，如圖所示。操作系統(tǒng)10k小作業(yè)4k中等作業(yè)區(qū)6k大作業(yè)區(qū)12k 這種分區(qū)分配方式在整個系統(tǒng)運行期間是不變的。在這種情況下，當為一個作業(yè)分配空間時，應(yīng)該先判定它分在哪個區(qū)域比較合適，然后再進行分配。第第4章章 存儲器管理存儲器管理194.2.3 動態(tài)分區(qū)分配動態(tài)分區(qū)分配動態(tài)分區(qū)分

11、配需要解決的問題有三個：（1）分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)。（2）分區(qū)的分配算法。（3）分區(qū)的分配與回收操作。1分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)。 要實現(xiàn)分區(qū)分配，系統(tǒng)必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來記錄內(nèi)存的使用情況。為分配提供依據(jù)。常用的數(shù)據(jù)結(jié)構(gòu)有兩種：第第4章章 存儲器管理存儲器管理20（1）空閑分區(qū)表其表的結(jié)構(gòu)表所示：序號分區(qū)大?。╧b）分區(qū)始址（k）狀態(tài)16444可用224132可用340210可用430270可用5第第4章章 存儲器管理存儲器管理21（2）空閑分區(qū)鏈）空閑分區(qū)鏈 為了實現(xiàn)對空閑分區(qū)的分配與鏈接，在每個分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息，以及用于鏈接各分區(qū)的前向指針：在分區(qū)尾

12、部則設(shè)置一后向指針；然后形成一個雙向鏈。其結(jié)構(gòu)如圖4.8所示。如圖4.8 空閑鏈結(jié)構(gòu)第第4章章 存儲器管理存儲器管理22二、分區(qū)分配算法二、分區(qū)分配算法 為把一個新作業(yè)裝入內(nèi)存，須按照一定的分配算法，從空閑區(qū)表或空閑分區(qū)鏈中，選一個分區(qū)分配給該作業(yè)，目前常用以下三種分配算法：1首次適應(yīng)算法 此算法可以在上述兩種數(shù)據(jù)結(jié)構(gòu)上實施，但通常要求自由塊按始地址從小到大的順序排序。當須分配空間時，總是從頭開始查找，直到找到一個符合要求的自由塊。第第4章章 存儲器管理存儲器管理232最佳適應(yīng)法 可以在上述兩種數(shù)據(jù)結(jié)構(gòu)上實施，但要求按自由塊從小到大的順序排序。分配從頭開始查找，即從小端到大端的方向查找。直到找

13、到第一個滿足要求的自由塊。顯然，所能找到的自由塊能滿足要求的最小塊。3最壞適應(yīng)算法 數(shù)據(jù)結(jié)構(gòu)和排序方法如上。當分配空間時不 是從小往大查，而是從大往小查，因此，所找到的自由塊是所有自由塊中最大者。第第4章章 存儲器管理存儲器管理24三、分區(qū)分配和回收三、分區(qū)分配和回收在動態(tài)分區(qū)存儲管理方式中，主要操作是分配和回收內(nèi)存。1分配內(nèi)存 首先，系統(tǒng)利用某鐘算法，從空閑區(qū)表中找到所需的分區(qū)。設(shè)請求的分區(qū)的大小為u.size,表中每個分區(qū)的大小可表為m.size。若m.size-u.sizesize (size是事先規(guī)定的不再切割的剩余分區(qū)的大小)，說明多余部分太小，可不再切割，將整個分區(qū)分給請求者；否則

14、，從該分區(qū)中劃分出與請求的大小相等的內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)鏈或空閑分區(qū)表中。最后，將分配的首地址返回給調(diào)用者。第第4章章 存儲器管理存儲器管理252回收內(nèi)存回收內(nèi)存 回收分區(qū)的主要工作是：首先檢查是否有臨接的空閑區(qū)，如有則合并，使之成為一個連續(xù)的空閑區(qū)，而不是許多零散的小的部分；之后，修改有關(guān)的分區(qū)描述信息。一個回收分區(qū)鄰接空閑區(qū)的情況有四種：如圖4.9所示。第一種情況是回收分區(qū)r上鄰的一個空閑區(qū)，此時應(yīng)合并成為一個連續(xù)的空閑區(qū)，其始址為r上鄰的空閑區(qū)始址，而大小為二者之和。第二種情況與r下面的空閑區(qū)相鄰。直接合并。第三種情況是與上下空閑區(qū)相鄰。將三個區(qū)域合并成一個連續(xù)的空

15、閑區(qū)。第四種情況不和任何空閑區(qū)相鄰，應(yīng)建立一個新的空閑區(qū)，并加到自由主存隊列中。第第4章章 存儲器管理存儲器管理26fr作業(yè)1作業(yè)2rf2f1rf2作業(yè)1r作業(yè)2回收分區(qū)r上鄰的空閑區(qū)回收分區(qū)r下鄰的空閑區(qū)回收分區(qū)r上、下鄰的空閑區(qū)回收分區(qū)r單獨為空閑區(qū)圖4.9內(nèi)存回收時的情況第第4章章 存儲器管理存儲器管理274.2.4 可重定位分區(qū)可重定位分區(qū)1緊湊 在連續(xù)分配方式中，必須把一個系統(tǒng)程序或用戶程序，裝入到連續(xù)的內(nèi)存空間中，如果在系統(tǒng)中若干個小的分區(qū)，其總?cè)萘看笥谝b入的程序，但由于它們不相連接，使該程序不能裝入內(nèi)存。例如圖4.9(a)所示.，緊湊后如圖4.9(b)所示。第第4章章 存儲器管

16、理存儲器管理28操作系統(tǒng)用戶程序1用戶程序3用戶程序610kb30kb用戶程序914kb26kb操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序980KBa緊湊前b緊湊后圖4.9 緊湊的示意第第4章章 存儲器管理存儲器管理292動態(tài)重定位動態(tài)重定位 在該方式中，將程序中的相對地址轉(zhuǎn)換為物理地址的工作被推遲到程序指令真正要執(zhí)行時進行。因此，允許作業(yè)在運行過程中移動的技術(shù)，必須獲得硬件地址變換機構(gòu)的支持。即在系統(tǒng)增加一個重定位寄存器，用它來裝入程序在內(nèi)存中的起始地址。程序在執(zhí)行時，真正訪問的內(nèi)存地址是相對地址與重定位寄存器中地址相加而形成的。第第4章章 存儲器管理存儲器管理30Load1,25003

17、65010025005 0 00100002500Load1,250036510000101001250015000+作業(yè)J相對地址重定位寄存器處 理 機 一側(cè)主存存 儲 器 一側(cè)圖 4-10 動態(tài)重定位示意第第4章章 存儲器管理存儲器管理313動態(tài)重定位分區(qū)分配算法動態(tài)重定位分區(qū)分配算法 動態(tài)重定位分區(qū)分配算法，與動態(tài)分區(qū)分配算法基本相同；差別僅在于：在這種分配算法中，增加了“緊湊”功能，通常是找不到足夠大的空閑區(qū)來滿足用戶的需要，進行“緊湊”。然后尋找合適的內(nèi)存空間。第第4章章 存儲器管理存儲器管理324.3 分頁存儲管理方式分頁存儲管理方式 4.3.1頁式系統(tǒng)應(yīng)解決的問題 采用“緊湊”技

18、術(shù)解決按區(qū)分配中存在的碎片問題，是以花費CPU時間為代價換來的。為了尋找解決碎片問題的新途徑，人們很容易想到讓程序不連續(xù)存放，例如，有一個作業(yè)要求投入運行，其程序的地址空間是3KB,而主存當前只有兩個各為1KB和2KB的空閑區(qū)。顯然各空閑區(qū)的大小比該程序的地址空間小，而總和卻相同。這樣就考慮將程序分開存放。放在不相鄰的兩個區(qū)域中。這正是分頁的思想。在分頁存儲管理中，主存被分成一系列的塊，程序的地址空間被分成一系列的頁面。然后將頁面存放在主存塊中。為了便于實現(xiàn)動態(tài)地址變，一般主存的塊和頁面大小相等并為2的冪次。第第4章章 存儲器管理存儲器管理334.3.2分頁存儲管理的基本方法分頁存儲管理的基本

19、方法一、頁面和物理塊 在分頁存儲管理中，將一個進程的邏輯地址空間分成若干個相等的片。稱為頁面或頁。相應(yīng)的，內(nèi)存空間也分成與頁相同的大小的若干個存儲塊，或稱為物理塊或頁框。為它們從0開始依次編號。如圖4.11所示。為進程分配內(nèi)存時，以塊為單位將進程中若干頁分別裝入不相接的塊中。由于進程的最后一頁經(jīng)常裝不滿一塊，而形成不可利用的碎片稱為“頁內(nèi)碎片”。二、頁表 在分頁系統(tǒng)中，允許進程的每一頁離散地存儲在內(nèi)存的任一物理塊中，但系統(tǒng)應(yīng)能保證進程的正確運行。即能在內(nèi)存中找到每個頁面所對應(yīng)的物理塊。為此系統(tǒng)又為每個進程建立一張頁面映象表，簡稱頁表。在進程地址空間的所有頁內(nèi)（0n），依次在頁表中有一頁表項，其

20、中記錄了相應(yīng)頁在內(nèi)存中對應(yīng)的物理塊。見圖的中間部分?？梢婍摫淼淖饔脤崿F(xiàn)了從頁號到物理塊號的地址映象。即使在簡單的分頁系統(tǒng)中，也常在頁表的表項中設(shè)置一存取控制字。用于對存儲塊中內(nèi)容進行保護。第第4章章 存儲器管理存儲器管理34用戶程序0頁1頁2頁3頁4頁5頁n頁頁號0頁1頁2頁3頁4頁5頁n頁2頁3頁6頁8頁9頁頁號塊號內(nèi)存圖4-11頁表第第4章章 存儲器管理存儲器管理35三、虛地址結(jié)構(gòu)三、虛地址結(jié)構(gòu) 如何利用頁表進行地址變換，這和計算機所采用的地址結(jié)構(gòu)有關(guān)。而地址結(jié)構(gòu)又與所選擇的頁面尺寸有關(guān)。比如，當CPU給出的虛地址長度為32位，頁面的大小為4kb時，在分區(qū)系統(tǒng)中的地址格式如圖4.12所示。

21、頁號頁內(nèi)偏移量如圖4-12虛地址結(jié)構(gòu)頁號頁內(nèi)偏移量第第4章章 存儲器管理存儲器管理36四、頁式地址變換四、頁式地址變換 下面圖4.12所示作業(yè)2程序中的一條指令的執(zhí)行過程，來說明頁式系統(tǒng)中的地址變換過程。程序的地址空間中第100號單元處有一條指令為“ mov r1,2500”。這條指令在主存中的實際位置為2148號單元（第2塊100號單元），而這條指令要取的數(shù)123在程序的地址空間中位于2500號單元（第2頁的452號單元）處。它在主存中存于7620號單元（第7塊452號單元）。假設(shè)頁面大小為1kb，機器的地址長度為16位。第第4章章 存儲器管理存儲器管理371KB2KB3KB-10mov 1

22、,2500123mov 1,2500作業(yè)2的進程在CPU上運行 0000100111000100091015mov 1,2500123頁號p頁內(nèi)偏移量02KB4KB7KB256KB-1+頁表始址寄存器0001110111000100091015p=2w=452頁內(nèi)偏移量頁號p012247頁號塊號圖4.12 頁式系統(tǒng)地址變換結(jié)構(gòu)第第4章章 存儲器管理存儲器管理38 當作業(yè)2的相應(yīng)進程在CPU上運行時，操作系統(tǒng)負責把該作業(yè)的頁表在主存中的起始地址（a）送到頁表起始地址寄存器中。以便在進程運行中進行地址變換時由它控制找到該作業(yè)的頁表。 當作業(yè)2的程序執(zhí)行到指令“mov r1,2500”時，CPU給出

23、的操作數(shù)地址為2500，首先由分頁機構(gòu)自動把它分成兩部分，得到頁號p=2,頁內(nèi)相對位移w=452。然后，根據(jù)頁表始址寄存器指示的頁表始地址，以頁號為索引，找到第2頁所對應(yīng)的塊號7。然后，將塊號7和頁內(nèi)位移量w拼接在一起，就形成了訪問主存的物理地址7620。這正是所取數(shù)123所在主存的實際位置。第第4章章 存儲器管理存儲器管理39五、快表五、快表 有一些系統(tǒng)將部分頁表放在快速存儲器中，其余部仍放在主存中。存放頁表部分內(nèi)容的快速存儲器稱相聯(lián)存儲器，也稱為聯(lián)想存儲器。聯(lián)想存儲器中存放的部分頁表稱為“快表”。它的格式如圖4.13所示。這樣的聯(lián)想存儲器一般由8個16個單元組成。它們用來存放正在運行進程的

24、當前最常用的頁號和它相應(yīng)的塊號，并具有進行查找的能力和通常的執(zhí)行過程一樣，只要訪問一次主存，就可以取出指令或存取數(shù)據(jù)。如果所需要查的頁號和聯(lián)想存儲器中所有的頁號不匹配，則地址變換過程還得通過主存中的頁表進行。實采用聯(lián)想存儲器和主存中頁表相結(jié)合的分頁地址變換過程如圖4.13所示。 第第4章章 存儲器管理存儲器管理40頁表始址寄存器a+ba+pa塊號聯(lián)想存儲器不匹配時所有頁表在主存中PWpbbw分頁機構(gòu)物理地址聯(lián)想存儲器圖4-13 帶有快表的分頁地址變換第第4章章 存儲器管理存儲器管理414.3.3 兩級和多級頁表兩級和多級頁表一、兩級頁表 針對難以找到大的存儲空間以存放頁表的問題，可利用頁表進行

25、分頁的辦法，使每個頁面的大小與內(nèi)存物理塊的大小相同，并為它們編號?？梢噪x散地將各個頁面分別放在不同的物理塊中，同樣為每個離散的頁面建立一張頁表，稱為外層頁表。在每個頁表項中記錄物理塊號。如圖4.14所示。第第4章章 存儲器管理存儲器管理4210230121640121141151023第0頁表第1頁表第n頁表012n101110781742外部頁表01214681023012345671141151468內(nèi)存空間圖4-14 帶有快表的分頁地址變換第第4章章 存儲器管理存儲器管理43 由圖可以看出，在頁表的每個表項中存放的是進程的某頁在內(nèi)存中的物理塊號，如第0#頁存放在1號物理塊中，1#頁存放在

26、4#物理塊中。而在外層頁表的每個頁表項中，所存放的是某頁表分頁的首址。如0#頁表存放在第1011#物理塊中。我們可以利用外層頁表和頁表這兩級頁表，來實現(xiàn)從進程的邏輯地址到內(nèi)存地址的變換。第第4章章 存儲器管理存儲器管理44外部頁表寄存器外部頁號外部頁內(nèi)地址頁內(nèi)地址p1p2d +bd外部頁表 頁表 物理地址 圖4-15 具有兩級頁表的地址變換機構(gòu)第第4章章 存儲器管理存儲器管理45 為了地址變換實現(xiàn)，在地址機構(gòu)中同樣需要設(shè)置一個外層頁表寄存器，用于存放外層頁表的始址。并利用邏輯地址的外層頁號，作為外層頁表的索引。從中找到指定頁表分頁的首址。再利用P2作為指定頁表分頁的索引，找到指定的頁表項。其中

27、即含有該頁在內(nèi)存中的物理塊號。用該塊號和頁內(nèi)地址d即可構(gòu)成訪問內(nèi)存的物理地址。圖4.16即為兩級頁表的地址變換機構(gòu)。第第4章章 存儲器管理存儲器管理46二、多級頁表結(jié)構(gòu)二、多級頁表結(jié)構(gòu) 對于32位的機器，采用兩級頁表的結(jié)構(gòu)是合適的。但對于64位的機器，對于二級頁表是否合適，需要簡單的分析。如果頁面大小仍采用4KB即212B,那么還剩52位，假定仍按物理塊的大?。?10位）來劃分頁表，則將所有剩余的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項，即使按220位來劃分頁表。此時，每個頁表分頁將達1MB;外層頁表仍有4G個頁表項。要占用16GB的連續(xù)內(nèi)存空間?？梢?，不論怎樣劃分，其結(jié)果

28、都是不能接受的。第第4章章 存儲器管理存儲器管理474.4 分段存儲管理方式分段存儲管理方式4.4.1分段系統(tǒng)的基本原理一、分段 在分段存儲管理方式中，段是一組邏輯信息集合。例如，把作業(yè)按邏輯關(guān)系加以組織，劃分成若干段，并按這些段來分配內(nèi)存。這些段是主程序段MAIN，子程序段，數(shù)據(jù)段，和堆棧段等。 每個段都有自己的名字和長度，為了實現(xiàn)簡單，通常用一個段號來代替段名。每個段從0開始編號，并采用一段連續(xù)的地址空間，各段長度不同。第第4章章 存儲器管理存儲器管理48 分段系統(tǒng)中的邏輯地址由段號s和段內(nèi)偏移量w組成。其地址結(jié)構(gòu)如圖所示。段號s段內(nèi)偏移量w0151632圖4-16分段系統(tǒng)中的地址結(jié)構(gòu)第第

29、4章章 存儲器管理存儲器管理49二、分頁和分段的主要區(qū)別二、分頁和分段的主要區(qū)別分頁和分段存儲管理系統(tǒng)雖然有很多地方相似，（1）頁是信息的物理單位，分頁是為了實現(xiàn)離散分配，提高內(nèi)存利用率，便于系統(tǒng)管理；而段是信息的邏輯單位，每一段在邏輯上是相對完整的一組信息，如一個函數(shù)，一個過程，一個數(shù)組，分段是為了滿足用戶的需要。（2）分頁式存儲管理的作業(yè)的地址空間是一維的，地址從0開始編號一直到末尾，而分段式存儲管理作業(yè)地址空間是二維的，要識別一個地址，除給了段內(nèi)地址外，還必須給出段號。（3）頁的長度由系統(tǒng)決定，是等長的。而段的長度是由具有相對完整意義上的信息長度決定。第第4章章 存儲器管理存儲器管理50

30、三、基本原理三、基本原理 所謂分段管理，就是管理由若干段組成的作業(yè)，并且按分段來進行存儲分配，由于分段的作業(yè)地址空間是二維的，所以分段的關(guān)鍵在于如何把分段的地址空間變成一維的地址空間。和分業(yè)管理一樣，可以采用動態(tài)重定位技術(shù)進行地址轉(zhuǎn)換。起初系統(tǒng)作業(yè)建立一張段表，每個表目至少有4個數(shù)據(jù)：段號，段長，內(nèi)存始址和存取控制。其中，段長指明段的大小，內(nèi)存始址指明該段在內(nèi)存中的位置，存取控制說明對該段訪問的限制（RWX）。 段地址轉(zhuǎn)換和分頁地址轉(zhuǎn)換得過程基本相同，其大致過程如圖4.17所示：第第4章章 存儲器管理存儲器管理51LBsd+d+頁表長度頁表始址0123段表b0213塊號b塊內(nèi)地址頁 表段表寄存

31、器圖4-21 段頁式系統(tǒng)中的地址轉(zhuǎn)換機構(gòu)第第4章章 存儲器管理存儲器管理63段頁式系統(tǒng)中的地址轉(zhuǎn)換過程大致如下：（1）首先利用段號s，將它與段長TL進行比較，若s頁表長度？CPU檢索快表 頁表項在快表中？訪問頁表頁在內(nèi)存？N缺頁中段Y修改快表修改訪問位和修改位形成物理地址地址變換結(jié)束YNYN越界中斷圖4-23 請求分頁系統(tǒng)的地址變換過程第第4章章 存儲器管理存儲器管理814.6.2.頁面置換算法頁面置換算法1先進先出頁面置換算法（先進先出頁面置換算法（FIFO） FIFO，即先進先出算法，這是一種最簡單的置換算法。當需要置換一個頁面時，總是置換最老即進入內(nèi)存時間最長的那個頁面。 下例中，我們設(shè)

32、某進程的最大頁面數(shù)為3，則對于所示頁面的走向，其頁面失效的次數(shù)為15，頁面失效率為3/4。FIFO 置換算法是易于理解和實行的。實行時，只要建立一個FIFO隊列，并規(guī)定最新進入的頁面總排在隊列最前，而當需要置換時，總是把當前隊尾的那個頁面換掉。第第4章章 存儲器管理存儲器管理82頁面走向7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1頁面置換770701201231230403701702712012013023423420圖 4-32 頁面置換算法 然而，F(xiàn)IFO算法有可能產(chǎn)生異?，F(xiàn)象。所謂異常，是指在相同的頁面走向下當分給某一進程的頁面數(shù)增多時，頁面失效不但不

33、降，反而增加這種情況。第第4章章 存儲器管理存儲器管理832最近最久未使用頁面置換算法（最近最久未使用頁面置換算法（LRU）算法）算法該算法在出現(xiàn)缺頁中斷時，總是選擇最近一段時間內(nèi)，最長時間沒有被訪問過的頁面，將它喚出外存。 假定現(xiàn)有一進程所訪問頁面的頁號序列為：4，7，0，7，1，0，1，2，1，2，6。隨著進程的訪問，棧中頁面號的變化情況如圖4.33所示，當訪問頁面6時，發(fā)生缺頁，此時頁面4是最近最久未被訪問的頁，應(yīng)將它置換出內(nèi)存。頁面置換情況如下圖所示。444444444477070717001711070721207126210704-33 用棧保存當前使用頁面時棧的變化情況843最佳

34、置換算法（最佳置換算法（OPT） 最佳置換算法是一種理論上的理想算法。采用最佳置換算法可以保證最低的缺頁率。例：已知頁面走向為：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系統(tǒng)為該作業(yè)分配三個內(nèi)存塊。求頁面淘汰順序。頁面置換過程如圖4-34所示。 031700430223 212017017707012432032017012012034-34 利用最佳頁面置換算法時的置換圖854.7 請求分段存儲管理請求分段存儲管理4.7.1請求分段的實現(xiàn)請求分段的實現(xiàn) 1段表機制段表機制 請求分段式管理中，用的主要數(shù)據(jù)結(jié)構(gòu)是段表。段表結(jié)構(gòu)如下：段名段長段的基址存取方式訪

35、問字段A修改字段M存在位P增補位外存起址第第4章章 存儲器管理存儲器管理86 在段表項中，除了段名，段長，段在內(nèi)存的起始地址外，還增加了以下幾項：（1）存取方式。用于標識本分段的存取屬性是執(zhí)行、只讀還是可讀可寫。（2）訪問字段A。其含義與請求分段的相應(yīng)字段相同。用于記錄被訪問段的頻率。（3）修改位M。表示該頁進入內(nèi)存后是否被修改過。（4）存在位P。指示本段是否已調(diào)入內(nèi)存。（5）增補位。表示該段在運行過程中是否動態(tài)增長。（6）外存始址。指示本段在外存中的起始地址，即起始盤塊號。第第4章章 存儲器管理存儲器管理873缺段中斷機構(gòu)缺段中斷機構(gòu) 在請求分段系統(tǒng)中，采用的是請求調(diào)段策略。每當進程要訪問的

36、段不在內(nèi)存時，就產(chǎn)生缺頁中斷。缺段中斷的處理：（1）判斷虛段S不在內(nèi)存（2）讓請求進程處于阻塞狀態(tài)（3）判斷一下內(nèi)存中是否有空閑區(qū)域（4）若有空閑區(qū)域，則從外存讀入段S，修改段表和空閑區(qū)域表，喚醒請求進程，結(jié)束。（5）若沒有空閑區(qū)域，判總的空閑區(qū)是否滿足，若滿足，則空閑區(qū)合并，調(diào)入段S，修改段表。若總的空閑區(qū)不夠，則淘汰一個或幾個段，形成一個合適的空閑區(qū)，再調(diào)入段S。缺段中斷流程圖如4.35所示：第第4章章 存儲器管理存儲器管理88形成合適的空區(qū)虛段s不在內(nèi)存阻塞請求進程 從內(nèi)存讀入段S容量滿足嗎？內(nèi)存有空閑區(qū)嗎？修改段表及內(nèi)存空區(qū)鏈喚醒請求進程返回YNYN淘汰合適的段形成空區(qū)4-35 缺段中

37、斷流程圖第第4章章 存儲器管理存儲器管理893地址變換機構(gòu)地址變換機構(gòu) 請求分段系統(tǒng)的地址變換機構(gòu)，是在分段系統(tǒng)地址變換的基礎(chǔ)上形成的。當所要訪問的段不在內(nèi)存時。將所缺的段調(diào)入內(nèi)存，并修改段表，再利用段表進行地址變換。變換過程如下：（1）有一個訪問地址格式為S|w,其中S為段，w為偏移量。（2）若w的值大于段長，則進行越界中斷處理。（3）若w的值小于段長，則檢查是否是合法的存取方式，不是，則進行分段保護中斷處理。（4）若其它兩種情況合法，就判斷S是否在主存，在，則修改訪問位，形成主存的地址段的始址加上偏移量。第第4章章 存儲器管理存儲器管理90地址變換機構(gòu)流程圖如下所示：Yw小于等于段長？NY

38、訪問s|w符合存取方式？分段越界中斷處理N分段保護中斷處理段 S 在主存？YN缺段中段處理修改訪問字位，如寫訪問，置1形成訪問主存地址返回圖4-35請求分段系統(tǒng)的地址變換過程第第4章章 存儲器管理存儲器管理914.7.2共享與保護共享與保護 分段存儲管理便于實現(xiàn)分段的共享和保護。也簡單的介紹了實現(xiàn)分段共享的方法。分段共享采用以下幾種方法。1段表段表 為了實現(xiàn)分段共享，可在系統(tǒng)中配置一張段表，所有的共享段在段表中占一項。段表項的結(jié)構(gòu)如圖4-24所示。第第4章章 存儲器管理存儲器管理92段名段長內(nèi)存始址狀態(tài)外存始址共享進程計數(shù)COUNT狀態(tài)進程名進程號段號存儲控制圖 4-24 共享段表第第4章章

39、存儲器管理存儲器管理93 (1)共享進程計熟count 共享段僅為一個進程所需要。當進程不再需要該段時，可釋放該段。并收回該段所占居的內(nèi)存空間。為了記錄有多少個進程需要共享該分段，特設(shè)置了一個整型變量count。(2)存取控制字段 對于一個共享段，應(yīng)給不同的進程以不同的存取權(quán)限。例如，對于文件主，通常允許它讀和寫；而對其它進程，只允許讀或執(zhí)行。(3)段號 對于同一個共享段，不同的進程可以使用不同的段號去共享該段。第第4章章 存儲器管理存儲器管理942共享段的分配與回收共享段的分配與回收（1）共享段的分配 由于共享段是供多個進程共享，因此，對共享段的內(nèi)存分配方式和非共享段的內(nèi)存分配方式是一樣的。

40、在分配共享段時，對第一個使用該段的進程，系統(tǒng)將該共享段調(diào)入內(nèi)存，為共享段加一表項，填寫有關(guān)表項，把 count加1.當其它的段想共享該段時，不再需要調(diào)入內(nèi)存，只須加一表項，填入該共享段的物理地址；在共享段的段表中，填上進程名，存取控制，再執(zhí)行count=count+1 操作，表明正有兩個進程共享該段。（2）共享段的回收 當共享此段的某進程不再需要它時，該將該段釋放。包括取消在該進程段表中共享該段所對應(yīng)的表項。以及執(zhí)行count:=count-1操作。若減1結(jié)果為0,則有該系統(tǒng)收回該共享段的物理地址。第第4章章 存儲器管理存儲器管理953分段保護分段保護 在分段系統(tǒng)中，由于每個分段是獨立的，因此

41、比較容易實現(xiàn)信息保護。目前，采用以下幾種方式保護信息。（1）越界檢查 在段表寄存器中，存放段表長度信息；同樣，在段表中也為每個段表設(shè)置段長字段，將邏輯地址空間的段號和段表長度進行比較，若等于或大于段表長度，則發(fā)出越界中斷信號，其次還要檢查段內(nèi)地址是否等于或大于段長。若大于段長，將產(chǎn)生越界中斷信號，從而保證進程有自己的地址空間。第第4章章 存儲器管理存儲器管理96（2）存取控制檢查 在段表的每個表項中，設(shè)置一個存取控制字段，通常的訪問方式有（a）只讀。只允許程序?qū)υ摱沃械某绦蚝蛿?shù)據(jù)進行訪問。（b）只執(zhí)行。只允許執(zhí)行，但不允許讀寫。（c）讀/寫。允許程序?qū)υ摱芜M行讀寫控制。不同的訪問對象，賦予不同

42、的權(quán)限。97(3)環(huán)保護機構(gòu) 它是一種較完善的保護機構(gòu)。在該機制中規(guī)定：低編號的環(huán)具有較高的優(yōu)先權(quán)。OS居于0環(huán)內(nèi)；某些重要的系統(tǒng)軟件占據(jù)中間環(huán)。而一般的應(yīng)用程序位于外環(huán)。程序訪問和調(diào)用的規(guī)則遵循：（a）一個程序可以訪問駐留在相同環(huán)或較低環(huán)中的數(shù)據(jù)。（b）一個程序可以調(diào)用駐留在相同環(huán)或高特權(quán)環(huán)中的服務(wù)。第第4章章 存儲器管理存儲器管理984.8 Linux系統(tǒng)的內(nèi)存管理方法系統(tǒng)的內(nèi)存管理方法4.8.1 Linux的分頁管理機制 在Linux中，每個用戶進程都可以訪問4GB的線性虛擬內(nèi)存空間。其中從0到 3GB的虛擬地址空間是用戶空間，用戶進程可以直接對其進行訪問。從3GB到4GB的虛擬內(nèi)存地址

43、空間為內(nèi)核態(tài)空間，存放僅供內(nèi)核態(tài)訪問的代碼和數(shù)據(jù)，用戶態(tài)進程不可訪問。所有的進程從3GB到4GB 的虛擬空間是一樣的，有同樣的頁目錄項，同樣的頁表，對應(yīng)同樣的物理內(nèi)存段。Linux以此方式讓內(nèi)核態(tài)進程共享代碼段和數(shù)據(jù)段。 99內(nèi)核態(tài)虛擬空間從3GB到3GB+4MB的一段，被映射到物理空間0到4MB。Linux 采用“按需調(diào)頁”技術(shù)管理虛擬內(nèi)存。標準Linux的虛存頁表應(yīng)為三級頁表，依次為頁目錄（Pgd,page Directory）、中間頁目錄（PMD,page Middlie Directory）和頁表(PTE,PageTable) 。 1004.8.2虛存段的組織與管理 用戶進程實際可申請

44、的虛存空間為0至3GB。在用戶進程創(chuàng)建時，已由系統(tǒng)調(diào)用fork()的執(zhí)行函數(shù)do_fork()將內(nèi)核的代碼段和數(shù)據(jù)段映射到3GB以后的虛存空間，供內(nèi)核態(tài)進程訪問。所有進程的3GB到4GB的虛存空間的映象都是相同的。以此方式共享代碼段和數(shù)據(jù)段。 1014.8.34.8.3內(nèi)存的共享和保護內(nèi)存的共享和保護Linux中內(nèi)存共享以頁表的形式實現(xiàn)，共享該頁的各進程的頁表表項直接指向共享頁。這種結(jié)構(gòu)不需要設(shè)立共享頁表，節(jié)約內(nèi)存的占用，但效率較低。當共享頁狀態(tài)發(fā)生變化時，共享該頁的各進程的頁表均需要修改，要多次訪問頁表。 1024.8.4物理空間管理 盡管Linux采用虛擬存儲管理策略，有些申請仍然需要直接

45、分配物理空間。例如，為剛創(chuàng)建的進程分配頁目錄，為裝入進程的代碼段分配空間，為I/O操作準備緩沖區(qū)等等。物理內(nèi)存以頁幀為單位，頁幀的長度固定，等于頁長，對于INTEL CPU缺省為4KB字節(jié)。Linux對物理內(nèi)存的管理通過mem_map表描述。mem_map在系統(tǒng)初始化時，由free_area_init()函數(shù)創(chuàng)建。 1034.8.5空閑物理內(nèi)存管理 在物理內(nèi)存低端，緊跟mem_map表的bitmap表以位示圖方式記錄了所有物理內(nèi)存的空閑情況。與men_map一樣，bitmap表在系統(tǒng)初始化時有free_area_init()函數(shù)創(chuàng)建。1044.8.6態(tài)內(nèi)內(nèi)核存的申請與釋放 內(nèi)核態(tài)內(nèi)存是用來存放Linux內(nèi)核系統(tǒng)數(shù)據(jù)結(jié)構(gòu)的內(nèi)存區(qū)域，處