前言

內(nèi)存作為計(jì)算機(jī)系統(tǒng)的組成部分，跟開(kāi)發(fā)人員的日常開(kāi)發(fā)活動(dòng)有著密切的聯(lián)系，我們平時(shí)遇到的Segment Fault、OutOfMemory、Memory Leak、GC等都與它有關(guān)。本文所說(shuō)的內(nèi)存，指的是計(jì)算機(jī)系統(tǒng)中的主存（Main Memory），它位于存儲(chǔ)金字塔中CPU緩存和磁盤(pán)之間，是程序運(yùn)行不可或缺的一部分。

圖1

在計(jì)算機(jī)系統(tǒng)中，主存通常都是由操作系統(tǒng)（OS）來(lái)管理，而內(nèi)存管理的細(xì)則對(duì)開(kāi)發(fā)者來(lái)說(shuō)是無(wú)感的。對(duì)于一個(gè)普通的開(kāi)發(fā)者，他只需懂得如何調(diào)用編程語(yǔ)言的接口來(lái)進(jìn)行內(nèi)存申請(qǐng)和釋放，即可寫(xiě)出一個(gè)可用的應(yīng)用程序。如果你使用的是帶有垃圾回收機(jī)制的語(yǔ)言，如Java和Go，甚至都不用主動(dòng)釋放內(nèi)存。但如果你想寫(xiě)出高效應(yīng)用程序，熟悉OS的內(nèi)存管理原理就變得很有必要了。

下面，我們將從最簡(jiǎn)單的內(nèi)存管理原理說(shuō)起，帶大家一起窺探OS的內(nèi)存管理機(jī)制，由此熟悉底層的內(nèi)存管理機(jī)制，寫(xiě)出高效的應(yīng)用程序。

獨(dú)占式內(nèi)存管理

早期的單任務(wù)系統(tǒng)中，同一時(shí)刻只能有一個(gè)應(yīng)用程序獨(dú)享所有的內(nèi)存（除開(kāi)OS占用的內(nèi)存），因此，內(nèi)存管理可以很簡(jiǎn)單，只需在內(nèi)存上劃分兩個(gè)區(qū)域：

圖2

在多任務(wù)系統(tǒng)中，計(jì)算機(jī)系統(tǒng)已經(jīng)可以做到多個(gè)任務(wù)并發(fā)運(yùn)行。如果還是按照獨(dú)占式的管理方式，那么每次任務(wù)切換時(shí)，都會(huì)涉及多次內(nèi)存和磁盤(pán)之間的數(shù)據(jù)拷貝，效率極其低下：

圖3

最直觀(guān)的解決方法就是讓所有程序的數(shù)據(jù)都常駐在內(nèi)存中（假設(shè)內(nèi)存足夠大），這樣就能避免數(shù)據(jù)拷貝了：

圖4

但這樣又會(huì)帶來(lái)另一個(gè)問(wèn)題，程序之間的內(nèi)存地址空間是沒(méi)有隔離的，也就是程序A可以修改程序B的內(nèi)存數(shù)據(jù)。這樣的一個(gè)重大的安全問(wèn)題是用戶(hù)所無(wú)法接受的，要解決該問(wèn)題，就要借助虛擬化的力量了。

虛擬地址空間

為了實(shí)現(xiàn)程序間內(nèi)存的隔離，OS對(duì)物理內(nèi)存做了一層虛擬化。OS為每個(gè)程序都虛擬化出一段內(nèi)存空間，這段虛擬內(nèi)存空間會(huì)映射到一段物理內(nèi)存上。但對(duì)程序自身而言，它只能看到自己的虛擬地址空間，也就有獨(dú)占整個(gè)內(nèi)存的錯(cuò)覺(jué)了。

圖5

上圖中，虛擬內(nèi)存空間分成了三個(gè)區(qū)域，其中Code區(qū)域存儲(chǔ)的是程序代碼的機(jī)器指令；Heap區(qū)域存儲(chǔ)程序運(yùn)行過(guò)程中動(dòng)態(tài)申請(qǐng)的內(nèi)存；Stack區(qū)域則是存儲(chǔ)函數(shù)入?yún)ⅰ⒕植孔兞俊⒎祷刂档?。Heap和Stack會(huì)在程序運(yùn)行過(guò)程中不斷增長(zhǎng)，分別放置在虛擬內(nèi)存空間的上方和下方，并往相反方向增長(zhǎng)。

從虛擬地址空間到物理地址空間的映射，需要一個(gè)轉(zhuǎn)換的過(guò)程，完成這個(gè)轉(zhuǎn)換運(yùn)算的部件就是MMU（memory management unit），也即內(nèi)存管理單元，它位于CPU芯片之內(nèi)。

要完成從虛擬地址到物理地址到轉(zhuǎn)換，MMU需要base和bound兩個(gè)寄存器。其中base寄存器用來(lái)存儲(chǔ)程序在物理內(nèi)存上的基地址，比如在圖5中，程序A的基地址就是192KB；bound寄存器（有時(shí)候也叫limit寄存器）則保存虛擬地址空間的Size，主要用來(lái)避免越界訪(fǎng)問(wèn)，比如圖5中程序A的size值為64K。那么，基于這種方式的地址轉(zhuǎn)換公式是這樣的：

物理地址 = 虛擬地址 + 基地址

以圖5中程序A的地址轉(zhuǎn)換為例，當(dāng)程序A嘗試訪(fǎng)問(wèn)超過(guò)其bound范圍的地址時(shí)，物理地址會(huì)轉(zhuǎn)換失?。?/p>

圖6

現(xiàn)在，我們?cè)俅巫屑?xì)看下程序A的物理內(nèi)存分布，如下圖7所示，中間有很大的一段空閑內(nèi)存是“已申請(qǐng)，未使用”的空閑狀態(tài)。這也意味著即使這部分是空閑的，也無(wú)法再次分配給其他程序使用，這是一種巨大的空間浪費(fèi)！為了解決這個(gè)內(nèi)存利用率低下的問(wèn)題，我們熟悉的段式內(nèi)存管理出現(xiàn)了。

圖7

段式內(nèi)存管理

在上一節(jié)中，我們發(fā)現(xiàn)如果以程序?yàn)閱挝蝗プ鰞?nèi)存管理，會(huì)存在內(nèi)存利用率不足的問(wèn)題。為了解決該問(wèn)題，段式內(nèi)存管理被引入。段（Segment）是邏輯上的概念，本質(zhì)上是一塊連續(xù)的、有一定大小限制的內(nèi)存區(qū)域，前文中，我們一共提到過(guò)3個(gè)段：Code、Heap和Stack。

段式內(nèi)存管理以段為單位進(jìn)行管理，它允許OS將每個(gè)段靈活地放置在物理內(nèi)存的空閑位置上，因此也避免了“已申請(qǐng)，未使用”的內(nèi)存區(qū)域出現(xiàn)：

圖8

地址轉(zhuǎn)換

從上圖8可知，段式內(nèi)存管理中程序的物理內(nèi)存空間可能不再連續(xù)了，因此為了實(shí)現(xiàn)從虛擬地址到物理地址到轉(zhuǎn)換，MMU需要為每個(gè)段都提供一對(duì)base-bound寄存器，比如：

圖9

給一個(gè)虛擬地址，MMU是如何知道該地址屬于哪個(gè)段，從而根據(jù)對(duì)應(yīng)的base-bound寄存器轉(zhuǎn)換為對(duì)應(yīng)的物理地址呢？

假設(shè)虛擬地址有16位，因?yàn)橹挥?個(gè)段，因此，我們可以使用虛擬地址的高2位來(lái)作為段標(biāo)識(shí)，比如00表示Code段，01表示Heap段，11表示Stack段。這樣MMU就能根據(jù)虛擬地址來(lái)找到對(duì)應(yīng)段的base-bound寄存器了：

圖10

但這樣還不是能夠順利的將虛擬地址轉(zhuǎn)換為物理地址，我們忽略了重要的一點(diǎn)：Heap段和Stack段的增長(zhǎng)方向是相反的，這也意味著兩者的地址轉(zhuǎn)換方式是不一樣的。因此，我們還必須在虛擬地址中多使用一位來(lái)標(biāo)識(shí)段的增長(zhǎng)方向，比如0表示向上（低地址方向）增長(zhǎng)，1表示向下（高地址方向）增長(zhǎng)：

圖11

下面，看一組段式內(nèi)存管理地址轉(zhuǎn)換的例子：

圖12

那么，總結(jié)段式內(nèi)存管理的地址轉(zhuǎn)換算法如下：

?

//?獲取當(dāng)前虛擬地址屬于哪個(gè)段
Segment?=?(VirtualAddress?&?SEG_MASK)?>>?SEG_SHIFT
//?得到段內(nèi)偏移量
Offset??=?VirtualAddress?&?OFFSET_MASK
//?獲得內(nèi)存增長(zhǎng)的方向
GrowsDirection?=?VirtualAddress?&?GROWS_DIRECTION_MASK
//?有效性校驗(yàn)
if?(Offset?>=?Bounds[Segment])
????RaiseException(PROTECTION_FAULT)
else
????if?(GrowsDirection?==?0)?{
??????PhysAddr?=?Base[Segment]?+?Offset
????}?else?{
??????PhysAddr?=?Base[Segment]?-?Offset
????}

?

內(nèi)存共享和保護(hù)

段式內(nèi)存管理還可以很方便地支持內(nèi)存共享，從而達(dá)到節(jié)省內(nèi)存的目的。比如，如果存在多個(gè)程序都是同一個(gè)可執(zhí)行文件運(yùn)行起來(lái)的，那么這些程序是可以共享Code段的。為了實(shí)現(xiàn)這個(gè)功能，我們可以在虛擬地址上設(shè)置保護(hù)位，當(dāng)保護(hù)位為只讀時(shí)，表示該段可以共享。另外，如果程序修改了只讀的段，則轉(zhuǎn)換地址失敗，因此也可以達(dá)到內(nèi)存保護(hù)的目的。

圖13

內(nèi)存碎片

段式內(nèi)存管理的最明顯的缺點(diǎn)就是容易產(chǎn)生內(nèi)存碎片，這是因?yàn)樵谙到y(tǒng)上運(yùn)行的程序的各個(gè)段的大小往往都不是固定的，而且段的分布也不是連續(xù)的。當(dāng)系統(tǒng)的內(nèi)存碎片很多時(shí)，內(nèi)存的利用率也會(huì)急劇下降，對(duì)外表現(xiàn)就是雖然系統(tǒng)看起來(lái)還有很多內(nèi)存，卻無(wú)法再運(yùn)行起一個(gè)程序。

解決內(nèi)存碎片的方法之一是定時(shí)進(jìn)行碎片整理：

圖14

但是碎片整理的代價(jià)極大，一方面需要進(jìn)行多次內(nèi)存拷貝；另一方面，在拷貝過(guò)程中，正在運(yùn)行的程序必須停止，這對(duì)于一些以人機(jī)交互任務(wù)為主的應(yīng)用程序，將會(huì)極大影響用戶(hù)體驗(yàn)。

另一個(gè)解決方法就是接下來(lái)要介紹的頁(yè)式內(nèi)存管理。

頁(yè)式內(nèi)存管理

頁(yè)式內(nèi)存管理的思路，是將虛擬內(nèi)存和物理內(nèi)存都劃分為多個(gè)固定大小的區(qū)域，這些區(qū)域我們稱(chēng)之為頁(yè)（Page）。頁(yè)是內(nèi)存的最小分配單位，一個(gè)應(yīng)用程序的虛擬頁(yè)可以存放在任意一個(gè)空閑的物理頁(yè)中。

物理內(nèi)存中的頁(yè)，我們通常稱(chēng)之為頁(yè)幀（Page Frame）

圖15

因?yàn)轫?yè)的大小是固定的，而且作為最小的分配單位，這樣就可以解決段式內(nèi)存管理中內(nèi)存碎片的問(wèn)題了。

但頁(yè)內(nèi)仍然有可能存在內(nèi)存碎片。

地址轉(zhuǎn)換

頁(yè)式內(nèi)存管理使用頁(yè)表（Page Table）來(lái)進(jìn)行虛擬地址到物理地址到轉(zhuǎn)換，地址轉(zhuǎn)換的關(guān)鍵步驟如下：

1）根據(jù)虛擬頁(yè)找到對(duì)應(yīng)的物理頁(yè)幀

每個(gè)虛擬頁(yè)都有一個(gè)編號(hào)，叫做VPN（Virtual Page Number）；相應(yīng)的，每個(gè)物理頁(yè)幀也有一個(gè)編號(hào)，叫做PFN（Physical Frame Number）。頁(yè)表存儲(chǔ)的就是VPN到PFN的映射關(guān)系。

2）找到地址在物理頁(yè)幀內(nèi)的偏移（Offset）

地址在物理頁(yè)幀內(nèi)的偏移與在虛擬頁(yè)內(nèi)的偏移保持一致。

我們可以將虛擬地址劃分成兩部分，分別存儲(chǔ)VPN和Offset，這樣就能通過(guò)VPN找到PFN，從而得到PFN+Offset的實(shí)際物理地址了。

比如，假設(shè)虛擬內(nèi)存空間大小為64Byte（6位地址），頁(yè)的大小為16Byte，那么整個(gè)虛擬內(nèi)存空間一共有4個(gè)頁(yè)。因此我們可以使用高2位來(lái)存儲(chǔ)VPN，低4位存儲(chǔ)Offset：

圖16

下面看一個(gè)轉(zhuǎn)換例子，VPN（01）通過(guò)頁(yè)表找到對(duì)應(yīng)的PFN（111），虛擬地址和物理地址的頁(yè)內(nèi)偏移都是0100，那么虛擬地址010100對(duì)應(yīng)的物理地址就是1110100了。

圖17

頁(yè)表和頁(yè)表項(xiàng)

OS為每個(gè)程序都分配了一個(gè)頁(yè)表，存儲(chǔ)在內(nèi)存當(dāng)中，頁(yè)表里由多個(gè)頁(yè)表項(xiàng)（PTE，Page Table Entry）組成。我們可以把頁(yè)表看成是一個(gè)數(shù)組，數(shù)組的元素為PTE：

圖18

以x86系統(tǒng)下的PTE組成為例，PTE一共占32位，除了PFN之外，還有一些比較重要的信息，比如P（Present）標(biāo)識(shí)當(dāng)前頁(yè)是否位于內(nèi)存上（或是磁盤(pán)上）；R/W（Read/Write）標(biāo)識(shí)當(dāng)前頁(yè)是否允許讀寫(xiě)（或是只讀）；U/S（User/Supervisor）標(biāo)識(shí)當(dāng)前頁(yè)是否允許用戶(hù)態(tài)訪(fǎng)問(wèn)；A（Access）標(biāo)識(shí)當(dāng)前頁(yè)是否被訪(fǎng)問(wèn)過(guò)，在判斷當(dāng)前頁(yè)是否為熱點(diǎn)數(shù)據(jù)、頁(yè)換出時(shí)特別有用；D（Dirty）標(biāo)識(shí)當(dāng)前頁(yè)是否被修改過(guò)。

頁(yè)式內(nèi)存管理的缺點(diǎn)

地址轉(zhuǎn)換效率低

根據(jù)前文介紹，我們可以總結(jié)頁(yè)式內(nèi)存管理機(jī)制下地址轉(zhuǎn)換的算法如下：

?

//?從虛擬地址上得到VPN
VPN?=?(VirtualAddress?&?VPN_MASK)?>>?SHIFT
//?找到VPN對(duì)應(yīng)的PTE的內(nèi)存地址
PTEAddr?=?PTBR?+?(VPN?*?sizeof(PTE))
//?訪(fǎng)問(wèn)主存，獲取PTE
PTE?=?AccessMemory(PTEAddr)
//?有效性校驗(yàn)
if?(PTE.Valid?==?False)
????RaiseException(INVALID_ACCESS)
else
????//?獲取頁(yè)內(nèi)偏移量
????offset?=?VirtualAddress?&?OFFSET_MASK
????//?計(jì)算得出物理地址
????PhysAddr?=?(PTE.PFN?<

	?

	我們發(fā)現(xiàn)，每次地址轉(zhuǎn)換都會(huì)訪(fǎng)問(wèn)一次主存來(lái)獲取頁(yè)表，比段式內(nèi)存管理（無(wú)主存訪(fǎng)問(wèn)）低效很多。

	占用空間大

	假設(shè)地址空間為32-bit，頁(yè)的大小固定為4KB，那么整個(gè)地址空間一共有個(gè)頁(yè)表，也即頁(yè)表一共有個(gè)PTE?，F(xiàn)假設(shè)每個(gè)PTE大小為4-byte，那么每個(gè)頁(yè)表占用4MB的內(nèi)存。如果整個(gè)系統(tǒng)中有100個(gè)程序在運(yùn)行，那么光是頁(yè)表就占用了400MB的內(nèi)存，這同樣是用戶(hù)無(wú)法接受的。

	接下來(lái)，我們將介紹如何去優(yōu)化頁(yè)式內(nèi)存管理的這兩個(gè)顯著缺點(diǎn)。

	讓頁(yè)式管理的地址轉(zhuǎn)換更快

	TLB：Translation-Lookaside Buffer

	根據(jù)前文所述，頁(yè)式內(nèi)存管理地址轉(zhuǎn)換因?yàn)槎嗔艘淮沃鞔嬖L(fǎng)問(wèn)，導(dǎo)致效率很低。如果能夠避免或者減少對(duì)主存的訪(fǎng)問(wèn)，那么就能讓地址轉(zhuǎn)換更快了。

	很多人應(yīng)該都可以想到通過(guò)增加緩存的方式提升效率，比如為避免頻繁查詢(xún)磁盤(pán)，我們一般在內(nèi)存中增加一層緩存來(lái)提升數(shù)據(jù)訪(fǎng)問(wèn)效率。那么為了提升訪(fǎng)問(wèn)主存中數(shù)據(jù)的效率，自然應(yīng)該在離CPU更近的地方增加一層緩存。這個(gè)離CPU更近的地方，就是前文提到的位于CPU芯片之內(nèi)的MMU。而這個(gè)高速緩存，就是TLB（Translation-Lookaside Buffer），它緩存了VPN到PFN到映射關(guān)系，類(lèi)似于這樣：

	圖19

	增加TLB之后，地址轉(zhuǎn)換的算法如下：

	?
VPN?=?(VirtualAddress?&?VPN_MASK)?>>?SHIFT
(Success,?TlbEntry)?=?TLB_Lookup(VPN)
if?(Success?==?True)???//?TLB?Hit
????if?(CanAccess(TlbEntry.ProtectBits)?==?True)
????????Offset???=?VirtualAddress?&?OFFSET_MASK
????????PhysAddr?=?(TlbEntry.PFN?<

	?

	從上述算法可以發(fā)現(xiàn)，在TLB緩存命中（TLB Hit）時(shí)，能夠避免直接訪(fǎng)問(wèn)主存，從而提升了地址轉(zhuǎn)換的效率；但是在TLB緩存不命中（TLB Miss）時(shí)，仍然需要訪(fǎng)問(wèn)一次主存，而且還要往TLB中插入從主存中查詢(xún)到的PFN，效率變得更低了。因此，我們必須盡量避免TLB Miss的出現(xiàn)。

	更好地利用TLB

	下面，我們通過(guò)一個(gè)數(shù)組遍歷的例子來(lái)介紹如何更好地利用TLB。

	假設(shè)我們要進(jìn)行如下的一次數(shù)組遍歷：

	?
int?sum?=?0;
for?(i?=?0;?i?

	?

	數(shù)組的內(nèi)存的分布如下：

	圖20

	a[0]~a[2]位于Page 5上，a[3]~a[6]位于Page 6上，a[7]~a[8]位于Page 7上。當(dāng)我們首先訪(fǎng)問(wèn)a[0]時(shí)，由于Page 5并未在TLB緩存里，所以會(huì)先出現(xiàn)一次TLB Miss，接下來(lái)的a[1]和a[2]都是TLB Hit；同理，訪(fǎng)問(wèn)a[3]和a[7]時(shí)都是TLB Miss，a[4]~a[6]和a[8]~a[9]都是TLB Hit。所以，整個(gè)數(shù)組遍歷下來(lái)，TLB的緩存命中情況為：Miss，Hit，Hit，Miss，Hit，Hit，Hit，Miss，Hit，Hit，TLB緩存命中率為70%。我們發(fā)現(xiàn)，訪(fǎng)問(wèn)同一頁(yè)上的數(shù)據(jù)TLB的緩存更易命中，這就是空間局部性的原理。

	接下來(lái)，我們?cè)俅沃匦卤闅v一次數(shù)組，由于經(jīng)過(guò)上一次之后Page 5 ～ Page 7的轉(zhuǎn)換信息已經(jīng)在TLB緩存里里，所以第二次遍歷的TLB命中情況為：Hit，Hit，Hit，Hit，Hit，Hit，Hit，Hit，Hit，Hit，TLB緩存命中率為100%！這就是時(shí)間局部性的原理，短時(shí)間內(nèi)訪(fǎng)問(wèn)同一內(nèi)存數(shù)據(jù)也能夠提升TLB緩存命中率。

	TLB的上下文切換

	因?yàn)門(mén)LB緩存的是當(dāng)前正在運(yùn)行程序的上下文信息，當(dāng)出現(xiàn)程序切換時(shí)，TLB里面的上下文信息也必須更新，否則地址轉(zhuǎn)換就會(huì)異常。解決方法主要有2種：

	方法1：每次程序切換都清空TLB緩存（Flush TLB），讓程序在運(yùn)行過(guò)程中重新建立緩存。

	方法2：允許TLB緩存多個(gè)程序的上下文信息，并通過(guò)ASID（address space identifier，地址空間標(biāo)識(shí)符，可以理解為程序的PID）做區(qū)分。

	方法1實(shí)現(xiàn)簡(jiǎn)單，但是每次程序切換都需要重新預(yù)熱一遍緩存，效率較低，主流的做法是采用方法2。

	需要注意的是TLB是嵌入到CPU芯片之內(nèi)的，對(duì)于多核系統(tǒng)而言，如果程序在CPU之間來(lái)回切換，也是需要重新建立TLB緩存！因此，把一個(gè)程序綁定在一個(gè)固定的核上有助于提升性能。

	讓頁(yè)表更小

	大頁(yè)內(nèi)存

	降低頁(yè)表大小最簡(jiǎn)單的方法就是讓頁(yè)更大。前文的例子中，地址空間為32-bit，頁(yè)的大小為4KB，PTE的大小為4-byte，那么每個(gè)頁(yè)表需要4MB的內(nèi)存空間?，F(xiàn)在，我們把頁(yè)的大小增加到16KB，其他保持不變，那么每個(gè)頁(yè)表只需要個(gè)PTE，也即1MB內(nèi)存，內(nèi)存占用降低了4倍。

	大頁(yè)內(nèi)存對(duì)TLB的使用也有優(yōu)化效果，因TLB能夠緩存的上下文數(shù)量是固定的，當(dāng)頁(yè)的數(shù)量更少時(shí)，上下文換出的頻率會(huì)降低，TLB的緩存命中率也就增加了，從而讓地址轉(zhuǎn)換的效率更高。

	段頁(yè)式內(nèi)存管理

	根據(jù)前文所述，程序的地址空間中，堆與棧之間的空間很多時(shí)候都是處于未使用狀態(tài)。對(duì)應(yīng)到頁(yè)表里，就是有很大一部分的PTE是invalid狀態(tài)。但因?yàn)?strong>頁(yè)表要涵蓋整個(gè)地址空間的范圍，這部分invalid的PTE只能留在頁(yè)表中，從而造成了很大的空間浪費(fèi)。

	圖21

	前文中，我們通過(guò)段式內(nèi)存管理解決了堆與棧之間內(nèi)存空間的浪費(fèi)問(wèn)題。對(duì)應(yīng)到頁(yè)表中，我們也可以為頁(yè)式內(nèi)存管理引入段式管理的方式，也即段頁(yè)式內(nèi)存管理，解決頁(yè)表空間浪費(fèi)的問(wèn)題。

	具體的方法是，為程序的地址空間劃分出多個(gè)段，比如Code、Heap、Stack等。然后，在每個(gè)段內(nèi)單獨(dú)進(jìn)行頁(yè)式管理，也即為每個(gè)段引入一個(gè)頁(yè)表：

	圖22

	從上圖可知，將頁(yè)表分段之后，頁(yè)表不再需要記錄那些處于空閑狀態(tài)的頁(yè)的PTE，從而節(jié)省了內(nèi)存空間的消耗。

	多級(jí)頁(yè)表

	降低頁(yè)表大小另一個(gè)常見(jiàn)的方法就是多級(jí)頁(yè)表（Multi-level Page Table），多級(jí)頁(yè)表的思路也是減少處于空閑狀態(tài)的頁(yè)的PTE數(shù)量，但方法與段頁(yè)式內(nèi)存管理不同。如果說(shuō)段頁(yè)式內(nèi)存管理可以看成是將頁(yè)表分段，那么多級(jí)頁(yè)表則可以看成是將頁(yè)表分頁(yè)。

	具體的做法是將頁(yè)表按照一定大小分成多個(gè)部分（頁(yè)目錄，Page Directory，PD），如果某個(gè)頁(yè)目錄下所有的頁(yè)都是處于空閑狀態(tài)，則無(wú)須為該頁(yè)目錄下的頁(yè)申請(qǐng)PTE。

	以二級(jí)頁(yè)表為例，下圖對(duì)比了普通頁(yè)表和多級(jí)頁(yè)表的構(gòu)成差異：

	圖23

	下面，我們?cè)賹?duì)比一下普通頁(yè)表和多級(jí)頁(yè)表的空間消耗。還是假設(shè)地址空間為32-bit，頁(yè)的大小為4KB，PTE的大小為4-byte，一共有個(gè)頁(yè)，那么普通頁(yè)表需要4MB的內(nèi)存空間?，F(xiàn)在，我們將個(gè)頁(yè)切分為份，也即有個(gè)頁(yè)目錄，每個(gè)頁(yè)目錄下管理個(gè)頁(yè)，也即有個(gè)PDE（Page Directory Entry）。假設(shè)PDE也占4-byte內(nèi)存，且根據(jù)20/80定律假設(shè)有80%的頁(yè)處于空閑狀態(tài)，那么二級(jí)頁(yè)表只需要0.804MB！()

	由此可見(jiàn)，多級(jí)頁(yè)表能夠有效降低頁(yè)表的內(nèi)存消耗。多級(jí)頁(yè)表在實(shí)際運(yùn)用中還是較為常見(jiàn)的，比如Linux系統(tǒng)采用的就是4級(jí)頁(yè)表的結(jié)構(gòu)。

	Swap Sapce: 磁盤(pán)交換區(qū)

	到目前為止，我們都是假設(shè)物理內(nèi)存足夠大，可以容納所有程序的虛擬內(nèi)存空間。然而，這往往是不切實(shí)際的，以32-bit地址空間為例，一個(gè)程序的虛擬內(nèi)存為4G，假設(shè)有100個(gè)程序，那么一共需要400G的物理內(nèi)存（忽略共享部分）！另外，程序運(yùn)行過(guò)程中，并不是一直都需要所有的頁(yè)，很多時(shí)候只需要其中的一小部分。

	因此，如果我們可以先把那些暫時(shí)用不到的頁(yè)先存在磁盤(pán)上，等需要用到時(shí)再加載到內(nèi)存上，那么就可以節(jié)省很多物理內(nèi)存。磁盤(pán)中用來(lái)存放這些頁(yè)的區(qū)域，被稱(chēng)作Swap Sapce，也即交換區(qū)。

	圖24

	在這種機(jī)制之下，當(dāng)程序訪(fǎng)問(wèn)某一個(gè)地址，而這個(gè)地址所在的頁(yè)又不在內(nèi)存上時(shí)，就會(huì)觸發(fā)缺頁(yè)（Page Fault）中斷。就像TLB緩存不命中時(shí)會(huì)帶來(lái)額外的開(kāi)銷(xiāo)一樣，缺頁(yè)也會(huì)導(dǎo)致內(nèi)存的訪(fǎng)問(wèn)效率降低。因?yàn)樵谔幚砣表?yè)中斷時(shí)，OS必須從磁盤(pán)交換區(qū)上把數(shù)據(jù)加載到內(nèi)存上；而且當(dāng)空閑內(nèi)存不足時(shí)，OS還必須將內(nèi)存上的某些頁(yè)換出到交換區(qū)中。這一進(jìn)一出的磁盤(pán)IO訪(fǎng)問(wèn)也直接導(dǎo)致缺頁(yè)發(fā)生時(shí)，內(nèi)存訪(fǎng)問(wèn)的效率下降許多。

	因此，在空閑內(nèi)存不足時(shí)，頁(yè)的換出策略顯得極為重要。如果把一個(gè)即將要被訪(fǎng)問(wèn)的頁(yè)換出到交換區(qū)上，就會(huì)帶來(lái)本可避免的無(wú)謂消耗。頁(yè)的換出策略很多，常見(jiàn)的有FIFO（先進(jìn)先出）、Random（隨機(jī)）、LRU（最近最少使用）、LFU（最近最不經(jīng)常使用）等。在常見(jiàn)的工作負(fù)載下，F(xiàn)IFO和Random算法的效果較差，實(shí)際用的不多；LRU和LFU算法都是建立在歷史內(nèi)存訪(fǎng)問(wèn)統(tǒng)計(jì)的基礎(chǔ)上，因此表現(xiàn)較前兩者好些，實(shí)際應(yīng)用也多一些。目前很多主流的操作系統(tǒng)的頁(yè)換出算法都是在LRU或LFU的基礎(chǔ)上進(jìn)行優(yōu)化改進(jìn)的結(jié)果。

	最后

	本文主要介紹了OS內(nèi)存管理的一些基本原理，從獨(dú)占式內(nèi)存管理，到頁(yè)式內(nèi)存管理，這過(guò)程中經(jīng)歷了許多次優(yōu)化。這其中的每一種優(yōu)化手段，都朝著如下3個(gè)目標(biāo)前進(jìn)：

	1、透明化（transparency）。內(nèi)存管理的細(xì)節(jié)對(duì)程序不可見(jiàn)，換句話(huà)說(shuō)，程序可以自認(rèn)為獨(dú)占整個(gè)內(nèi)存空間。

	2、效率（efficiency ）。地址轉(zhuǎn)換和內(nèi)存訪(fǎng)問(wèn)的效率要高，不能讓程序運(yùn)行太慢；空間利用效率也要高，不能占用太多空閑內(nèi)存。

	3、保護(hù)（protection）。保證OS自身不受應(yīng)用程序的影響；應(yīng)用程序之間也不能相互影響。

	當(dāng)然，目前主流的操作系統(tǒng)（如Linux、MacOS等）的內(nèi)存管理機(jī)制要比本文介紹的原理復(fù)雜許多，但本質(zhì)原理依然離不開(kāi)本文所描述的幾種基礎(chǔ)的內(nèi)存管理原理。

	　　審核編輯：湯梓紅