Linux的物理地址一直深受碎片化的困擾椒丧。
1壹甥、什么是碎片化？
用戶頻繁地請求和釋放不同大小的一組連續(xù)頁框壶熏，必然導(dǎo)致在已分配頁框的塊內(nèi)分散了許多小塊的空閑頁面句柠。
這些小塊的空間分散開來，無法分配一個(gè)大塊的連續(xù)頁框棒假，這就是物理地址的碎片化溯职。
由此帶來的問題是，即使有足夠的空閑頁框可以滿足請求帽哑，但要分配一個(gè)大塊的連續(xù)頁框可能無法滿足請求谜酒。
2、伙伴算法的相關(guān)概念
伙伴算法（Buddy system）把所有的空閑頁框分為11個(gè)塊鏈表祝拯，每塊鏈表中分布包含特定的連續(xù)頁框地址空間甚带，第0個(gè)塊鏈表包含大小為2 ^ 0個(gè)連續(xù)的頁框她肯，第1個(gè)塊鏈表中，每個(gè)鏈表元素包含2 ^ 1個(gè)頁框大小的連續(xù)地址空間鹰贵，….晴氨，第10個(gè)塊鏈表中，每個(gè)鏈表元素包含2 ^ 10個(gè)頁框大小的連續(xù)地址空間碉输。每個(gè)鏈表中元素的個(gè)數(shù)在系統(tǒng)初始化時(shí)決定籽前，在執(zhí)行過程中，動(dòng)態(tài)變化敷钾。
伙伴算法每次只能分配2的冪次頁的空間枝哄，比如一次分配1頁，2頁阻荒，4頁挠锥，8頁，…侨赡，1024頁(2^10)等等蓖租，每頁(pageSize)大小一般為4K，因此羊壹，伙伴算法最多一次能夠分配4M的內(nèi)存空間蓖宦。
兩個(gè)內(nèi)存塊，大小相同油猫，地址連續(xù)稠茂，同屬于一個(gè)大塊區(qū)域。（第0塊和第1塊是伙伴情妖，第2塊和第3塊是伙伴睬关，但第1塊和第2塊不是伙伴）
伙伴位圖：用一位描述伙伴塊的狀態(tài)位碼，稱之為伙伴位碼毡证。比如共螺，bit0為第0塊和第1塊的伙伴位碼，如果bit0為1情竹，表示這兩塊至少有一塊已經(jīng)分配出去藐不，如果bit0為0，說明兩塊都空閑秦效，還沒分配雏蛮。
Linux為每個(gè)管理區(qū)使用不同的伙伴系統(tǒng)，內(nèi)核空間分為三種區(qū)阱州，DMA挑秉，NORMAL，HIGHMEM苔货，對(duì)于每一種區(qū)犀概，都有對(duì)應(yīng)的伙伴算法立哑。
3、申請和回收內(nèi)存的過程
比如姻灶，我要分配4(2^2)頁（16k）的內(nèi)存空間铛绰，算法會(huì)先從free_area[2]中查看nr_free是否為空，如果有空閑塊产喉，則從中分配捂掰，如果沒有空閑塊，就從它的上一級(jí)free_area[3]（每塊32K）中分配出16K曾沈，并將多余的內(nèi)存（16K）加入到free_area[2]中去这嚣。如果free_area[3]也沒有空閑，則從更上一級(jí)申請空間塞俱，依次遞推姐帚，直到free_area[max_order]，如果頂級(jí)都沒有空間障涯，那么就報(bào)告分配失敗卧土。
釋放是申請的逆過程，當(dāng)釋放一個(gè)內(nèi)存塊時(shí)像樊，先在其對(duì)于的free_area鏈表中查找是否有伙伴存在，如果沒有伙伴塊旅敷，直接將釋放的塊插入鏈表頭生棍。如果有或板塊的存在，則將其從鏈表摘下媳谁，合并成一個(gè)大塊涂滴，然后繼續(xù)查找合并后的塊在更大一級(jí)鏈表中是否有伙伴的存在，直至不能合并或者已經(jīng)合并至最大塊2^10為止晴音。
4柔纵、伙伴算法的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
較好的解決外部碎片問題
當(dāng)需要分配若干個(gè)內(nèi)存頁面時(shí)，用于DMA的內(nèi)存頁面必須連續(xù)锤躁，伙伴算法很好的滿足了這個(gè)要求
只要請求的塊不超過512個(gè)頁面(2K)搁料，內(nèi)核就盡量分配連續(xù)的頁面。
針對(duì)大內(nèi)存分配設(shè)計(jì)系羞。
缺點(diǎn)：
合并的要求太過嚴(yán)格郭计，只能是滿足伙伴關(guān)系的塊才能合并，比如第1塊和第2塊就不能合并椒振。
碎片問題：一個(gè)連續(xù)的內(nèi)存中僅僅一個(gè)頁面被占用昭伸，導(dǎo)致整塊內(nèi)存區(qū)都不具備合并的條件
浪費(fèi)問題：伙伴算法只能分配2的冪次方內(nèi)存區(qū)，當(dāng)需要8K（2頁）時(shí)澎迎，好說庐杨，當(dāng)需要9K時(shí)选调，那就需要分配16K（4頁）的內(nèi)存空間，但是實(shí)際只用到9K空間灵份，多余的7K空間就被浪費(fèi)掉仁堪。
算法的效率問題： 伙伴算法涉及了比較多的計(jì)算還有鏈表和位圖的操作，開銷還是比較大的各吨，如果每次2 ^ n大小的伙伴塊就會(huì)合并到2 ^ (n+1)的鏈表隊(duì)列中枝笨，那么2 ^ n大小鏈表中的塊就會(huì)因?yàn)楹喜⒉僮鞫鴾p少，但系統(tǒng)隨后立即有可能又有對(duì)該大小塊的需求揭蜒，為此必須再從2 ^ (n+1)大小的鏈表中拆分横浑，這樣的合并又立即拆分的過程是無效率的。
Linux針對(duì)大內(nèi)存的物理地址分配屉更，采用伙伴算法徙融，如果是針對(duì)小于一個(gè)page的內(nèi)存，頻繁的分配和釋放瑰谜，有更加適宜的解決方案欺冀，如slab和kmem_cache等，這不在本文的討論范圍內(nèi)萨脑。
