[發明專利]一種提高Linux空閑內存塊利用率的方法

在審

• 申請號: 201310421985.0
• 申請日: 2013-09-17
• 公開（公告）號: CN103500145A
• 公開（公告）日: 2014-01-08
• 發明（設計）人: 張樹東;孟兆飛;周麗娟;黃向陽;任仲山
• 申請（專利權）人: 首都師范大學
• 主分類號: G06F12/06
• 分類號: G06F12/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于內存管理技術領域，具體涉及Linux內存管理中伙伴算法對放寬伙伴關系空閑內存塊的分配與回收管理。

背景技術

Linux內存中的所有頁面按照2的冪進行劃分，方冪的指數被稱為階(order)。階的大小一般是O-MAX_ORDER-1。操作內存時經常將這些內存塊分成大小相等的兩個塊，這兩個塊具有伙伴關系，當系統請求(0≤n<MAX_ORDER)個頁面大小的頁塊時，伙伴算法首先在2n空閑塊中查找，如果找到就會分配，如果沒有找到就會一次在2(n+1)～2(MAX_ORDER-1)空閑塊中查找進行分配并把伙伴塊插入到相應的鏈表中。當釋放的頁塊時，伙伴算法先查找其伙伴塊是否在空閑鏈表中，如果沒有就把頁塊插入到2n大小的鏈表中，如果有就將這兩個伙伴塊合并，繼續查找上一級是否存在伙伴塊，以此進行下去，最后將合并的塊插入到對應的空閑鏈表中。如圖1伙伴算法空閑內存組織，Linux內存管理器采用的是鏈表和位圖相結合的方法，具有伙伴關系的兩個塊在位圖中采用一位來表示它們的伙伴關系。當這個位為1，表示一塊在使用，當這個位為O表示兩塊都空閑或都在使用。系統每次分配和回收伙伴塊時都要對它們對應位圖的取值跟1異或運算。剛開始時候，兩個伙伴塊都空閑，它們的位圖取值為O，后來其中一位被使用，異或一下得1，后來另一塊也被使用，異或一下得O，后來前面一塊回收了，異或一下得1，后來另一塊也回收了異或一下得O。

例如，系統請求23個頁面大小的內存塊，系統會在order為3的free_area[3]中查找鏈表，如果有空閑塊，則從此鏈表中刪除一個空閑塊分配，并將對應的位圖位異或1；如果在free_area[3]中沒用空閑塊，系統會繼續查找order為4的free_area[4】中查找鏈表，如果有空閑塊，系統會從此鏈表中刪除一個空閑塊，并將其對應的位圖位異或1，這個空閑塊分成大小相等的兩部分，前半部分插入到free_area[3]的鏈表首部，并將其對應的位圖位異或1，后半部分分配給請求者；如果free_area[4]中也沒有空閑塊，系統會繼續查找order為5的free_area[5]中查找鏈表，如果有空閑塊，系統會從此鏈表中刪除一個空閑塊，并將其對應的位圖位異或1，這個空閑塊分成大小相等的兩部分，前半部分插入到free_area[4]的鏈表首部，并將其對應的位圖位異或1，后半部分再分成大小相等的兩部分，前半部分插入到free_area[3]鏈表中，并將其對應的位圖位異或l，后半部分分配給請求者；如果free_area[5]鏈表中任然沒有空閑塊，則重復前面的過程，以此類推，直到order為MAX_ORDER-1為止，否則，喚醒kswapd守護進程釋放部分內存。

伙伴算法雖然是經典算法，但也存在不足之處。比如它的合并要求過于嚴格，伙伴關系必須滿足三個條件(1)大小相等(2)地址連續(3)兩個伙伴從同一個大塊中拆分出。這限制了某些相鄰但不是伙伴的空閑內存塊的合并。這使得大塊內存空間不能得到更好的利用，對緊俏的內存資源來說比較浪費。

發明內容

本發明旨在解決現伙伴算法中存在的空閑內存資源浪費問題，將內存中大小相等，地址連續但不滿足伙伴關系的空閑內存塊，同樣合并成大的內存塊，在內存緊張時，滿足內存的請求。

本發明為解決上述伙伴算法存在的問題所采取的技術方案為：一種提高Linux空閑內存塊利用率的方法，其特征在于：在保證原伙伴算法的性能前提下，只是增加一個二維數組availablefreeblock[][2]和一個變量availablecount，就能使原伙伴算法中相鄰但非伙伴關系的空閑內存塊組合成大的內存塊充分利用，打破了伙伴算法只有伙伴塊可以合并的禁錮，同時，該優化管理開銷小，使得Linux在更廣泛環境中(尤其內存緊張時)得到使用。

本發明提出的上述技術方案克服了傳統伙伴算法中對大小相等、地址連續但非伙伴關系的空閑內存塊不能充分利用的缺陷。

本發明的其他特征和效果將在下面結合附圖的具體實施方式中詳細說明。

附圖說明

圖1伙伴算法空閑內存組織；

圖2算法修改前內存分配流程圖；

圖3算法修改后內存分配流程圖；

圖4算法修改前內存釋放流程圖；

圖5算法修改內存釋放流程圖圖。

具體實施方式

下面將結合附圖描述本發明的針對Linux內存管理中伙伴算法不足提出的優化方法。