頻繁地請(qǐng)求和釋放不同大小的內(nèi)存钧唐，必然導(dǎo)致內(nèi)存碎片問(wèn)題的產(chǎn)生征候，結(jié)果就是當(dāng)再次要求分配連續(xù)的內(nèi)存時(shí)，即使整體內(nèi)存是足夠的趟妥，也無(wú)法滿足連續(xù)內(nèi)存的需求猫态。該問(wèn)題也稱之為外碎片(external fragmentation)。
解決方案：
避免外碎片的方法有兩種:
1披摄、利用分頁(yè)單元把一組非連續(xù)的空閑頁(yè)框映射到連續(xù)的線性地址
2亲雪、開發(fā)一種適當(dāng)?shù)募夹g(shù)來(lái)記錄現(xiàn)存的空閑的連續(xù)頁(yè)框塊的情況，以盡量避免為滿足對(duì)小塊的請(qǐng)求而分割大的空閑快
第一種方案的意思是行疏，我們使用地址轉(zhuǎn)換技術(shù)匆光，把非連續(xù)的物理地址轉(zhuǎn)換成連續(xù)的線性地址套像。
第二種方案的意思是酿联，開發(fā)一種特有的分配技術(shù)來(lái)記錄下來(lái)空閑內(nèi)存的情況，從而解決內(nèi)存碎片問(wèn)題。
Linux采用了第二種方案贞让，因?yàn)樵谀承┣闆r下周崭，系統(tǒng)的確需要連續(xù)的物理地址（DMA處理器可以直接訪問(wèn)總線）。
Linux采用著名的伙伴系統(tǒng)(buddy system)算法來(lái)解決外碎片問(wèn)題喳张。把所有的空閑頁(yè)框分組為11個(gè)塊鏈表续镇，每個(gè)鏈表分別包含大小為1,2,4,8,16,32,64,128,256,512,1024個(gè)連續(xù)的頁(yè)框，對(duì)1024個(gè)頁(yè)框的最大請(qǐng)求對(duì)應(yīng)著4MB大小的連續(xù)RAM（每頁(yè)大小為4KB）销部，每個(gè)塊的第一個(gè)頁(yè)框的物理地址是該塊大小的整數(shù)倍摸航，例如，大小為16個(gè)頁(yè)框的塊舅桩，其起始地址是16*2^12的倍數(shù)酱虎。
我們通過(guò)一個(gè)例子來(lái)說(shuō)明伙伴算法的工作原理，假設(shè)現(xiàn)在要請(qǐng)求一個(gè)256個(gè)頁(yè)框的塊（1MB）擂涛，算法步驟如下：
? 在256個(gè)頁(yè)框的鏈表中檢查是否有一個(gè)空閑快读串，如果沒(méi)有，查找下一個(gè)更大的塊撒妈，如果有恢暖，請(qǐng)求滿足。
? 在512個(gè)頁(yè)框的鏈表中檢查是否有一個(gè)空閑塊狰右，如果有杰捂，把512個(gè)頁(yè)框的空閑塊分為兩份，第一份用于滿足請(qǐng)求棋蚌，第二份鏈接到256個(gè)頁(yè)框的鏈表中琼娘。如果沒(méi)有空閑塊，繼續(xù)尋找下一個(gè)更大的塊附鸽。
以上過(guò)程的逆過(guò)程脱拼，就是頁(yè)框塊的釋放過(guò)程，也是該算法名字的由來(lái)坷备，內(nèi)核試圖把大小為B的一對(duì)空閑伙伴塊合并為一個(gè)2B的單獨(dú)塊熄浓，滿足以下條件的兩個(gè)塊稱之為伙伴：
? 兩個(gè)塊具有相同的大小
? 他們的物理地址是連續(xù)的
第一塊的第一個(gè)頁(yè)框的物理地址是2 * B * 2^12
該算法是遞歸的，如果它成功合并了B省撑，就會(huì)試圖去合并2B赌蔑，以再次試圖形成更大的塊。
