[發(fā)明專利]內存分配的方法及裝置

有效

• 申請?zhí)枺?/td>: 201210316944.0
• 申請日: 2012-08-31
• 公開（公告）號: CN102866954A
• 公開（公告）日: 2013-01-09
• 發(fā)明（設計）人: 雷鎮(zhèn)
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F12/06
• 分類號: G06F12/06
• 代理公司: 北京龍雙利達知識產權代理有限公司 11329
• 代理人: 王君;肖鸝

技術領域

本發(fā)明涉及計算機領域，具體而言，涉及內存分配的方法及裝置。

背景技術

在如軟件編程的計算機應用中，經常涉及內存資源的動態(tài)申請和釋放。比如創(chuàng)建一個線程時需要為該線程分配棧空間，當該線程被刪除時需要回收對應的棧空間。關于內存管理，業(yè)界已存在多種算法，各有其優(yōu)缺點。評價一款內存算法的優(yōu)劣，主要有性能、利用率、可靠性、可格式化等要素。

內存算法主要分為靜態(tài)內存算法、塊內存算法、分割合并式內存算法等幾大類。靜態(tài)內存算法性能很高，但只能申請內存資源而不能釋放內存資源，一般用在初始化階段。塊內存算法性能也很高，可動態(tài)申請或釋放內存資源，但其可分配的內存資源的大小受到內存塊的大小的限制，而且利用率也比較差。分割合并式內存算法可滿足任意大小的內存資源的申請或釋放，利用率也高，但現有算法的性能比較差。

例如，一種塊內存算法是指將內存池等分成若干個頁：申請內存資源時，若對應內存塊的塊類型的鏈表不為空則從該鏈表中摘取一個內存塊，否則申請一個空閑的內存頁，將該空閑的內存頁按對應的內存塊的大小進行等分，釋放內存資源時，若內存頁中的所有內存塊都空閑，則回收該內存頁并掛入空閑的內存頁的鏈表。但是，該算法會導致頁內碎片與塊內碎片，并且最大可申請的內存資源的大小不能超過最大內存塊的大小。

例如，另一種塊內存算法是指每個內存塊的塊類型都維護一個空閑鏈表：申請內存資源時，先檢查對應的鏈表是否為空，如果不為空則從鏈表中摘取一個內存塊，否則根據分配指針再劃分一個當前大小的內存塊；釋放內存資源時，直接將當前釋放的內存塊掛到對應塊類型的空閑鏈表中。但是，該算法容易導致塊內碎片，最大可申請的內存資源的大小不能超過最大內存塊的大小，并且已被劃分出的內存塊不能格式化為其它塊類型。

例如，一種分割合并式內存算法是指可按任意大小劃分內存塊，并且當內存塊被釋放時可以對前后緊鄰的空閑內存塊進行合并。在該算法中，為了迅速查找到適合的內存塊，將所有空閑內存塊維護成一個平衡二叉樹。但是，該算法涉及二叉樹結點的申請、釋放、查找和平衡操作，因此性能比較差。

發(fā)明內容

本發(fā)明實施例提出了內存分配的方法及裝置，旨在解決現有內存分配中無法兼具高性能、高利用率和申請任意內存大小的問題。

一方面，提出了一種內存分配的方法，包括：將空閑內存塊串接到相應的空閑鏈表中，所述空閑鏈表的頭指針維護在大小為N的空閑鏈表頭數組中，所述空閑鏈表頭數組中頭指針指向的相應的空閑鏈表的索引為n，其中所述N為正整數，所述n為0至N-1的整數，索引為n的空閑鏈表用于串接大小為X的空閑內存塊，其中X大于或等于2ⁿ且小于或等于2ⁿ⁺¹-1；當申請的內存的大小為Y時，從索引為m+1的空閑鏈表開始、在索引為m+1的空閑鏈表與索引為n的空閑鏈表之間確定第一個非空的空閑鏈表，其中所述m小于或等于N-1，Y大于或等于2^m且小于或等于2^m+1-1；提取所述第一個非空的空閑鏈表中的第一個空閑內存塊，按照所述申請的內存的大小分配第一個空閑內存塊。

在第一方面的第一種可能的實現方式中，所述當申請的內存的大小為Y時，從索引為m+1的空閑鏈表開始、在索引為m+1的空閑鏈表與索引為n的空閑鏈表之間確定第一個非空的空閑鏈表包括：當申請的內存的大小在2^m至2^m+1-1之間時，從索引為m+1的空閑鏈表開始、在索引為m+1的空閑鏈表與索引為n的空閑鏈表之間，通過與所述空閑鏈表頭數組對應的位圖確定第一個非空的空閑鏈表，其中所述位圖中的每個位標示所述空閑鏈表頭數組中對應的空閑鏈表是否為空。

結合第一方面或第一方面的第一種可能的實現方式，在第二種可能的實現方式中，還包括：若所述第一個空閑內存塊中存在未分配的剩余空閑內存，根據所述剩余空閑內存的大小將所述剩余空閑內存對應的空閑內存塊串接到相應的空閑鏈表中。

結合第一方面或第一方面的第一種可能的實現方式或第一方面的第二種可能的實現方式，在第三種可能的實現方式中，所述將空閑內存塊串接到相應的空閑鏈表中包括：以雙向鏈表的形式將所述空閑內存塊串接到空閑鏈表中。