有了前兩節的學習相信讀者已經知道CPU所有的操作都是建立在虛擬地址上處理(這裡的虛擬地址分為內核態虛擬地址和用戶態虛擬地址)，CPU看到的內存管理都是對page的管理，接下來我們看一下用來管理page的經典算法--Buddy。

Buddy分配算法

假設這是一段連續的頁框，陰影部分表示已經被使用的頁框，現在需要申請一個連續的5個頁框。這個時候，在這段內存上不能找到連續的5個空閒的頁框，就會去另一段內存上去尋找5個連續的頁框，這樣子，久而久之就形成了頁框的浪費。為了避免出現這種情況，Linux內核中引入了夥伴系統算法(Buddy system)。把所有的空閒頁框分組為11個塊鍊表，每個塊鍊表分別包含大小為1，2，4，8，16，32，64，128，256，512和1024個連續頁框的頁框塊。最大可以申請1024個連續頁框，對應4MB大小的連續內存。每個頁框塊的第一個頁框的物理地址是該塊大小的整數倍，如圖：

假設要申請一個256個頁框的塊，先從256個頁框的鍊表中查找空閒塊，如果沒有，就去512個頁框的鍊表中找，找到了則將頁框塊分為2個256個頁框的塊，一個分配給應用，另外一個移到256個頁框的鍊表中。如果512個頁框的鍊表中仍沒有空閒塊，繼續向1024個頁框的鍊表查找，如果仍然沒有，則返回錯誤。頁框塊在釋放時，會主動將兩個連續的頁框塊合併為一個較大的頁框塊。

從上面可以知道Buddy算法一直在對頁框做拆開合併拆開合併的動作。Buddy算法牛逼就牛逼在運用了世界上任何正整數都可以由2^n的和組成。這也是Buddy算法管理空閒頁表的本質。

空閒內存的信息我們可以通過以下命令獲取：

也可以通過echo m > /proc/sysrq-trigger來觀察buddy狀態，與/proc/buddyinfo的信息是一致的：

CMA

細心的讀者或許會發現當Buddy算法對內存拆拆合合的過程中會造成碎片化的現象，以至於內存後來沒有了大塊的連續內存，全是小塊內存。當然這對應用程式是不影響的(前面我們講過用頁表可以把不連續的物理地址在虛擬地址上連續起來)，但是內核態就沒有辦法獲取大塊連續的內存（比如DMA, Camera, GPU都需要大塊物理地址連續的內存）。

在嵌入式設備中一般用CMA來解決上述的問題。CMA的全稱是contiguous memory allocator， 其工作原理是：預留一段的內存給驅動使用，但當驅動不用的時候，CMA區域可以分配給用戶進程用作匿名內存或者頁緩存。而當驅動需要使用時，就將進程占用的內存通過回收或者遷移的方式將之前占用的預留內存騰出來，供驅動使用。

Slab

在Linux中，夥伴系統（buddy system）是以頁為單位管理和分配內存。但是現實的需求卻以字節為單位，假如我們需要申請20Bytes，總不能分配一頁吧！那豈不是嚴重浪費內存。那麼該如何分配呢？slab分配器就應運而生了，專為小內存分配而生。slab分配器分配內存以Byte為單位。但是slab分配器並沒有脫離夥伴系統，而是基於夥伴系統分配的大內存進一步細分成小內存分配。我們先來看一張圖：

kmem_cache是一個cache_chain的鍊表，描述了一個高速緩存，每個高速緩存包含了一個slabs的列表，這通常是一段連續的內存塊。存在3種slab：

• slabs_full(完全分配的slab)

• slabs_partial(部分分配的slab)

• slabs_empty(空slab,或者沒有對象被分配)。

slab是slab分配器的最小單位，在實現上一個slab有一個貨多個連續的物理頁組成（通常只有一頁）。單個slab可以在slab鍊表之間移動，例如如果一個半滿slab被分配了對象後變滿了，就要從slabs_partial中被刪除，同時插入到slabs_full中去。

為了進一步解釋，這裡舉個例子來說明，用struct kmem_cache結構描述的一段內存就稱作一個slab緩存池。一個slab緩存池就像是一箱牛奶，一箱牛奶中有很多瓶牛奶，每瓶牛奶就是一個object。分配內存的時候，就相當於從牛奶箱中拿一瓶。總有拿完的一天。當箱子空的時候，你就需要去超市再買一箱回來。超市就相當於partial鍊表，超市存儲著很多箱牛奶。如果超市也賣完了，自然就要從廠家進貨，然後出售給你。廠家就相當於夥伴系統。

可以通過下面命令查看slab緩存的信息：

總結

從內存DDR分為不同的ZONE，到CPU訪問的Page通過頁表來映射ZONE，再到通過Buddy算法和Slab算法對這些Page進行管理，我們應該可以從感官的角度理解了下圖：