Linux內(nèi)存管理-內(nèi)存碎片的終極解決方案

內(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,以再次試圖形成更大的塊隐砸。
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末之碗,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子季希,更是在濱河造成了極大的恐慌褪那,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件式塌,死亡現(xiàn)場離奇詭異武通,居然都是意外死亡,警方通過查閱死者的電腦和手機珊搀,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進店門楼誓,熙熙樓的掌柜王于貴愁眉苦臉地迎上來肛搬,“玉大人吟税,你說我怎么就攤上這事偎球。” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長。 經(jīng)常有香客問我默赂,道長,這世上最難降的妖魔是什么括勺? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任缆八,我火速辦了婚禮,結(jié)果婚禮上疾捍,老公的妹妹穿的比我還像新娘奈辰。我一直安慰自己,他們只是感情好乱豆,可當我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布奖恰。 她就那樣靜靜地躺著,像睡著了一般宛裕。 火紅的嫁衣襯著肌膚如雪瑟啃。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天揩尸,我揣著相機與錄音蛹屿,去河邊找鬼。 笑死岩榆,一個胖子當著我的面吹牛蜡峰,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播朗恳,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼载绿!你這毒婦竟也來了粥诫?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤崭庸,失蹤者是張志新(化名)和其女友劉穎怀浆,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體怕享,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡执赡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了函筋。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片沙合。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖跌帐,靈堂內(nèi)的尸體忽然破棺而出首懈,到底是詐尸還是另有隱情绊率,我是刑警寧澤,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布究履,位于F島的核電站滤否,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏最仑。R本人自食惡果不足惜藐俺,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望泥彤。 院中可真熱鬧欲芹,春花似錦、人聲如沸全景。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽爸黄。三九已至滞伟,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間炕贵,已是汗流浹背梆奈。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留称开,地道東北人亩钟。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像鳖轰,于是被迫代替她去往敵國和親清酥。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 1 內(nèi)存尋址 1.1 物理地址蕴侣、虛擬地址以及線性地址 物理地址: 物理內(nèi)存的內(nèi)存單元地址 虛擬地址: 程序員看到的...
    瘋狂小王子閱讀 2,820評論 3 21
  • 第八章 內(nèi)存管理 本章通過三部分內(nèi)容描述內(nèi)核給自己動態(tài)分配內(nèi)存: ...
    rlkbk閱讀 441評論 0 1
  • Linux 內(nèi)存管理 1 頁的概念 linux 內(nèi)核中把物理頁作為內(nèi)存分配的最小單位焰轻,32位CPU 頁的大小通常為...
    赤兔歡閱讀 3,282評論 0 5
  • 概述 我們都知道一個進程是與其他進程共享CPU和內(nèi)存資源的。正因如此昆雀,操作系統(tǒng)需要有一套完善的內(nèi)存管理機制才能防止...
    SylvanasSun閱讀 3,858評論 0 25
  • 短信最大的壞處辱志,就是讓你說的話落在文字上,而且別人不會認為你當時欠考慮狞膘,覺得這是你的真實表達揩懒,這就有了公關(guān)的價值。...
    嗨丨小丑閱讀 410評論 0 5