什么是伙伴堆算法

伙伴堆算法(也叫伙伴系統(tǒng)蝙昙，buddy system)是Linux系統(tǒng)中的一種動(dòng)態(tài)的內(nèi)存管理算法

伙伴堆算法的用途

每當(dāng)分配和釋放內(nèi)存的時(shí)候系統(tǒng)都將遇到尾部碎片的問題疏之，比如當(dāng)請(qǐng)求一個(gè)頁面的時(shí)候冀膝，即使系統(tǒng)可用頁面總數(shù)足夠多裂逐，但是無法分配大塊連續(xù)的頁面输涕。也就是說可用頁面會(huì)被一個(gè)或多個(gè)不連續(xù)的不可用頁面拆開展东。使用伙伴算法就可以一定程度解決這種頁面碎片的問題蜒滩。

算法基本思想

Linux把所有的空閑頁框分組為11個(gè)塊鏈表寄雀，每個(gè)鏈表上的頁框塊是固定的得滤。在第i條鏈表中每個(gè)頁框塊都包含2的i次方個(gè)連續(xù)頁，其中i稱為分配階盒犹。
下面以一個(gè)例子懂更，講述伙伴算法的思想：假設(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è)頁框的鏈表查找呜呐。如果1024塊存在，則將其中的256頁框作為請(qǐng)求返回悍募，剩余的768分成256塊和512塊分別插到相應(yīng)的鏈表中蘑辑。如果仍然沒有，則返回錯(cuò)誤坠宴。

算法涉及的數(shù)據(jù)結(jié)構(gòu)

Linux中伙伴堆算法的核心數(shù)據(jù)結(jié)構(gòu)包含以下兩個(gè)部分

1.free_area

//在mmzone.h中
#define MAX_ORDER 11
   struct zone
{
  ... ...
  struct free_area free_area[MAX_ORDER]洋魂；
  ... ...
};

每個(gè)物理內(nèi)存節(jié)點(diǎn)上都可以劃分為不同的zone，劃分zone的原因是因?yàn)閄86的一些架構(gòu)的影響(這一部分不是本文關(guān)鍵)喜鼓，因此可以理解為zone就是一塊內(nèi)存的管理符副砍，其中有一個(gè)很重要的數(shù)據(jù)就是free_area，并且它是一個(gè)結(jié)構(gòu)體數(shù)組庄岖，具體定義如下豁翎。

//在mmzone.h中
struct free_area
{
  struct list_head free_list[MIGRATR_TYPES];//說明了頁的屬性
  unsigned long nr_free;//來說明每個(gè)界中有多少可用的頁
};

在這個(gè)結(jié)構(gòu)體中有兩個(gè)域，第一個(gè)是free_list隅忿，是個(gè)鏈表心剥，它表示的就是當(dāng)前分配階所對(duì)應(yīng)的頁框塊的鏈表邦尊。第二個(gè)nr_free指的是當(dāng)前鏈表中空閑頁框塊的數(shù)目，比如free_area[2]中nr_free的值為5优烧，表示有5個(gè)大小為4的頁框塊蝉揍，那么總的空閑頁為20.其具體結(jié)構(gòu)可見下面兩幅圖

zone+free_area.gif

這張圖很好的說明了zone的結(jié)構(gòu)體中包含以分free_area字段并且free_area是一個(gè)數(shù)組后面用鏈表的形式附加了各種大小的頁面對(duì)于zone中另一個(gè)比較重要的結(jié)構(gòu)mem_map結(jié)構(gòu)在稍后進(jìn)行說明。free_area的具體實(shí)現(xiàn)見下圖畦娄。

free_area2.png

2. zone_mem_map數(shù)組

zone_mem_map是用于查找連續(xù)伙伴空間用的伙伴位圖捍掺。用一位描述伙伴塊的狀態(tài)位碼，稱之為伙伴位碼再膳。比如，bit0為第0塊和第1塊的伙伴位碼曲横，如果bit0為1喂柒，表示這兩塊至少有一塊已經(jīng)分配出去，如果bit0為0禾嫉，說明兩塊都空閑灾杰，還沒分配。整個(gè)內(nèi)存釋放或者分配過程中熙参，位圖扮演了重要的角色艳吠。

內(nèi)存分配與釋放得原理

分配原理：假如系統(tǒng)需要4(2 * 2)個(gè)頁面大小的內(nèi)存塊，該算法就到free_area[2]中查找孽椰，如果鏈表中有空閑塊昭娩，就直接從中摘下并分配出去。如果沒有黍匾，算法將順著數(shù)組向上查找free_area[3],如果free_area[3]中有空閑塊栏渺，則將其從鏈表中摘下，分成等大小的兩部分锐涯，前四個(gè)頁面作為一個(gè)塊插入free_area[2]磕诊，后4個(gè)頁面分配出去，free_area[3]中也沒有纹腌，就再向上查找霎终，如果free_area[4]中有，就將這16(2 * 2 * 2 * 2)個(gè)頁面等分成兩份升薯，前一半掛如free_area[3]的鏈表頭部莱褒，后一半的8個(gè)頁等分成兩等分，前一半掛free_area[2]的鏈表中覆劈，后一半分配出去保礼。假如free_area[4]也沒有沛励，則重復(fù)上面的過程，知道到達(dá)free_area數(shù)組的最后炮障，如果還沒有則放棄分配目派。

釋放原理：內(nèi)存的釋放是分配的逆過程，也可以看作是伙伴的合并過程胁赢。當(dāng)釋放一個(gè)塊時(shí)企蹭，先在其對(duì)應(yīng)的鏈表中考查是否有伙伴存在，如果沒有伙伴塊智末，就直接把要釋放的塊掛入鏈表頭谅摄；如果有，則從鏈表中摘下伙伴系馆，合并成一個(gè)大塊送漠，然后繼續(xù)考察合并后的塊在更大一級(jí)鏈表中是否有伙伴存在，直到不能合并或者已經(jīng)合并到了最大的塊(2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2個(gè)頁面)由蘑。整個(gè)過程中闽寡，位圖扮演了重要的角色，位圖的某一位對(duì)應(yīng)兩個(gè)互為伙伴的塊尼酿，為1表示其中一塊已經(jīng)分配出去了爷狈，為0表示兩塊都空閑∩亚妫伙伴中無論是分配還是釋放都只是相對(duì)的位圖進(jìn)行異或操作涎永。分配內(nèi)存時(shí)對(duì)位圖的是為釋放過程服務(wù)，釋放過程根據(jù)位圖判斷伙伴是否存在鹿响，如果對(duì)相應(yīng)位的異或操作得1羡微，則沒有伙伴可以合并，如果異或操作得0抢野，就進(jìn)行合并拷淘，并且繼續(xù)按這種方式合并伙伴，直到不能合并為止指孤。

內(nèi)存分配與釋放的例子

下面通過一個(gè)例子启涯，來深入地理解一下伙伴算法的真正內(nèi)涵（下面這個(gè)例子并不嚴(yán)格表示Linux 內(nèi)核中的實(shí)現(xiàn)，是闡述伙伴算法的實(shí)現(xiàn)思想）：
假設(shè)系統(tǒng)中有 1MB 大小的內(nèi)存需要?jiǎng)討B(tài)管理恃轩，按照伙伴算法的要求：需要將這1M大小的內(nèi)存進(jìn)行劃分结洼。這里，我們將這1M的內(nèi)存分為 64K叉跛、64K松忍、128K、256K筷厘、和512K 共五個(gè)部分鸣峭，如下圖 a 所示

伙伴堆.jpg

1.此時(shí)宏所，如果有一個(gè)程序A想要申請(qǐng)一塊45K大小的內(nèi)存，則系統(tǒng)會(huì)將第一塊64K的內(nèi)存塊分配給該程序（產(chǎn)生內(nèi)部碎片為代價(jià)）摊溶，如圖b所示爬骤；

2.然后程序B向系統(tǒng)申請(qǐng)一塊68K大小的內(nèi)存，系統(tǒng)會(huì)將128K內(nèi)存分配給該程序莫换，如圖c所示霞玄；

3.接下來，程序C要申請(qǐng)一塊大小為35K的內(nèi)存拉岁。系統(tǒng)將空閑的64K內(nèi)存分配給該程序坷剧，如圖d所示；

4.之后程序D需要一塊大小為90K的內(nèi)存喊暖。當(dāng)程序提出申請(qǐng)時(shí)惫企，系統(tǒng)本該分配給程序D一塊128K大小的內(nèi)存，但此時(shí)內(nèi)存中已經(jīng)沒有空閑的128K內(nèi)存塊了陵叽，于是根據(jù)伙伴算法的原理雅任，系統(tǒng)會(huì)將256K大小的內(nèi)存塊平分，將其中一塊分配給程序D咨跌，另一塊作為空閑內(nèi)存塊保留，等待以后使用硼婿，如圖e所示锌半；

5.緊接著，程序C釋放了它申請(qǐng)的64K內(nèi)存寇漫。在內(nèi)存釋放的同時(shí)刊殉，系統(tǒng)還負(fù)責(zé)檢查與之相鄰并且同樣大小的內(nèi)存是否也空閑，由于此時(shí)程序A并沒有釋放它的內(nèi)存州胳，所以系統(tǒng)只會(huì)將程序C的64K內(nèi)存回收记焊，如圖f所示；

6.然后程序A也釋放掉由它申請(qǐng)的64K內(nèi)存栓撞，系統(tǒng)隨機(jī)發(fā)現(xiàn)與之相鄰且大小相同的一段內(nèi)存塊恰好也處于空閑狀態(tài)遍膜。于是，將兩者合并成128K內(nèi)存瓤湘，如圖g所示瓢颅；

7.之后程序B釋放掉它的128k，系統(tǒng)也將這塊內(nèi)存與相鄰的128K內(nèi)存合并成256K的空閑內(nèi)存弛说，如圖h所示挽懦；

8.最后程序D也釋放掉它的內(nèi)存，經(jīng)過三次合并后木人，系統(tǒng)得到了一塊1024K的完整內(nèi)存信柿，如圖i所示冀偶。

buddy算法的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

1.解決內(nèi)存碎片問題

2.避免把內(nèi)存拆得太碎得同時(shí)，使內(nèi)存的分配和釋放過程迅速

缺點(diǎn)

1.雖然解決了內(nèi)存碎片問題渔嚷，但是該算法中进鸠，一個(gè)很小的塊往往會(huì)阻礙一個(gè)大塊的合并。（一片內(nèi)存中僅一個(gè)小的內(nèi)存塊沒有釋放圃伶，旁邊兩個(gè)大的就不能合并堤如。）

2.算法中有一定的浪費(fèi)現(xiàn)象，伙伴算法是按2的冪次方大小進(jìn)行分配內(nèi)存塊窒朋。

3.另外拆分和合并涉及到 較多的鏈表和位圖操作搀罢，開銷還是比較大的。

reference

[1].https://www.cnblogs.com/alantu2018/p/8527821.html
[2].https://www.cnblogs.com/cherishui/p/4246133.html
[3].https://blog.csdn.net/yq272393925/article/details/89286963
[4].https://www.cnblogs.com/huhuuu/p/3598760.html
[5].https://blog.csdn.net/qq_22238021/article/details/80208630

總結(jié)
文章寫的并不全侥猩，包括位圖具體得算法榔至，linux內(nèi)存池中的具體實(shí)現(xiàn)也都暫時(shí)沒看完，以及優(yōu)缺點(diǎn)總結(jié)并不全面欺劳。水平有限唧取，暫時(shí)也就先這樣吧。等我啥時(shí)候明白了我再更好了划提。Linux這種東西還是要多看幾遍得