淺談Linux內(nèi)存管理那些事兒
1 前言
內(nèi)存管理是Linux內(nèi)核中非常重要的部分,今天和大家一起學(xué)習(xí)一下。
當(dāng)我們要學(xué)習(xí)一個(gè)新知識(shí)點(diǎn)時(shí),比較好的過(guò)程是先理解出現(xiàn)這個(gè)技術(shù)點(diǎn)的 背景原因,同期其他解決方案,新技術(shù)點(diǎn)解決了什么問(wèn)題以及它存在哪些不足和改進(jìn)之處,這樣整個(gè)學(xué)習(xí)過(guò)程是 閉環(huán) 的,個(gè)人覺(jué)得這是個(gè)很好的學(xué)習(xí)思路。
凡事都是相通的,計(jì)算機(jī)學(xué)科的一些問(wèn)題在現(xiàn)實(shí)生活中都可以找到原型,所以我覺(jué)得計(jì)算機(jī)科學(xué)家大部分都是善于觀察生活并總結(jié)歸納的。人類(lèi)社會(huì)就是一臺(tái)復(fù)雜的機(jī)器,其中充滿(mǎn)了機(jī)制和規(guī)則,所以有時(shí)候跳進(jìn)代碼海洋不如先回到生活之中,尋找原型再探究代碼,可能理解會(huì)更深刻。
linux內(nèi)存管理卷帙浩繁,本文只能層層遞進(jìn)地帶你領(lǐng)略冰山輪廓,通過(guò)本文你將了解到以下內(nèi)容:
為什么需要管理內(nèi)存
linux段頁(yè)管理機(jī)制
內(nèi)存碎片的產(chǎn)生機(jī)理
-
伙伴系統(tǒng)的基本原理 -
伙伴系統(tǒng)的優(yōu)勢(shì)和不足 -
slab分配器的基本原理
2 為什么需要管理內(nèi)存
老子的著名觀點(diǎn)是無(wú)為而治,簡(jiǎn)單說(shuō)就是不過(guò)多干預(yù)而充分依靠自覺(jué)就可以有條不紊地運(yùn)作,理想是美好的,現(xiàn)實(shí)是殘酷的。
在linux系統(tǒng)中如果以一種原始簡(jiǎn)單的方式管理內(nèi)存是存在一些問(wèn)題的,我們來(lái)看幾個(gè)場(chǎng)景。
2.1 內(nèi)存管理的問(wèn)題
進(jìn)程空間隔離問(wèn)題
假如現(xiàn)在有ABC三個(gè)進(jìn)程運(yùn)行在linux的內(nèi)存空間,設(shè)定os給進(jìn)程A分配的地址空間是0-20M 進(jìn)程B地址空間30-80M,進(jìn)程C地址空間90-120M,如圖:
在某些時(shí)候程序空間的訪問(wèn)可能出現(xiàn)問(wèn)題,比如進(jìn)程A訪問(wèn)了屬于進(jìn)程B的空間,進(jìn)程B訪問(wèn)了屬于進(jìn)程C的空間,甚至修改了空間的值,這樣就會(huì)造成混亂和錯(cuò)誤,所以實(shí)際中是不允許這種情況發(fā)生的。
內(nèi)存效率和內(nèi)存不足問(wèn)題
機(jī)器的內(nèi)存是有限資源,而進(jìn)程數(shù)量是無(wú)法確定的,如果在某些時(shí)候已經(jīng)啟動(dòng)的進(jìn)程占據(jù)了所有內(nèi)存空間,此時(shí)就無(wú)法啟動(dòng)新進(jìn)程了,因?yàn)闆](méi)有新內(nèi)存可分配了,但是我們觀察到已經(jīng)啟動(dòng)的進(jìn)程有時(shí)候是在睡大覺(jué),也就是給了內(nèi)存也不用,這樣效率確實(shí)是有點(diǎn)低,所以我們需要一個(gè)管理員把不用的內(nèi)存倒騰出來(lái),另外連續(xù)內(nèi)存實(shí)在是很珍貴,很多時(shí)候我們沒(méi)法有效及時(shí)地分配連續(xù)內(nèi)存,因此虛擬化和離散化可能會(huì)有效提高內(nèi)存的使用率。
程序定位調(diào)試和編譯運(yùn)行問(wèn)題
由于程序運(yùn)行時(shí)的位置時(shí)不確定的,我們?cè)诙ㄎ粏?wèn)題、調(diào)試代碼、編譯執(zhí)行時(shí)都會(huì)存在很多問(wèn)題,我們希望每個(gè)進(jìn)程有一致且完整的地址空間,同樣的起始位置放置了堆、棧以及代碼段等,從而簡(jiǎn)化編譯和執(zhí)行過(guò)程中的 linker 鏈接器、loader 加載器的使用。
2.2 虛擬地址空間
為了解決上述的一些問(wèn)題,linux系統(tǒng)引入了虛擬空間的概念,虛擬化的出現(xiàn)和硬件有密不可分的聯(lián)系,可以說(shuō)是軟硬件組合的結(jié)果,虛擬地址空間就是在程序和物理空間所增加的中間層,這也是內(nèi)存管理的重點(diǎn)。
磁盤(pán) disk 作為一種大容量的存儲(chǔ)也作為"內(nèi)存"的一部分參與程序的運(yùn)行,內(nèi)存管理系統(tǒng)會(huì)將不常用非活躍內(nèi)存進(jìn)行頁(yè)面換出,可以認(rèn)為內(nèi)存是磁盤(pán)的緩存,內(nèi)存中保留了活躍的數(shù)據(jù),從而間接擴(kuò)展了有限的物理內(nèi)存空間,這部分空間稱(chēng)為虛擬內(nèi)存是相對(duì)于物理內(nèi)存而言的。
3.段頁(yè)管理機(jī)制
本文并不深入地將分段管理內(nèi)存和分頁(yè)管理內(nèi)存,因?yàn)閷⑦@些細(xì)節(jié)的優(yōu)秀文章很多,感興趣的使用搜索引擎一鍵即達(dá)。
段頁(yè)機(jī)制也不是一蹴而就的,經(jīng)歷了單純物理分段、單純分頁(yè)、單純邏輯分段等階段,最終演進(jìn)出來(lái)了分段和分頁(yè)結(jié)合的內(nèi)存管理方式,段頁(yè)結(jié)合獲得了分段和分頁(yè)的優(yōu)勢(shì)也避免了單一模式的弊端,是一種比較好的管理模式。
本文對(duì)于段頁(yè)管理機(jī)制只想通俗地說(shuō)明一些概念,段頁(yè)管理機(jī)制是分段式管理和分頁(yè)式管理的組合,段式管理是邏輯上的管理方式,分頁(yè)管理是偏物理上的管理方式。
計(jì)算機(jī)里面的一些技術(shù)和實(shí)現(xiàn)都可以在現(xiàn)實(shí)生活中找到縮影,所謂藝術(shù)和科技源自生活大概就是這個(gè)意思吧。
舉個(gè)栗子:
在進(jìn)行居民戶(hù)籍管理時(shí)都會(huì)有區(qū)縣市的概念,但是實(shí)際上并沒(méi)有這種實(shí)體,都是邏輯上的,增加了這些行政單位之后可以讓地址管理更加直接。
對(duì)于我們居民來(lái)說(shuō)唯一的實(shí)體就是自己的房子住所,這是物理上的單位,是真實(shí)存在的,這也是最基本的單位。
對(duì)比linux段頁(yè)時(shí)管理來(lái)說(shuō),段是邏輯上的單位相當(dāng)于區(qū)縣市的概念,頁(yè)是物理上的單位相當(dāng)于小區(qū)/房屋的概念,這樣就方便很多。
多級(jí)頁(yè)表也很好理解,總的物理內(nèi)存假如有4GB,頁(yè)大小為4KB,那么就總共有2^20個(gè)頁(yè),數(shù)量還是非常大的,這樣編號(hào)來(lái)建立索引尋址比較不方便,所以引入多級(jí)頁(yè)表,來(lái)減少存儲(chǔ)便于管理。
段頁(yè)機(jī)制加持下的邏輯地址和物理地址的映射關(guān)系簡(jiǎn)圖,也就是虛擬地址到物理地址的對(duì)應(yīng)關(guān)系:
圖片來(lái)自網(wǎng)絡(luò)
內(nèi)存管理單元( MMU Memory Management Unit )是硬件層組件,主要提供將虛擬地址映射為物理地址。
MMU 的工作流程:CPU 生成邏輯地址交給分段單元,分段單元進(jìn)行處理將邏輯地址轉(zhuǎn)換為線(xiàn)性地址,再線(xiàn)性地址交給分頁(yè)單元,分頁(yè)單元根據(jù)頁(yè)表映射轉(zhuǎn)換內(nèi)存物理地址,其中可能出現(xiàn)缺頁(yè)中斷。
缺頁(yè)中斷( Page Fault )是只當(dāng)軟件試圖訪問(wèn)一個(gè)虛擬地址時(shí),經(jīng)過(guò)段頁(yè)轉(zhuǎn)換為物理地址之后,此時(shí)發(fā)現(xiàn)該頁(yè)并沒(méi)有在內(nèi)存中,這時(shí) cpu 就會(huì)報(bào)出中斷,再進(jìn)行相關(guān)虛擬內(nèi)存的調(diào)入工作或者分配工作,如果出現(xiàn)異常也可能直接中斷。
4.物理內(nèi)存和內(nèi)存碎片
前面說(shuō)的段頁(yè)管理機(jī)制算是虛擬空間的部分,然而linux內(nèi)存管理的另外一個(gè)重要部分就是物理內(nèi)存的管理了,也就是如何分配和回收物理內(nèi)存,這就涉及到一些內(nèi)存分配算法和分配器。
4.1 物理內(nèi)存分配器
分配器和分配算法就像公司財(cái)務(wù),內(nèi)存就像公司資金,如何把資金合理使用是財(cái)務(wù)的本職工作,如何把物理內(nèi)存合理使用是分配器的分內(nèi)之事。
4.2 內(nèi)存碎片分類(lèi)和機(jī)理
如果我們不知道內(nèi)存碎片是什么,試想一下我們常說(shuō)的碎片化的時(shí)間,也就是那些雖然空閑但是沒(méi)有被利用的時(shí)間,其實(shí)內(nèi)存也是如此。
無(wú)論是時(shí)間還是內(nèi)存被碎片化之后都無(wú)法被有效利用,因此合理管理減少碎片對(duì)我們來(lái)說(shuō)是至關(guān)重要的,這也是物理內(nèi)存分配算法和分配器的研究重點(diǎn)。
按照碎片的位置和產(chǎn)生原因,內(nèi)存碎片分為外部碎片和內(nèi)部碎片,我們看下這兩種碎片的直觀展示:
圖片來(lái)自網(wǎng)絡(luò)
從圖中可以知道,外部碎片是進(jìn)程與進(jìn)程間未分配的內(nèi)存空間,外部碎片的出現(xiàn)和進(jìn)程頻繁的分配和釋放內(nèi)存有直接關(guān)系,這個(gè)很好理解,模擬一下分配不同空間的進(jìn)程不同時(shí)間釋放就可以看到外部碎片的產(chǎn)生了。
內(nèi)部碎片主要因?yàn)?/span>分配器粒度問(wèn)題以及一些地址限制導(dǎo)致實(shí)際分配的內(nèi)存大于所需內(nèi)存,這樣在進(jìn)程內(nèi)部就會(huì)出現(xiàn)內(nèi)存空洞。
雖然虛擬地址讓進(jìn)程使用的內(nèi)存在物理內(nèi)存上是離散的,但是很多時(shí)候進(jìn)程需要一定量連續(xù)物理內(nèi)存,如果大量碎片存在,就會(huì)造成無(wú)法啟動(dòng)進(jìn)程的問(wèn)題,如圖Process7需要一塊連續(xù)的物理內(nèi)存卻無(wú)法被分配:
圖片來(lái)自網(wǎng)絡(luò)
如果還是沒(méi)有很清楚,試想一下平時(shí)和三五好友去食堂吃飯或者坐公交的場(chǎng)景,整個(gè)車(chē)廂都沒(méi)有連續(xù)的3個(gè)座位,所以要么分開(kāi)坐要么都站著:
5. 伙伴系統(tǒng)算法基本原理
5.1 一些準(zhǔn)備知識(shí)
物理頁(yè)框
linux將物理內(nèi)存按照頁(yè)來(lái)劃分,內(nèi)存頁(yè)的大小在不同的軟硬件中可能不一樣,linux內(nèi)核設(shè)置為4KB,有的內(nèi)核可能更大也可能更小,當(dāng)時(shí)不同的大小在實(shí)際中都是有考量的,就像面包一樣有大有小,并不是整齊劃一的。
頁(yè)框記錄結(jié)構(gòu)
在內(nèi)核中為了建立對(duì)物理內(nèi)存頁(yè)page的使用情況的監(jiān)控,會(huì)有struct page這樣的數(shù)據(jù)結(jié)構(gòu)來(lái)記錄頁(yè)的位置地址/使用情況等,相當(dāng)于內(nèi)核對(duì)內(nèi)存頁(yè)管理的一本賬目。
延時(shí)分配和實(shí)時(shí)分配
linux系統(tǒng)有內(nèi)核態(tài)和用戶(hù)態(tài)之分,內(nèi)核態(tài)申請(qǐng)內(nèi)存就立刻滿(mǎn)足并且認(rèn)為這個(gè)請(qǐng)求一定是合理的。然而用戶(hù)態(tài)申請(qǐng)內(nèi)存的請(qǐng)求,總是盡量延后分配物理內(nèi)存,所以用戶(hù)態(tài)進(jìn)程是先獲得一個(gè)虛擬內(nèi)存區(qū),在運(yùn)行時(shí)通過(guò)缺頁(yè)異常獲得一塊真正的物理內(nèi)存,我們執(zhí)行 malloc 時(shí)獲取的只是虛擬內(nèi)存而已,并不是真實(shí)的物理內(nèi)存,也是這個(gè)原因造成的。
5.2 伙伴系統(tǒng)簡(jiǎn)介
第一次聽(tīng)到這個(gè)算法名稱(chēng)就很好奇為什么叫伙伴系統(tǒng)?讓我們來(lái)一起揭秘。
伙伴系統(tǒng)要解決什么問(wèn)題
伙伴系統(tǒng)算法是解決外部碎片的有力工具,簡(jiǎn)單來(lái)說(shuō)它針對(duì)頻繁請(qǐng)求和釋放不同大小的一組連續(xù)頁(yè)框的場(chǎng)景,建立一套管理機(jī)制來(lái)高效的分配和回收資源,降低外部碎片。
解決外部碎片的思路
第一種思路:把已經(jīng)存在的外部碎片通過(guò)新的技術(shù)把這些非連續(xù)的空閑內(nèi)存映射到連續(xù)的線(xiàn)性空間,其實(shí)相當(dāng)于沒(méi)有去降低外部碎片的產(chǎn)生而是治理型方案,但是這種方案在真實(shí)需要連續(xù)物理內(nèi)存時(shí)是無(wú)效的。
第二種思路:把這些小的空閑的不連續(xù)內(nèi)存記錄在案,如果有新的分配需求就從中搜索合適的將空閑內(nèi)存分配出去,這樣就避免了在新的區(qū)域進(jìn)行分配內(nèi)存,有種變廢為寶的感覺(jué),其實(shí)這樣場(chǎng)景也很熟悉當(dāng)你想吃一包餅干時(shí),你媽媽肯定會(huì)說(shuō)先把之前剩下一半沒(méi)吃完的吃掉,不要先開(kāi)新的了。
基于一些其他方面的考量,linux內(nèi)核選擇了第二種思路來(lái)解決外部碎片。
伙伴內(nèi)存塊的定義
在伙伴系統(tǒng)中把大小相同且物理地址連續(xù)的兩塊內(nèi)存區(qū)域稱(chēng)為伙伴,連續(xù)地址的要求其實(shí)是比較苛刻了,但是這也是算法的關(guān)鍵,因?yàn)檫@樣的兩塊內(nèi)存區(qū)域可以合并成一塊更大的區(qū)域。
伙伴系統(tǒng)的核心思想
伙伴系統(tǒng)將不同大小的連續(xù)物理頁(yè)框進(jìn)行管理,在申請(qǐng)時(shí)從最接近的頁(yè)框大小進(jìn)行分配,剩余的進(jìn)行新的拆解,并將有伙伴關(guān)系的內(nèi)存會(huì)進(jìn)行合并成為大的頁(yè)框。
5.3 伙伴系統(tǒng)的基本過(guò)程
伙伴系統(tǒng)維護(hù)了 n=0~10 共 11 個(gè)塊鏈表,每個(gè)塊鏈表分別包含了大小為 2^n 個(gè)連續(xù)的物理頁(yè)。當(dāng) n=10 時(shí)即 1024 個(gè) 4KB 頁(yè)對(duì)應(yīng) 4MB 大小的連續(xù)物理內(nèi)存塊,這里的 n稱(chēng)為 order,在伙伴系統(tǒng)中 order為0~10,也就是最小的是 4KB,最大的內(nèi)存塊是4MB,這些相同大小的物理塊組成雙向鏈表進(jìn)行管理,如圖展示了 order=0 和 order=2 的兩個(gè)雙向鏈表的情況:
圖片來(lái)自網(wǎng)絡(luò)
申請(qǐng)內(nèi)存過(guò)程:假設(shè)請(qǐng)求一個(gè)頁(yè)框塊,伙伴系統(tǒng)算法先在 order=0 的鏈表中檢查是否有空閑塊可分配。如果沒(méi)有則查找下一個(gè)更大的塊,在 order=1 的鏈表中找一個(gè)空閑塊,鏈表中存在就把2個(gè)頁(yè)框拆分,1個(gè)頁(yè)框分配出去1 個(gè)頁(yè)框加入到 order=0的鏈表中。如果 order=1 的鏈表中仍未找到空閑塊,就繼續(xù)向更大的order搜索,如果找到進(jìn)行拆分處理,如果最終至 order=10 的鏈表也沒(méi)有空閑塊,則算法報(bào)錯(cuò)。
合并內(nèi)存過(guò)程:合并內(nèi)存的過(guò)程是伙伴算法中伙伴塊的體現(xiàn),算法把兩個(gè)塊具有相同大小 A且它們物理地址連續(xù)的內(nèi)存合并為一個(gè)大小為 2A 的單獨(dú)塊。伙伴算法是自底向上迭代合并的,其實(shí)這個(gè)過(guò)程和 leveldb 中 sst 的合并過(guò)程很相似,區(qū)別在于伙伴算法要求內(nèi)存塊是連續(xù)的,這個(gè)過(guò)程也體現(xiàn)了伙伴系統(tǒng)對(duì)于大塊內(nèi)存的友好。
圖片來(lái)自網(wǎng)絡(luò)
5.4 伙伴系統(tǒng)的優(yōu)勢(shì)和不足
伙伴系統(tǒng)算法較好地解決了外部碎片問(wèn)題,并且對(duì)于大內(nèi)存塊的分配比較友好小粒度的內(nèi)存可能造成內(nèi)部碎片,但是伙伴系統(tǒng)對(duì)于伙伴塊的定義很苛刻,并且在合并伙伴塊的過(guò)程涉及較多的鏈表操作,對(duì)于一些頻繁的申請(qǐng)可能剛合并就會(huì)被拆分掉,這就做了無(wú)用功,所以伙伴系統(tǒng)還是存在一些問(wèn)題的。
6. Slab分配器
從伙伴系統(tǒng)的介紹可以知道其分配的最小單位是 4KB 的頁(yè)框,這對(duì)于一些頻繁申請(qǐng)的小到幾十字節(jié)的內(nèi)存來(lái)說(shuō)還是十分浪費(fèi)的,所以我們需要更細(xì)粒度的分配器,這就是slab分配器。
slab分配器并不是和伙伴系統(tǒng)分立的,而是建立在伙伴系統(tǒng)之上,可以看作是伙伴系統(tǒng)的二級(jí)分銷(xiāo)商,更加靠近用戶(hù)側(cè),但是slab分配器因?yàn)楦拷褂梅?,因此在結(jié)構(gòu)實(shí)現(xiàn)上比伙伴系統(tǒng)更加復(fù)雜,本文只能簡(jiǎn)單概括。
個(gè)人感覺(jué)slab分配器的亮點(diǎn)包括:最小粒度為對(duì)象和內(nèi)存惰性歸還。
Linux 所使用的 slab 分配器的基礎(chǔ)是 Jeff Bonwick 為 SunOS 操作系統(tǒng)首次引入的一種算法。Jeff 的分配器是圍繞對(duì)象緩存進(jìn)行的。在內(nèi)核中,會(huì)為有限的對(duì)象集(例如文件描述符和其他常見(jiàn)結(jié)構(gòu))分配大量?jī)?nèi)存。Jeff 發(fā)現(xiàn)對(duì)內(nèi)核中普通對(duì)象進(jìn)行初始化所需的時(shí)間超過(guò)了對(duì)其進(jìn)行分配和釋放所需的時(shí)間。因此他的結(jié)論是不應(yīng)該將內(nèi)存釋放回一個(gè)全局的內(nèi)存池,而是將內(nèi)存保持為針對(duì)特定初始化的狀態(tài)。
from 《linux slab 分配器剖析》
slab采用對(duì)象作為最小單位的理論基礎(chǔ)就在于初始化一個(gè)結(jié)構(gòu)的時(shí)間可能超過(guò)了分配和釋放的時(shí)間。
slab分配器可以看作是一種內(nèi)存預(yù)分配機(jī)制,就像超市會(huì)把常用的物品放到大家更容易找到的位置,事先把這些對(duì)象準(zhǔn)備好申請(qǐng)時(shí)就可以立刻分配出去了。
slabs_full:鏈表中slab已經(jīng)完全分配出去
slabs_partial:鏈表中的slab部分已經(jīng)被分配出去了
slabs_empty: 鏈表中的slab都是空閑的 也就是可以被回收
對(duì)象是從 slab 中進(jìn)行分配和釋放的,每個(gè)kmem_cache的slab列表是存在狀態(tài)遷移的,但是被回收的部分slab并不會(huì)立刻歸還給伙伴系統(tǒng),并且在分配時(shí)會(huì)優(yōu)先分配最近被釋放的對(duì)象,目的是利用cpu緩存的局部性原理,可以看出來(lái)slab分配器的細(xì)節(jié)做的很足,但是為了實(shí)現(xiàn)這一套復(fù)雜的邏輯,就要維護(hù)多個(gè)隊(duì)列會(huì)比伙伴系統(tǒng)更復(fù)雜。
slab的內(nèi)容相比buddy更復(fù)雜,本文不再展開(kāi)。
7.結(jié)語(yǔ)
linux內(nèi)存管理的東西確實(shí)非常多,本文也只有5k字并且沒(méi)有源碼,所以只能是淺談。
從工程角度來(lái)說(shuō),本文也只是拋磚引玉的作用,所以這篇文章并不是深入的探討內(nèi)存管理,對(duì)此我也表示歉意。
讓我的好朋友sy審稿了一下,他說(shuō)看著寫(xiě)了很多但又好像啥也沒(méi)寫(xiě),其實(shí)我跟他的感受一樣,可能最近寫(xiě)文章沒(méi)感覺(jué),和上篇快手面試題差不多,寫(xiě)完之后有點(diǎn)迷茫。
所以最后還是那句話(huà),本文只是淺談,深入理解還是需要去看內(nèi)核書(shū)籍,沒(méi)有捷徑。
8.巨人的肩膀
https://blog.csdn.net/XD_hebuters/article/details/79519406
https://blog.csdn.net/xd_hebuters/article/details/79506062
https://jacktang816.github.io/post/linuxmemorymanage/
https://jacktang816.github.io/post/memoryfragmentation/
https://www.jianshu.com/p/98f9f86b2aeb
https://www.cnblogs.com/sunsky303/p/9214223.html
https://www.cnblogs.com/klb561/p/11062166.html
http://abcdxyzk.github.io/blog/2015/03/03/kernel-mm-slab2/
https://www.ibm.com/developerworks/cn/linux/l-linux-slab-allocator/index.html
免責(zé)聲明:本文內(nèi)容由21ic獲得授權(quán)后發(fā)布,版權(quán)歸原作者所有,本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn),不代表本平臺(tái)立場(chǎng),如有問(wèn)題,請(qǐng)聯(lián)系我們,謝謝!