內(nèi)存碎片問題
頻繁地請求和釋放不同大小的內(nèi)存咨堤，必然導致內(nèi)存碎片問題的產(chǎn)生仔蝌，結(jié)果就是當再次要求分配連續(xù)的內(nèi)存時，即使整體內(nèi)存是足夠的思恐，也無法滿足連續(xù)內(nèi)存的需求沾谜。該問題也稱之為外碎片(external fragmentation)。
解決方案
避免外碎片的方法有兩種:
- 利用分頁單元把一組非連續(xù)的空閑頁框映射到連續(xù)的線性地址
- 開發(fā)一種適當?shù)募夹g(shù)來記錄現(xiàn)存的空閑的連續(xù)頁框塊的情況胀莹，以盡量避免為滿足對小塊的請求而分割大的空閑快
第一種方案的意思是基跑，我們使用地址轉(zhuǎn)換技術(shù)，把非連續(xù)的物理地址轉(zhuǎn)換成連續(xù)的線性地址描焰。
第二種方案的意思是媳否，開發(fā)一種特有的分配技術(shù)來記錄下來空閑內(nèi)存的情況，從而解決內(nèi)存碎片問題荆秦。
Linux采用了第二種方案篱竭，因為在某些情況下，系統(tǒng)的確需要連續(xù)的物理地址（DMA處理器可以直接訪問總線）步绸。
伙伴系統(tǒng)(buddy system)
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ù)尋找下一個更大的塊仆潮。
下圖比較形象地描述了該過程宏蛉。
以上過程的逆過程，就是頁框塊的釋放過程性置，也是該算法名字的由來拾并，內(nèi)核試圖把大小為B的一對空閑伙伴塊合并為一個2B的單獨塊，滿足以下條件的兩個塊稱之為伙伴：
- 兩個塊具有相同的大小
- 他們的物理地址是連續(xù)的
- 第一塊的第一個頁框的物理地址是2 * B * 2^12
該算法是遞歸的鹏浅，如果它成功合并了B嗅义，就會試圖去合并2B，以再次試圖形成更大的塊隐砸。
