[發明專利]內存的分配、清理和釋放方法及內存管理的裝置

無效

• 申請號: 200810048215.5
• 申請日: 2008-06-27
• 公開（公告）號: CN101320351A
• 公開（公告）日: 2008-12-10
• 發明（設計）人: 余鑫;李江雄
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F12/02
• 分類號: G06F12/02
• 代理公司: 北京市德權律師事務所
• 代理人: 王建國

技術領域

本發明涉及內存管理技術，特別是內存的分配、清理和釋放方法及內存管理的裝置。

背景技術

隨著linux系統廣泛使用，該系統中動態內存的管理方式已經變得愈發重要。因為如果動態內存短缺或管理不當，將導致整個系統反應遲緩，甚至整個系統的崩潰。

為了保證linux內存管理機制能夠高效運行，在現代操作系統中采用了許多技術，其中比較常用的就是伙伴算法。該算法最早是由Donal?d?E.Knuth于1968年提出的，是一個快速的動態內存管理經典算法。

在該算法中有多個空閑隊列，塊長為2^k個頁面的空閑塊都在同一個隊列中。當要分配一個長為m的內存塊時，需從塊長為2ⁱ的空閑隊列中分配一個內存塊(其中i滿足2^i-1＜m＜2ⁱ)。如果塊長為2ⁱ的空閑隊列耗盡，則從塊長為2ⁱ⁺¹的空閑隊列中分配一塊，將其分為長度相等的兩段，這兩段互為伙伴，一段用于分配，另一段鏈入塊長為2ⁱ的伙伴空閑隊列中。如果塊長為2ⁱ⁺¹的空閑隊列也為空，則繼續向塊長更大的內存塊(2ⁱ⁺²，2ⁱ⁺³……)提出請求。

而當塊長為2^j個頁面的內存塊被釋放時，首先檢查其伙伴塊是否空閑，如果空閑則與伙伴塊合并為塊長為2^j+1的空閑塊，并鏈入對應隊列中；若忙則直接鏈入塊長為2^j的空閑隊列中。當合并得到塊長為2^j+1的空閑內存塊時，也要檢查它的伙伴塊狀態并做相同的處理，直到得到最大的空閑塊。在伙伴算法中，內存的分配和合并都是一個遞歸的過程。

經典的伙伴算法是一個非常強調時效的算法。最壞的情況下，內存分配和回收的時間開銷都是O(log₂M)，其中M是內存的大小。從而內存的分配和回收可在一定時限內完成。在經典的伙伴算法中主要時間消耗在分配時沒有合適的內存塊，需要把大的內存塊分裂成較小的內存塊的過程，以及在回收時，把小的空閑塊合并成較大空閑塊的過程。

經典伙伴算法雖然具有較強的時效性，但存在兩個問題嚴重制約著算法的性能。首先，經典伙伴算法由于塊長為2的冪次方，造成了較多的內部碎片，從而導致即使系統中有足夠的內存，但由于其不連續也不能滿足某些內存請求；其次，若分配的內存塊生存周期很短，經典的伙伴算法要求系統不斷進行內存塊的分裂和合并過程，使得系統產生過大的負載影響了系統的運行效率。

針對經典伙伴算法中存在的問題，對該算法的研究一直沒有停止過。例如，針對內部碎片問題，研究者們先后提出了三種比較重要的改進算法：Knowlton和knuth的binary伙伴算法，Hirschberg的fibonacci伙伴算法，以及Shen和Peterson的weighted伙伴算法。這三種算法均通過增加內存塊尺寸的種類，希望最大程度的使內存塊尺寸更加接近應用需求，以減少內部碎片的產生。雖然這些算法提供了更多合適的內存塊尺寸，似乎達到了減少內部碎片的目的，但是仔細分析則不難發現，在提供更多的內存塊尺寸時，系統就要增加維護新尺寸內存塊的表項，從而增加了空間開銷；同時由于內存塊尺寸的粒度變細，增加了分裂回收伙伴的次數，增加了時間開銷；而且試驗證明，系統的內部碎片總量總是保持在25％-40％這個恒定的區間，并沒有有效減少。總的來說，這三種算法實現內部碎片的減少是以犧牲算法性能為代價的。

發明內容

有鑒于此，本發明的目的在于提供內存的分配、清理和釋放方法及內存管理的裝置，用于減小內存碎片和提高系統效率。

為實現上述目的，本發明提供了一種內存的分配方法，在接收到內存請求時，包括以下步驟：

從大小最合適的空閑隊列為所述內存請求分配內存塊，對內存分配時產生的內部碎片進行回收，將所述內部碎片分別插到不同的空閑隊列；當最大的空閑內存塊也無法滿足所述內存請求時，進行內存塊合并操作。

本發明還提供了一種清理內存的方法，在接收到內存請求時，如果空閑內存中最大的內存塊也無法滿足所述內存請求時，進行內存塊合并操作。