Linux內(nèi)核伙伴系統(tǒng)分析①

薛 峰

(安徽師范大學 數(shù)學計算機科學學院,蕪湖 241002)

1 引言

伙伴算法是一種動態(tài)存儲分配算法,用于實現(xiàn)操作系統(tǒng)內(nèi)核空間和用戶空間(如C語言庫)的分配和回收操作.Knowlton[1]和Knuth[2]最早系統(tǒng)地描述了用于內(nèi)存管理中的二分伙伴算法.之后,Hirschberg[3]和Shen[4]先后提出斐波那契伙伴算法和加權(quán)伙伴算法,作為伙伴算法的兩種變體.為了適應不同的內(nèi)存請求概率分布,Peterson[5]又進一步提出泛化伙伴算法,針對不同請求概率分布采取不同的分配策略.

實現(xiàn)伙伴算法的內(nèi)存管理模塊稱為伙伴系統(tǒng),是固定分區(qū)和可變分區(qū)的一個合理折中方案[6].然而,由于存在內(nèi)碎片和外碎片的問題,以及無法支持虛擬存儲器的緣故,在現(xiàn)代操作系統(tǒng)內(nèi)核中單純的伙伴系統(tǒng)并沒有得到廣泛應用,而分頁機制則成為內(nèi)存管理的主流技術(shù).盡管如此,Linux內(nèi)核成功地將分頁機制與伙伴系統(tǒng)系統(tǒng)結(jié)合起來,分頁機制將邏輯地址空間映射到物理地址空間,伙伴系統(tǒng)負責在物理地址空間中分配和回收頁框,因而內(nèi)存塊的尺寸被限定為頁框尺寸的倍數(shù).為了追求時間效率,Linux內(nèi)核選擇實現(xiàn)了二分伙伴算法,該算法的優(yōu)點在于伙伴地址的計算更加簡便、高效.

目前,涉及Linux內(nèi)核伙伴系統(tǒng)分析的文獻很多,其中以Bovet[7]和Gorman[8]的著作最具代表性.但此類文獻都側(cè)重源代碼的分析,涉及眾多的實現(xiàn)細節(jié),很難突出伙伴系統(tǒng)的核心部分,而且也缺乏能夠演示算法過程的相關(guān)的實例.此外,在Linux內(nèi)核伙伴算法的實現(xiàn)中,如何確定一個內(nèi)存塊伙伴的索引,以及在完成合并之后如何確定內(nèi)存塊的首頁索引,是理解該算法的關(guān)鍵所在.上述文獻僅描述了解決這兩個問題的計算方法,但并未對其正確性給出嚴格的證明.

本文旨在結(jié)合實例,在更加抽象的層面詳細分析Linux內(nèi)核所實現(xiàn)伙伴系統(tǒng)的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)和算法,并針對上述兩個關(guān)鍵計算方法,給出相應的證明.第2節(jié)描述伙伴系統(tǒng)的主要數(shù)據(jù)結(jié)構(gòu).第3節(jié)分析伙伴系統(tǒng)的分配算法.第4節(jié)首先證明與索引計算相關(guān)的幾條結(jié)論,然后分析伙伴系統(tǒng)的回收算法.

2 數(shù)據(jù)結(jié)構(gòu)

2.1 物理內(nèi)存的三級管理結(jié)構(gòu)

Linux內(nèi)核將物理內(nèi)存管理對象分為節(jié)點、區(qū)和頁框三個層次.早期的內(nèi)核僅支持單處理器系統(tǒng),而現(xiàn)在的Linux內(nèi)核則可以在包括多處理器系統(tǒng)在內(nèi)的各類體系結(jié)構(gòu)的計算機上運行.為了適應NUMA體系結(jié)構(gòu)中處理器擁有各自本地內(nèi)存節(jié)點(即分布式內(nèi)存)的情況,內(nèi)核采用節(jié)點描述符存儲內(nèi)存節(jié)點的相關(guān)信息.每個物理內(nèi)存節(jié)點對應一個節(jié)點描述符,其中包含相應內(nèi)存節(jié)點的標識符、起始頁框號、頁框數(shù)等字段.單處理器系統(tǒng)和對稱多處理器系統(tǒng)屬于UMA體系結(jié)構(gòu),這類系統(tǒng)僅包含一個內(nèi)存節(jié)點,因而內(nèi)核僅為其分配唯一的節(jié)點描述符.

依據(jù)內(nèi)存節(jié)點尋址特點及用途的不同可將每個內(nèi)存節(jié)點進一步劃分為若干個內(nèi)存區(qū).例如,在IA32系統(tǒng)中,唯一的內(nèi)存結(jié)點被分為DMA,NORMAL和HIGHMEM三個區(qū).內(nèi)核為每個內(nèi)存區(qū)分配一個區(qū)描述符,其中包含內(nèi)存區(qū)的名稱、起始頁框號、頁框數(shù)等字段.

物理內(nèi)存是一個線性地址空間,即使在NUMA系統(tǒng)中,所有內(nèi)存節(jié)點也是統(tǒng)一編址.頁框是物理內(nèi)存管理的基本單位,如果以頁框作為元素,整個物理內(nèi)存就可以視為一個頁框數(shù)組,而物理內(nèi)存管理的主要工作就是從這個數(shù)組中分配和回收頁框.內(nèi)核為每個頁框分配一個頁描述符,用于記錄對應頁框的信息.

節(jié)點描述符、區(qū)描述符和頁描述符構(gòu)成物理內(nèi)存管理的基本數(shù)據(jù)結(jié)構(gòu),這些結(jié)構(gòu)被相互關(guān)聯(lián)并組織在一起.所有頁描述符被存儲在全局數(shù)組mem_map中,區(qū)描述符中用zone_mem_map指針指向?qū)獌?nèi)存區(qū)起始頁框的頁描述符,而內(nèi)存節(jié)點所含內(nèi)存區(qū)的區(qū)描述符則存儲在node_zones字段中,該字段是一個區(qū)描述符數(shù)組,區(qū)描述符的數(shù)量存儲在nr_zones字段中.所有節(jié)點描述符被鏈接成一個鏈表,全局變量pgdat_list指針指向第一個節(jié)點描述符.圖1演示了一個典型的IA32系統(tǒng)中各描述符之間的關(guān)系.

圖1中,pgdat_list指針指向系統(tǒng)唯一的內(nèi)存節(jié)點描述符,該描述符的node_zones數(shù)組中包含三個區(qū)描述符,每個區(qū)描述符的zone_mem_map字段指向相應內(nèi)存區(qū)起始頁框的頁描述符,系統(tǒng)中所有頁描述符存儲在全局數(shù)組mem_map中.

2.2 伙伴系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)

伙伴系統(tǒng)從指定的內(nèi)存區(qū)中分配頁框,使用完畢后頁框被回收到其所屬的內(nèi)存區(qū).為了滿足不同尺寸的需要,內(nèi)存區(qū)中的頁框被組合成一些內(nèi)存塊,每個內(nèi)存塊包含2k個連續(xù)的頁框,其中k稱為內(nèi)存塊的階,階為k的內(nèi)存塊稱為k階內(nèi)存塊.MAX_ORDER宏定義了階數(shù)的上限,默認為11,即階的取值范圍是0～10,因此內(nèi)存塊的尺寸最小為4 K,最大為4 M.對于一個內(nèi)存塊,它的第一個頁框稱為首頁,其余頁框稱為尾頁.一個內(nèi)存塊的第一個頁框的描述符稱為首頁描述符.內(nèi)存區(qū)的第一個頁框在區(qū)內(nèi)的相對索引稱為該內(nèi)存塊的首頁索引,一個k階內(nèi)存塊的首頁索引必須被2k整除.

未分配內(nèi)存塊處于空閑狀態(tài),為了便于分配和回收,所有空閑內(nèi)存塊被鏈接到其階數(shù)對應的空閑鏈表中.區(qū)描述符中的free_area數(shù)組用于跟蹤空閑內(nèi)存塊,該數(shù)組包含MAX_ORDER個元素,每個元素的下標即階數(shù).數(shù)組元素是free_area結(jié)構(gòu)體,包含free_list和nr_free兩個字段.其中,free_list字段是空閑鏈表的頭節(jié)點,用于鏈接對應階數(shù)第一個空閑內(nèi)存塊的首頁描述符,nr_free字段記錄空閑鏈表長度,即相應階數(shù)的空閑內(nèi)存塊數(shù).頁描述符的lru字段鏈接同階下一個空閑內(nèi)存塊的首頁描述符.

圖2上方展示一個包含16個頁框的內(nèi)存區(qū)的空閑鏈表.在區(qū)描述符的free_area數(shù)組中,0階、1階和3階空閑鏈表中分別鏈接一些空閑內(nèi)存塊的首頁描述符.其中,0階空閑鏈表中包含一個內(nèi)存塊的首頁描述符,首頁索引為11;1階空閑鏈表中包含兩個內(nèi)存塊的首頁描述符,首頁索引分別為8和14.3階空閑鏈表中包含一個內(nèi)存塊的首頁描述符,首頁索引為0.

圖2 空閑鏈表與內(nèi)存塊分布圖示例

圖2下方展示該內(nèi)存區(qū)中的頁描述符數(shù)組.其中白色方塊代表空閑頁框描述符,標注數(shù)字的白色方塊代表空閑內(nèi)存塊的首頁描述符,其中的數(shù)字表示該內(nèi)存塊的階數(shù),灰色方塊代表已分配的頁框描述符.

頁框狀態(tài)存放在頁描述符的private和flags兩個字段中.其中,private字段用于存放內(nèi)存塊的階數(shù),該字段僅在空閑內(nèi)存塊的首頁描述符中有效.flags字段包含一個PG_Private標志位,用于指示private字段的取值是否有效.PG_Private為1表示頁框是空閑內(nèi)存塊的首頁,其中的private字段取值有效;否則,表示頁框已分配或?qū)儆诳臻e內(nèi)存塊的尾頁,其中的private字段取值無效.在圖2的頁描述符數(shù)組中,灰色方塊和未標注數(shù)字的白色方塊代表的頁描述符的PG_Private標志為0,標注數(shù)字的白色方塊代表的首頁描述符的PG_Private標志為1.

3 分配算法

3.1 分配算法描述

當內(nèi)核請求分配內(nèi)存時,伙伴系統(tǒng)執(zhí)行分配算法以滿足其需求.分配算法的基本思想是尋找能夠滿足內(nèi)核需求的最小空閑內(nèi)存塊,如果該內(nèi)存塊的階大于內(nèi)核請求的階,則將其逐步劃分為一系列低階內(nèi)存塊,直到劃分出恰好滿足需求的一個內(nèi)存塊,并分配給內(nèi)核使用.其余低階內(nèi)存塊按其所屬的階被依次插入相應的空閑鏈表,用于滿足今后的內(nèi)存請求.

假設內(nèi)核需要從內(nèi)存區(qū)zone分配一塊order階空閑內(nèi)存塊,分配算法從order階開始遍歷zone內(nèi)存區(qū)的free_area數(shù)組,查找能夠滿足需求的空閑內(nèi)存塊.如果order階的空閑鏈表非空,則說明至少存在一個恰好滿足需求的內(nèi)存塊,此時查找成功.否則,逐階遞增查找每一個高階空閑鏈表,直至成功找到空閑鏈表非空的一個階.如果直到MAX_ORDER-1階也未能找到,則查找失敗,說明無法滿足內(nèi)核提出的內(nèi)存分配請求,此時返回空指針,表示內(nèi)存分配失敗.

若查找成功,將找到的階記為current.從current階空閑鏈表移除第一個空閑內(nèi)存塊的首頁描述符,用page指針指向它,并計算free_area[current].nr_free--.如果current＞order,則說明該內(nèi)存塊大于請求的內(nèi)存塊,因而需要對其進行劃分.這里將其等分為兩個current-1階的空閑內(nèi)存塊,位于低地址端的一塊記為BL,其頁描述符由page指針指向;位于高地址端的一塊記為BH,其頁描述符由page+2current-1指針指向.將BH插入current-1階空閑鏈表,并計算free_area[current-1].nr_free++.然后,通過page+2current-1指針修改BH的頁描述符,將flags.PG_Private置位,為private賦值current-1.如果current-1仍然大于order,則需要對BL進行類似的劃分,直到剩余內(nèi)存塊的階恰好等于order.此時,page指針指向剩余內(nèi)存塊的首頁描述符,將其flags.PG_Private清零,表示該內(nèi)存塊已被分配.最后,將zone的頁框數(shù)free_pages減2order,這樣就成功完成了內(nèi)存塊的分配工作.

3.2 分配算法實例

下面結(jié)合實例說明分配算法的執(zhí)行過程.假設內(nèi)存區(qū)zone包含16個頁框,如圖3上方空閑鏈表所示,zone當前存在兩個0階和一個3階空閑內(nèi)存塊.圖2中間演示了內(nèi)存分配過程.假設內(nèi)核請求分配一個1階空閑內(nèi)存塊,對于free_area數(shù)組的查找將從1階開始.由于1階的空閑鏈表為空,因此繼續(xù)查找高階空閑鏈表,直到發(fā)現(xiàn)3階空閑鏈表非空,查找結(jié)果current取值為3,這說明存在一個3階的空閑內(nèi)存塊可供分配.然后,從3階空閑鏈表移除第一個內(nèi)存塊(首頁索引為8)的首頁描述符,并用page指針指向它,同時計算free_area[3].nr_free--.

圖3 內(nèi)存塊的分配過程示例

由于找到的空閑內(nèi)存塊的尺寸(3階)超過了內(nèi)核請求的尺寸(1階),因此需要劃分.首先將其等分為兩個2階內(nèi)存塊,其中高地址端一塊的首頁描述符指針為page+22,其首頁索引為12.在描述符中將flags.PG_Private置位,private賦值為2.同時將描述符插入2階空閑鏈表,并計算free_area[2].nr_free++.然后,進一步劃分低地址端的另一個2階內(nèi)存塊,將其等分為兩個1階內(nèi)存塊.高地址端一塊的首頁描述符指針為page+21,首頁索引為10.在其描述符中將flags.PG_Private置位,private賦值為1.然后,將頁描述符插入1階空閑鏈表,并計算free_area[1].nr_free++.剩下低地址端的一塊1階內(nèi)存塊恰好滿足內(nèi)核的需求,因此停止劃分.此時,page指針指向剩余內(nèi)存塊的首頁描述符,將其flags.PG_Private清零,再將zone的頁框數(shù)free_pages減21,最后返回page指針,至此內(nèi)存分配成功.圖2下方展示分配成功后的空閑鏈表.

4 回收算法

4.1 伙伴的概念及性質(zhì)

伙伴系統(tǒng)回收算法的基本思想是首先確定待回收內(nèi)存塊的伙伴,如果伙伴是空閑的,則將二者合并為一個高階空閑內(nèi)存塊.重復上述合并過程,直至伙伴不再空閑或合并形成的空閑內(nèi)存塊達到最高階.在上述過程中,每次合并前都要將伙伴從其所在的空閑鏈表中移除.合并完成后,最終形成的高階空閑內(nèi)存塊被插入相應空閑鏈表的表頭.不難看出,回收算法的一項重要的工作是確定待回收內(nèi)存塊的伙伴,因此在描述回收算法之前,首先需要明確伙伴的含義.

定義.兩個內(nèi)存塊互為伙伴(Buddy)當且僅當滿足以下三個條件:(1)二者在內(nèi)存中相鄰且不重疊;(2)二者具有相同的階;(3)假設二者的階都為k,則合并后形成一個k+1階空閑內(nèi)存塊,該內(nèi)存塊的首頁索引恰好能夠被2k+1整除.

此外,為了高效地完成回收工作,還需要解決下列兩個關(guān)鍵問題:(1)如何確定伙伴內(nèi)存塊? (2)如何確定合并后形成的高階內(nèi)存塊的首頁? 下列幾條結(jié)論可以幫助解決這兩個問題.

定理1.假設待回收內(nèi)存塊B的階為k,其首頁索引為p,其伙伴的首頁索引為b,則有下式成立:

證明:根據(jù)伙伴應滿足的條件(1)和條件(2)可知,B內(nèi)存塊的伙伴只可能是與其相鄰的兩個k階內(nèi)存塊,下面分兩種情況討論:

綜合上述兩種情況,p[k]的取值決定了B的伙伴:若p[k]=0,則伙伴是B右邊相鄰的k階內(nèi)存塊,否則伙伴是B左邊相鄰的k階內(nèi)存塊.又由于p與2k做異或運算相當于對p[k]求反,故當p[k]=0時,有:

當p[k]=1時,有:

由(2)、(3)兩式可知式(1)成立.

推論.p與b的二進制形式中除了p[k]與b[k]是相反的,其余各位完全相同.

定理2.假設待回收內(nèi)存塊B的階為k,其首頁索引為p,其伙伴的首頁索引為b,B與其伙伴合并后形成的k+1階內(nèi)存塊B′的首頁索引為:

證明:分兩種情況討論:

(1)若伙伴在B的右邊,則p[k]=0,因此有:

成立.此時,B′的首頁即B的首頁,故:

由(5)、(6)兩式可知(4)式成立.

(2)若伙伴在B的左邊,則p[k]=1,因此有:

成立.此時,B′的首頁即B的首頁,故:

由(7)、(8)兩式可知(4)式成立.

4.2 回收算法描述

完成上述準備工作后,下面討論回收算法.假設內(nèi)核請求伙伴系統(tǒng)回收屬于zone內(nèi)存區(qū)的一個order階內(nèi)存塊B,page指針指向B的首頁描述符.首先用page-base計算出B的首頁索引,記為p,其中base是zone內(nèi)存區(qū)的起始頁描述符指針.然后將p代入式(1)計算出伙伴的首頁索引,記為b,伙伴的首頁描述符指針為base+b.如果描述符的flags.PG_Private為0則說明伙伴已經(jīng)被分配,因此無法與B合并.否則,將B與其伙伴合并.

合并時首先從order階空閑鏈表中移除B的伙伴,同時計算free_area[order].nr_free--,然后將伙伴頁描述符中的flags.PG_Private清零,從而完成兩個內(nèi)存塊的合并,形成一個order+1階的空閑內(nèi)存塊B1.然后,將p和b代入式(4)計算出B1的首頁索引p(被替換為新值,因此p始終是當前合并內(nèi)存塊的首頁索引).如果B1的伙伴空閑則再次合并形成order+2階的空閑內(nèi)存塊B2,該過程一直持續(xù)下去,直到伙伴不再空閑,或者合并獲得的空閑內(nèi)存塊達到最高階,合并過程結(jié)束.此時,p是最終合并獲得空閑內(nèi)存塊B’的首頁索引,B’的階數(shù)記為 order’.

接下來還需要進行一些數(shù)據(jù)結(jié)構(gòu)的修改操作.首先,base+p是B’的首頁描述符指針,通過該指針將描述符的flags.PG_Private置位,private賦值為order’.然后,將B’的首頁描述符插入order’階的空閑鏈表,并計算 free_area[order’].nr_free++.最后,為 zone 內(nèi)存區(qū)的空閑頁數(shù)加 2order’.

4.3 回收算法實例

下面結(jié)合實例說明回收算法的執(zhí)行過程.假設內(nèi)存區(qū)zone包含16個頁框,如圖4上方空閑鏈表所示,zone當前存在一個0階、一個1階和兩個3階空閑內(nèi)存塊.圖4中間演示了內(nèi)存塊的回收過程.

圖4 內(nèi)存塊的回收過程示例

假設內(nèi)核需要回收一塊0階內(nèi)存塊,其首頁索引p為9.由式(1)計算出該內(nèi)存塊伙伴的首頁索引b為8,然后從0階空閑鏈表中移除伙伴的首頁描述符,其flags.PG_Private為1,表明伙伴是空閑的.將兩個內(nèi)存塊合并后形成一個1階空閑內(nèi)存塊,由式(2)計算出該內(nèi)存塊的首頁索引p為8.

表1概括了合并內(nèi)存塊的三次迭代所涉及的伙伴,及合并內(nèi)存塊首頁索引的計算過程.其中,第一行對應上面描述的第一次迭代,后兩行對應后續(xù)兩次迭代.最后一行表示第三次迭代后,合并形成一個3階空閑內(nèi)存塊,其首頁索引為8,伙伴的首頁索引為0,由于伙伴首頁描述符的flags.PG_Private為0,因而不再空閑,合并過程結(jié)束.

表1 回收過程中伙伴和合并內(nèi)存塊索引的計算

合并完成后,修改合并形成的3階空閑內(nèi)存塊的首頁描述符,將flags.PG_Private置位,private賦值為3.然后,將描述符插入3階的空閑鏈表,并計算free_area[3].nr_free++.最后,為zone內(nèi)存區(qū)的空閑頁數(shù)加20.圖4下方展示回收成功后的空閑鏈表.

5 結(jié)論

本文以Linux內(nèi)核源代碼為基礎,對負責物理內(nèi)存分配和回收的伙伴系統(tǒng)進行了詳細的分析,通過對源代碼的抽象,突出了伙伴系統(tǒng)的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)和算法.此外,本文著重分析伙伴索引以及合并內(nèi)存塊首頁索引的計算方法,給出了論證算法正確性的相關(guān)證明.

物理內(nèi)存管理是Linux內(nèi)核的底層機制,其分配和回收算法的性能會顯著影響操作系統(tǒng)的整體性能.伙伴算法是一種簡潔、高效的存儲管理算法,Linux內(nèi)核對該算法的實現(xiàn)代碼也非常簡短、優(yōu)雅.盡管如此,Linux內(nèi)核的伙伴系統(tǒng)仍然存在優(yōu)化的空間.本文的研究內(nèi)容有助于深入理解伙伴系統(tǒng)的實現(xiàn)思想,這為進一步優(yōu)化算法的研究奠定了基礎.

1 Knowlton KC.A fast storage allocator.Communications of the ACM,1965,8(10):623–625.[doi:10.1145/365628.365655]

2 唐納德·E.克努特.計算機程序設計藝術(shù)-第1卷:基本算法.蘇運霖,譯.3版.北京:國防工業(yè)出版社,2002:415–417.

3 Hirschberg DS.A class of dynamic memory allocation algorithms.Communications of the ACM,1973,16(10):615–618.[doi:10.1145/362375.362392]

4 Shen KK,Peterson JL.A weighted buddy method for dynamic storage allocation.Communications of the ACM,1974,17(10):558–562.[doi:10.1145/355620.361164]

5 Peterson JL,Norman TA.Buddy systems.Communications of the ACM,1977,20(6):421–431.[doi:10.1145/359605.359626]

6 Stallings W.操作系統(tǒng)——精髓與設計原理.陳向群,陳渝,譯.7版.北京:電子工業(yè)出版社,2012:225–226.

7 Bovet DP,Cesati M.Understanding the linux kernel.3rd ed.O'Reilly Media,2005:311–316.

8 Gorman M.Understanding the linux virtual memory manager.Upper Saddle River,New Jersey,USA:Prentice Hall,2004:105–110.