前戲
我們都知道，頻繁的申請釋放小塊的內存會造成內存碎片，為了減少這個內存碎片，常常會採用內存池的方案。而本文的方案目的是：在給定的內存buffer上建立內存管理機制，根據用戶需求從該buffer上分配內存或者將已經分配的內存釋放回buffer中。要求是儘量減少內存碎片，平均效率高於C語言的malloc和free。
設計思路
將buffer分為四部分，第1部分是mem_pool結構體；第2部分是內存映射表；第3部分是內存chunk結構體緩衝區；第4部分是實際可分配的內存區。整個buffer結構如圖所示：
內存buffer結構圖
- 第1部分的作用是可以通過該mem_pool結構體控制整個內存池。
- 第2部分的作用是記錄第4部分，即實際可分配的內存區的使用情況。表中的每一個單元表示一個固定大小的內存塊（block），多個連續的block組成一個chunk，每個block的詳細結構如圖所示：
memory block結構圖
其中count表示該block後面的與該block同屬於一個chunk的blokc的個數，start表示該block所在的chunk的起始block索引。其實start這個域只有在每個chunk的最後一個block中才會用到（用於從當前chunk尋找前一個chunk的起始位置），而pmem_chunk則是一個指針，指向一個mem_chunk結構體。任意一塊大小的內存都會被取向上整到block大小的整數倍。
- 第3部分是一個mem_chunk pool，其作用是存儲整個程序可用的mem_chunk結構體。mem_chunk pool中的mem_chunk被組織成雙向鏈表結構（快速插入和刪除）。每個mem_chunk結構圖如圖所示：
memory chunk結構圖
其中pmem_block指向該chunk在內存映射表中的位置，others表示其他一些域，不同的實現對應該域的內容略有不同。
- 第4部分就是實際可以被分配給用戶的內存。
整個內存池管理程序除了這四部分外，還有一個重要的內容就是memory chunk set。雖然其中的每個元素都來自mem_chunk pool，但是它與mem_chunk pool的不同之處在於其中的每個memory chunk中記錄了當前可用的一塊內存的相關信息。而mem_chunk pool中的memory chunk的內容是無定以的。可以這樣理解mem_chunk pool與memory chunk set：mem_chunk pool是為memory chunk set分配內存的“內存池”，只是該“內存池”每次分配的內存大小是固定的，為mem_chunk結構體的大小。內存池程序主要是通過搜索這個memory chunk set來獲取可被分配的內存。在memory chunk set上建立不同的數據結構就構成了不同的內存池實現方法，同時也導致了不同的搜索效率，直接影響內存池的性能，本文采用的是鏈表結構內存池的實現。
內存池管理程序運行過程
- 初始化：內存映射表中只有一塊可用的內存信息，大小為內存池中所有可用的內存。從memory chunk pool中分配一個mem_chunk，使其指向內存映射表中的第一個block，並根據具體的內存池實現方式填充mem_chunk中的其他域，然後將該mem_chunk添加到memory chunk set中。
- 申請內存：當用戶申請一塊內存時，首先在memory chunk set中查找合適的內存塊。如果找到符合要求的內存塊，就在內存映射表中找到相應的chunk，並修改chunk中相應block結構體的內容，然後根據修改後的chunk修改memory chunk set中chunk的內容，最後返回分配內存的起始地址；否則返回NULL。
- 釋放內存：當用戶釋放一塊內存時，首先根據這塊內存的起始地址找到其在內存映射表中對應的chunk，然後嘗試將該chunk和與其相鄰的chunk合併，修改chunk中相應block的內容並修改memory chunk set中相應chunk的內容或者向memory chunk set加入新的mem_chunk（這種情況在不能合併內存是發生）。
減少內存碎片方法
本文設計的方法只能在一定程度上減少內存碎片，並不能徹底消除內存碎片。具體方法如下：
在用戶釋放內存時，嘗試將該內存與其相鄰的內存合併。如果其相鄰內存為未分配內存則合併成功，合併後作為一整塊內存使用；如火其相鄰內存為已分配內存則不能合併，該釋放的內存塊作為一個獨立的內存塊被使用。
鏈表結構的內存池實現
代碼就不貼了，很長，而且頭條的排版沒法看。
性能分析
鏈表結構的內存池實現是指將memory chunk set實現為雙鏈表結構。這種方法的優缺點如下：
優點：釋放內存很快，O(1)複雜度。
缺點：分配內存較慢，O(n)複雜度。
內存池運行狀態轉移圖
綠色表示未使用的內存，紅色表示已經使用的內存。其中每個block表示64B，這個值可以根據具體需要設定。
- 初始化
內存池初始化狀態
- 申請內存
第1次申請128B內存後
第n次申請、釋放內存後
- 釋放內存
釋放64B內存前後
性能測試
- 測試對象：C語言的malloc、free和內存池（大小為500M，實際可分配內存為310M）。
- 測試指標：執行n=2000次隨機分配、釋放隨機大小內存（範圍為64B~1024B）的時間比。
- 測試方法1：
（1） 生成n個隨機數，大小在64~1024之間，用於表示n個要分配的內存大小；
（2） 生成n個隨機數，取值 為0或者1，表示每次分配內存後緊接著是否釋放內存；
（3） 測量C語言的malloc、free和內存池執行n次隨機分配、釋放隨機大小內存的時間比ratio；
（4） 重複（3）m=200次，記錄每次活動的ratio，並繪製相應的曲線。
- 測試方法2：
（1） 生成n個隨機數，大小在a~b之間（初始值a=64，b=1024），用於表示n個要分配的內存大小；
（2） 測量C語言的malloc、free和內存池執行n次分配、釋放隨機大小內存的時間比ratio；
（3） 重複（2）m=512次，每次分配的內存容量的範圍比前一次大1024B，記錄每次獲得的ratio，並繪製相應曲線。
性能測試結果
鏈表結構內存池性能測試結果1
鏈表結構內存池性能測試結果2
結論
從上面的內存池性能測試結果中可以看出，相比C語言的malloc和free，內存池使得用戶分配內存和釋放內存的效率有了較大的提高，這一優勢尤其分配較大快的內存時體現的尤為突出。當然，本文的測試具有一定的侷限性。測試用例還是不夠全面。
好了，本期文章就到這裡，感謝支持，咱們下期再見！
喜歡我的文章的話，就關注我吧！在本頭條號的置頂文章中有【文章分類】包含:
[C++進階篇系列]
[高級網絡編程篇系列]
[Linux系統篇系列]
[C++基礎知識篇]
[協議篇系列]
[數據結構和算法系列]
[設計模式系列]
不要只收藏和轉發哦，寫文章其實很累的。
閱讀更多 cpp軟件架構獅 的文章
