作者：CppExplore
http://www.shnenglu.com/CppExplore/和
http://blog.csdn.net/cppexplore同步發布
一 linux內存管理以及內存碎片產生原因 
最底層使用伙伴算法管理內存頁面。系統將所有空閑內存頁面分10個組，每個組中的內存塊大小依次是1，2，4......512個內存頁面，每組中的內存塊大小相同，并且以鏈表結構保存。大小相同，并且內存地址連續的兩個內存塊稱為伙伴。伙伴算法的中心思想就是將成為伙伴的空閑內存合并成一個更大的內存塊。
os中使用get_free_page獲取空閑頁面，如果找不到合適大小的空閑頁面，則從更大的組中找到空閑內存塊，分配出去，并將剩余內存分割，插入到合適的組中。當歸還內存時，啟動伙伴算法合并空閑內存。如果不停的申請內存，并且部分歸還，但歸還的內存不能成為伙伴，長期運行后，所有內存將被分割成不相鄰的小塊，當再次申請大塊內存時，則可能由于找不到足夠大的連續內存塊而失敗，這種零散的不相鄰的小塊內存稱之為內存碎片。當然這只是理論上的說明，伙伴算法本身就是為了解決內存碎片問題。
二 malloc子系統內存管理（dlmalloc) 應用層面的開發并不是直接調用sbrk/mmap之類的函數，而是調用malloc/free等malloc子系統提供的函數，linux上安裝的大多為DougLea的dlmalloc或者其變形ptmalloc。下面以dlmalloc為例說明malloc工作的原理。
1 dlmalloc下名詞解釋： boundary tag: 邊界標記，每個空閑內存塊均有頭部表識和尾部標識，尾部表識的作為是合并空閑內存塊時更快。這部分空間屬于無法被應用層面使用浪費的內存空間。
smallbins: 小內存箱。dlmalloc將8,16,24......512大小的內存分箱，相臨箱子中的內存相差8字節。每個箱子中的內存大小均相同，并且以雙向鏈表連接。
treebins: 樹結構箱。大于512字節的內存不再是每8字節1箱，而是一個范圍段一箱。比如512~640, 640~896.....每個箱子的范圍段依次是128，256，512......。每箱中的結構不再是雙向鏈表，而是樹形結構。
dv chunk: 當申請內存而在對應大小的箱中找不到大小合適的內存，則從更大的箱中找一塊內存，劃分出需要的內存，剩余的內存稱之為dv chunk.
top chunk: 當dlmalloc中管理的內存都找不到合適的內存時，則調用sbrk從系統申請內存，可以增長內存方向的chunk稱為top chunk.
2 內存分配算法 從合適的箱子中尋找內存塊-->從相臨的箱子中尋找內存塊-->從dv chunk分配內存-->從其他可行的箱子中分配內存-->從top chunk中分配內存-->調用sbrk/mmap申請內存
3 內存釋放算法 臨近內存合并-->如屬于top chunk，判斷top chunk>128k，是則歸還系統
-->不屬于chunk，則歸相應的箱子
dlmalloc還有小內存緩存等其他機制?？梢钥闯鼋涍^dlmalloc，頻繁調用malloc/free并不會產生內存碎片，只要后續還有相同的內存大小的內存被申請，仍舊會使用以前的合適內存，除非大量調用malloc之后少量釋放free，并且新的malloc又大于以前free的內存大小，造成dlmalloc不停的從系統申請內存，而free掉的小內存因被使用的內存割斷，而使top chunk<128k，不能歸還給系統。即便如此，占用的總內存量也小于的確被使用的內存量的2倍（使用的內存和空閑的內存交叉分割，并且空閑的內存總是小于使用的內存大小）。因此可以說，在沒有內存泄露的情況，常規頻繁調用malloc/free并不會產生內存碎片。
三 應用層內存池
即便沒有內存碎片問題，應用層仍然需要內存池，原因如下：
1 使用的內存固定可控 穩定性角度
2 減少與內核態交互的可能 性能角度
3 減少互斥操作 性能角度，各個線程直接調用malloc，極有可能有線程進入競態條件，陷入內核態。
其中穩定性只能是聊以自慰的說法，os本身都不可信，哪里還來得穩定性的說法。最重要的出發點，是應用層控制內存，提高應用層性能。那么如何創建使用內存池，才能充分提高內存使用的性能呢？我們先從著名的內存池看起。
四 常見內存池
變長內存池：
1 apr pool : 針對業務處理，將整個業務場景分段，不同階段使用不同類型內存池，內存歸還池后并不能被再次使用，而是池本身可以被重復使用，特浪費內存。
2 obstack: gcc自帶變長內存池
定長內存池：
1 SGI STL: 針對小內存做池，字節長度為8,16......128共16個池，每個池中內存大小相同，使用鏈表連接，小內存采取永不歸還malloc子系統策略，大于128直接調用malloc。SGI STL為gcc攜帶的stl實現。vc以及bc攜帶的stl，雖然也有allocator對象，但并沒有真正的池，而是直接調用malloc。
2 boost/loki
兩種內存池采用類似的底層算法，以loki為例子，首次申請一塊定長內存，loki會一次性申請255個，之后再次申請從該池中直接獲取，從池中申請釋放內存算法示例如下：
（1）首次申請內存后，對空閑內存編號，并且前一個內存保存下一塊內存的編號，一變量NextBlock保存下次可以申請出的內存塊，首次NextBlock=0
（2）當申請出3塊內存后，NextBlock=3
（3）當第二塊內存歸還時，根據內存基址找到所屬的內存chunk，對比chunk基址以及該持中內存塊長度，找到該塊編號，尾部編號保存NextBlock，NextBlock=1
（4）再次歸還第三塊，第三塊尾部保存上次的NextBlock，NextBlock=2
（5）再次申請內存，根據NextBlock指定分配出的內存，NextBlock等于該塊內存尾部指向的值1.
以上模擬stack的壓棧出棧行為.
loki和boost對內存的處理上有稍許差別，包括內存的組織層次上，這些差別我個人看都是loki相對于boost的缺點。
loki/boost代表了當前內存池的最高水準，該池無任何冗余頭部（free的內存才保存冗余信息），更節省內存；另外分配釋放內存快速，只有固定極少的常數步驟計算。
以上算法只是給內存池的后續使用打下堅實基礎，并沒有給出內存池的使用方式。
五 內存池使用方式分類
loki給出了內存池使用的策略，分以下3種：
1 全局內存池 所有相同長度的內存申請，使用同一個內存池，不同長度內存申請使用不同內存池。對池中的內存進行申請釋放操作時，對池執行加鎖操作。
2 對象內存池 每個對象一個內存池。內存申請釋放執行加鎖操作。
3 線程內存池 相同長度的內存并且在同一個內存中的內存申請釋放使用線程內存池，內存申請釋放不執行加鎖操作。
對比第三部分，應用層使用內存池的原因。顯然全局內存池并沒有解決性能問題，各線程并發申請內存，仍然存在類似直接調用malloc的互斥問題。
而對象內存池將這種互斥進一步降低，僅僅跨線程對同一對象申請釋放內存才會遇到互斥問題。
而線程內存池無疑是最高效的，沒有鎖開銷。
可見最佳的內存池使用方式為，對存在跨線程操作的對象，使用對象內存池，對于只在同一線程內操作的對象使用線程內存池。對象可以通過重載對象的operator new, operator delete等實現。
boost庫極其適合進一步封裝，供對象內存池和線程內存池（結合thread-specific storage）使用。
六 Linux下內存池終結者 tcmalloc，可以通過cache等機制智能判斷應該使用對象內存池還是線程內存池，編碼不需要任何額外策略，直接使用new/delete，只要最后連接上libtcmalloc之類的庫即可。可惜僅僅支持linux。
已有明確的測試數據支持，鏈接tcmalloc后，原cpu居高不下，突高的服務器程序，大大減少了直接調用malloc的互斥競態條件出現，cpu趨于平穩。典型的就是linux下鏈接tcmalloc后重編譯的mysql。