[[251667]]

Buddy分配算法

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

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

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

空閑內(nèi)存的信息我們可以通過以下命令獲取：

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

CMA

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

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

Slab

在Linux中，伙伴系統(tǒng)(buddy system)是以頁為單位管理和分配內(nèi)存。但是現(xiàn)實的需求卻以字節(jié)為單位，假如我們需要申請20Bytes，總不能分配一頁吧!那豈不是嚴重浪費內(nèi)存。那么該如何分配呢?slab分配器就應(yīng)運而生了，專為小內(nèi)存分配而生。slab分配器分配內(nèi)存以Byte為單位。但是slab分配器并沒有脫離伙伴系統(tǒng)，而是基于伙伴系統(tǒng)分配的大內(nèi)存進一步細分成小內(nèi)存分配。我們先來看一張圖

kmem_cache是一個cache_chain的鏈表，描述了一個高速緩存，每個高速緩存包含了一個slabs的列表，這通常是一段連續(xù)的內(nèi)存塊。存在3種slab：

• slabs_full(完全分配的slab)
• slabs_partial(部分分配的slab)
• slabs_empty(空slab,或者沒有對象被分配)。

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

為了進一步解釋，這里舉個例子來說明，用struct kmem_cache結(jié)構(gòu)描述的一段內(nèi)存就稱作一個slab緩存池。一個slab緩存池就像是一箱牛奶，一箱牛奶中有很多瓶牛奶，每瓶牛奶就是一個object。分配內(nèi)存的時候，就相當于從牛奶箱中拿一瓶?？傆心猛甑囊惶臁．斚渥涌盏臅r候，你就需要去超市再買一箱回來。超市就相當于partial鏈表，超市存儲著很多箱牛奶。如果超市也賣完了，自然就要從廠家進貨，然后出售給你。廠家就相當于伙伴系統(tǒng)。

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

總結(jié)

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