內(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,以再次試圖形成更大的塊隐砸。