內(nèi)存碎片問(wèn)題
頻繁地請(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)。
解決方案
避免外碎片的方法有兩種:
- 利用分頁(yè)單元把一組非連續(xù)的空閑頁(yè)框映射到連續(xù)的線性地址
- 開(kāi)發(fā)一種適當(dāng)?shù)募夹g(shù)來(lái)記錄現(xiàn)存的空閑的連續(xù)頁(yè)框塊的情況，以盡量避免為滿足對(duì)小塊的請(qǐng)求而分割大的空閑快
第一種方案的意思是，我們使用地址轉(zhuǎn)換技術(shù)，把非連續(xù)的物理地址轉(zhuǎn)換成連續(xù)的線性地址。
第二種方案的意思是，開(kāi)發(fā)一種特有的分配技術(shù)來(lái)記錄下來(lái)空閑內(nèi)存的情況，從而解決內(nèi)存碎片問(wèn)題。
Linux采用了第二種方案，因?yàn)樵谀承┣闆r下，系統(tǒng)的確需要連續(xù)的物理地址（DMA處理器可以直接訪問(wèn)總線）。
伙伴系統(tǒng)(buddy system)
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ò)程的逆過(guò)程，就是頁(yè)框塊的釋放過(guò)程，也是該算法名字的由來(lái)，內(nèi)核試圖把大小為B的一對(duì)空閑伙伴塊合并為一個(gè)2B的單獨(dú)塊，滿足以下條件的兩個(gè)塊稱之為伙伴：
- 兩個(gè)塊具有相同的大小
- 他們的物理地址是連續(xù)的
- 第一塊的第一個(gè)頁(yè)框的物理地址是2 * B * 2^12
該算法是遞歸的，如果它成功合并了B，就會(huì)試圖去合并2B，以再次試圖形成更大的塊。
