虛擬地址、物理地址、邏輯地址、線性地址

虛擬地址又叫線性地址。linux沒(méi)有采用分段機(jī)制，所以邏輯地址和虛擬地址（線性地址）（在用戶態(tài)，內(nèi)核態(tài)邏輯地址專指下文說(shuō)的線性偏移前的地址）是一個(gè)概念。物理地址自不必提。內(nèi)核的虛擬地址和物理地址，大部分只差一個(gè)線性偏移量。用戶空間的虛擬地址和物理地址則采用了多級(jí)頁(yè)表進(jìn)行映射，但仍稱之為線性地址。

DMA/HIGH_MEM/NROMAL 分區(qū)

在x86結(jié)構(gòu)中，Linux內(nèi)核虛擬地址空間劃分0~3G為用戶空間，3~4G為內(nèi)核空間(注意，內(nèi)核可以使用的線性地址只有1G)。內(nèi)核虛擬空間（3G~4G）又劃分為三種類型的區(qū)：

ZONE_DMA 3G之后起始的16MB

ZONE_NORMAL 16MB~896MB

ZONE_HIGHMEM 896MB ~1G

由于內(nèi)核的虛擬和物理地址只差一個(gè)偏移量：物理地址 = 邏輯地址 – 0xC0000000。所以如果1G內(nèi)核空間完全用來(lái)線性映射，顯然物理內(nèi)存也只能訪問(wèn)到1G區(qū)間，這顯然是不合理的。HIGHMEM就是為了解決這個(gè)問(wèn)題，專門(mén)開(kāi)辟的一塊不必線性映射，可以靈活定制映射，以便訪問(wèn)1G以上物理內(nèi)存的區(qū)域。從網(wǎng)上扣來(lái)一圖，

?

高端內(nèi)存的劃分，又如下圖，

?

?
?

內(nèi)核直接映射空間 PAGE_OFFSET~VMALLOC_START，kmalloc和__get_free_page()分配的是這里的頁(yè)面。二者是借助slab分配器，直接分配物理頁(yè)再轉(zhuǎn)換為邏輯地址（物理地址連續(xù)）。適合分配小段內(nèi)存。此區(qū)域 包含了內(nèi)核鏡像、物理頁(yè)框表mem_map等資源。

內(nèi)核動(dòng)態(tài)映射空間 VMALLOC_START~VMALLOC_END，被vmalloc用到，可表示的空間大。

內(nèi)核永久映射空間 PKMAP_BASE ~ FIXADDR_START，kmap

內(nèi)核臨時(shí)映射空間 FIXADDR_START~FIXADDR_TOP，kmap_atomic

伙伴算法和slab分配器

伙伴Buddy算法解決了外部碎片問(wèn)題.內(nèi)核在每個(gè)zone區(qū)管理著可用的頁(yè)面，按2的冪級(jí)（order）大小排成鏈表隊(duì)列，存放在free_area數(shù)組。

?

?

具體buddy管理基于位圖，其分配回收頁(yè)面的算法描述如下，

buddy算法舉例描述:

假設(shè)我們的系統(tǒng)內(nèi)存只有16個(gè)頁(yè)面RAM。因?yàn)镽AM只有16個(gè)頁(yè)面，我們只需用四個(gè)級(jí)別（orders）的伙伴位圖（因?yàn)樽畲筮B續(xù)內(nèi)存大小為16個(gè)頁(yè)面），如下圖所示。

?

?

?

order（0）bimap有8個(gè)bit位（頁(yè)面最多16個(gè)頁(yè)面，所以16/2） order（1）bimap有4個(gè)bit位（order（0）bimap有8個(gè)bit位，所以8/2）； 也就是order（1）第一塊由兩個(gè)頁(yè)框page1 與page2組成與order（1）第2塊由兩個(gè)頁(yè)框page3 與page4組成，這兩個(gè)塊之間有一個(gè)bit位 order（2）bimap有2個(gè)bit位（order（1）bimap有4個(gè)bit位，所以4/2） order（3）bimap有1個(gè)bit位（order（2）bimap有4個(gè)bit位，所以2/2） 在order（0），第一個(gè)bit表示開(kāi)始的2個(gè)頁(yè)面，第二個(gè)bit表示接下來(lái)的2個(gè)頁(yè)面，以此類推。因?yàn)轫?yè)面4已分配，而頁(yè)面5空閑，故第三個(gè)bit為1。 同樣在order（1）中，bit3是1的原因是一個(gè)伙伴完全空閑（頁(yè)面8和9），和它對(duì)應(yīng)的伙伴（頁(yè)面10和11）卻并非如此，故以后回收頁(yè)面時(shí)，可以合并。

分配過(guò)程

當(dāng)我們需要order（1）的空閑頁(yè)面塊時(shí)，則執(zhí)行以下步驟：

1、初始空閑鏈表為： order(0): 5, 10 order(1): 8 [8,9] order(2): 12 [12,13,14,15] order(3): 2、從上面空閑鏈表中，我們可以看出，order（1）鏈表上，有一個(gè)空閑的頁(yè)面塊，把它分配給用戶，并從該鏈表中刪除。 3、當(dāng)我們?cè)傩枰粋€(gè)order（1）的塊時(shí)，同樣我們從order（1）空閑鏈表上開(kāi)始掃描。 4、若在order（1）上沒(méi)有空閑頁(yè)面塊，那么我們就到更高的級(jí)別（order）上找，order（2）。 5、此時(shí)（order（1）上沒(méi)有空閑頁(yè)面塊）有一個(gè)空閑頁(yè)面塊，該塊是從頁(yè)面12開(kāi)始。該頁(yè)面塊被分割成兩個(gè)稍微小一些order（1）的頁(yè)面塊，[12，13]和[14，15]。[14，15]頁(yè)面塊加到order（1）空閑鏈表中，同時(shí)[12，13]頁(yè)面塊返回給用戶。 6、最終空閑鏈表為： order(0): 5, 10 order(1): 14 [14,15] order(2): order(3):

回收過(guò)程

當(dāng)我們回收頁(yè)面11（order 0）時(shí)，則執(zhí)行以下步驟：

1、找到在order（0）伙伴位圖中代表頁(yè)面11的位，計(jì)算使用下面公示： index = page_idx >> (order + 1) = 11 >> (0 + 1) = 5 2、檢查上面一步計(jì)算位圖中相應(yīng)bit的值。若該bit值為1，則和我們臨近的，有一個(gè)空閑伙伴。Bit5的值為1（注意是從bit0開(kāi)始的，Bit5即為第6bit），因?yàn)樗幕锇轫?yè)面10是空閑的。 3、現(xiàn)在我們重新設(shè)置該bit的值為0，因?yàn)榇藭r(shí)兩個(gè)伙伴（頁(yè)面10和頁(yè)面11）完全空閑。 4、我們將頁(yè)面10，從order（0）空閑鏈表中摘除。 5、此時(shí)，我們對(duì)2個(gè)空閑頁(yè)面（頁(yè)面10和11，order（1））進(jìn)行進(jìn)一步操作。 6、新的空閑頁(yè)面是從頁(yè)面10開(kāi)始的，于是我們?cè)趏rder（1）的伙伴位圖中找到它的索引，看是否有空閑的伙伴，以進(jìn)一步進(jìn)行合并操作。使用第一步中的計(jì)算公司，我們得到bit 2（第3位）。 7、Bit 2（order（1）位圖）同樣也是1，因?yàn)樗幕锇轫?yè)面塊（頁(yè)面8和9）是空閑的。 8、重新設(shè)置bit2（order（1）位圖）的值，然后在order（1）鏈表中刪除該空閑頁(yè)面塊。 9、現(xiàn)在我們合并成了4頁(yè)面大?。◤捻?yè)面8開(kāi)始）的空閑塊，從而進(jìn)入另外的級(jí)別。在order（2）中找到伙伴位圖對(duì)應(yīng)的bit值，是bit1，且值為1，需進(jìn)一步合并（原因同上）。 10、從oder（2）鏈表中摘除空閑頁(yè)面塊（從頁(yè)面12開(kāi)始），進(jìn)而將該頁(yè)面塊和前面合并得到的頁(yè)面塊進(jìn)一步合并。現(xiàn)在我們得到從頁(yè)面8開(kāi)始，大小為8個(gè)頁(yè)面的空閑頁(yè)面塊。 11、我們進(jìn)入另外一個(gè)級(jí)別，order（3）。它的位索引為0，它的值同樣為0。這意味著對(duì)應(yīng)的伙伴不是全部空閑的，所以沒(méi)有再進(jìn)一步合并的可能。我們僅設(shè)置該bit為1，然后將合并得到的空閑頁(yè)面塊放入order（3）空閑鏈表中。 12、最終我們得到大小為8個(gè)頁(yè)面的空閑塊，

?

?

buddy避免內(nèi)部碎片的努力

物理內(nèi)存的碎片化一直是Linux操作系統(tǒng)的弱點(diǎn)之一，盡管已經(jīng)有人提出了很多解決方法，但是沒(méi)有哪個(gè)方法能夠徹底的解決，memory buddy分配就是解決方法之一。 我們知道磁盤(pán)文件也有碎片化問(wèn)題，但是磁盤(pán)文件的碎片化只會(huì)減慢系統(tǒng)的讀寫(xiě)速度，并不會(huì)導(dǎo)致功能性錯(cuò)誤，而且我們還可以在不影響磁盤(pán)功能的前提的下，進(jìn)行磁盤(pán)碎片整理。而物理內(nèi)存碎片則截然不同，物理內(nèi)存和操作系統(tǒng)結(jié)合的太過(guò)于緊密，以至于我們很難在運(yùn)行時(shí)，進(jìn)行物理內(nèi)存的搬移（這一點(diǎn)上，磁盤(pán)碎片要容易的多；實(shí)際上mel gorman已經(jīng)提交了內(nèi)存緊縮的patch，只是還沒(méi)有被主線內(nèi)核接收）。 因此解決的方向主要放在預(yù)防碎片上。在2.6.24內(nèi)核開(kāi)發(fā)期間，防止碎片的內(nèi)核功能加入了主線內(nèi)核。在了解反碎片的基本原理前，先對(duì)內(nèi)存頁(yè)面做個(gè)歸類：

不可移動(dòng)頁(yè)面 unmoveable：在內(nèi)存中位置必須固定，無(wú)法移動(dòng)到其他地方，核心內(nèi)核分配的大部分頁(yè)面都屬于這一類。

可回收頁(yè)面 reclaimable：不能直接移動(dòng)，但是可以回收，因?yàn)檫€可以從某些源重建頁(yè)面，比如映射文件的數(shù)據(jù)屬于這種類別，kswapd會(huì)按照一定的規(guī)則，周期性的回收這類頁(yè)面。

可移動(dòng)頁(yè)面 movable：可以隨意的移動(dòng)。屬于用戶空間應(yīng)用程序的頁(yè)屬于此類頁(yè)面，它們是通過(guò)頁(yè)表映射的，因此我們只需要更新頁(yè)表項(xiàng)，并把數(shù)據(jù)復(fù)制到新位置就可以了，當(dāng)然要注意，一個(gè)頁(yè)面可能被多個(gè)進(jìn)程共享，對(duì)應(yīng)著多個(gè)頁(yè)表項(xiàng)。

防止碎片的方法就是把這三類page放在不同的鏈表上，避免不同類型頁(yè)面相互干擾。考慮這樣的情形，一個(gè)不可移動(dòng)的頁(yè)面位于可移動(dòng)頁(yè)面中間，那么我們移動(dòng)或者回收這些頁(yè)面后，這個(gè)不可移動(dòng)的頁(yè)面阻礙著我們獲得更大的連續(xù)物理空閑空間。

?

每個(gè)zone區(qū)都有一個(gè)自己的失活凈頁(yè)面隊(duì)列，與此對(duì)應(yīng)的是兩個(gè)跨zone的全局隊(duì)列，失活臟頁(yè)隊(duì)列 和 活躍隊(duì)列。這些隊(duì)列都是通過(guò)page結(jié)構(gòu)的lru指針鏈入的。

思考：失活隊(duì)列的意義是什么(見(jiàn))?內(nèi)核源代碼情景分析>

slab分配器：解決內(nèi)部碎片問(wèn)題

內(nèi)核通常依賴于對(duì)小對(duì)象的分配，它們會(huì)在系統(tǒng)生命周期內(nèi)進(jìn)行無(wú)數(shù)次分配。slab 緩存分配器通過(guò)對(duì)類似大小（遠(yuǎn)小于1page）的對(duì)象進(jìn)行緩存而提供這種功能，從而避免了常見(jiàn)的內(nèi)部碎片問(wèn)題。此處暫貼一圖，關(guān)于其原理，常見(jiàn)參考文獻(xiàn)3。很顯然，slab機(jī)制是基于buddy算法的，前者是對(duì)后者的細(xì)化。

?

?

頁(yè)面回收/側(cè)重機(jī)制

頁(yè)面回收簡(jiǎn)述

有頁(yè)面分配，就會(huì)有頁(yè)面回收。頁(yè)面回收的方法大體上可分為兩種：

一是主動(dòng)釋放。就像用戶程序通過(guò)free函數(shù)釋放曾經(jīng)通過(guò)malloc函數(shù)分配的內(nèi)存一樣，頁(yè)面的使用者明確知道頁(yè)面什么時(shí)候要被使用，什么時(shí)候又不再需要了。 上面提到的前兩種分配方式，一般都是由內(nèi)核程序主動(dòng)釋放的。對(duì)于直接從伙伴系統(tǒng)分配的頁(yè)面，這是由使用者使用free_pages之類的函數(shù)主動(dòng)釋放的，頁(yè)面釋放后被直接放歸伙伴系統(tǒng)；從slab中分配的對(duì)象（使用kmem_cache_alloc函數(shù)），也是由使用者主動(dòng)釋放的（使用kmem_cache_free函數(shù)）。

另一種頁(yè)面回收方式是通過(guò)linux內(nèi)核提供的頁(yè)框回收算法（PFRA）進(jìn)行回收。頁(yè)面的使用者一般將頁(yè)面當(dāng)作某種緩存，以提高系統(tǒng)的運(yùn)行效率。緩存一直存在固然好，但是如果緩存沒(méi)有了也不會(huì)造成什么錯(cuò)誤，僅僅是效率受影響而已。頁(yè)面的使用者不明確知道這些緩存頁(yè)面什么時(shí)候最好被保留，什么時(shí)候最好被回收，這些都交由PFRA來(lái)關(guān)心。

簡(jiǎn)單來(lái)說(shuō)，PFRA要做的事就是回收這些可以被回收的頁(yè)面。為了避免系統(tǒng)陷入頁(yè)面緊缺的困境，PFRA會(huì)在內(nèi)核線程中周期性地被調(diào)用運(yùn)行?；蛘哂捎谙到y(tǒng)已經(jīng)頁(yè)面緊缺，試圖分配頁(yè)面的內(nèi)核執(zhí)行流程因?yàn)榈貌坏叫枰捻?yè)面，而同步地調(diào)用PFRA。

上面提到的后兩種分配方式，一般是由PFRA來(lái)進(jìn)行回收的（或者由類似刪除文件、進(jìn)程退出、這樣的過(guò)程來(lái)同步回收）。

?

PFRA回收一般頁(yè)面

而對(duì)于上面提到的前兩種頁(yè)面分配方式（直接分配頁(yè)面和通過(guò)slab分配對(duì)象），也有可能需要通過(guò)PFRA來(lái)回收。

頁(yè)面的使用者可以向PFRA注冊(cè)回調(diào)函數(shù)（使用register_shrink函數(shù)）。然后由PFRA在適當(dāng)?shù)臅r(shí)機(jī)來(lái)調(diào)用這些回調(diào)函數(shù)，以觸發(fā)對(duì)相應(yīng)頁(yè)面或?qū)ο蟮幕厥铡?/p>

其中較為典型的是對(duì)dentry的回收。dentry是由slab分配的，用于表示虛擬文件系統(tǒng)目錄結(jié)構(gòu)的對(duì)象。在dentry的引用記數(shù)被減為0的時(shí)候，dentry并不是直接被釋放，而是被放到一個(gè)LRU鏈表中緩存起來(lái)，便于后續(xù)的使用。

而這個(gè)LRU鏈表中的dentry最終是需要被回收的，于是虛擬文件系統(tǒng)在初始化時(shí)，調(diào)用register_shrinker注冊(cè)了回收函數(shù)shrink_dcache_memory。

系統(tǒng)中所有文件系統(tǒng)的超級(jí)塊對(duì)象被存放在一個(gè)鏈表中，shrink_dcache_memory函數(shù)掃描這個(gè)鏈表，獲取每個(gè)超級(jí)塊的未被使用dentry的LRU，然后從中回收一些最老的dentry。隨著dentry的釋放，對(duì)應(yīng)的inode將被減引用，也可能引起inode被釋放。

inode被釋放后也是放在一個(gè)未使用鏈表中，虛擬文件系統(tǒng)在初始化時(shí)還調(diào)用register_shrinker注冊(cè)了回調(diào)函數(shù)shrink_icache_memory，用來(lái)回收這些未使用的inode，從而inode中關(guān)聯(lián)的磁盤(pán)高速緩存也將被釋放。

?

另外，隨著系統(tǒng)的運(yùn)行，slab中可能會(huì)存在很多的空閑對(duì)象（比如在對(duì)某一對(duì)象的使用高峰過(guò)后）。PFRA中的cache_reap函數(shù)就用于回收這些多余的空閑對(duì)象，如果某些空閑的對(duì)象正好能夠還原成一個(gè)頁(yè)面，則這個(gè)頁(yè)面可以被釋放回伙伴系統(tǒng)；

cache_reap函數(shù)要做的事情說(shuō)起來(lái)很簡(jiǎn)單。系統(tǒng)中所有存放對(duì)象池的kmem_cache結(jié)構(gòu)連成一個(gè)鏈表，cache_reap函數(shù)掃描其中的每一個(gè)對(duì)象池，然后尋找可以回收的頁(yè)面，并將其回收。（當(dāng)然，實(shí)際的過(guò)程要更復(fù)雜一點(diǎn)。）

關(guān)于內(nèi)存映射

前面說(shuō)到，磁盤(pán)高速緩存和內(nèi)存映射一般由PFRA來(lái)進(jìn)行回收。PFRA對(duì)這兩者的回收是很類似的，實(shí)際上，磁盤(pán)高速緩存很可能就被映射到了用戶空間。下面簡(jiǎn)單對(duì)內(nèi)存映射做一些介紹：

內(nèi)存映射分為文件映射和匿名映射

文件映射是指代表這個(gè)映射的vma對(duì)應(yīng)到一個(gè)文件中的某個(gè)區(qū)域。這種映射方式相對(duì)較少被用戶態(tài)程序顯式地使用，用戶態(tài)程序一般習(xí)慣于open一個(gè)文件、然后read/write去讀寫(xiě)文件。

而實(shí)際上，用戶程序也可以使用mmap系統(tǒng)調(diào)用將一個(gè)文件的某個(gè)部分映射到內(nèi)存上（對(duì)應(yīng)到一個(gè)vma），然后以訪存的方式去讀寫(xiě)文件。盡管用戶程序較少這樣使用，但是用戶進(jìn)程中卻充斥著這樣的映射：進(jìn)程正在執(zhí)行的可執(zhí)行代碼（包括可執(zhí)行文件、lib庫(kù)文件）就是以這樣的方式被映射的。

實(shí)際上，文件映射是將文件的磁盤(pán)高速緩存中的頁(yè)面直接映射到了用戶空間（可見(jiàn)，文件映射的頁(yè)面是磁盤(pán)高速緩存頁(yè)面的子集），用戶可以0拷貝地對(duì)其進(jìn)行讀寫(xiě)。而使用read/write的話，則會(huì)在用戶空間的內(nèi)存和磁盤(pán)高速緩存間發(fā)生一次拷貝。

匿名映射相對(duì)于文件映射，代表這個(gè)映射的vma沒(méi)有對(duì)應(yīng)到文件。對(duì)于用戶空間普通的內(nèi)存分配（堆空間、棧空間），都屬于匿名映射。 顯然，多個(gè)進(jìn)程可能通過(guò)各自的文件映射來(lái)映射到同一個(gè)文件上（比如大多數(shù)進(jìn)程都映射了libc庫(kù)的so文件）；那匿名映射呢？實(shí)際上，多個(gè)進(jìn)程也可能通過(guò)各自的匿名映射來(lái)映射到同一段物理內(nèi)存上，這種情況是由于fork之后父子進(jìn)程共享原來(lái)的物理內(nèi)存（copy-on-write）而引起的。

文件映射又分為共享映射和私有映射。私有映射時(shí)，如果進(jìn)程對(duì)映射的地址空間進(jìn)行寫(xiě)操作，則映射對(duì)應(yīng)的磁盤(pán)高速緩存并不會(huì)直接被寫(xiě)。而是將原有內(nèi)容復(fù)制一份，然后再寫(xiě)這個(gè)復(fù)制品，并且當(dāng)前進(jìn)程的對(duì)應(yīng)頁(yè)面映射將切換到這個(gè)復(fù)制品上去（寫(xiě)時(shí)復(fù)制）。也就是說(shuō)，寫(xiě)操作是只有自己可見(jiàn)的。而對(duì)于共享映射，寫(xiě)操作則會(huì)影響到磁盤(pán)高速緩存，是大家都可見(jiàn)的。

哪些頁(yè)面該回收

至于回收，磁盤(pán)高速緩存的頁(yè)面（包括文件映射的頁(yè)面）都是可以被丟棄并回收的。但是如果頁(yè)面是臟頁(yè)面，則丟棄之前必須將其寫(xiě)回磁盤(pán)。

而匿名映射的頁(yè)面則都是不可以丟棄的，因?yàn)轫?yè)面里面存有用戶程序正在使用的數(shù)據(jù)，丟棄之后數(shù)據(jù)就沒(méi)法還原了。相比之下，磁盤(pán)高速緩存頁(yè)面中的數(shù)據(jù)本身是保存在磁盤(pán)上的，可以復(fù)現(xiàn)。

于是，要想回收匿名映射的頁(yè)面，只好先把頁(yè)面上的數(shù)據(jù)轉(zhuǎn)儲(chǔ)到磁盤(pán)，這就是頁(yè)面交換（swap）。顯然，頁(yè)面交換的代價(jià)相對(duì)更高一些。

匿名映射的頁(yè)面可以被交換到磁盤(pán)上的交換文件或交換分區(qū)上（分區(qū)即是設(shè)備，設(shè)備即也是文件。所以下文統(tǒng)稱為交換文件）。

于是，除非頁(yè)面被保留或被上鎖（頁(yè)面標(biāo)記PG_reserved/PG_locked被置位。某些情況下，內(nèi)核需要暫時(shí)性地將頁(yè)面保留，避免被回收），所有的磁盤(pán)高速緩存頁(yè)面都可回收，所有的匿名映射頁(yè)面都可交換。

盡管可以回收的頁(yè)面很多，但是顯然PFRA應(yīng)當(dāng)盡可能少地去回收/交換（因?yàn)檫@些頁(yè)面要從磁盤(pán)恢復(fù)，需要很大的代價(jià)）。所以，PFRA僅當(dāng)必要時(shí)才回收/交換一部分很少被使用的頁(yè)面，每次回收的頁(yè)面數(shù)是一個(gè)經(jīng)驗(yàn)值：32。

于是，所有這些磁盤(pán)高速緩存頁(yè)面和匿名映射頁(yè)面都被放到了一組LRU里面。（實(shí)際上，每個(gè)zone就有一組這樣的LRU，頁(yè)面都被放到自己對(duì)應(yīng)的zone的LRU中。）

一組LRU由幾對(duì)鏈表組成，有磁盤(pán)高速緩存頁(yè)面（包括文件映射頁(yè)面）的鏈表、匿名映射頁(yè)面的鏈表、等。一對(duì)鏈表實(shí)際上是active和inactive兩個(gè)鏈表，前者是最近使用過(guò)的頁(yè)面、后者是最近未使用的頁(yè)面。

進(jìn)行頁(yè)面回收的時(shí)候，PFRA要做兩件事情，一是將active鏈表中最近最少使用的頁(yè)面移動(dòng)到inactive鏈表、二是嘗試將inactive鏈表中最近最少使用的頁(yè)面回收。

確定最近最少使用

現(xiàn)在就有一個(gè)問(wèn)題了，怎么確定active/inactive鏈表中哪些頁(yè)面是最近最少使用的呢？

?

一種方法是排序，當(dāng)頁(yè)面被訪問(wèn)時(shí)，將其移動(dòng)到鏈表的尾部（假設(shè)回收從頭部開(kāi)始）。但是這就意味著頁(yè)面在鏈表中的位置可能頻繁移動(dòng)，并且移動(dòng)之前還必須先上鎖（可能有多個(gè)CPU在同時(shí)訪問(wèn)），這樣做對(duì)效率影響很大。

linux內(nèi)核采用的是標(biāo)記加順序的辦法。當(dāng)頁(yè)面在active和inactive兩個(gè)鏈表之間移動(dòng)時(shí)，總是將其放到鏈表的尾部（同上，假設(shè)回收從頭部開(kāi)始）。

頁(yè)面沒(méi)有在鏈表間移動(dòng)時(shí)，并不會(huì)調(diào)整它們的順序。而是通過(guò)訪問(wèn)標(biāo)記來(lái)表示頁(yè)面是否剛被訪問(wèn)過(guò)。如果inactive鏈表中已設(shè)置訪問(wèn)標(biāo)記的頁(yè)面再被訪問(wèn)，則將其移動(dòng)到active鏈表中，并且清除訪問(wèn)標(biāo)記。（實(shí)際上，為了避免訪問(wèn)沖突，頁(yè)面并不會(huì)直接從inactive鏈表移動(dòng)到active鏈表，而是有一個(gè)pagevec中間結(jié)構(gòu)用作緩沖，以避免鎖鏈表。）

頁(yè)面的訪問(wèn)標(biāo)記有兩種情況，一是放在page->flags中的PG_referenced標(biāo)記，在頁(yè)面被訪問(wèn)時(shí)該標(biāo)記置位。對(duì)于磁盤(pán)高速緩存中（未被映射）的頁(yè)面，用戶進(jìn)程通過(guò)read、write之類的系統(tǒng)調(diào)用去訪問(wèn)它們，系統(tǒng)調(diào)用代碼中會(huì)將對(duì)應(yīng)頁(yè)面的PG_referenced標(biāo)記置位。 而對(duì)于內(nèi)存映射的頁(yè)面，用戶進(jìn)程可以直接訪問(wèn)它們（不經(jīng)過(guò)內(nèi)核），所以這種情況下的訪問(wèn)標(biāo)記不是由內(nèi)核來(lái)設(shè)置的，而是由mmu。在將虛擬地址映射成物理地址后，mmu會(huì)在對(duì)應(yīng)的頁(yè)表項(xiàng)上置一個(gè)accessed標(biāo)志位，表示頁(yè)面被訪問(wèn)。（同樣的道理，mmu會(huì)在被寫(xiě)的頁(yè)面所對(duì)應(yīng)的頁(yè)表項(xiàng)上置一個(gè)dirty標(biāo)志，表示頁(yè)面是臟頁(yè)面。）

頁(yè)面的訪問(wèn)標(biāo)記（包括上面兩種標(biāo)記）將在PFRA處理頁(yè)面回收的過(guò)程中被清除，因?yàn)樵L問(wèn)標(biāo)記顯然是應(yīng)該有有效期的，而PFRA的運(yùn)行周期就代表這個(gè)有效期。page->flags中的PG_referenced標(biāo)記可以直接清除，而頁(yè)表項(xiàng)中的accessed位則需要通過(guò)頁(yè)面找到其對(duì)應(yīng)的頁(yè)表項(xiàng)后才能清除（見(jiàn)下文的“反向映射”）。

那么，回收過(guò)程又是怎樣掃描LRU鏈表的呢？ 由于存在多組LRU（系統(tǒng)中有多個(gè)zone，每個(gè)zone又有多組LRU），如果PFRA每次回收都掃描所有的LRU找出其中最值得回收的若干個(gè)頁(yè)面的話，回收算法的效率顯然不夠理想。

linux內(nèi)核PFRA使用的掃描方法是：定義一個(gè)掃描優(yōu)先級(jí)，通過(guò)這個(gè)優(yōu)先級(jí)換算出在每個(gè)LRU上應(yīng)該掃描的頁(yè)面數(shù)。整個(gè)回收算法以最低的優(yōu)先級(jí)開(kāi)始，先掃描每個(gè)LRU中最近最少使用的幾個(gè)頁(yè)面，然后試圖回收它們。如果一遍掃描下來(lái)，已經(jīng)回收了足夠數(shù)量的頁(yè)面，則本次回收過(guò)程結(jié)束。否則，增大優(yōu)先級(jí)，再重新掃描，直到足夠數(shù)量的頁(yè)面被回收。而如果始終不能回收足夠數(shù)量的頁(yè)面，則優(yōu)先級(jí)將增加到最大，也就是所有頁(yè)面將被掃描。這時(shí)，就算回收的頁(yè)面數(shù)量還是不足，回收過(guò)程都會(huì)結(jié)束。

每次掃描一個(gè)LRU時(shí)，都從active鏈表和inactive鏈表獲取當(dāng)前優(yōu)先級(jí)對(duì)應(yīng)數(shù)目的頁(yè)面，然后再對(duì)這些頁(yè)面做處理：如果頁(yè)面不能被回收（如被保留或被上鎖），則放回對(duì)應(yīng)鏈表頭部（同上，假設(shè)回收從頭部開(kāi)始）；否則如果頁(yè)面的訪問(wèn)標(biāo)記置位，則清除該標(biāo)記，并將頁(yè)面放回對(duì)應(yīng)鏈表尾部（同上，假設(shè)回收從頭部開(kāi)始）；否則頁(yè)面將從active鏈表被移動(dòng)到inactive鏈表、或從inactive鏈表被回收。

?

被掃描到的頁(yè)面根據(jù)訪問(wèn)標(biāo)記是否置位來(lái)決定其去留。那么這個(gè)訪問(wèn)標(biāo)記是如何設(shè)置的呢？有兩個(gè)途徑，一是用戶通過(guò)read/write之類的系統(tǒng)調(diào)用訪問(wèn)文件時(shí)，內(nèi)核操作磁盤(pán)高速緩存中的頁(yè)面，會(huì)設(shè)置這些頁(yè)面的訪問(wèn)標(biāo)記（設(shè)置在page結(jié)構(gòu)中）；二是進(jìn)程直接訪問(wèn)已映射的頁(yè)面時(shí)，mmu會(huì)自動(dòng)給對(duì)應(yīng)的頁(yè)表項(xiàng)加上訪問(wèn)標(biāo)記（設(shè)置在頁(yè)表的pte中）。關(guān)于訪問(wèn)標(biāo)記的判斷就基于這兩個(gè)信息。（給定一個(gè)頁(yè)面，可能有多個(gè)pte引用到它。如何知道這些pte是否被設(shè)置了訪問(wèn)標(biāo)記呢？那就需要通過(guò)反向映射找到這些pte。下面會(huì)講到。）

PFRA不傾向于從active鏈表回收匿名映射的頁(yè)面，因?yàn)橛脩暨M(jìn)程使用的內(nèi)存一般相對(duì)較少，且回收的話需要進(jìn)行交換，代價(jià)較大。所以在內(nèi)存剩余較多、匿名映射所占比例較少的情況下，都不會(huì)去回收匿名映射對(duì)應(yīng)的active鏈表中的頁(yè)面。（而如果頁(yè)面已經(jīng)被放到inactive鏈表中，就不再去管那么多了。）

反向映射

像這樣，在PFRA處理頁(yè)面回收的過(guò)程中，LRU的inactive鏈表中的某些頁(yè)面可能就要被回收了。

如果頁(yè)面沒(méi)有被映射，直接回收到伙伴系統(tǒng)即可（對(duì)于臟頁(yè)，先寫(xiě)回、再回收）。否則，還有一件麻煩的事情要處理。因?yàn)橛脩暨M(jìn)程的某個(gè)頁(yè)表項(xiàng)正引用著這個(gè)頁(yè)面呢，在回收頁(yè)面之前，還必須給引用它的頁(yè)表項(xiàng)一個(gè)交待。 于是，問(wèn)題就來(lái)了，內(nèi)核怎么知道這個(gè)頁(yè)面被哪些頁(yè)表項(xiàng)所引用呢？為了做到這一點(diǎn)，內(nèi)核建立了從頁(yè)面到頁(yè)表項(xiàng)的反向映射。

通過(guò)反向映射可以找到一個(gè)被映射的頁(yè)面對(duì)應(yīng)的vma，通過(guò)vma->vm_mm->pgd就能找到對(duì)應(yīng)的頁(yè)表。然后通過(guò)page->index得到頁(yè)面的虛擬地址。再通過(guò)虛擬地址從頁(yè)表中找到對(duì)應(yīng)的頁(yè)表項(xiàng)。（前面說(shuō)到的獲取頁(yè)表項(xiàng)中的accessed標(biāo)記，就是通過(guò)反向映射實(shí)現(xiàn)的。）

頁(yè)面對(duì)應(yīng)的page結(jié)構(gòu)中，page->mapping如果最低位置位，則這是一個(gè)匿名映射頁(yè)面，page->mapping指向一個(gè)anon_vma結(jié)構(gòu)；否則是文件映射頁(yè)面，page->mapping文件對(duì)應(yīng)的address_space結(jié)構(gòu)。（顯然，anon_vma結(jié)構(gòu)和address_space結(jié)構(gòu)在分配時(shí)，地址必須要對(duì)齊，至少保證最低位為0。）

對(duì)于匿名映射的頁(yè)面，anon_vma結(jié)構(gòu)作為一個(gè)鏈表頭，將映射這個(gè)頁(yè)面的所有vma通過(guò)vma->anon_vma_node鏈表指針連接起來(lái)。每當(dāng)一個(gè)頁(yè)面被（匿名）映射到一個(gè)用戶空間時(shí)，對(duì)應(yīng)的vma就被加入這個(gè)鏈表。

對(duì)于文件映射的頁(yè)面，address_space結(jié)構(gòu)除了維護(hù)了一棵用于存放磁盤(pán)高速緩存頁(yè)面的radix樹(shù)，還為該文件映射到的所有vma維護(hù)了一棵優(yōu)先搜索樹(shù)。因?yàn)檫@些被文件映射到的vma并不一定都是映射整個(gè)文件，很可能只映射了文件的一部分。所以，這棵優(yōu)先搜索樹(shù)除了索引到所有被映射的vma，還要能知道文件的哪些區(qū)域是映射到哪些vma上的。每當(dāng)一個(gè)頁(yè)面被（文件）映射到一個(gè)用戶空間時(shí)，對(duì)應(yīng)的vma就被加入這個(gè)優(yōu)先搜索樹(shù)。于是，給定磁盤(pán)高速緩存上的一個(gè)頁(yè)面，就能通過(guò)page->index得到頁(yè)面在文件中的位置，就能通過(guò)優(yōu)先搜索樹(shù)找出這個(gè)頁(yè)面映射到的所有vma。

上面兩步中，神奇的page->index做了兩件事，得到頁(yè)面的虛擬地址、得到頁(yè)面在文件磁盤(pán)高速緩存中的位置。

vma->vm_start記錄了vma的首虛擬地址，vma->vm_pgoff記錄了該vma在對(duì)應(yīng)的映射文件（或共享內(nèi)存）中的偏移，而page->index記錄了頁(yè)面在文件（或共享內(nèi)存）中的偏移。

通過(guò)vma->vm_pgoff和page->index能得到頁(yè)面在vma中的偏移，加上vma->vm_start就能得到頁(yè)面的虛擬地址；而通過(guò)page->index就能得到頁(yè)面在文件磁盤(pán)高速緩存中的位置。

頁(yè)面換入換出

在找到了引用待回收頁(yè)面的頁(yè)表項(xiàng)后，對(duì)于文件映射，可以直接把引用該頁(yè)面的頁(yè)表項(xiàng)清空。等用戶再訪問(wèn)這個(gè)地址的時(shí)候觸發(fā)缺頁(yè)異常，異常處理代碼再重新分配一個(gè)頁(yè)面，并去磁盤(pán)里面把對(duì)應(yīng)的數(shù)據(jù)讀出來(lái)就行了（說(shuō)不定，頁(yè)面在對(duì)應(yīng)的磁盤(pán)高速緩存里面已經(jīng)有了，因?yàn)槠渌M(jìn)程先訪問(wèn)過(guò)）。這就跟頁(yè)面映射以后，第一次被訪問(wèn)的情形一樣；

對(duì)于匿名映射，先將頁(yè)面寫(xiě)回到交換文件，然后還得在頁(yè)表項(xiàng)中記錄該頁(yè)面在交換文件中的index。

頁(yè)表項(xiàng)中有一個(gè)present位，如果該位被清除，則mmu認(rèn)為頁(yè)表項(xiàng)無(wú)效。在頁(yè)表項(xiàng)無(wú)效的情況下，其他位不被mmu關(guān)心，可以用來(lái)存儲(chǔ)其他信息。這里就用它們來(lái)存儲(chǔ)頁(yè)面在交換文件中的index了（實(shí)際上是交換文件號(hào)+交換文件內(nèi)的索引號(hào)）。

將匿名映射的頁(yè)面交換到交換文件的過(guò)程（換出過(guò)程）與將磁盤(pán)高速緩存中的臟頁(yè)寫(xiě)回文件的過(guò)程很相似。

交換文件也有其對(duì)應(yīng)的address_space結(jié)構(gòu)，匿名映射的頁(yè)面在換出時(shí)先被放到這個(gè)address_space對(duì)應(yīng)磁盤(pán)高速緩存中，然后跟臟頁(yè)寫(xiě)回一樣，被寫(xiě)回到交換文件中。寫(xiě)回完成后，這個(gè)頁(yè)面才被釋放（記住，我們的目的是要釋放這個(gè)頁(yè)面）。

那么為什么不直接把頁(yè)面寫(xiě)回到交換文件，而要經(jīng)過(guò)磁盤(pán)高速緩存呢？因?yàn)椋@個(gè)頁(yè)面可能被映射了多次，不可能一次性把所有用戶進(jìn)程的頁(yè)表中對(duì)應(yīng)的頁(yè)表項(xiàng)都修改好（修改成頁(yè)面在交換文件中的索引），所以在頁(yè)面被釋放的過(guò)程中，頁(yè)面被暫時(shí)放在磁盤(pán)高速緩存上。

而并不是所有頁(yè)表項(xiàng)的修改過(guò)程都是能成功的（比如在修改之前頁(yè)面又被訪問(wèn)了，于是現(xiàn)在又不需要回收這個(gè)頁(yè)面了），所以頁(yè)面放到磁盤(pán)高速緩存的時(shí)間也可能會(huì)很長(zhǎng)。

同樣，將匿名映射的頁(yè)面從交換文件讀出的過(guò)程（換入過(guò)程）也與將文件數(shù)據(jù)讀出的過(guò)程很相似。

先去對(duì)應(yīng)的磁盤(pán)高速緩存上看看頁(yè)面在不在，不在的話再去交換文件里面讀。文件里的數(shù)據(jù)也是被讀到磁盤(pán)高速緩存中的，然后用戶進(jìn)程的頁(yè)表中對(duì)應(yīng)的頁(yè)表項(xiàng)將被改寫(xiě)，直接指向這個(gè)頁(yè)面。

這個(gè)頁(yè)面可能不會(huì)馬上從磁盤(pán)高速緩存中拿下來(lái)，因?yàn)槿绻€有其他用戶進(jìn)程也映射到這個(gè)頁(yè)面（它們的對(duì)應(yīng)頁(yè)表項(xiàng)已經(jīng)被修改成了交換文件的索引），他們也可以引用到這里。直到?jīng)]有其他的頁(yè)表項(xiàng)再引用這個(gè)交換文件索引時(shí)，頁(yè)面才可以從磁盤(pán)高速緩存中被取下來(lái)。

最后的必殺

前面說(shuō)到，PFRA可能掃描了所有的LRU還沒(méi)辦法回收需要的頁(yè)面。同樣，在slab、dentry cache、inode cache、等地方，可能也無(wú)法回收到頁(yè)面。

這時(shí)，如果某段內(nèi)核代碼一定要獲得頁(yè)面呢（沒(méi)有頁(yè)面，系統(tǒng)可能就要崩潰了）？PFRA只好使出最后的必殺技——OOM（out of memory）。所謂的OOM就是尋找一個(gè)最不重要的進(jìn)程，然后將其殺死。通過(guò)釋放這個(gè)進(jìn)程所占有的內(nèi)存頁(yè)面，以緩解系統(tǒng)壓力。

5.內(nèi)存管理架構(gòu)

?

?
?

針對(duì)上圖，說(shuō)幾句，

地址映射(圖：左中)

linux內(nèi)核使用頁(yè)式內(nèi)存管理，應(yīng)用程序給出的內(nèi)存地址是虛擬地址，它需要經(jīng)過(guò)若干級(jí)頁(yè)表一級(jí)一級(jí)的變換，才變成真正的物理地址。

想一下，地址映射還是一件很恐怖的事情。當(dāng)訪問(wèn)一個(gè)由虛擬地址表示的內(nèi)存空間時(shí)，需要先經(jīng)過(guò)若干次的內(nèi)存訪問(wèn)，得到每一級(jí)頁(yè)表中用于轉(zhuǎn)換的頁(yè)表項(xiàng)（頁(yè)表是存放在內(nèi)存里面的），才能完成映射。也就是說(shuō)，要實(shí)現(xiàn)一次內(nèi)存訪問(wèn)，實(shí)際上內(nèi)存被訪問(wèn)了N+1次（N=頁(yè)表級(jí)數(shù)），并且還需要做N次加法運(yùn)算。

所以，地址映射必須要有硬件支持，mmu（內(nèi)存管理單元）就是這個(gè)硬件。并且需要有cache來(lái)保存頁(yè)表，這個(gè)cache就是TLB（Translation lookaside buffer）。

盡管如此，地址映射還是有著不小的開(kāi)銷。假設(shè)cache的訪存速度是內(nèi)存的10倍，命中率是40%，頁(yè)表有三級(jí)，那么平均一次虛擬地址訪問(wèn)大概就消耗了兩次物理內(nèi)存訪問(wèn)的時(shí)間。

于是，一些嵌入式硬件上可能會(huì)放棄使用mmu，這樣的硬件能夠運(yùn)行VxWorks（一個(gè)很高效的嵌入式實(shí)時(shí)操作系統(tǒng)）、linux（linux也有禁用mmu的編譯選項(xiàng)）、等系統(tǒng)。

但是使用mmu的優(yōu)勢(shì)也是很大的，最主要的是出于安全性考慮。各個(gè)進(jìn)程都是相互獨(dú)立的虛擬地址空間，互不干擾。而放棄地址映射之后，所有程序?qū)⑦\(yùn)行在同一個(gè)地址空間。于是，在沒(méi)有mmu的機(jī)器上，一個(gè)進(jìn)程越界訪存，可能引起其他進(jìn)程莫名其妙的錯(cuò)誤，甚至導(dǎo)致內(nèi)核崩潰。

在地址映射這個(gè)問(wèn)題上，內(nèi)核只提供頁(yè)表，實(shí)際的轉(zhuǎn)換是由硬件去完成的。那么內(nèi)核如何生成這些頁(yè)表呢？這就有兩方面的內(nèi)容，虛擬地址空間的管理和物理內(nèi)存的管理。（實(shí)際上只有用戶態(tài)的地址映射才需要管理，內(nèi)核態(tài)的地址映射是寫(xiě)死的。）

虛擬地址管理(圖：左下)

每個(gè)進(jìn)程對(duì)應(yīng)一個(gè)task結(jié)構(gòu)，它指向一個(gè)mm結(jié)構(gòu)，這就是該進(jìn)程的內(nèi)存管理器。（對(duì)于線程來(lái)說(shuō)，每個(gè)線程也都有一個(gè)task結(jié)構(gòu)，但是它們都指向同一個(gè)mm，所以地址空間是共享的。）

mm->pgd指向容納頁(yè)表的內(nèi)存，每個(gè)進(jìn)程有自已的mm，每個(gè)mm有自己的頁(yè)表。于是，進(jìn)程調(diào)度時(shí)，頁(yè)表被切換（一般會(huì)有一個(gè)CPU寄存器來(lái)保存頁(yè)表的地址，比如X86下的CR3，頁(yè)表切換就是改變?cè)摷拇嫫鞯闹担?。所以，各個(gè)進(jìn)程的地址空間互不影響（因?yàn)轫?yè)表都不一樣了，當(dāng)然無(wú)法訪問(wèn)到別人的地址空間上。但是共享內(nèi)存除外，這是故意讓不同的頁(yè)表能夠訪問(wèn)到相同的物理地址上）。

用戶程序?qū)?nèi)存的操作（分配、回收、映射、等）都是對(duì)mm的操作，具體來(lái)說(shuō)是對(duì)mm上的vma（虛擬內(nèi)存空間）的操作。這些vma代表著進(jìn)程空間的各個(gè)區(qū)域，比如堆、棧、代碼區(qū)、數(shù)據(jù)區(qū)、各種映射區(qū)、等等。

用戶程序?qū)?nèi)存的操作并不會(huì)直接影響到頁(yè)表，更不會(huì)直接影響到物理內(nèi)存的分配。比如malloc成功，僅僅是改變了某個(gè)vma，頁(yè)表不會(huì)變，物理內(nèi)存的分配也不會(huì)變。

假設(shè)用戶分配了內(nèi)存，然后訪問(wèn)這塊內(nèi)存。由于頁(yè)表里面并沒(méi)有記錄相關(guān)的映射，CPU產(chǎn)生一次缺頁(yè)異常。內(nèi)核捕捉異常，檢查產(chǎn)生異常的地址是不是存在于一個(gè)合法的vma中。如果不是，則給進(jìn)程一個(gè)"段錯(cuò)誤"，讓其崩潰；如果是，則分配一個(gè)物理頁(yè)，并為之建立映射。

物理內(nèi)存管理(圖：右上)

那么物理內(nèi)存是如何分配的呢？

首先，linux支持NUMA（非均質(zhì)存儲(chǔ)結(jié)構(gòu)），物理內(nèi)存管理的第一個(gè)層次就是介質(zhì)的管理。pg_data_t結(jié)構(gòu)就描述了介質(zhì)。一般而言，我們的內(nèi)存管理介質(zhì)只有內(nèi)存，并且它是均勻的，所以可以簡(jiǎn)單地認(rèn)為系統(tǒng)中只有一個(gè)pg_data_t對(duì)象。

每一種介質(zhì)下面有若干個(gè)zone。一般是三個(gè)，DMA、NORMAL和HIGH。

DMA：因?yàn)橛行┯布到y(tǒng)的DMA總線比系統(tǒng)總線窄，所以只有一部分地址空間能夠用作DMA，這部分地址被管理在DMA區(qū)域（這屬于是高級(jí)貨了）；

HIGH：高端內(nèi)存。在32位系統(tǒng)中，地址空間是4G，其中內(nèi)核規(guī)定3~4G的范圍是內(nèi)核空間，0~3G是用戶空間（每個(gè)用戶進(jìn)程都有這么大的虛擬空間）（圖：中下）。前面提到過(guò)內(nèi)核的地址映射是寫(xiě)死的，就是指這3~4G的對(duì)應(yīng)的頁(yè)表是寫(xiě)死的，它映射到了物理地址的0~1G上。（實(shí)際上沒(méi)有映射1G，只映射了896M。剩下的空間留下來(lái)映射大于1G的物理地址，而這一部分顯然不是寫(xiě)死的）。所以，大于896M的物理地址是沒(méi)有寫(xiě)死的頁(yè)表來(lái)對(duì)應(yīng)的，內(nèi)核不能直接訪問(wèn)它們（必須要建立映射），稱它們?yōu)楦叨藘?nèi)存（當(dāng)然，如果機(jī)器內(nèi)存不足896M，就不存在高端內(nèi)存。如果是64位機(jī)器，也不存在高端內(nèi)存，因?yàn)榈刂房臻g很大很大，屬于內(nèi)核的空間也不止1G了）；

NORMAL：不屬于DMA或HIGH的內(nèi)存就叫NORMAL。

在zone之上的zone_list代表了分配策略，即內(nèi)存分配時(shí)的zone優(yōu)先級(jí)。一種內(nèi)存分配往往不是只能在一個(gè)zone里進(jìn)行分配的，比如分配一個(gè)頁(yè)給內(nèi)核使用時(shí)，最優(yōu)先是從NORMAL里面分配，不行的話就分配DMA里面的好了（HIGH就不行，因?yàn)檫€沒(méi)建立映射），這就是一種分配策略。

每個(gè)內(nèi)存介質(zhì)維護(hù)了一個(gè)mem_map，為介質(zhì)中的每一個(gè)物理頁(yè)面建立了一個(gè)page結(jié)構(gòu)與之對(duì)應(yīng)，以便管理物理內(nèi)存。

每個(gè)zone記錄著它在mem_map上的起始位置。并且通過(guò)free_area串連著這個(gè)zone上空閑的page。物理內(nèi)存的分配就是從這里來(lái)的，從 free_area上把page摘下，就算是分配了。（內(nèi)核的內(nèi)存分配與用戶進(jìn)程不同，用戶使用內(nèi)存會(huì)被內(nèi)核監(jiān)督，使用不當(dāng)就"段錯(cuò)誤"；而內(nèi)核則無(wú)人監(jiān)督，只能靠自覺(jué)，不是自己從free_area摘下的page就不要亂用。）

建立地址映射

內(nèi)核需要物理內(nèi)存時(shí)，很多情況是整頁(yè)分配的，這在上面的mem_map中摘一個(gè)page下來(lái)就好了。比如前面說(shuō)到的內(nèi)核捕捉缺頁(yè)異常，然后需要分配一個(gè)page以建立映射。

說(shuō)到這里，會(huì)有一個(gè)疑問(wèn)，內(nèi)核在分配page、建立地址映射的過(guò)程中，使用的是虛擬地址還是物理地址呢？首先，內(nèi)核代碼所訪問(wèn)的地址都是虛擬地址，因?yàn)镃PU指令接收的就是虛擬地址（地址映射對(duì)于CPU指令是透明的）。但是，建立地址映射時(shí)，內(nèi)核在頁(yè)表里面填寫(xiě)的內(nèi)容卻是物理地址，因?yàn)榈刂酚成涞哪繕?biāo)就是要得到物理地址。

那么，內(nèi)核怎么得到這個(gè)物理地址呢？其實(shí)，上面也提到了，mem_map中的page就是根據(jù)物理內(nèi)存來(lái)建立的，每一個(gè)page就對(duì)應(yīng)了一個(gè)物理頁(yè)。

于是我們可以說(shuō)，虛擬地址的映射是靠這里page結(jié)構(gòu)來(lái)完成的，是它們給出了最終的物理地址。然而，page結(jié)構(gòu)顯然是通過(guò)虛擬地址來(lái)管理的（前面已經(jīng)說(shuō)過(guò)，CPU指令接收的就是虛擬地址）。那么，page結(jié)構(gòu)實(shí)現(xiàn)了別人的虛擬地址映射，誰(shuí)又來(lái)實(shí)現(xiàn)page結(jié)構(gòu)自己的虛擬地址映射呢？沒(méi)人能夠?qū)崿F(xiàn)。

這就引出了前面提到的一個(gè)問(wèn)題，內(nèi)核空間的頁(yè)表項(xiàng)是寫(xiě)死的。在內(nèi)核初始化時(shí)，內(nèi)核的地址空間就已經(jīng)把地址映射寫(xiě)死了。page結(jié)構(gòu)顯然存在于內(nèi)核空間，所以它的地址映射問(wèn)題已經(jīng)通過(guò)“寫(xiě)死”解決了。

由于內(nèi)核空間的頁(yè)表項(xiàng)是寫(xiě)死的，又引出另一個(gè)問(wèn)題，NORMAL（或DMA）區(qū)域的內(nèi)存可能被同時(shí)映射到內(nèi)核空間和用戶空間。被映射到內(nèi)核空間是顯然的，因?yàn)檫@個(gè)映射已經(jīng)寫(xiě)死了。而這些頁(yè)面也可能被映射到用戶空間的，在前面提到的缺頁(yè)異常的場(chǎng)景里面就有這樣的可能。映射到用戶空間的頁(yè)面應(yīng)該優(yōu)先從HIGH區(qū)域獲取，因?yàn)檫@些內(nèi)存被內(nèi)核訪問(wèn)起來(lái)很不方便，拿給用戶空間再合適不過(guò)了。但是HIGH區(qū)域可能會(huì)耗盡，或者可能因?yàn)樵O(shè)備上物理內(nèi)存不足導(dǎo)致系統(tǒng)里面根本就沒(méi)有HIGH區(qū)域，所以，將NORMAL區(qū)域映射給用戶空間是必然存在的。

但是NORMAL區(qū)域的內(nèi)存被同時(shí)映射到內(nèi)核空間和用戶空間并沒(méi)有問(wèn)題，因?yàn)槿绻硞€(gè)頁(yè)面正在被內(nèi)核使用，對(duì)應(yīng)的page應(yīng)該已經(jīng)從free_area被摘下，于是缺頁(yè)異常處理代碼中不會(huì)再將該頁(yè)映射到用戶空間。反過(guò)來(lái)也一樣，被映射到用戶空間的page自然已經(jīng)從free_area被摘下，內(nèi)核不會(huì)再去使用這個(gè)頁(yè)面。

內(nèi)核空間管理(圖：右下)

除了對(duì)內(nèi)存整頁(yè)的使用，有些時(shí)候，內(nèi)核也需要像用戶程序使用malloc一樣，分配一塊任意大小的空間。這個(gè)功能是由slab系統(tǒng)來(lái)實(shí)現(xiàn)的。

slab相當(dāng)于為內(nèi)核中常用的一些結(jié)構(gòu)體對(duì)象建立了對(duì)象池，比如對(duì)應(yīng)task結(jié)構(gòu)的池、對(duì)應(yīng)mm結(jié)構(gòu)的池、等等。 而slab也維護(hù)有通用的對(duì)象池，比如"32字節(jié)大小"的對(duì)象池、"64字節(jié)大小"的對(duì)象池、等等。內(nèi)核中常用的kmalloc函數(shù)（類似于用戶態(tài)的malloc）就是在這些通用的對(duì)象池中實(shí)現(xiàn)分配的。

slab除了對(duì)象實(shí)際使用的內(nèi)存空間外，還有其對(duì)應(yīng)的控制結(jié)構(gòu)。有兩種組織方式，如果對(duì)象較大，則控制結(jié)構(gòu)使用專門(mén)的頁(yè)面來(lái)保存；如果對(duì)象較小，控制結(jié)構(gòu)與對(duì)象空間使用相同的頁(yè)面。

除了slab，linux 2.6還引入了mempool（內(nèi)存池）。其意圖是：某些對(duì)象我們不希望它會(huì)因?yàn)閮?nèi)存不足而分配失敗，于是我們預(yù)先分配若干個(gè)，放在mempool中存起來(lái)。正常情況下，分配對(duì)象時(shí)是不會(huì)去動(dòng)mempool里面的資源的，照常通過(guò)slab去分配。到系統(tǒng)內(nèi)存緊缺，已經(jīng)無(wú)法通過(guò)slab分配內(nèi)存時(shí)，才會(huì)使用 mempool中的內(nèi)容。

頁(yè)面換入換出(圖：左上)(圖：右上)

頁(yè)面換入換出又是一個(gè)很復(fù)雜的系統(tǒng)。內(nèi)存頁(yè)面被換出到磁盤(pán)，與磁盤(pán)文件被映射到內(nèi)存，是很相似的兩個(gè)過(guò)程（內(nèi)存頁(yè)被換出到磁盤(pán)的動(dòng)機(jī)，就是今后還要從磁盤(pán)將其載回內(nèi)存）。所以swap復(fù)用了文件子系統(tǒng)的一些機(jī)制。

頁(yè)面換入換出是一件很費(fèi)CPU和IO的事情，但是由于內(nèi)存昂貴這一歷史原因，我們只好拿磁盤(pán)來(lái)擴(kuò)展內(nèi)存。但是現(xiàn)在內(nèi)存越來(lái)越便宜了，我們可以輕松安裝數(shù)G的內(nèi)存，然后將swap系統(tǒng)關(guān)閉。于是swap的實(shí)現(xiàn)實(shí)在讓人難有探索的欲望，在這里就不贅述了。

用戶空間內(nèi)存管理

malloc是libc的庫(kù)函數(shù)，用戶程序一般通過(guò)它（或類似函數(shù)）來(lái)分配內(nèi)存空間。

libc對(duì)內(nèi)存的分配有兩種途徑，一是調(diào)整堆的大小，二是mmap一個(gè)新的虛擬內(nèi)存區(qū)域（堆也是一個(gè)vma）。

在內(nèi)核中，堆是一個(gè)一端固定、一端可伸縮的vma（圖：左中）。可伸縮的一端通過(guò)系統(tǒng)調(diào)用brk來(lái)調(diào)整。libc管理著堆的空間，用戶調(diào)用malloc分配內(nèi)存時(shí)，libc盡量從現(xiàn)有的堆中去分配。如果堆空間不夠，則通過(guò)brk增大堆空間。

當(dāng)用戶將已分配的空間free時(shí)，libc可能會(huì)通過(guò)brk減小堆空間。但是堆空間增大容易減小卻難，考慮這樣一種情況，用戶空間連續(xù)分配了10塊內(nèi)存，前9塊已經(jīng)free。這時(shí)，未free的第10塊哪怕只有1字節(jié)大，libc也不能夠去減小堆的大小。因?yàn)槎阎挥幸欢丝缮炜s，并且中間不能掏空。而第10塊內(nèi)存就死死地占據(jù)著堆可伸縮的那一端，堆的大小沒(méi)法減小，相關(guān)資源也沒(méi)法歸還內(nèi)核。

當(dāng)用戶malloc一塊很大的內(nèi)存時(shí)，libc會(huì)通過(guò)mmap系統(tǒng)調(diào)用映射一個(gè)新的vma。因?yàn)閷?duì)于堆的大小調(diào)整和空間管理還是比較麻煩的，重新建一個(gè)vma會(huì)更方便（上面提到的free的問(wèn)題也是原因之一）。

那么為什么不總是在malloc的時(shí)候去mmap一個(gè)新的vma呢？第一，對(duì)于小空間的分配與回收，被libc管理的堆空間已經(jīng)能夠滿足需要，不必每次都去進(jìn)行系統(tǒng)調(diào)用。并且vma是以page為單位的，最小就是分配一個(gè)頁(yè)；第二，太多的vma會(huì)降低系統(tǒng)性能。缺頁(yè)異常、vma的新建與銷毀、堆空間的大小調(diào)整、等等情況下，都需要對(duì)vma進(jìn)行操作，需要在當(dāng)前進(jìn)程的所有vma中找到需要被操作的那個(gè)（或那些）vma。vma數(shù)目太多，必然導(dǎo)致性能下降。（在進(jìn)程的vma較少時(shí)，內(nèi)核采用鏈表來(lái)管理vma；vma較多時(shí)，改用紅黑樹(shù)來(lái)管理。）

用戶的棧

與堆一樣，棧也是一個(gè)vma（圖：左中），這個(gè)vma是一端固定、一端可伸（注意，不能縮）的。這個(gè)vma比較特殊，沒(méi)有類似brk的系統(tǒng)調(diào)用讓這個(gè)vma伸展，它是自動(dòng)伸展的。

當(dāng)用戶訪問(wèn)的虛擬地址越過(guò)這個(gè)vma時(shí)，內(nèi)核會(huì)在處理缺頁(yè)異常的時(shí)候?qū)⒆詣?dòng)將這個(gè)vma增大。內(nèi)核會(huì)檢查當(dāng)時(shí)的棧寄存器（如：ESP），訪問(wèn)的虛擬地址不能超過(guò)ESP加n（n為CPU壓棧指令一次性壓棧的最大字節(jié)數(shù)）。也就是說(shuō)，內(nèi)核是以ESP為基準(zhǔn)來(lái)檢查訪問(wèn)是否越界。

但是，ESP的值是可以由用戶態(tài)程序自由讀寫(xiě)的，用戶程序如果調(diào)整ESP，將棧劃得很大很大怎么辦呢？?jī)?nèi)核中有一套關(guān)于進(jìn)程限制的配置，其中就有棧大小的配置，棧只能這么大，再大就出錯(cuò)。

對(duì)于一個(gè)進(jìn)程來(lái)說(shuō)，棧一般是可以被伸展得比較大（如：8MB）。然而對(duì)于線程呢？

首先線程的棧是怎么回事？前面說(shuō)過(guò)，線程的mm是共享其父進(jìn)程的。雖然棧是mm中的一個(gè)vma，但是線程不能與其父進(jìn)程共用這個(gè)vma（兩個(gè)運(yùn)行實(shí)體顯然不用共用一個(gè)棧）。于是，在線程創(chuàng)建時(shí)，線程庫(kù)通過(guò)mmap新建了一個(gè)vma，以此作為線程的棧（大于一般為：2M）。

可見(jiàn)，線程的棧在某種意義上并不是真正棧，它是一個(gè)固定的區(qū)域，并且容量很有限。