• 最近在網上看到了幾篇篇講述内存池技術的文章，有一篇是有IBM中國研發中心的人寫的，寫的不錯~~文章地址在本篇blog最後。原文的講述比我的要清晰很多，我在這隻是把我的一些理解和遇到的一些問題和大家分享一下~~

• 主要有兩個原因：

1. 減少new、delete次數，減少運行時間；
2. 避免内存碎片。

• c語言中使用malloc/free來分配内存，c 中使用new/delete來分配内存，他們的内存申請與釋放都是與操作系統進行交互的。具體的内容在嚴蔚敏數據結構的第八章有相關講述，主要就是系統要維護一個内存鍊表，當有一個内存申請過來時，根據相應的分配算法在鍊表中找個一個合适的内存分配給它。這些算法有的是分配最先找到的不小于申請内存的内存塊，有的是分配最大的内存塊，有的是分配最接近申請内存大小的内存塊。分配的内存塊可能會大于所申請的内存大小，這樣還有進行切割，将剩餘的内存插入到空閑鍊表中。當釋放的時候，系統可能要對内存進行整理，判斷free的内存塊的前後是否有空閑，若有的話還要進行合并。此外，new/delete還要考慮多線程的情況。總之一句話，調用庫中的内存分配函數，十分的耗時~~

• 什麼是内存碎片内，從字面意思就很好理解了，就是内存不再是一整塊的了，而是碎了。因為連續的這種new/delete操作，一大塊内存肯能就被分割成小的内存分配出去了，這些小的内存都是不連續的。當你再去分配大的連續内存的時候，盡管剩餘内存的總和可能大于所要分配的内存大小，但系統就找不到連續的内存了，所以導緻分配錯誤。malloc的時候會導緻返回NULL，而new的時候再vc6.0中返回NULL，vs2003以上則是抛出異常。

更多linux内核視頻教程文檔資料免費領取後台私信【内核】自行獲取.

• 要解決上述兩個問題，最好的方法就是内存池技術。具體方法就是大小固定、提前申請、重複利用。
• 因為内存的申請和釋放是很低效的，所以我們隻在開始時申請一塊大的内存（在該塊内存不夠用時在二次分配），然後每次需要時都從這塊内存中取出，并标記下這塊内存被用了，釋放時标記此内存被釋放了。釋放時，并不真的把内存釋放給操作系統，隻要在一大塊内存都空閑的時候，才釋放給操作系統。這樣，就減少了new/delete的操作次數，從而提高了效率。
• 在調用内存分配函數的時候，大部分時間所分配的内存大小都是一定的，所以可以采用每次都分配固定大小的内存塊，這樣就避免了内存碎片産生的可能。

• 我所采用的内存池的構造方法完全是按照文章1所介紹的方法，内存池的結構圖如下：

• 如圖所示MemoryPool是一個内存池類，其中pBlock是一個指向了一個内存塊的指針，nUintSzie是分配單元的大小，nInitSize是第一次分配時向系統申請的内存的大小，nGrouSize是後面每次向系統申請的内存的大小。
• MemoryBloc代表一個内存塊單元，它有兩部分構成，一部分時MemoryBlock類的大小，另一部分則是實際的内存部分。一個MemoryBlock的内存是在重載的new操作符中分配的，如下所示：

void* MemoryBlock::operator new(size_t, int nUnitSize,int nUnitAmount ) { return ::operator new( sizeof(MemoryBlock) nUnitSize * nUnitAmount ); }

• MemoryBlock内中，nSize代碼該内存塊的大小（系統分配内存大小-MemoryBlock類的大小），nFree是空閑内存單元的個數，nFirst代表的是下一個要分配的内存單元的序号。aData是用來記錄待分配内存的位置的。因為要分配的内存是在new中一起向系統申請的，并沒有一個指針指向這塊内存的位置，但它的位置就在MemoryBlock這個類的地址開始的，所以可以用MemoryBlock的最後一個成員的位置來表示待分配内存的位置。
• 帶分配内存中，是以nUnitSize為單位的，一個内存單元的頭兩個字節都記錄了下一個要分配的内存單元的序号，序号從0開始。這樣實際也就構成了一個數組鍊表。由MemoryBlock的構造函數來完成這個鍊表的初始化工作：

MemoryBlock::MemoryBlock( int nUnitSize,int nUnitAmount ) : nSize (nUnitAmount * nUnitSize), nFree (nUnitAmount - 1), //構造的時候，就已将第一個單元分配出去了，所以減一 nFirst (1), //同上 pNext (NULL) { //初始化數組鍊表，将每個分配單元的下一個分配單元的序号寫在當前單元的前兩個字節中 char* pData = aData; //最後一個位置不用寫入 for( int i = 1; i < nSize - 1; i ) { (*(USHORT*)pData) = i; pData = nUnitSize; } }

• 在MemoryPool的Alloc（）中，遍曆block鍊表，找到nFree大于0的block，從其上分配内存單元。然後将nFree減一，修改nFirst的值。
• 在MemoryPool的Free（pFree）函數中，根據pFree的值，找到它所在的内存塊，然後将它的序号作為nFirst的值（因為它絕對是空閑的），在pFree的頭兩個字節中寫入原來nFirst的值。然後要判斷，該block是否全部為free，方法是檢測nFree * nUnitSize == nSize。若是，則向系統釋放内存，若不是，則将該block放到鍊表的頭部，因為該block上一定含有空隙的内存單元，這樣可以減少分配時遍曆鍊表所消耗的時間。

• 内存池一般都是作為一個類的靜态成員，或者全局變量。使用時，重載new操作符，使其到MemoryPool中去分配内存，而不是向系統申請。這樣，一個類的所以對象都在一個内存池中開辟空間。

void CTest::operator delete( void* pTest ) { Pool.Free(pTest); } void* CTest::operator new(size_t) { return (CTest*)Pool.Alloc(); }

• MemoryPool.h

#include <stdlib.h> #include <wtypes.h> #define MEMPOOL_ALIGNMENT 8 //對齊長度 //内存塊，每個内存塊管理一大塊内存，包括許多分配單元 class MemoryBlock { public: MemoryBlock (int nUnitSize,int nUnitAmount); ~MemoryBlock(){}; static void* operator new (size_t,int nUnitSize,int nUnitAmount); static void operator delete (void* ,int nUnitSize,int nUnitAmount){}; static void operator delete (void* pBlock); int nSize; //該内存塊的大小，以字節為單位 int nFree; //該内存塊還有多少可分配的單元 int nFirst; //當前可用單元的序号，從0開始 MemoryBlock* pNext; //指向下一個内存塊 char aData[1]; //用于标記分配單元開始的位置，分配單元從aData的位置開始 }; class MemoryPool { public: MemoryPool (int _nUnitSize, int _nGrowSize = 1024, int _nInitSzie = 256); ~MemoryPool(); void* Alloc(); void Free(void* pFree); private: int nInitSize; //初始大小 int nGrowSize; //增長大小 int nUnitSize; //分配單元大小 MemoryBlock* pBlock; //内存塊鍊表 };

• MemoryPool.cpp

#include "MemoryPool.h" MemoryBlock::MemoryBlock( int nUnitSize,int nUnitAmount ) : nSize (nUnitAmount * nUnitSize), nFree (nUnitAmount - 1), //構造的時候，就已将第一個單元分配出去了，所以減一 nFirst (1), //同上 pNext (NULL) { //初始化數組鍊表，将每個分配單元的下一個分配單元的序号寫在當前單元的前兩個字節中 char* pData = aData; //最後一個位置不用寫入 for( int i = 1; i < nSize - 1; i ) { (*(USHORT*)pData) = i; pData = nUnitSize; } } void* MemoryBlock::operator new(size_t, int nUnitSize,int nUnitAmount ) { return ::operator new( sizeof(MemoryBlock) nUnitSize * nUnitAmount ); } void MemoryBlock::operator delete( void* pBlock) { ::operator delete(pBlock); } MemoryPool::MemoryPool( int _nUnitSize, int _nGrowSize /*= 1024*/, int _nInitSzie /*= 256*/ ) { nInitSize = _nInitSzie; nGrowSize = _nGrowSize; pBlock = NULL; if(_nUnitSize > 4) nUnitSize = (_nUnitSize (MEMPOOL_ALIGNMENT - 1)) & ~(MEMPOOL_ALIGNMENT - 1); else if( _nUnitSize < 2) nUnitSize = 2; else nUnitSize = 4; } MemoryPool::~MemoryPool() { MemoryBlock* pMyBlock = pBlock; while( pMyBlock != NULL) { pMyBlock = pMyBlock->pNext; delete(pMyBlock); } } void* MemoryPool::Alloc() { if( NULL == pBlock) { //首次生成MemoryBlock,new帶參數，new了一個MemoryBlock類 pBlock = (MemoryBlock*)new(nUnitSize,nInitSize) MemoryBlock(nUnitSize,nUnitSize); return (void*)pBlock->aData; } //找到符合條件的内存塊 MemoryBlock* pMyBlock = pBlock; while( pMyBlock != NULL && 0 == pMyBlock->nFree ) pMyBlock = pMyBlock->pNext; if( pMyBlock != NULL) { //找到了，進行分配 char* pFree = pMyBlock->aData pMyBlock->nFirst * nUnitSize; pMyBlock->nFirst = *((USHORT*)pFree); pMyBlock->nFree--; return (void*)pFree; } else { //沒有找到，說明原來的内存塊都滿了，要再次分配 if( 0 == nGrowSize) return NULL; pMyBlock = (MemoryBlock*)new(nUnitSize,nGrowSize) MemoryBlock(nUnitSize,nGrowSize); if( NULL == pMyBlock) return NULL; //進行一次插入操作 pMyBlock->pNext = pBlock; pBlock = pMyBlock; return (void*)pMyBlock->aData; } } void MemoryPool::Free( void* pFree ) { //找到p所在的内存塊 MemoryBlock* pMyBlock = pBlock; MemoryBlock* PreBlock = NULL; while ( pMyBlock != NULL && ( pBlock->aData > pFree || pMyBlock->aData pMyBlock->nSize)) { PreBlock = pMyBlock; pMyBlock = pMyBlock->pNext; } if( NULL != pMyBlock ) //該内存在本内存池中pMyBlock所指向的内存塊中 { //Step1 修改數組鍊表 *((USHORT*)pFree) = pMyBlock->nFirst; pMyBlock->nFirst = (USHORT)((ULONG)pFree - (ULONG)pMyBlock->aData) / nUnitSize; pMyBlock->nFree ; //Step2 判斷是否需要向OS釋放内存 if( pMyBlock->nSize == pMyBlock->nFree * nUnitSize ) { //在鍊表中删除該block delete(pMyBlock); } else { //将該block插入到隊首 PreBlock = pMyBlock->pNext; pMyBlock->pNext = pBlock; pBlock = pMyBlock; } } }

• CTest.cpp

#include <stdio.h> #include "MemoryPool.h" class CTest { public: CTest(){data1 = data2 = 0;}; ~CTest(){}; void* operator new (size_t); void operator delete(void* pTest); public: static MemoryPool Pool; int data1; int data2; }; void CTest::operator delete( void* pTest ) { Pool.Free(pTest); } void* CTest::operator new(size_t) { return (CTest*)Pool.Alloc(); } MemoryPool CTest::Pool(sizeof(CTest)); int main() { CTest* pTest = new CTest; printf("%d",pTest->data2); }

• 在編寫代碼時，遇到了一些小問題，現與大家分享如下：

1. 重載new操作符時，編譯器要求是第一個參數必須是size_t，返回值必須是void*;free的第一個參數必須是void*.
2. 一般要在類的成員中重載new操作符，而不要重載全局的new操作符。
3. 一個類中要是重載了一個new操作符，一定要有一個相應類型的delete操作符，可以什麼都不幹，但必須有，否則在構造函數失敗時，找不到對應的delete函數。

• 例如：　

static void* operator new (size_t,int nUnitSize,int nUnitAmount); static void operator delete (void* ,int nUnitSize,int nUnitAmount){};

4. 帶參數的new操作符

pBlock = (MemoryBlock*)new(nUnitSize,nInitSize) MemoryBlock(nUnitSize,nUnitSize);

• 第一個nUnitSize nInitSize是new操作符的參數，該new操作符是new了一個MemoryBlock對象，在new返回的地址上構造MemoryBlock的對象。

5. 如果在類的内部不能進行靜态成員的定義的話，可以隻在内部進行聲明，在外部定義：

MemoryPool CTest::Pool(sizeof(CTest));

​