薛 峰

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

1 引言

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

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

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

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

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

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

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

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

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

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

圖1中,pgdat_list指針指向系統(tǒng)唯一的內(nèi)存節(jié)點(diǎn)描述符,該描述符的node_zones數(shù)組中包含三個(gè)區(qū)描述符,每個(gè)區(qū)描述符的zone_mem_map字段指向相應(yīng)內(nèi)存區(qū)起始頁框的頁描述符,系統(tǒng)中所有頁描述符存儲(chǔ)在全局?jǐn)?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)存塊,每個(gè)內(nèi)存塊包含2k個(gè)連續(xù)的頁框,其中k稱為內(nèi)存塊的階,階為k的內(nèi)存塊稱為k階內(nèi)存塊.MAX_ORDER宏定義了階數(shù)的上限,默認(rèn)為11,即階的取值范圍是0～10,因此內(nèi)存塊的尺寸最小為4 K,最大為4 M.對(duì)于一個(gè)內(nèi)存塊,它的第一個(gè)頁框稱為首頁,其余頁框稱為尾頁.一個(gè)內(nèi)存塊的第一個(gè)頁框的描述符稱為首頁描述符.內(nèi)存區(qū)的第一個(gè)頁框在區(qū)內(nèi)的相對(duì)索引稱為該內(nèi)存塊的首頁索引,一個(gè)k階內(nèi)存塊的首頁索引必須被2k整除.

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

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

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

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

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

3 分配算法

3.1 分配算法描述

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

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

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

3.2 分配算法實(shí)例

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

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

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

4 回收算法

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

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

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

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

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

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

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

當(dāng)p[k]=1時(shí),有:

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

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

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

證明:分兩種情況討論:

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

成立.此時(shí),B′的首頁即B的首頁,故:

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

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

成立.此時(shí),B′的首頁即B的首頁,故:

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

4.2 回收算法描述

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

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

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

4.3 回收算法實(shí)例

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

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

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

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

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

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

5 結(jié)論

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

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

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

2 唐納德·E.克努特.計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)-第1卷:基本算法.蘇運(yùn)霖,譯.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)——精髓與設(shè)計(jì)原理.陳向群,陳渝,譯.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.