關鍵點:
1).考慮到小型區塊所可能造成的內存破碎問題,設計了雙層級配置器.
當配置區塊超過128bytes時,調用第壹層級配置器,第壹層級配置器直接使用malloc()和free().
當配置區塊小於128bytes時,調用第二層級配置器,采用復雜的memory pool整理方式,降低額外開銷.
2).內存池管理方式是每次配置壹大塊內存,並維護對應之自由鏈表.
若有相同大小的內存分配,就直接從自由鏈表中分配內存塊.
若內存釋放時,則由配置器回收到自由鏈表中.
第二級配置器會主動將任何小額區塊的內存需求量調至8的倍數.
3).自由鏈表(free-list)節點的結構如下:
利用union的特性,從第壹字段觀之,obj可被視為壹個指針,指向相同形式的另壹個obj.
從第二字段觀之,obj可被視為壹個指針,指向實際區塊.
壹物二用,不會為了維護鏈表所必須的指針而造成內存的壹種浪費.
具體代碼實現,請參考STL源碼.下面附幾張圖說明.
第壹級配置器與第二級配置器之間的關系:
第二級配置器分配內存時,自由鏈表變化示意圖:
第二級配置器釋放內存時,自由鏈表變化示意圖:
第二級配置器分配內存時,其具體步驟如下:
1).判斷內存塊大小,是否大於128bytes,若大於,則調用第壹級配置器.若小於,進行步驟2).
2).從16個自由鏈表中,根據內存塊大小選擇合適的自由鏈表.
3).判斷自由鏈表是否為空,若為空,則重新真充自由鏈表,否則,進行步驟4).
4).調整當前自由鏈表指向壹塊內存塊,並返回當前的內存塊.(類似於鏈表的刪除操作)
第二級配置器釋放內存時,其具體步驟如下:
1).判斷內存塊大小,是否大於128bytes,若大於,則調用第壹級配置器.若小於,進行步驟2).
2).從16個自由鏈表中,根據內存塊大小選擇合適的自由鏈表.
3).調整當前自由鏈表回收當前的內存塊.(類似於鏈表的插入操作)
內存池的實際操作結果示意圖:
內存池管理:
1).三個變量來標識內存池的使用情況和大小,start_free,end_free,heap_size.
2).從內存池中取空間給自由鏈表時,主要分三種情況進行.
a).內存池剩余空間完全滿足需求量,則直接修改start_free的值,返回對應的區塊.
b).內存池剩余空間不能完全滿足需求量,但足夠供應壹個(含)以上的區塊,則減少分配的區塊數目,然後分配.
c).內存池剩余空間連壹個區塊的大小都無法提供,則利用malloc增加內存空間.
若malloc成功,則修改start_free,end_free,heap_size,然後遞歸調用自身,重新分配區塊.
若malloc不成功,則尋找自由鏈表中,看是否存在足夠大的區塊.
若存在,則將對應區塊作為內存池,調整start_free,end_free,遞歸調用自身,重新分配區塊.
若不存,則調用第壹級配置器。