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

第5章存儲(chǔ)管理

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

5.1存儲(chǔ)管理概述

操作系統(tǒng)中用于管理內(nèi)存空間的模塊稱(chēng)為內(nèi)存管理模塊，它負(fù)責(zé)內(nèi)存的全部管理工作，具體地說(shuō)就是要完成4個(gè)功能，即存儲(chǔ)空間的分配、存儲(chǔ)地址的變換、存儲(chǔ)空間的保護(hù)以及存儲(chǔ)空間的擴(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)存空間。

存儲(chǔ)分配方案主要包括以下要素：

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

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

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

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

1.地址的概念

1)符號(hào)地址

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

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

main()

{inti=1;

…

i++;

…

}

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

2)邏輯地址

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

例如，對(duì)上例所示的源程序進(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)容寫(xiě)回0060地址

…

00000060: 0x0001 ;i變量的存儲(chǔ)單元

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

3)物理地址

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

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

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

2.地址變換

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

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

00000400: …

…

0000044B:

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

寄存器

0000044D:

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

0000044E:

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

…

00000460: 0x0001 ;i變量的存儲(chǔ)單元

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

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

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

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

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

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

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

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

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

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

“擴(kuò)充”存儲(chǔ)器空間的基本思想是借用外存空間來(lái)擴(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è)存儲(chǔ)空間。它們平時(shí)駐留在外存中，在需要時(shí)才裝入內(nèi)存，覆蓋掉某個(gè)暫時(shí)不用的模塊。

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

2.交換技術(shù)

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

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

3.虛擬存儲(chǔ)器

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

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

5.2存儲(chǔ)管理方案

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

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

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

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

1.簡(jiǎn)單分區(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ù)先劃分好的，通常會(huì)大于程序的實(shí)際尺寸，因此分區(qū)內(nèi)余下的空閑空間就被浪費(fèi)掉了。圖5-3(a)所示為固定分區(qū)的內(nèi)存分配方式。

對(duì)固定分區(qū)分配策略進(jìn)行改進(jìn)就產(chǎn)生了可變分區(qū)分配。它的思想是：在程序調(diào)入內(nèi)存時(shí)，按其實(shí)際大小動(dòng)態(tài)地劃分分區(qū)。這種量體裁衣的分配方式避免了分區(qū)內(nèi)空間的浪費(fèi)。圖5-3(b)所示為可變分區(qū)的內(nèi)存分配方式。圖5-3分區(qū)存儲(chǔ)分配示意圖分區(qū)分配的方法是：系統(tǒng)設(shè)置兩個(gè)表格來(lái)記錄內(nèi)存空間的使用情況。一個(gè)是已分配分區(qū)表，說(shuō)明各個(gè)已用分區(qū)的分區(qū)號(hào)、起始地址和大小等。另一個(gè)是空閑區(qū)表，說(shuō)明內(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ū)分配的碎片問(wèn)題

分區(qū)分配的主要問(wèn)題是存儲(chǔ)“碎片”。碎片(fragment)是無(wú)法被利用的空閑存儲(chǔ)空間。固定分區(qū)存在“內(nèi)部碎片”問(wèn)題，即遍布在各個(gè)分區(qū)內(nèi)的零碎剩余空間?？勺兎謪^(qū)存在“外部碎片”問(wèn)題，即隨著進(jìn)程不斷地進(jìn)入和退出系統(tǒng)，一段時(shí)間后，內(nèi)存中的空閑分區(qū)會(huì)變得支離破碎，這些碎片空間的總和可能足夠大，但因?yàn)椴贿B續(xù)，所以不能被利用。圖描述了外部碎片的產(chǎn)生過(guò)程。假設(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í)無(wú)法接納這個(gè)作業(yè)。圖5-4可變分區(qū)的存儲(chǔ)碎片

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

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

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

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

2)動(dòng)態(tài)地址變換過(guò)程

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

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

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

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

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

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

在分區(qū)管理中，用戶(hù)程序的大小受可用分區(qū)大小的限制。可以使用覆蓋或交換技術(shù)來(lái)實(shí)現(xiàn)內(nèi)存擴(kuò)充。

總的來(lái)說(shuō)，分區(qū)管理的特點(diǎn)是簡(jiǎn)單、支持多道程序，但有碎片問(wèn)題。可重定位分區(qū)管理提供了解決碎片問(wèn)題的一種途徑，因而提高了存儲(chǔ)空間的利用率。但存儲(chǔ)緊縮比較耗時(shí)，在進(jìn)行存儲(chǔ)緊縮時(shí)，所有用戶(hù)進(jìn)程都要停止運(yùn)行，系統(tǒng)為此付出的代價(jià)過(guò)大。5.2.3頁(yè)式存儲(chǔ)管理

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

1.分頁(yè)的概念

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

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

2.頁(yè)式分配思想

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

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

3.頁(yè)面的分配與釋放

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

4.頁(yè)式地址變換

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

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

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

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

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

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

1.段的概念

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

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

2.段式分配思想

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

3.段的分配與釋放

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

4.段式地址變換

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

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

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

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

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

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

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

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

5.3虛擬存儲(chǔ)管理

5.3.1虛擬存儲(chǔ)技術(shù)

1.程序的局部性原理

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

2.虛擬存儲(chǔ)器原理

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

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

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

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

1.請(qǐng)求頁(yè)式管理

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

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

2.地址變換過(guò)程

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

3.缺頁(yè)中斷的處理

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

圖5-14描述了缺頁(yè)中斷的處理過(guò)程。圖5?14缺頁(yè)中斷處理

4.頁(yè)面淘汰算法

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

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

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

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

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

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

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

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

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

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

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

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

5.4Linux的存儲(chǔ)管理

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

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

i386體系結(jié)構(gòu)支持兩種內(nèi)存訪問(wèn)模式，即實(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ǔ)上還可以選擇啟用頁(yè)式管理機(jī)制。當(dāng)CPU中的控制寄存器CR0的PG位為1時(shí)啟用分頁(yè)機(jī)制，為0則不啟用。

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

2.?i386的地址變換

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

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

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

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

1.頁(yè)幀的描述

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

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

2.虛擬地址空間的描述

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

進(jìn)程的用戶(hù)地址空間由mm_struct結(jié)構(gòu)描述，mm_struct結(jié)構(gòu)包含進(jìn)程的頁(yè)目錄指針(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)程的虛擬存儲(chǔ)空間，如圖5-16所示。圖5-16進(jìn)程虛擬空間的描述在新進(jìn)程建立時(shí)，內(nèi)核為其分配頁(yè)表和mm_struct結(jié)構(gòu)，并為其在磁盤(pán)上的映像建立虛存區(qū)，連入進(jìn)程的用戶(hù)地址空間。隨著進(jìn)程的運(yùn)行，被引用的程序部分會(huì)由操作系統(tǒng)裝入到物理內(nèi)存。5.4.3Linux多級(jí)分頁(yè)機(jī)制

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

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

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

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

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

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

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

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

1.伙伴分配算法

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

當(dāng)要分配內(nèi)存時(shí)，先根據(jù)需要確定要分配的頁(yè)塊組大小。如需要n頁(yè)，2k－1＜n≤2k，則分配一個(gè)2k大小的頁(yè)塊組。分配時(shí)，在free_area[k]的鏈表中找一個(gè)空閑頁(yè)塊組，將其從鏈表中刪除，返回首地址。若沒(méi)有2k大小的頁(yè)塊組，就在free_area[k+1]的鏈表中取下一個(gè)，一分為二，分配一個(gè)，將另一個(gè)鏈入free_area[k]的鏈表中。如果沒(méi)有2k+1大小的頁(yè)塊組就進(jìn)一步地分裂更大的頁(yè)塊組。回收內(nèi)存時(shí)，將釋放的頁(yè)塊組鏈入適當(dāng)?shù)逆湵碇?。如果該?yè)塊組的伙伴為空閑(位示圖的對(duì)應(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è)頁(yè)，如果需要的內(nèi)存量是33?KB，則實(shí)際分配的是16個(gè)連續(xù)的頁(yè)幀(64?KB)，將近50%的內(nèi)存就浪費(fèi)掉了。所以說(shuō)，算法的高效率是通過(guò)犧牲內(nèi)存資源利用率換來(lái)的。

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

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

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

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

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