《Linux操作系統(tǒng)原理與應(yīng)用》課件第5章

第5章存儲管理

5.1存儲管理概述5.2存儲管理方案5.3虛擬存儲管理5.4Linux的存儲管理習(xí)題

5.1存儲管理概述

操作系統(tǒng)中用于管理內(nèi)存空間的模塊稱為內(nèi)存管理模塊，它負(fù)責(zé)內(nèi)存的全部管理工作，具體地說就是要完成4個(gè)功能，即存儲空間的分配、存儲地址的變換、存儲空間的保護(hù)以及存儲空間的擴(kuò)充。5.1.1內(nèi)存的分配與回收

內(nèi)存分配是為進(jìn)入系統(tǒng)準(zhǔn)備運(yùn)行的程序分配內(nèi)存空間，內(nèi)存回收是當(dāng)程序運(yùn)行結(jié)束后回收其所占用的內(nèi)存空間。為實(shí)現(xiàn)此功能，系統(tǒng)須跟蹤并記錄所有內(nèi)存空間的使用情況，按照一定的算法為進(jìn)程分配和回收內(nèi)存空間。

存儲分配方案主要包括以下要素：

(1)描述存儲分配的數(shù)據(jù)結(jié)構(gòu)：系統(tǒng)需采用某種數(shù)據(jù)結(jié)構(gòu)(表格、鏈表或隊(duì)列等)來登記當(dāng)前內(nèi)存使用情況以及空閑區(qū)的分布情況，供存儲分配程序使用。在每次分配或回收操作后，系統(tǒng)都要相應(yīng)地修改這些數(shù)據(jù)結(jié)構(gòu)以反映這次分配或回收的結(jié)果。

(2)實(shí)施分配的策略：確定內(nèi)存分配和回收的算法。好的算法應(yīng)既能滿足進(jìn)程的運(yùn)行要求，又能充分利用內(nèi)存空間。

分配策略及相關(guān)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)直接決定存儲空間的利用率以及存儲分配的效率，因而對系統(tǒng)的整體性能有很大的影響。5.1.2地址變換

由于用戶在編寫程序時(shí)無法預(yù)先確定程序在內(nèi)存中的具體位置，所以只能采用邏輯地址進(jìn)行編程。而當(dāng)程序進(jìn)入內(nèi)存后，必須把程序中的邏輯地址轉(zhuǎn)換為程序所在的實(shí)際內(nèi)存地址。這一轉(zhuǎn)換過程稱為存儲空間的地址變換，或稱為地址映射。地址變換是由內(nèi)存管理模塊與硬件的地址變換機(jī)構(gòu)共同完成的。

1.地址的概念

1)符號地址

在用高級語言編寫的源程序中，我們使用符號名(變量名、函數(shù)名、語句標(biāo)號等)來表示操作對象或控制的轉(zhuǎn)移地址。比如用變量名代表一個(gè)存儲單元、用函數(shù)名代表函數(shù)的入口地址、用語句標(biāo)號代表跳轉(zhuǎn)地址等。這些符號名的集合稱為符號名空間。因此，高級語言程序使用的地址空間是符號名空間，編程者不需考慮程序代碼和數(shù)據(jù)的具體存放地址。

例如，以下所示的是一個(gè)C源程序的片段：

main()

{inti=1;

…

i++;

…

}

此源程序中沒有具體地址，只有符號名。這里main代表的是程序的入口地址，i代表的是一個(gè)數(shù)據(jù)的存放地址。

2)邏輯地址

編譯程序?qū)⒃创a中的語句逐條翻譯為機(jī)器指令，為每個(gè)變量分配存儲單元，并用存儲單元的地址替換變量名。這些指令和數(shù)據(jù)順序存放在一起，從0開始編排地址，形成目標(biāo)代碼。目標(biāo)代碼所占有的地址范圍稱為邏輯地址空間，范圍是0～n-1，n為目標(biāo)代碼的長度。邏輯地址空間中的地址稱為邏輯地址，或稱為相對地址。在訪問內(nèi)存的指令中用邏輯地址來指定一個(gè)操作數(shù)的地址，在跳轉(zhuǎn)指令中用邏輯地址來表示要跳轉(zhuǎn)到的那條指令的地址。

例如，對上例所示的源程序進(jìn)行編譯，生成的目標(biāo)代碼的反匯編結(jié)果如下：

00000000: …

…

0000004B: LDS R24,0x0060 ;從0060地址取數(shù)據(jù)，加載到R24

寄存器

0000004D: ADIW R24,0x01 ;R24寄存器內(nèi)容加1

0000004E: STS 0x0060,R24 ;將R24寄存器內(nèi)容寫回0060地址

…

00000060: 0x0001 ;i變量的存儲單元

…左側(cè)列出的是指令和數(shù)據(jù)的邏輯地址，從0地址開始順序排列。i變量被分配到邏輯地址0060處，i++語句被譯為LDS、ADIW和STS3條指令，它們排在邏輯地址004B、004D和004E處。在目標(biāo)代碼的指令中已看不到符號名了，而代之以具體的地址值。如LDS和STS指令的操作數(shù)地址是0060，表示要到這個(gè)地址(也就是i變量)讀/寫數(shù)據(jù)。

3)物理地址

物理內(nèi)存由一系列的內(nèi)存單元組成，這些存儲單元從0開始按字節(jié)編址，稱為內(nèi)存地址。當(dāng)目標(biāo)程序加載到內(nèi)存中時(shí)，它所占據(jù)的實(shí)際內(nèi)存空間就是它的物理存儲空間，物理空間中的地址稱為物理地址，或稱為絕對地址。

每次程序加載時(shí)所獲得的實(shí)際地址空間取決于系統(tǒng)當(dāng)時(shí)的運(yùn)行狀態(tài)，因而是不確定的。但物理地址空間不會是從0開始的，因?yàn)橄到y(tǒng)內(nèi)存的低端地址通常被操作系統(tǒng)占用。由此可看出，程序的邏輯地址空間與物理地址空間是不同的。由于編譯程序無法預(yù)知程序執(zhí)行時(shí)的實(shí)際內(nèi)存地址，所以目標(biāo)程序中的地址都是從0開始的邏輯地址，而實(shí)際地址只有在程序加載時(shí)才能得知。假設(shè)上面例子的程序加載到內(nèi)存，它分配到的內(nèi)存地址空間是從1024(即十六進(jìn)制的0x0400)開始的，則程序中各條指令和變量的地址是原來的相對地址加上1024這個(gè)基址。因此程序在內(nèi)存的起始地址為0x0400，LDS、ADIW和STS3條指令的絕對地址分別為0x044B、0x044D和0x044E，i變量的絕對地址為0x0460。

圖5-1所示是關(guān)于內(nèi)存地址的示意圖。仍以前面的程序?yàn)槔?，源程序中的i變量是用符號名i標(biāo)識的一個(gè)存儲單元，它沒有具體的地址值。i++語句的操作就是對這個(gè)存儲單元進(jìn)行的操作。編譯時(shí)，編譯程序?yàn)閕分配了具體的存儲單元，并用該單元的編號地址96(0x0060)替換掉所有i符號名。程序在加載時(shí)獲得實(shí)際的內(nèi)存空間。如果得到的內(nèi)存空間的起始地址是1024，則程序中的相對地址96單元就是實(shí)際內(nèi)存的1120(0x0460)單元。圖5-1內(nèi)存地址的概5FF5

2.地址變換

用戶編程時(shí)只能使用邏輯地址，而CPU執(zhí)行指令時(shí)必須指定物理地址，因此必須在指令執(zhí)行前進(jìn)行地址變換，將指令中的邏輯地址轉(zhuǎn)換為CPU可直接尋址的物理地址，這樣才能保證CPU訪問到正確的存儲單元。

假設(shè)上面的例子程序加載到內(nèi)存，它分配到的內(nèi)存地址空間是從1024開始的，則程序中各條指令和變量的地址都是原來的相對地址加上1024。為了適應(yīng)這個(gè)變化，指令中引用的操作數(shù)地址也應(yīng)進(jìn)行相應(yīng)的調(diào)整。下面所示是經(jīng)過地址變換后的目標(biāo)代碼，粗體部分為變換后的操作數(shù)的絕對地址。

00000400: …

…

0000044B:

LDS R24,0x0460 ;從0460地址取數(shù)據(jù)，加載到R24

寄存器

0000044D:

ADIW R24,0x01 ;R24寄存器內(nèi)容加1

0000044E:

STS 0x0460,R24 ;將R24寄存器內(nèi)容寫回0460地址

…

00000460: 0x0001 ;i變量的存儲單元

…地址變換的方式有兩種：

(1)靜態(tài)地址變換：程序在裝入內(nèi)存前一次性完成地址轉(zhuǎn)換。程序裝入內(nèi)存后即可直接執(zhí)行。DOS系統(tǒng)中的程序就是采用這種方式加載的。采用靜態(tài)地址變換的程序在內(nèi)存中始終處于最初加載的位置，不可移動。

(2)動態(tài)地址變換：程序在裝入內(nèi)存時(shí)不進(jìn)行地址變換，而是保持指令中的邏輯地址不變。在程序執(zhí)行過程中，每執(zhí)行一條指令時(shí)，如果指令中用到了邏輯地址，地址變換機(jī)構(gòu)就會自動進(jìn)行地址轉(zhuǎn)換，將邏輯地址變換為實(shí)際地址。例如，當(dāng)CPU取到LDSR24,0x0060指令時(shí)，先將0060這個(gè)邏輯地址變換為絕對地址0460，然后再執(zhí)行LDSR24,0x0460指令。

動態(tài)地址變換的特點(diǎn)是程序在內(nèi)存中可移動、可共享。但是動態(tài)地址變換需要有硬件的支持，不過目前PC機(jī)以上檔次的計(jì)算機(jī)都具有動態(tài)地址變換的硬件機(jī)構(gòu)。5.1.3內(nèi)存的保護(hù)

內(nèi)存保護(hù)的含義是要確保每個(gè)進(jìn)程都在自己的地址空間中運(yùn)行，互不干擾，尤其是不允許用戶進(jìn)程訪問操作系統(tǒng)的存儲區(qū)域。對于允許多個(gè)進(jìn)程共享的內(nèi)存區(qū)域，每個(gè)進(jìn)程也只能按自己的權(quán)限(只讀或讀/寫)進(jìn)行訪問，不允許超越權(quán)限進(jìn)行訪問。

許多程序錯(cuò)誤都會導(dǎo)致地址越界，比如使用了未賦值的“野”指針或空指針等。還有一些程序代碼則屬于惡意的破壞。存儲保護(hù)的目的是為了防止因?yàn)楦鞣N原因?qū)е碌某绦蛟浇绾驮綑?quán)行為。為此，系統(tǒng)必須設(shè)置內(nèi)存保護(hù)機(jī)制，對每條指令所訪問的地址進(jìn)行檢查。一旦發(fā)現(xiàn)非法的內(nèi)存訪問就會中斷程序的運(yùn)行，由操作系統(tǒng)進(jìn)行干預(yù)?，F(xiàn)代操作系統(tǒng)都具有良好的存儲保護(hù)功能，因此程序錯(cuò)誤通常只會導(dǎo)致程序的異常結(jié)束，而不會造成系統(tǒng)的崩潰。常用的存儲保護(hù)措施有：

(1)界限保護(hù)：在CPU中設(shè)置界限寄存器，限制進(jìn)程的活動空間。

(2)保護(hù)鍵：為共享內(nèi)存區(qū)設(shè)置一個(gè)讀/寫保護(hù)鍵，在CPU中設(shè)置保護(hù)鍵開關(guān)，它表示進(jìn)程的讀/寫權(quán)限。只有進(jìn)程的開關(guān)代碼和內(nèi)存區(qū)的保護(hù)鍵匹配時(shí)方可進(jìn)行訪問。

(3)保護(hù)模式：將CPU的工作模式分為用戶態(tài)與核心態(tài)。核心態(tài)下的進(jìn)程可以訪問整個(gè)內(nèi)存地址空間，而用戶態(tài)下的進(jìn)程只能訪問在界限寄存器所規(guī)定范圍內(nèi)的空間。5.1.4內(nèi)存的擴(kuò)充

盡管內(nèi)存容量不斷提高，但相比應(yīng)用規(guī)模的增長來說，內(nèi)存總是不夠的。因此，內(nèi)存擴(kuò)充始終是存儲管理的一個(gè)重要功能。

“擴(kuò)充”存儲器空間的基本思想是借用外存空間來擴(kuò)展內(nèi)存空間，方法是讓程序的部分代碼進(jìn)入內(nèi)存，其余駐留在外存，在需要時(shí)再調(diào)入內(nèi)存。主要的實(shí)現(xiàn)方法有以下3種：

1.覆蓋技術(shù)

覆蓋(overlay)技術(shù)的原理是將一個(gè)程序劃分為幾個(gè)模塊。程序的必要模塊(主控或常用功能)常駐內(nèi)存，其余模塊共享一個(gè)或幾個(gè)存儲空間。它們平時(shí)駐留在外存中，在需要時(shí)才裝入內(nèi)存，覆蓋掉某個(gè)暫時(shí)不用的模塊。

覆蓋技術(shù)的缺點(diǎn)是必須在編程時(shí)對程序進(jìn)行模塊劃分，并確定程序模塊之間的覆蓋關(guān)系。這無疑增加了編程的復(fù)雜度。

2.交換技術(shù)

在多個(gè)程序并發(fā)執(zhí)行時(shí)，往往有一些程序因等待某事件而暫時(shí)不能運(yùn)行。如果將暫時(shí)不能執(zhí)行的程序換到外存中，就可以獲得空閑內(nèi)存空間來運(yùn)行別的程序。這就是交換(swapping)技術(shù)的思想。與覆蓋技術(shù)不同的是，交換是以進(jìn)程為單位進(jìn)行的。

交換技術(shù)的優(yōu)點(diǎn)是增加了可并發(fā)運(yùn)行的程序數(shù)目，且對用戶的程序結(jié)構(gòu)沒有要求。其缺點(diǎn)是對整個(gè)進(jìn)程進(jìn)行的換入、換出操作往往需要花費(fèi)大量的CPU時(shí)間。

3.虛擬存儲器

以上兩種存儲擴(kuò)充技術(shù)都不能稱為虛擬存儲技術(shù)，因?yàn)樵谟脩?編程者)眼里看到的還是實(shí)際大小的內(nèi)存。虛擬存儲(virtualmemory)的原理是只將程序的部分代碼調(diào)入內(nèi)存，其余駐留在外存空間中，在需要時(shí)調(diào)入內(nèi)存。程序代碼的換入和換出完全由系統(tǒng)動態(tài)地完成，用戶察覺不到。因此，用戶看到的是一個(gè)比實(shí)際內(nèi)存大得多的“虛擬內(nèi)存”。

虛擬存儲技術(shù)的特點(diǎn)是方便用戶編程，存儲擴(kuò)充的性能也是最好的。關(guān)于虛擬存儲器的介紹見5.3節(jié)。

5.2存儲管理方案

隨著操作系統(tǒng)的發(fā)展，內(nèi)存管理技術(shù)也在不斷地發(fā)展著。本節(jié)將簡要介紹各種存儲管理方案的技術(shù)和特點(diǎn)。5.2.1單一連續(xù)存儲管理

最簡單的存儲器管理方案是在內(nèi)存中只存放一個(gè)應(yīng)用程序，這個(gè)應(yīng)用程序和操作系統(tǒng)共享存儲器。這是最簡單的一種存儲管理方式，只能用于單用戶、單任務(wù)的操作系統(tǒng)中。DOS系統(tǒng)采用的就是這種方式。

單一連續(xù)存儲管理方式的分配策略是將內(nèi)存分成兩個(gè)分區(qū)，稱為系統(tǒng)區(qū)和用戶區(qū)，如圖5-2所示。系統(tǒng)區(qū)僅供操作系統(tǒng)和硬件使用，用戶區(qū)供給用戶程序使用，它只能容納一個(gè)程序。地址變換方式是靜態(tài)地址變換，即程序加載前一次性完成全部地址變換。存儲保護(hù)措施采用界限保護(hù)，即不允許用戶程序訪問操作系統(tǒng)區(qū)域，否則就發(fā)生地址越界中斷。存儲擴(kuò)充的手段只能采用覆蓋技術(shù)。圖5-2單一連續(xù)存儲分配示意圖單一連續(xù)存儲管理的特點(diǎn)是簡單，它只適用于單道程序系統(tǒng)。5.2.2分區(qū)存儲管理

多道程序系統(tǒng)的出現(xiàn)要求內(nèi)存中能同時(shí)容納多個(gè)程序，分區(qū)管理方案因而誕生。分區(qū)分配是多道程序系統(tǒng)最早使用的一種管理方式，其思想是將內(nèi)存劃分為若干個(gè)分區(qū)，操作系統(tǒng)占用其中一個(gè)分區(qū)，其他分區(qū)由用戶程序使用，每個(gè)分區(qū)容納一個(gè)用戶程序。

1.簡單分區(qū)管理

1)分區(qū)分配策略

最初的分區(qū)劃分方法是固定分區(qū)，即系統(tǒng)把內(nèi)存靜態(tài)地劃分為若干個(gè)固定大小的分區(qū)。當(dāng)一個(gè)進(jìn)程被建立時(shí)，系統(tǒng)按其程序的大小為其分配一個(gè)足夠大的分區(qū)。由于分區(qū)大小是預(yù)先劃分好的，通常會大于程序的實(shí)際尺寸，因此分區(qū)內(nèi)余下的空閑空間就被浪費(fèi)掉了。圖5-3(a)所示為固定分區(qū)的內(nèi)存分配方式。

對固定分區(qū)分配策略進(jìn)行改進(jìn)就產(chǎn)生了可變分區(qū)分配。它的思想是：在程序調(diào)入內(nèi)存時(shí)，按其實(shí)際大小動態(tài)地劃分分區(qū)。這種量體裁衣的分配方式避免了分區(qū)內(nèi)空間的浪費(fèi)。圖5-3(b)所示為可變分區(qū)的內(nèi)存分配方式。圖5-3分區(qū)存儲分配示意圖分區(qū)分配的方法是：系統(tǒng)設(shè)置兩個(gè)表格來記錄內(nèi)存空間的使用情況。一個(gè)是已分配分區(qū)表，說明各個(gè)已用分區(qū)的分區(qū)號、起始地址和大小等。另一個(gè)是空閑區(qū)表，說明內(nèi)存中空閑區(qū)的分布位置和大小。當(dāng)為進(jìn)程分配空間時(shí)，系統(tǒng)在空閑區(qū)表中找到一個(gè)合適的空閑區(qū)，按進(jìn)程需要的大小為它劃分出一個(gè)分區(qū)，從空閑分區(qū)表中扣除，加入到已分配分區(qū)表中。釋放分區(qū)時(shí)將其從已分配分區(qū)表中刪除，插入或并入空閑區(qū)表中。

2)分區(qū)分配的碎片問題

分區(qū)分配的主要問題是存儲“碎片”。碎片(fragment)是無法被利用的空閑存儲空間。固定分區(qū)存在“內(nèi)部碎片”問題，即遍布在各個(gè)分區(qū)內(nèi)的零碎剩余空間?？勺兎謪^(qū)存在“外部碎片”問題，即隨著進(jìn)程不斷地進(jìn)入和退出系統(tǒng)，一段時(shí)間后，內(nèi)存中的空閑分區(qū)會變得支離破碎，這些碎片空間的總和可能足夠大，但因?yàn)椴贿B續(xù)，所以不能被利用。圖描述了外部碎片的產(chǎn)生過程。假設(shè)系統(tǒng)最初有進(jìn)程1、2和3在運(yùn)行，它們的映像的大小分別為320?KB、224?KB和288?KB，所占據(jù)的內(nèi)存分區(qū)如圖5-4(a)所示。一段時(shí)間后，進(jìn)程2運(yùn)行結(jié)束退出，進(jìn)程4進(jìn)入內(nèi)存，它的大小是128?KB，此時(shí)內(nèi)存的分區(qū)情況如圖(b)所示。又一段時(shí)間后，進(jìn)程1運(yùn)行結(jié)束退出，進(jìn)程5進(jìn)入內(nèi)存，它的大小是220?KB。此時(shí)內(nèi)存的分區(qū)情況如圖5-4(c)所示。當(dāng)一個(gè)新的300?KB的進(jìn)程6想要進(jìn)入系統(tǒng)運(yùn)行時(shí)，內(nèi)存中的空閑空間的總數(shù)雖然足夠，但因?yàn)槭撬槠?，所以系統(tǒng)暫時(shí)無法接納這個(gè)作業(yè)。圖5-4可變分區(qū)的存儲碎片

2.可重定位分區(qū)管理

可重定位分區(qū)管理的思想是在可變分區(qū)分配的基礎(chǔ)上利用存儲緊縮技術(shù)來消除碎片。

1)存儲緊縮技術(shù)

解決外部碎片問題的一個(gè)有效方法是存儲緊縮技術(shù)。存儲緊縮(compaction)的思想是采用動態(tài)地址變換，使程序在內(nèi)存中可以移動。當(dāng)內(nèi)存出現(xiàn)碎片現(xiàn)象時(shí)，系統(tǒng)將暫停所有進(jìn)程的運(yùn)行，將各個(gè)進(jìn)程的分區(qū)向內(nèi)存一端移動，從而將碎片合并成一個(gè)連續(xù)的存儲空間。緊縮完成后，程序繼續(xù)運(yùn)行。

2)動態(tài)地址變換過程

簡單分區(qū)采用靜態(tài)地址變換方式，程序裝入內(nèi)存后就不能再移動了。因?yàn)槌绦蛞苿雍?，指令和?shù)據(jù)的存放地址變了，而指令中的操作數(shù)地址卻沒有相對地變化，導(dǎo)致指令不能正確地尋址。為了使程序在內(nèi)存中可以移動，就必須采用動態(tài)地址變換。

可重定位分區(qū)的動態(tài)地址變換過程如圖5-5所示。圖5-5可重定位分區(qū)的地址變換過程

CPU中設(shè)置了一對表示程序存儲空間界限的寄存器，長度寄存器中存放的是程序的長度，基址寄存器中存放的是程序所占內(nèi)存空間的起始地址。每個(gè)進(jìn)程的PCB中都有一對相應(yīng)的寄存器值，當(dāng)進(jìn)程得到CPU準(zhǔn)備運(yùn)行時(shí)，現(xiàn)場恢復(fù)操作會將這兩個(gè)值裝入寄存器中。當(dāng)CPU取到一條指令時(shí)，硬件地址變換機(jī)構(gòu)將邏輯地址與基址寄存器內(nèi)容相加就可得到實(shí)際內(nèi)存地址。

每次存儲緊縮完成后，系統(tǒng)根據(jù)程序的新位置更新各個(gè)進(jìn)程的基址值。這樣，當(dāng)程序重新運(yùn)行時(shí)，CPU將按新的基址來做地址轉(zhuǎn)換，程序的運(yùn)行不會受到任何影響。

3.分區(qū)的保護(hù)與擴(kuò)充

進(jìn)程只能在自己的分區(qū)內(nèi)活動。存儲保護(hù)的方式是上下界地址保護(hù)，即進(jìn)程運(yùn)行時(shí)，它的空間上下界地址被加載到CPU的界限(或基址/長度)寄存器中。如果進(jìn)程試圖訪問超越分區(qū)上下界的地址，則會引起地址越界中斷，使進(jìn)程結(jié)束。

在分區(qū)管理中，用戶程序的大小受可用分區(qū)大小的限制?？梢允褂酶采w或交換技術(shù)來實(shí)現(xiàn)內(nèi)存擴(kuò)充。

總的來說，分區(qū)管理的特點(diǎn)是簡單、支持多道程序，但有碎片問題?？芍囟ㄎ环謪^(qū)管理提供了解決碎片問題的一種途徑，因而提高了存儲空間的利用率。但存儲緊縮比較耗時(shí)，在進(jìn)行存儲緊縮時(shí)，所有用戶進(jìn)程都要停止運(yùn)行，系統(tǒng)為此付出的代價(jià)過大。5.2.3頁式存儲管理

產(chǎn)生碎片問題的根源在于程序要求連續(xù)的存儲空間，而解決這一問題的根本措施就是突破這一限制，使程序代碼可以分散地存放在不同的存儲空間中。分散存儲使得內(nèi)存中每一個(gè)空閑的區(qū)域都可以被程序利用，這就是頁式存儲分配的基本思想。

1.分頁的概念

分頁(paging)的概念是：將程序的邏輯地址空間分成若干大小相等的片段，稱為頁面(page)，用0、1、2…序號表示；同時(shí)，把內(nèi)存空間也按同樣大小分為若干區(qū)域，稱為塊，或頁幀(pageframe)，也用0、1、2…序號表示。

經(jīng)過分頁后，程序的邏輯地址可看成由兩部分組成，即頁號+頁內(nèi)位移。對i386體系結(jié)構(gòu)來說，邏輯地址為32位，頁面大小為4?KB，則邏輯地址的高20位為頁號，低12位為頁內(nèi)位移，如圖5-6所示。例如，有一個(gè)邏輯地址為十六進(jìn)制0001527A，則其頁號為十六進(jìn)制15，頁內(nèi)位移為十六進(jìn)制27A。圖5-6頁式存儲的邏輯地址結(jié)構(gòu)

2.頁式分配思想

頁式分配的思想是以頁為單位為程序分配內(nèi)存，每個(gè)內(nèi)存塊裝一頁。一個(gè)進(jìn)程的映像的各個(gè)頁面可分散存放在不相鄰的內(nèi)存塊中，用頁表記錄頁號與內(nèi)存塊號之間的映射關(guān)系。圖5?描述了這種分配方式。

頁表是進(jìn)程的一個(gè)重要資源，它記錄了進(jìn)程的頁面與塊號的對應(yīng)關(guān)系。例如在圖5-7中，進(jìn)程A的程序代碼被劃分為4頁，分別加載到內(nèi)存的第9、10、3和5塊中，進(jìn)程B的程序代碼被劃分為3頁，分別加載到內(nèi)存的第7、8和11塊中，它們的頁表如圖5?7所示。雖然它們都不是連續(xù)存放的，但通過頁表可以得到分散的各塊的邏輯順序。圖5?7頁式分配示意圖

3.頁面的分配與釋放

系統(tǒng)設(shè)有一個(gè)內(nèi)存塊表，記錄系統(tǒng)內(nèi)所有物理內(nèi)存塊的分配和使用狀況。內(nèi)存塊表可采用位示圖的方式或空閑塊鏈表方式表示。位示圖用一系列的二進(jìn)制位來描述各個(gè)內(nèi)存塊的狀態(tài)，每個(gè)位對應(yīng)一個(gè)內(nèi)存塊，0表示空閑，1表示占用?？臻e鏈?zhǔn)怯美湹姆绞絹斫M織空閑的內(nèi)存塊的。系統(tǒng)根據(jù)內(nèi)存塊表進(jìn)行存儲分配和釋放，每次分配和釋放操作后都要相應(yīng)地修改此表。不考慮虛擬存儲技術(shù)時(shí)，頁式的分配和釋放算法都比較簡單。當(dāng)進(jìn)程建立時(shí)，系統(tǒng)根據(jù)進(jìn)程映像的大小查找內(nèi)存塊表，若有足夠的空閑塊則為進(jìn)程分配塊，為其建立頁表并將頁表信息填入PCB中。若沒有足夠的空閑塊，則拒絕進(jìn)程裝入。進(jìn)程結(jié)束時(shí)，系統(tǒng)將進(jìn)程占用的內(nèi)存塊回收，并撤銷進(jìn)程的頁表。

4.頁式地址變換

頁式系統(tǒng)采用動態(tài)地址變換方式，通過頁表進(jìn)行地址變換。每個(gè)進(jìn)程有一個(gè)頁表。用邏輯地址的頁號查找頁表中對應(yīng)的表項(xiàng)即可獲得該頁表所在的內(nèi)存的塊號。頁表通常存放在內(nèi)存中，頁表的長度和內(nèi)存地址等信息記錄在進(jìn)程的PCB中。另外，在CPU中設(shè)有一個(gè)頁表寄存器，用來存放正在執(zhí)行的進(jìn)程的頁表長度和內(nèi)存地址。當(dāng)進(jìn)程進(jìn)入CPU執(zhí)行時(shí)，進(jìn)程的頁表信息被填入頁表寄存器，CPU根據(jù)頁表寄存器的值即可找到該進(jìn)程的頁表。當(dāng)CPU執(zhí)行到一條需要訪問內(nèi)存的指令時(shí)，指令操作數(shù)的邏輯地址被裝入邏輯地址寄存器，分頁地址轉(zhuǎn)換機(jī)構(gòu)會自動地進(jìn)行地址轉(zhuǎn)換，形成實(shí)際的內(nèi)存地址。CPU隨后對此地址進(jìn)行訪問操作。地址轉(zhuǎn)換的過程是：將邏輯地址按位分成頁號和頁內(nèi)位移兩部分，再以頁號為索引去檢索頁表，得到該頁號對應(yīng)的物理塊號。將頁內(nèi)位移作為塊內(nèi)位移與塊號拼接即得到實(shí)際的內(nèi)存地址。圖5-8描述了這一地址變換過程。圖5?8頁式地址變換過程設(shè)系統(tǒng)的頁面大小為4?KB，CPU的當(dāng)前指令要訪問的邏輯地址為10372，則該地址對應(yīng)的頁號為2(10372/4k的商)，頁內(nèi)位移為2180(10372/4k的余數(shù))。經(jīng)查頁表后，頁號2變換為塊號4，塊內(nèi)位移為2180，得到實(shí)際地址為18564(4*4k+2180)。

頁表存儲在內(nèi)存中。CPU為了訪問一個(gè)內(nèi)存單元需要兩次訪問內(nèi)存，第一次是查頁表，第二次完成對內(nèi)存單元的讀/寫操作。這顯然降低了帶有訪問內(nèi)存操作的指令的執(zhí)行速度。為縮短查頁表的時(shí)間，系統(tǒng)通常使用快表技術(shù)，就是將一些常用的頁表表項(xiàng)保存在CPU內(nèi)部的高速緩存中。存在高速緩存中的頁表稱為快表，快表的訪問速度比內(nèi)存頁表的訪問速度要高得多。當(dāng)進(jìn)行地址轉(zhuǎn)換時(shí)，先用頁號去查快表，查到則直接進(jìn)行地址轉(zhuǎn)換，未查到時(shí)則去內(nèi)存查頁表，再進(jìn)行地址轉(zhuǎn)換，同時(shí)將此頁對應(yīng)的頁表項(xiàng)登記到快表中。

5.頁式存儲的保護(hù)與擴(kuò)充

頁式存儲的保護(hù)是通過控制訪問地址的頁號來實(shí)現(xiàn)的。在地址轉(zhuǎn)換前，硬件將頁號與頁表長度進(jìn)行比較，如果沒有超出頁表長度，則進(jìn)行地址轉(zhuǎn)換，否則產(chǎn)生地址越界中斷信號。限制對共享頁面的訪問操作的方法是：在頁表中增加一個(gè)讀/寫權(quán)限字段，只有當(dāng)此權(quán)限與該頁的設(shè)置相匹配時(shí)方可訪問，否則產(chǎn)生讀/寫保護(hù)中斷。

頁式存儲管理的存儲擴(kuò)充功能是通過頁式虛擬存儲器來實(shí)現(xiàn)的，具體介紹見5.3節(jié)。頁式存儲管理是目前大部分系統(tǒng)所采用的內(nèi)存管理方案。頁式管理的優(yōu)點(diǎn)是解決了內(nèi)存碎片問題，有效地利用了內(nèi)存，使存儲空間的利用率大大地提高。不過頁式管理也有“頁內(nèi)碎片”問題，即程序的最后一頁不一定正好放滿，空余的部分成為了碎片。不過頁內(nèi)碎片平均為每個(gè)程序半頁，約2?KB左右，這個(gè)數(shù)目是可以接受的。另外，頁式管理需要硬件具備頁式地址變換機(jī)構(gòu)。5.2.4段式存儲管理

在分區(qū)和頁式存儲管理中，程序的地址空間是一維連續(xù)的。然而，從用戶的觀點(diǎn)來看，一維的程序結(jié)構(gòu)有時(shí)并不理想。比如，按模塊化設(shè)計(jì)準(zhǔn)則，一個(gè)應(yīng)用程序通常劃分為一個(gè)主模塊、若干個(gè)子模塊和數(shù)據(jù)模塊等。劃分模塊的好處是可以分別編寫和編譯源程序，并且可以實(shí)現(xiàn)代碼共享、動態(tài)鏈接等編程技術(shù)。段式存儲分配就是為了適應(yīng)用戶對程序結(jié)構(gòu)的需求而設(shè)計(jì)的存儲管理方案。

1.段的概念

在段式存儲管理系統(tǒng)中，程序的地址空間由若干個(gè)大小不等的段組成。段(segment)是邏輯上完整的信息單位，劃分段的依據(jù)是信息的邏輯完整性以及共享和保護(hù)等需要。分段后，程序的邏輯地址空間是一個(gè)二維空間，其邏輯地址由段號和段內(nèi)位移兩部分組成。

分段與分頁的區(qū)別在于：段是信息的邏輯單位，長度不固定，由用戶進(jìn)行劃分；頁是信息的物理單位，長度固定，由系統(tǒng)進(jìn)行劃分，用戶不可見。另外，頁式的地址空間是一維的，段式的地址空間是二維的。

2.段式分配思想

段式分配策略是以段為單位分配內(nèi)存，每個(gè)段分配一個(gè)連續(xù)的分區(qū)。段與段間可以不相鄰接，用段表描述進(jìn)程的各段在內(nèi)存中的存儲位置。段表中包括段長和段起始地址等信息。圖5-9描述了段式存儲的分配方式。圖5?9段式分配示意圖

3.段的分配與釋放

段式分配對內(nèi)存空間的管理類似于可重定位分區(qū)的管理方法。當(dāng)進(jìn)程建立時(shí)，系統(tǒng)為進(jìn)程的各段分配一個(gè)連續(xù)的存儲區(qū)，并為它建立段表。進(jìn)程結(jié)束后，系統(tǒng)回收段所占用的分區(qū)，并撤銷段表。進(jìn)程在運(yùn)行過程中也可以動態(tài)地請求分配或釋放某個(gè)段。

4.段式地址變換

當(dāng)進(jìn)程開始執(zhí)行時(shí)，進(jìn)程的段表信息被填入CPU中的段表寄存器。根據(jù)段表寄存器的值，CPU可以找到該進(jìn)程的段表。當(dāng)CPU執(zhí)行到一條要訪問某邏輯地址的指令時(shí)，以邏輯地址中的段號為索引去檢索段表，得到該段在內(nèi)存的起始地址，與邏輯地址中的段內(nèi)位移相加就可得到實(shí)際的內(nèi)存地址。圖5-10描述了這一地址變換過程。

設(shè)CPU的當(dāng)前指令要訪問的邏輯地址為2段的210位移處。經(jīng)查段表后，獲得2段的起始地址為6200，將其與段內(nèi)位移210相加，得到實(shí)際地址為6410。圖5?10段式地址變換過程

5.段式存儲的共享、保護(hù)與擴(kuò)充

段式存儲允許以段為單位的存儲共享。段的共享就是內(nèi)存中只保留該段的一個(gè)副本，供多個(gè)進(jìn)程使用。當(dāng)進(jìn)程需要共享內(nèi)存中的某段程序或數(shù)據(jù)時(shí)，只要在進(jìn)程的段表中填入共享段的信息，并置以適當(dāng)?shù)淖x/寫控制權(quán)，就可以訪問該段了。

當(dāng)CPU訪問某邏輯地址時(shí)，硬件自動把段號與段表長度進(jìn)行比較，同時(shí)還要將段內(nèi)地址與段表中該段長度進(jìn)行比較，如果訪問地址合法則進(jìn)行地址轉(zhuǎn)換，否則產(chǎn)生地址越界中斷信號。對共享段還要檢驗(yàn)進(jìn)程的訪問權(quán)限，權(quán)限匹配則可進(jìn)行訪問，否則產(chǎn)生讀/寫保護(hù)中斷。段式存儲空間的擴(kuò)充采用段式虛擬存儲器技術(shù)，在此不作介紹。

段式管理的特點(diǎn)是便于程序模塊化處理，可以充分實(shí)現(xiàn)分段共享和保護(hù)。但由于段需要連續(xù)存儲，可能出現(xiàn)碎片問題。另外，段式管理需要硬件具備段式地址變換機(jī)構(gòu)。5.2.5段頁式存儲管理

段頁式存儲管理是頁式和段式兩種存儲管理方案相結(jié)合的產(chǎn)物。它的分配思想是段式劃分，頁式存儲。即把程序的各段按頁式分配方式存儲在內(nèi)存的塊中，每段一個(gè)頁表。另設(shè)一個(gè)段表，指示各段的頁表位置。這樣就實(shí)現(xiàn)了程序的不連續(xù)存放。

采用段頁式方式時(shí)，程序的邏輯地址可以看做是由3部分組成的，即段號+頁號+頁內(nèi)地址。地址變換過程是：先根據(jù)段號查段表，獲得該段的頁表，再用頁號查頁表，得到實(shí)際內(nèi)存塊號，最后與頁內(nèi)地址合并即可得到實(shí)際內(nèi)存地址。段頁式存儲管理具備了頁式和段式兩種存儲管理方式的優(yōu)點(diǎn)，存儲空間的利用率高，并能滿足各種應(yīng)用要求。但這種管理技術(shù)過于復(fù)雜，軟硬件開銷也很大，因此較少使用。

5.3虛擬存儲管理

5.3.1虛擬存儲技術(shù)

1.程序的局部性原理

實(shí)驗(yàn)證明，在進(jìn)程的執(zhí)行過程中，CPU不是隨機(jī)訪問整個(gè)程序或數(shù)據(jù)范圍的，而是在一個(gè)時(shí)間段中只集中地訪問程序或數(shù)據(jù)的某一個(gè)部分。進(jìn)程的這種訪問特性稱為局部性(locality)原理。局部性原理表明，在進(jìn)程運(yùn)行的每個(gè)較短的時(shí)間段中，進(jìn)程的地址空間中只有部分空間是活動的(即被CPU訪問的)，其余的空間則處于不活動的狀態(tài)。這些不活動的代碼可能在較長的時(shí)間內(nèi)不會被用到(比如初始化和結(jié)束處理)，甚至在整個(gè)運(yùn)行期間都可能不會被用到(比如出錯(cuò)處理)。它們完全可以不在內(nèi)存中駐留，只當(dāng)被用到時(shí)再調(diào)入內(nèi)存，這就是虛擬存儲器的思想?？梢哉f，程序的局部性使虛擬存儲成為可能。

2.虛擬存儲器原理

虛擬存儲器的原理是用外存模擬內(nèi)存，實(shí)現(xiàn)內(nèi)存空間的擴(kuò)充。做法是：在外存開辟一個(gè)存儲空間，稱為交換區(qū)。進(jìn)程啟動時(shí)，只有部分程序代碼進(jìn)入內(nèi)存，其余駐留在外存交換區(qū)中，在需要時(shí)調(diào)入內(nèi)存。與覆蓋技術(shù)的不同之處在于，覆蓋是用戶有意識地進(jìn)行的，用戶所看到的地址空間還是實(shí)際大小的空間；而在虛擬存儲技術(shù)中，內(nèi)存與交換空間之間的交換完全由系統(tǒng)動態(tài)地完成，應(yīng)用程序并不會察覺，因而應(yīng)用程序看到的是一個(gè)比實(shí)際內(nèi)存大得多的“虛擬內(nèi)存”。與交換技術(shù)的不同之處在于，交換是對整個(gè)進(jìn)程進(jìn)行的，進(jìn)程映像的大小仍要受實(shí)際內(nèi)存的限制；而在虛擬存儲中，進(jìn)程的邏輯地址空間可以超越實(shí)際內(nèi)存容量的限制。因此，虛擬存儲管理是實(shí)現(xiàn)內(nèi)存擴(kuò)展的最有效的手段。不過，讀/寫硬盤的速度比讀/寫內(nèi)存要慢得多，因此訪問虛擬存儲器的速度比訪問真正內(nèi)存的速度要慢，所以這是一個(gè)以時(shí)間換取空間的技術(shù)。另外，虛擬空間的容量也是有限制的。一般來說，虛擬存儲器的容量是實(shí)際內(nèi)存容量與外存交換空間容量之和，這與具體的系統(tǒng)設(shè)置有關(guān)。但虛存容量最終要受地址寄存器位數(shù)的限制。對于32位計(jì)算機(jī)來說，32位可以表示的數(shù)字范圍是4G，因此它的虛存空間的上限就是4?GB。

3.虛擬存儲器的實(shí)現(xiàn)技術(shù)

虛擬存儲器的實(shí)現(xiàn)技術(shù)主要有頁式虛存和段式虛存兩種，以頁式虛存最為常用。本節(jié)將只介紹這種頁式虛存技術(shù)。5.3.2頁式虛擬存儲器原理

頁式虛擬存儲器的思想就是在頁式存儲管理基礎(chǔ)上加入以頁為單位的內(nèi)外存空間的交換來實(shí)現(xiàn)存儲空間擴(kuò)充功能。這種存儲管理方案稱為請求頁式存儲管理。

1.請求頁式管理

在請求頁式管理系統(tǒng)中，最初只將過程映像的若干頁面調(diào)入內(nèi)存，其余的頁面保存在外存的交換區(qū)中。當(dāng)程序運(yùn)行中訪問的頁面不在內(nèi)存時(shí)，則產(chǎn)生缺頁中斷。系統(tǒng)響應(yīng)此中斷，將缺頁從外存交換區(qū)中調(diào)入內(nèi)存。

請求頁式的頁表中除了內(nèi)存塊號外還增加了一些信息字段，設(shè)置這些信息是為了實(shí)施頁面的管理和調(diào)度，如地址變換、缺頁處理、頁面淘汰以及頁面保護(hù)等。實(shí)際系統(tǒng)的頁表結(jié)構(gòu)會有所不同，這取決于系統(tǒng)的頁面管理和調(diào)度策略。圖5-11所示是一種典型的請求頁式的頁表結(jié)構(gòu)。其中，“狀態(tài)位”表示該頁當(dāng)前是否在內(nèi)存；“修改位”表示該頁裝入內(nèi)存后是否被修改過；“訪問位”表示該頁最近是否被訪問過；“權(quán)限位”表示進(jìn)程對此頁的讀/寫權(quán)限；“外存地址”為該頁面在外存交換區(qū)中的存儲地址。圖5?11請求頁式頁表

2.地址變換過程

請求頁式的地址變換過程增加了對缺頁故障的檢測。當(dāng)要訪問的頁面對應(yīng)的頁表項(xiàng)的狀態(tài)位為N時(shí)，硬件地址變換機(jī)構(gòu)會立即產(chǎn)生一個(gè)缺頁中斷信號。CPU響應(yīng)此中斷后，將原進(jìn)程阻塞，轉(zhuǎn)去執(zhí)行中斷處理程序。缺頁中斷的處理程序負(fù)責(zé)將缺頁調(diào)入內(nèi)存，并相應(yīng)地修改進(jìn)程的頁表。中斷返回后，原進(jìn)程就可以重新進(jìn)行地址變換，繼續(xù)運(yùn)行下去了。圖5-12描述了這個(gè)地址變換過程。圖5?12請求頁式地址變換過程圖5-13所示是一個(gè)地址變換過程的實(shí)例，其中的地址均用十六進(jìn)制數(shù)字表示。設(shè)系統(tǒng)的頁面大小為4?KB，CPU的當(dāng)前指令要訪問的邏輯地址為0x3080，則該地址對應(yīng)的頁號為3，頁內(nèi)位移為0x80。設(shè)進(jìn)程當(dāng)前的頁表為圖中左面的頁表。由于3號頁面當(dāng)前不在內(nèi)存，故引起缺頁中斷，進(jìn)程被阻塞。CPU開始執(zhí)行缺頁中斷處理程序，調(diào)度頁面。中斷處理的結(jié)果是2號頁面被淘汰，3號頁面被調(diào)入，覆蓋了2號頁面。修改后的頁表為圖中右面的頁表。中斷返回后原進(jìn)程被喚醒，進(jìn)入就緒狀態(tài)。當(dāng)再次運(yùn)行時(shí)，重新執(zhí)行上次那條指令，并成功地將邏輯地址0x3080變換為0x9080。圖5?13請求頁式地址變換過程舉例

3.缺頁中斷的處理

缺頁中斷后，CPU暫停原進(jìn)程的運(yùn)行，轉(zhuǎn)去執(zhí)行缺頁中斷的處理程序。缺頁中斷處理程序的任務(wù)是將進(jìn)程請求的頁面調(diào)入內(nèi)存。它先查到該頁在外存的位置，如果內(nèi)存中還有空閑塊則將缺頁直接調(diào)入。如果沒有空閑塊就需要選擇淘汰一個(gè)已在內(nèi)存的頁面，再將缺頁調(diào)入，覆蓋被淘汰的頁面。在覆蓋被淘汰的頁面前，先檢查該頁在內(nèi)存駐留期間是否曾被修改過(頁表中的修改位為1)。如果被修改過，則要將其寫回外存交換空間，以保持內(nèi)外存數(shù)據(jù)的一致性。缺頁調(diào)入后，還要相應(yīng)地修改進(jìn)程頁表和系統(tǒng)的內(nèi)存分配表。中斷處理完成后，原進(jìn)程從等待狀態(tài)中被喚醒，進(jìn)入就緒狀態(tài)，準(zhǔn)備重新運(yùn)行。

圖5-14描述了缺頁中斷的處理過程。圖5?14缺頁中斷處理

4.頁面淘汰算法

在缺頁中斷處理中，頁面淘汰算法對系統(tǒng)的性能來說至關(guān)重要。如果淘汰算法不當(dāng)，系統(tǒng)有時(shí)會產(chǎn)生“抖動(thrashing)”現(xiàn)象，即剛調(diào)出的頁很快又被訪問到，馬上又被調(diào)入。抖動的系統(tǒng)處于頻繁的頁交換狀態(tài)，CPU的大量時(shí)間都花在處理缺頁中斷上，故系統(tǒng)效率大幅度降低。

理論上講，最優(yōu)的算法應(yīng)是淘汰以后不再訪問或很久以后才會訪問的頁面，然而最優(yōu)的算法是無法確定的。實(shí)際常用的是估計(jì)的方法，即優(yōu)先淘汰那些估計(jì)最近不太可能被用到的頁面。常用頁面淘汰算法有以下3種：

1)先進(jìn)先出法(First-InFirst-Out，F(xiàn)IFO)

FIFO算法的思想是優(yōu)先淘汰最先進(jìn)入內(nèi)存的頁面，即在內(nèi)存中駐留時(shí)間最久的頁面。不過在有些時(shí)候，頁面調(diào)入的先后并不能反映頁面的使用情況。最先進(jìn)入內(nèi)存執(zhí)行的代碼可能也是最常用到的，比如程序的主控部分。因此，F(xiàn)IFO算法性能比較差，通常還要附加其他的判斷來優(yōu)化此算法。

FIFO算法的實(shí)現(xiàn)比較簡單，只要用一個(gè)隊(duì)列記錄頁面進(jìn)入內(nèi)存的先后順序，淘汰時(shí)選擇隊(duì)頭的頁面即可。

2)最近最少使用法(LeastRecentlyUsed，LRU)

LRU算法不是簡單地以頁面進(jìn)入內(nèi)存的先后順序?yàn)橐罁?jù)，而是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無法預(yù)測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似。因此，LRU算法選擇淘汰在最近期間最久未被訪問的頁面予以淘汰。

LRU算法有多種實(shí)現(xiàn)和變種，其基本思想是在頁表中設(shè)置一個(gè)訪問字段，記錄頁面在最近時(shí)間段內(nèi)被訪問的次數(shù)或自上次訪問以來所經(jīng)歷的時(shí)間，當(dāng)須淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中訪問時(shí)間值最早的予以淘汰。

實(shí)際運(yùn)用證明LRU算法的性能相當(dāng)好，它產(chǎn)生的缺頁中斷次數(shù)已很接近理想算法。但LRU算法實(shí)現(xiàn)起來不太容易，需要增加硬件或軟件的開銷。與之相比，F(xiàn)IFO算法性能盡管不是最好，卻更容易實(shí)現(xiàn)。

3)最少使用頻率法(LeastFrequentlyUsed，LFU)

LFU算法是LRU的一個(gè)近似算法。它選擇淘汰最近時(shí)期使用頻率最少的頁面。實(shí)現(xiàn)時(shí)需要為每個(gè)頁面設(shè)置一個(gè)訪問記數(shù)器(也可以用移位寄存器實(shí)現(xiàn))，用來記錄該頁面被訪問的頻率，需要淘汰頁面時(shí)，選擇記數(shù)值最小的頁面淘汰。

應(yīng)當(dāng)指出的是，無論哪種算法都不可能完全避免抖動發(fā)生。產(chǎn)生抖動的原因一是頁面調(diào)度不當(dāng)，另一個(gè)就是實(shí)際內(nèi)存過小。對系統(tǒng)來說應(yīng)當(dāng)盡量優(yōu)化淘汰算法，減少抖動發(fā)生；而對用戶來說，加大物理內(nèi)存是解決抖動的最有效方法?？偟膩碚f，請求頁式存儲管理實(shí)現(xiàn)了虛擬存儲器，因而可以容納更大或更多的進(jìn)程，提高了系統(tǒng)的整體性能。但是，空間性能的提升是以犧牲時(shí)間性能為代價(jià)的，過度擴(kuò)展有可能產(chǎn)生抖動，應(yīng)權(quán)衡考慮。一般來說，外存交換空間為實(shí)際內(nèi)存空間的1～2倍比較合適。

5.4Linux的存儲管理

5.4.1Linux的內(nèi)存管理概述

1.?386體系結(jié)構(gòu)的內(nèi)存模式

i386體系結(jié)構(gòu)支持兩種內(nèi)存訪問模式，即實(shí)模式和保護(hù)模式。當(dāng)CPU中的控制寄存器CR0的PE位為0時(shí)工作在實(shí)模式，為1時(shí)是保護(hù)模式。在實(shí)模式下，只有20根地址線有效，CPU可尋址的內(nèi)存地址空間只有1?GB；而在保護(hù)模式下，全部32根地址線被激活，可尋址空間達(dá)4?GB。因此，只有工作在保護(hù)模式下，才能真正發(fā)揮i386硬件的功能。i386上的所有常用操作系統(tǒng)(除DOS外)都是運(yùn)行在保護(hù)模式下的，Linux也不例外。

i386使用的是段式管理機(jī)制，在段式管理的基礎(chǔ)上還可以選擇啟用頁式管理機(jī)制。當(dāng)CPU中的控制寄存器CR0的PG位為1時(shí)啟用分頁機(jī)制，為0則不啟用。

i386的頁式管理機(jī)制支持兩級頁表，CPU能夠識別頁表項(xiàng)中的一些標(biāo)志位并根據(jù)訪問情況做出反應(yīng)。如訪問一個(gè)“存在位”(即狀態(tài)位)為0的頁將引起缺頁中斷，寫一個(gè)“讀/寫權(quán)限位”為0的頁將引起保護(hù)中斷，訪問頁面后會自動設(shè)置“訪問位”等。

2.?i386的地址變換

i386的地址分為3種：邏輯地址、線性地址和物理地址。邏輯地址也稱為虛擬地址，是機(jī)器指令中使用的地址。由于i386采用段式管理，所以它的邏輯地址是二維的，由段和段內(nèi)位移表示。線性地址是邏輯地址經(jīng)過i386分段機(jī)構(gòu)處理后得到的一維地址。每個(gè)進(jìn)程的線性地址空間為4?GB。物理地址是線性地址經(jīng)過頁式變換得到的實(shí)際內(nèi)存地址，這個(gè)地址將被送到地址總線上，定位實(shí)際要訪問的內(nèi)存單元。內(nèi)存管理單元(MMU)是管理物理內(nèi)存并進(jìn)行地址變換的硬件，它完成虛擬地址到物理地址的變換。執(zhí)行指令時(shí)，MMU先對指令中的虛擬地址進(jìn)行段式映射，即通過“段基地址＋位移量”的方式將其轉(zhuǎn)換為線性地址，然后再進(jìn)行頁式映射，得到物理地址。

3.?Linux的內(nèi)存管理方案

Linux系統(tǒng)采用請求頁式存儲管理。在大多數(shù)硬件平臺上(如RISC處理器)，頁式管理都能很好地工作。這些平臺與i386系列平臺不同，它們采用的是分頁機(jī)制，基本上不支持分段功能。但i386體系結(jié)構(gòu)在發(fā)展之初因受到PC機(jī)內(nèi)存容量的限制而使用了分段的機(jī)制。Linux的設(shè)計(jì)目標(biāo)之一就是良好的可移植性，它必須能適應(yīng)各種流行的處理器平臺，當(dāng)然包括i386。為了適應(yīng)i386的段式內(nèi)存管理方式，Linux巧妙地利用了共享0基址段的方式，使i386的段式映射實(shí)際上不起作用。對于Linux系統(tǒng)來說，虛擬地址與線性地址是一樣的。Linux的所有的進(jìn)程都使用同樣的0～4?GB線性地址空間，這使得內(nèi)存管理變得簡單。

一些實(shí)時(shí)和嵌入式應(yīng)用對系統(tǒng)的響應(yīng)性要求很高，而虛存的頁面調(diào)度會影響系統(tǒng)的實(shí)時(shí)響應(yīng)性能。為解決這個(gè)問題，2.6版的內(nèi)核允許編譯無虛存的系統(tǒng)。無虛存系統(tǒng)實(shí)時(shí)性高，但要求有足夠的內(nèi)存來保證任務(wù)的執(zhí)行。5.4.2Linux存儲空間的描述

1.頁幀的描述

對于i386體系結(jié)構(gòu)來說，頁幀(即內(nèi)存塊)的大小為4?KB。1?GB的物理內(nèi)存空間可劃分為262?144個(gè)頁幀。內(nèi)核中描述頁幀的數(shù)據(jù)結(jié)構(gòu)是page，每個(gè)頁幀對應(yīng)一個(gè)page結(jié)構(gòu)，所有頁幀的page結(jié)構(gòu)組織在一個(gè)mem_map數(shù)組中，如圖5-15所示。

page結(jié)構(gòu)中包含有關(guān)于該頁幀的一些信息，供頁面調(diào)度時(shí)使用。主要信息包括頁的狀態(tài)(如該頁是否被修改過，是否被鎖定在內(nèi)存中不許換出等)、頁的引用計(jì)數(shù)以及該頁對應(yīng)的虛擬地址。圖5?15物理內(nèi)存的描述

2.虛擬地址空間的描述

在i386平臺上，進(jìn)程的虛擬存儲空間是4?GB。這4?GB的空間分為兩部分：最高的1?GB供內(nèi)核使用，稱為“內(nèi)核空間”，其中存放的是內(nèi)核代碼和數(shù)據(jù)，即“內(nèi)核映像”；較低的3?GB供用戶進(jìn)程使用，稱為“用戶空間”。因?yàn)槊總€(gè)進(jìn)程都可以通過系統(tǒng)調(diào)用進(jìn)入內(nèi)核，因此，內(nèi)核空間由系統(tǒng)內(nèi)的所有進(jìn)程共享，而用戶空間則是進(jìn)程的私有空間。當(dāng)進(jìn)程運(yùn)行在用戶態(tài)時(shí)，它是在自己的用戶空間內(nèi)運(yùn)行；當(dāng)它運(yùn)行在核心態(tài)時(shí)(通過系統(tǒng)調(diào)用)，它是在內(nèi)核空間運(yùn)行。進(jìn)程的用戶空間由5個(gè)部分組成，包括代碼區(qū)、數(shù)據(jù)區(qū)、堆棧區(qū)、共享庫代碼區(qū)和動態(tài)分配的內(nèi)存區(qū)，這些不同的區(qū)間稱為虛存區(qū)。每個(gè)虛存區(qū)用一個(gè)vm_area_structs結(jié)構(gòu)來描述，包含虛存區(qū)的起始和結(jié)束地址、讀/寫屬性等信息。進(jìn)程的各個(gè)虛存區(qū)的vm_area_struct結(jié)構(gòu)后連成一個(gè)鏈表。

進(jìn)程的用戶地址空間由mm_struct結(jié)構(gòu)描述，mm_struct結(jié)構(gòu)包含進(jìn)程的頁目錄指針(pgd)和指向虛存區(qū)鏈表的指針(mmap)等。在進(jìn)程的PCB(task_struct結(jié)構(gòu))中包含一個(gè)mm域，它是指向mm_struct結(jié)構(gòu)的指針。這些數(shù)據(jù)結(jié)構(gòu)描述了一個(gè)進(jìn)程的虛擬存儲空間，如圖5-16所示。圖5-16進(jìn)程虛擬空間的描述在新進(jìn)程建立時(shí)，內(nèi)核為其分配頁表和mm_struct結(jié)構(gòu)，并為其在磁盤上的映像建立虛存區(qū)，連入進(jìn)程的用戶地址空間。隨著進(jìn)程的運(yùn)行，被引用的程序部分會由操作系統(tǒng)裝入到物理內(nèi)存。5.4.3Linux多級分頁機(jī)制

Linux系統(tǒng)的頁面大小為4?KB，則整個(gè)4?GB的線性地址空間要?jiǎng)澐譃??M個(gè)頁面。如果用一個(gè)線性頁表描述的話，需要用長為1M個(gè)表項(xiàng)的頁表才能描述。如此大的頁表檢索起來顯然是非常低效的。

為解決這個(gè)問題，Linux系統(tǒng)采用了三級分頁機(jī)制，即對頁建立三級索引，分別稱為頁目錄、頁中間目錄和頁表。由于i386體系結(jié)構(gòu)的限制，在i386平臺上的Linux系統(tǒng)采用二級頁索引，頁目錄和頁中間目錄合二為一，從而巧妙地適應(yīng)了二級頁表的硬件結(jié)構(gòu)。采用二級分頁時(shí)，線性地址由三個(gè)部分組成，分別為頁目錄號、頁表號和頁內(nèi)位移。線性地址的劃分如圖5-17所示。在32位地址中，高10位和中間10位分別是頁目錄號和頁表號，尋址范圍為1K；低12位為頁內(nèi)位移，尋址范圍為4K。

二級分頁的方式是把所有頁表項(xiàng)按1K為單位劃分為若干個(gè)子表(最多1K個(gè))，用頁目錄表來記錄每一個(gè)子表的位置。頁目錄表也是1K項(xiàng)長。頁目錄和頁表的大小都是4K(每項(xiàng)4字節(jié)，1K項(xiàng))，恰好是一頁大小。頁目錄的每一項(xiàng)記錄一個(gè)頁表的內(nèi)存塊號，通過頁目錄就可以找到各個(gè)頁表。圖5-17二級分頁的線性地址劃分圖5-18描述了二級地址變換的過程。進(jìn)程的mmstruct結(jié)構(gòu)中記錄了它的頁目錄地址，在進(jìn)入CPU運(yùn)行時(shí)，頁目錄地址被置入CPU的寄存器中，通過它即可找到進(jìn)程的頁目錄。在地址變換時(shí)，首先用頁目錄號為索引查頁目錄，得到對應(yīng)的頁表的地址，再用頁號為索引查頁表，得到對應(yīng)的內(nèi)存塊號，與頁內(nèi)位移合并即得到實(shí)際內(nèi)存地址。

由于頁目錄表和頁表存放在內(nèi)存中，因此，要訪問內(nèi)存中的某一單元需要三次訪問內(nèi)存。為了加快訪問速度，Linux將常用的頁目錄和頁表的表項(xiàng)放在快表中。地址變換時(shí)首先訪問快表，如果表項(xiàng)不在快表中，再去內(nèi)存查找頁目錄表和頁表。圖5?18二級分頁地址變換示意圖5.4.4空閑內(nèi)存的管理

Linux系統(tǒng)用位示圖和鏈表相結(jié)合的方法記錄空閑內(nèi)存的分布情況。系統(tǒng)定義了一個(gè)稱為free_area的數(shù)組。對于i386平臺的Linux系統(tǒng)來說，free_area數(shù)組的大小為10項(xiàng)，每項(xiàng)包含空閑鏈表的2個(gè)指針(next和prev)和位示圖的1個(gè)指針(map)。它連接了10個(gè)空閑鏈表和位示圖。通過它內(nèi)核可以掌握系統(tǒng)中所有尺寸的連續(xù)的空閑空間的分布情況，作為分配內(nèi)存的依據(jù)。圖5-19所示是free_area數(shù)組的結(jié)構(gòu)示意圖。圖5?19空閑內(nèi)存空洞的描述若干個(gè)連續(xù)的頁幀稱為頁塊組(pageblock)。free_area數(shù)組用鏈表和位示圖的方式記錄了各種尺寸的空閑頁塊組的分布。

空閑鏈表是一個(gè)雙向鏈表，數(shù)組第k項(xiàng)對應(yīng)的鏈表記錄系統(tǒng)中所有2k大小的空閑頁塊組的起始頁幀號。例如，第0項(xiàng)描述所有單個(gè)空閑頁幀，第1項(xiàng)描述所有2個(gè)頁幀大的空閑頁塊組，第2項(xiàng)描述4個(gè)頁幀大的空閑頁塊組。

如果將內(nèi)存按相同大小的頁塊組劃分并編號，則以偶數(shù)號開始的相鄰的兩個(gè)頁塊組稱為伙伴(buddy)。如頁塊組大小為2幀，則0號頁塊組(0～1幀)與1號頁塊組(2～3幀)是伙伴，2號頁塊組(4～5幀)與3號頁塊組(6~7幀)是伙伴，但1號頁塊組與2號頁塊組不是伙伴。位示圖由若干個(gè)字節(jié)的二進(jìn)制位構(gòu)成，每位對應(yīng)一對伙伴。數(shù)組第k項(xiàng)對應(yīng)的位示圖記錄2k大小的一對伙伴的分配使用情況，為1表示對應(yīng)的伙伴中有一個(gè)是空閑的頁塊，為0表示對應(yīng)的兩個(gè)伙伴頁塊都空閑或都不空閑。

在圖5-19中，如果內(nèi)存中頁幀的使用情況如圖右側(cè)部分所示，則free_area[0]的空閑鏈表鏈接所有1幀長的空閑頁塊組，它們是第5、7、13等幀。它的位示圖描述1幀長的伙伴的使用情況。前16幀的8對伙伴用8位描述，其中，5、7、13幀對應(yīng)的伙伴位為1，其余為0。同理，free_area[1]的空閑鏈表鏈接所有2幀長的空閑頁塊組，分別是第10～11和14～15幀。它的位示圖描述2幀長的伙伴的使用情況。前16幀的4對伙伴用4位描述，其中，10～11和14～15幀對應(yīng)的伙伴位為1，其余為0。free_area[2]的空閑鏈表鏈接所有4幀長的空閑頁塊組，這里是0～3幀。它的位示圖描述4幀長的伙伴的使用情況。前16幀的2對伙伴用2位描述，其中，0～3幀對應(yīng)的伙伴位為1，其余為0。5.4.5內(nèi)存的分配與回收

1.伙伴分配算法

Linux采用伙伴(buddy)算法來分配和回收內(nèi)存，內(nèi)存的分配和回收的空間大小都是2k大小的頁塊組。對于i386系統(tǒng)，內(nèi)存一次分配的最小尺寸是4?KB(20×4?KB)，最大為2?MB(29×4?KB)。

當(dāng)要分配內(nèi)存時(shí)，先根據(jù)需要確定要分配的頁塊組大小。如需要n頁，2k－1＜n≤2k，則分配一個(gè)2k大小的頁塊組。分配時(shí)，在free_area[k]的鏈表中找一個(gè)空閑頁塊組，將其從鏈表中刪除，返回首地址。若沒有2k大小的頁塊組，就在free_area[k+1]的鏈表中取下一個(gè)，一分為二，分配一個(gè)，將另一個(gè)鏈入free_area[k]的鏈表中。如果沒有2k+1大小的頁塊組就進(jìn)一步地分裂更大的頁塊組?；厥諆?nèi)存時(shí)，將釋放的頁塊組鏈入適當(dāng)?shù)逆湵碇?。如果該頁塊組的伙伴為空閑(位示圖的對應(yīng)位為1)，則將其與伙伴合并，加入到下一個(gè)數(shù)組項(xiàng)的鏈表中。如果還能合并就進(jìn)一步合并下去。每次分配或回收操作后都要修改free_area數(shù)組的相應(yīng)的鏈表和位示圖。

Linux系統(tǒng)十分注重效率，buddy算法可以盡量減少內(nèi)存碎片，增加連續(xù)內(nèi)存分配成功的幾率，使總體效率顯著提高。但是這個(gè)算法可能造成空間的浪費(fèi)，因?yàn)樗看畏峙涞膬?nèi)存是2的整數(shù)冪個(gè)頁，如果需要的內(nèi)存量是33?KB，則實(shí)際分配的是16個(gè)連續(xù)的頁幀(64?KB)，將近50%的內(nèi)存就浪費(fèi)掉了。所以說，算法的高效率是通過犧牲內(nèi)存資源利用率換來的。

2.內(nèi)存分配機(jī)制

Linux內(nèi)核提供的最底層的內(nèi)存分配函數(shù)是alloc_pages()。該函數(shù)使用buddy算法，每次分配2的整數(shù)冪個(gè)連續(xù)的頁幀。分配成功后返回一個(gè)指針，指向第一個(gè)頁幀的page結(jié)構(gòu)。alloc_pages()函數(shù)的一個(gè)變種是_get_free_pages()函數(shù)，它的作用與alloc_pages()相同，只是返回的是第一個(gè)頁的邏輯地址。與此兩個(gè)函數(shù)對應(yīng)的是free_pages()，用于釋放頁幀。對于以字節(jié)為單位的分配來說，內(nèi)核提供的函數(shù)是kmalloc()。Kmalloc()函數(shù)與C語言的malloc()族函數(shù)類似，用于獲得以字節(jié)為單位的一塊內(nèi)存區(qū)。與alloc_pages()的不同之處在于，這個(gè)函數(shù)是按字節(jié)數(shù)分配一段足夠大的內(nèi)存區(qū)，返回它的首地址。Kmalloc()所分配的內(nèi)存區(qū)在物理上是連續(xù)的。由于內(nèi)核分配本質(zhì)上是基于頁的，所以真正分配的內(nèi)存可能比請求的要多。與kmalloc()函數(shù)對應(yīng)的是kfree()，用于釋放內(nèi)存區(qū)。

vmalloc()函數(shù)的工作方式類似于kmalloc()，只不過vmalloc()分配的內(nèi)存的邏輯地址是連續(xù)的，而物理地址則無需連續(xù)。該函數(shù)通過建立頁表將連續(xù)的邏輯地址映射到不連續(xù)的物理頁幀上，所以在使用vmalloc()分配的內(nèi)存時(shí)需要頻繁查詢頁表，效率相對較低。與vmalloc()函數(shù)對應(yīng)的釋放函數(shù)是vfree()。分配連續(xù)頁幀的好處是構(gòu)造頁表的時(shí)候開銷很低，同時(shí)訪問起來效率也高。大多數(shù)情況下，硬件設(shè)備使用的內(nèi)存區(qū)(如磁盤緩沖區(qū)等)必須是物理地址連續(xù)的頁幀，因?yàn)橛布O(shè)備不理解虛擬地址。而軟件使用的內(nèi)存塊(如進(jìn)程的緩沖區(qū))可以使用物理地址不連續(xù)的頁幀，當(dāng)然它的虛擬地址是連續(xù)的。盡管如此，很多內(nèi)核代碼都用kmalloc()來獲得內(nèi)存，而不是vmalloc()，這主要是出于性能的考慮。因此，vmalloc()僅在需要獲得大塊內(nèi)存時(shí)才會使用。

alloc_pages()函數(shù)是按頁分配的，即使是只需要小塊內(nèi)存也要分配整個(gè)頁面。然而，內(nèi)核和應(yīng)用程序在運(yùn)行過程中經(jīng)常會重復(fù)地進(jìn)行數(shù)據(jù)結(jié)構(gòu)或?qū)ο蟮姆峙渑c釋放。為這種小塊內(nèi)存而頻繁地進(jìn)行內(nèi)存分配是對內(nèi)存的極度浪費(fèi)，并會導(dǎo)致內(nèi)存碎片(難以找到大塊連續(xù)的空閑內(nèi)存)。

為滿足小塊內(nèi)存的分配與釋放，Linux提供了slab緩存機(jī)制，即slab分配器。它在頁分配的基礎(chǔ)上獲取并建立內(nèi)存緩存區(qū)域，管理對小塊內(nèi)存區(qū)的分配與釋放請求。多數(shù)情況下，sla