頻繁地請求和釋放不同大小的內存茎匠，必然導致內存碎片問題的產(chǎn)生格仲，結果就是當再次要求分配連續(xù)的內存時，即使整體內存是足夠的诵冒，也無法滿足連續(xù)內存的需求抓狭。該問題也稱之為外碎片(external fragmentation)。
解決方案：
避免外碎片的方法有兩種:
1造烁、利用分頁單元把一組非連續(xù)的空閑頁框映射到連續(xù)的線性地址
2否过、開發(fā)一種適當?shù)募夹g來記錄現(xiàn)存的空閑的連續(xù)頁框塊的情況午笛，以盡量避免為滿足對小塊的請求而分割大的空閑快
第一種方案的意思是，我們使用地址轉換技術苗桂，把非連續(xù)的物理地址轉換成連續(xù)的線性地址药磺。
第二種方案的意思是，開發(fā)一種特有的分配技術來記錄下來空閑內存的情況煤伟，從而解決內存碎片問題癌佩。
Linux采用了第二種方案，因為在某些情況下便锨，系統(tǒng)的確需要連續(xù)的物理地址（DMA處理器可以直接訪問總線）围辙。
Linux采用著名的伙伴系統(tǒng)(buddy system)算法來解決外碎片問題。把所有的空閑頁框分組為11個塊鏈表放案，每個鏈表分別包含大小為1,2,4,8,16,32,64,128,256,512,1024個連續(xù)的頁框姚建，對1024個頁框的最大請求對應著4MB大小的連續(xù)RAM（每頁大小為4KB），每個塊的第一個頁框的物理地址是該塊大小的整數(shù)倍吱殉，例如掸冤，大小為16個頁框的塊，其起始地址是16*2^12的倍數(shù)友雳。
我們通過一個例子來說明伙伴算法的工作原理稿湿，假設現(xiàn)在要請求一個256個頁框的塊（1MB），算法步驟如下：
? 在256個頁框的鏈表中檢查是否有一個空閑快押赊，如果沒有饺藤，查找下一個更大的塊，如果有流礁，請求滿足策精。
? 在512個頁框的鏈表中檢查是否有一個空閑塊，如果有崇棠，把512個頁框的空閑塊分為兩份咽袜，第一份用于滿足請求，第二份鏈接到256個頁框的鏈表中枕稀。如果沒有空閑塊询刹，繼續(xù)尋找下一個更大的塊。
以上過程的逆過程萎坷，就是頁框塊的釋放過程凹联，也是該算法名字的由來，內核試圖把大小為B的一對空閑伙伴塊合并為一個2B的單獨塊哆档，滿足以下條件的兩個塊稱之為伙伴：
? 兩個塊具有相同的大小
? 他們的物理地址是連續(xù)的
第一塊的第一個頁框的物理地址是2 * B * 2^12
該算法是遞歸的蔽挠，如果它成功合并了B，就會試圖去合并2B，以再次試圖形成更大的塊澳淑。
