[[251667]]

Buddy分配算法

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

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

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

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

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

CMA

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

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

Slab

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

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

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

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

為了進(jìn)一步解釋，這里舉個(gè)例子來說明，用struct kmem_cache結(jié)構(gòu)描述的一段內(nèi)存就稱作一個(gè)slab緩存池。一個(gè)slab緩存池就像是一箱牛奶，一箱牛奶中有很多瓶牛奶，每瓶牛奶就是一個(gè)object。分配內(nèi)存的時(shí)候，就相當(dāng)于從牛奶箱中拿一瓶。總有拿完的一天。當(dāng)箱子空的時(shí)候，你就需要去超市再買一箱回來。超市就相當(dāng)于partial鏈表，超市存儲(chǔ)著很多箱牛奶。如果超市也賣完了，自然就要從廠家進(jìn)貨，然后出售給你。廠家就相當(dāng)于伙伴系統(tǒng)。

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

總結(jié)

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