[發明專利]內存分配方法及系統

有效

• 申請號: 201310074180.3
• 申請日: 2013-03-08
• 公開（公告）號: CN103106147A
• 公開（公告）日: 2013-05-15
• 發明（設計）人: 李順芬;陳小剛;周密;宋志棠
• 申請（專利權）人: 中國科學院上海微系統與信息技術研究所
• 主分類號: G06F12/02
• 分類號: G06F12/02
• 代理公司: 上海光華專利事務所 31219
• 代理人: 李儀萍

技術領域

本發明涉及內存管理領域，特別是涉及一種內存分配方法及系統。

背景技術

內存是計算機系統中儲存指令代碼和各種數據的主要部件，如果內存短缺或者管理不當，將導致整個系統反應遲緩，甚至崩潰。所以，建立穩定、高效的內存管理策略是一個很重要的且必須面對的問題。

在現有的Linux操作系統的伙伴算法中，先將所有空閑頁面分為10個塊組，每組中，各內存塊包含2的冪次方個空閑頁面，例如，第0組中各內存塊各自均包含2⁰=1個空閑頁面，第1組中各內存塊各自均包含2¹=2個空閑頁面，……第9組中各內存塊各自均包含2⁹=512個空閑頁面，且每一內存塊組的內存塊形成一個鏈表。可見，在該種算法中，每一內存塊組中各內存塊包含的空閑頁面數量是相同的。

以下將通過一個簡單的例子來說明該Linux操作系統的伙伴算法的工作過程：

假如現操作系統需要一包含128個空閑頁面的內存塊，則該伙伴算法系統先在包含128個空閑頁面的內存塊組的鏈表中查找，以確定是否有包含128個空閑頁面的內存塊，如果有，就直接提供該操作系統使用；如果沒有，該伙伴算法系統會在包含256個空閑頁面的內存塊構成的內存塊組的鏈表中查找，如果該內存塊組中有可用的空閑內存塊，該伙伴算法系統會把該空閑內存塊的256個空閑頁面分為兩等份，一份提供給操作系統使用，另一份插入到包含128個空閑頁面的內存塊構成的內存塊組中。如果在包含256個空閑頁面的內存塊組的鏈表中也沒有找到可用的空閑頁塊，就繼續在更大的塊組，即在包含256個空閑頁面的內存塊構成的內存塊組的鏈表中查找，如果該內存塊組中有可用的空閑內存塊，該伙伴算法系統會把該空閑內存塊的512個空閑頁面分出128個頁面提供給操作系統使用，然后從剩余的384個頁面中取出256個頁面插入到塊大小為256個頁面的鏈表中，然后把剩余的128個頁面插入到塊大小為128個頁面的鏈表中；如果512個頁面的鏈表中還沒有可用的空閑內存塊，該伙伴算法系統就放棄查詢，并發出出錯信號。

內存的釋放是分配的逆過程，也可以看作是伙伴的合并過程。當釋放一個被占用的內存塊時，先在其對應的鏈表中考查是否有伙伴內存塊存在，如果沒有伙伴內存塊，就直接把該要釋放的內存塊掛入鏈表頭；如果有，則從鏈表中摘下伙伴內存塊，并合并成形成合并內存塊，然后繼續考查合并后的合并內存塊在所屬內存塊組的鏈表中是否還有伙伴內存塊存在，直到合并至已包含2⁹=512個頁面為止。其中，滿足以下條件的兩個內存塊互為伙伴內存塊：

（1）兩個內存塊各自包含的頁面數量相同；

（2）兩個內存塊的物理地址連續。

上述伙伴算法的優點是分配和回收速度快、算法簡單,當一個大小為2ⁿ字節的內存塊釋放后,存儲管理系統只需要搜索2ⁿ字節大小的內存塊以判定是否需要合并。

雖然伙伴算法是有名的經典算法，但也并非完美無缺；首先，從伙伴算法原理可知,所有的內存請求都必須以2的冪次方大小為單位，若需要一個包含129個頁面的內存塊時，系統必須提供包含256個頁面的空閑內存塊來使用，由于實際僅使用129個頁面，剩余的127個頁面顯然被浪費了，也就是近50%的內存資源被浪費，可見，該種算法容易導致內存利用率較低。

此外，伙伴算法的效率也容易出現問題：由于伙伴算法涉及比較多的計算、以及鏈表和位圖的操作，導致開銷比較大；例如，如果每次2ⁿ大小的伙伴塊合并到2ⁿ⁺¹的鏈表隊列中，那么2ⁿ大小的鏈表中的內存塊就會因為合并操作而減少，由此，當系統需要2ⁿ大小的內存塊時，就需要將2ⁿ⁺¹大小的內存塊又進行拆分，可見，如此合并又拆分的過程是無效率的。

因而，如何提出一種新的內存分配方法，既能很好的繼承伙伴算法的優點又能克服伙伴算法的不足，實現快速分配、回收內存，同時提高內存使用效率，實為本領域從業者亟待解決的問題。

發明內容

鑒于以上所述現有技術的缺點，本發明的目的在于提供一種內存使用效率高的內存分配方法及系統。

為實現上述目的及其他相關目的，本發明提供一種內存分配方法，其至少包括：