1、為什么需要空間配置器?
創(chuàng)新互聯(lián)建站是由多位在大型網(wǎng)絡公司、
廣告設計公司的優(yōu)秀設計人員和策劃人員組成的一個具有豐富經(jīng)驗的團隊,其中包括網(wǎng)站策劃、網(wǎng)頁美工、網(wǎng)站程序員、網(wǎng)頁設計師、平面廣告設計師、網(wǎng)絡營銷人員及形象策劃。承接:成都網(wǎng)站設計、網(wǎng)站建設、
外貿(mào)網(wǎng)站建設、網(wǎng)站改版、網(wǎng)頁設計制作、網(wǎng)站建設與維護、網(wǎng)絡推廣、數(shù)據(jù)庫開發(fā),以高性價比制作企業(yè)網(wǎng)站、行業(yè)門戶平臺等全方位的服務。
內(nèi)存碎片:
頻繁分配小內(nèi)存導致分配不出來大內(nèi)存,這就是外碎片;并且頻繁分配小內(nèi)存效率低
比如,系統(tǒng)依次分配了16、8、16、4、8byte,還剩一個8byte未分配,這時要分配一個24byte的空間,系統(tǒng)回收兩個16byte,總的空間剩余40byte, 但是卻分配不出來一個24byte。
二級空間配置器是為頻繁分配小內(nèi)存而生的一種算法,其實就是消除一級空間配置器的外碎片問題
2、一級空間配置器和二級空間配置器
如果申請的內(nèi)存大小超過128,那么空間配置器就自動調(diào)用一級空間配置器。反之調(diào)用二級空間配置器。而且在這里要說明的是空間配置器默認使用的是一級空間配置器。
一、一級空間配置器
一級空間配置器是malloc-free的封裝,實現(xiàn)類似C++中new-handler機制:一旦申請空間不成功,在丟出bad-allloc異常之前,會先調(diào)用用戶自己指定的處理例程new-handler()。
一級空間配置器的allocate()和reallocate()都是在調(diào)用malloc和realloc不成功時,改調(diào)用oom_malloc和oom_realloc,后兩者都能循環(huán)調(diào)用內(nèi)存不足處理例程,期待在某次調(diào)用之后可以獲得足夠內(nèi)存而達到目的 ,但是若處理例程未被用戶設定,oom_malloc和oom_realloc便會拋出bad-alloc的異?;蛴胑xit(1)終止程序。
代碼如下:
// 一級空間配置器(malloc/realloc/free) template //非類型模板參數(shù) class MallocAllocTemplate { //1:分配內(nèi)存成功,則直接返回 //2:若分配失敗,則檢查是否設置處理的句柄handler //有則調(diào)用以后再分配,不斷重復這個過程,直到分配成功為止. //沒有設置處理的句柄handler,則直接結(jié)束程序 public: static void* Allocate(size_t size) //用于分配空間 { void* ret = malloc(size); if (0 == ret) { ret = OomMalloc(size); } return ret; } static void Deallocate(void* p) //收回 { free(p); } static void* Reallocate(void* p, size_t newsize) //用于指定地址重新分配空間 { void* ret = realloc(p, newsize); if (ret == 0) { ret = OomRealloc(p, newsize); } return ret; } private: static void* OomMalloc(size_t size) //調(diào)用自定義的句柄處理函數(shù)handler釋放并分配內(nèi)存 { ALLOC_FUN handler; void* ret; while (1) { handler = MallocAllocHandler; if (0 == handler) { cout << "out of memory" << endl; exit(-1); } handler(); ret = malloc(size); if (ret) { return(ret); } } } static void* OomRealloc(void*p, size_t newsize) { ALLOC_FUN handler; void* ret; while (1) { handler = MallocAllocHandler; if (0 == handler) { cout << "out of memory" << endl; exit(-1); } handler(); ret = realloc(newsize); if (ret) { return(ret); } } } static void(*SetMallocHandler(void(*f)()))(); //設置操作系統(tǒng)分配內(nèi)存失敗時的句柄處理函數(shù) { void(*tmp)() = MallocAllocHandler; MallocAllocHandler = f; return(tmp); }
}; template ALLOC_FUN MallocAllocTemplate::MallocAllocHander = 0; //句柄函數(shù)初始化為0 |
二、二級空間配置器
二級空間配置器是由一個內(nèi)存池和自由鏈表配合實現(xiàn)的
startFree相當于水位線,標志內(nèi)存池的大小
自由鏈表中其實是一個大小為16的指針數(shù)組,間隔為8的倍數(shù)。各自管理大小分別為8,16,24,32,40,48,56,64,72,80,88,96,104, 112,120,128 字節(jié)的小額區(qū)塊。在每個下標下掛著一個鏈表,把同樣大小的內(nèi)存塊鏈接在一起。類似于哈希桶。
代碼如下:
// 二級空間配置器 template class DefaultallocTemplate //二級空間配置器 { public: enum{ ALIGN = 8 }; //基準值對齊 enum{ MAX_BYTES = 128 }; //大字節(jié) enum{ FREELISTS = MAX_BYTES / ALIGN }; //自由鏈表大小 union obj { union obj* listLink; //自由鏈表中指向下一個內(nèi)存塊的指針 char clientData[1]; //調(diào)試用 }; static size_t FreeListIndex(size_t bytes) //得到所需內(nèi)存塊在自由鏈表中的下標 { return ((bytes + ALIGN - 1) / ALIGN - 1); } static size_t RoundUpNum(size_t bytes) //得到內(nèi)存塊大小的向上對齊數(shù)(8的倍數(shù)) { return (bytes + ALIGN - 1)&~(ALIGN - 1); } static obj* FreeList[FREELISTS]; //維護自由鏈表 static char* startFree; //水位線(維護內(nèi)存池) static char* endFree; //池底 static size_t heapSize; static void* Allocate(size_t size) { if (size > MAX_BYTES) { return MallocAllocTemplate::Allocate(size); } void* ret = NULL; size_t index = FreeListIndex(size); if (FreeList[index]) //自由鏈表上有內(nèi)存塊 { obj* ret = FreeList[index]; //取走當前下標的第一個給用戶 FreeList[index] = ret->listLink; //FreeList[index]指向下一個 } else //若自由鏈表沒有,則調(diào)用refill從內(nèi)存池填充自由鏈表并返回內(nèi)存池的第一個內(nèi)存塊 { return Refill(RoundUpNum(size)); } return ret; } static void* Reallocate(void* p, size_t oldsize, size_t newsize) { void* ret = NULL; if (oldsize > (size_t)MAX_BYTES&&newsize > (size_t)MAX_BYTES) return (realloc(p, newsize)); if (RoundUpNum(oldsize) == RoundUpNum(newsize)) return p; ret = Allocate(newsize); size_t copysize = oldsize > newsize ? newsize : oldsize; memcopy(ret, p, copysize); DeAllocate(p, oldsize); return ret; } static void Deallocate(void* p, size_t size) { if (size> MAX_BYTES) //如果大于MAX_BYTES直接交還給一級空間配置器釋放 return MallocAllocTemplate::Deallocate(p, size); else //放回二級空間配置器的自由鏈表 { size_t index = FreeListIndex(size); obj* tmp = (obj*)p; tmp->listLink = FreeList[index]; Freelist[index] = tmp; } } //從內(nèi)存池拿出內(nèi)存填充自由鏈表 static void* Refill(size_t size) { int nobjs = 20;//申請20個size大小的內(nèi)存塊 char* chunk = ChunkAlloc(size, nobjs); if (nobjs == 1) //只分配到一個內(nèi)存 { return chunk; }
size_t index = FreeListIndex(size); obj* cur = chunk + size; obj* next = NULL; //將剩余內(nèi)存塊掛到自由鏈表上 FreeList[index] = cur; for (int i = 1; i < nobjs-1; ++i) { next=(obj*)((char*)cur +size); cur->listLink = next; cur = next; } cur->listLink = NULL; return chunk; }
//從內(nèi)存池中分配大塊內(nèi)存 static char* ChunkAlloc(size_t size, int& nobjs) { char* ret = NULL; size_t Leftbytes = endFree - startFree; //剩余的內(nèi)存塊 size_t Needbytes = size * nobjs; //所總共需要的內(nèi)存塊 if (Leftbytes >= Needbytes) { ret = startFree; startFree += Needbytes; } else if (Leftbytes >= size) //不夠分配總size大小,但是夠分配單個size大小的 { ret = startFree; nobjs = Leftbytes / size; startFree += nobjs*size; } else //一個內(nèi)存塊都分配不出來 { if (Leftbytes > 0) { size_t index = FreeListIndex(Leftbytes); ((obj*)startFree)->listLink = FreeList[index]; FreeList[index] = (obj*)startFree; startFree = NULL; } //向操作系統(tǒng)申請2倍Needbytes加上已分配的heapsize/8的內(nèi)存到內(nèi)存池 size_t getBytes = 2 * Needbytes + RoundUpNum(heapSize >> 4); startFree = (char*)malloc(getBytes); if (startFree == NULL) //從系統(tǒng)堆中分配內(nèi)存失敗 { //到后面更大的自由鏈表中去取 for (int i = size; i < MAX_BYTES; i += ALIGN) { size_t index = FreeList[FreeListIndex(i)]; if (FreeList[index]) { startFree = FreeList[index]; FreeList[index] = FreeList[index]->listLink; endFree = startFree + size; return ChunkAlloc(size, nobjs); } } //山窮水盡 //最后的一根救命稻草,找一級空間配置器分配內(nèi)存 //(其他進程歸還內(nèi)存,調(diào)用自定義的句柄處理函數(shù)釋放內(nèi)存) startFree = MallocAllocTemplate::Allocate(getBytes); } heapSize += getBytes; //從系統(tǒng)堆分配的總字節(jié)數(shù)(可以用于下次分配時進行調(diào)節(jié)) endFree = startFree + getBytes; return ChunkAlloc(size, nobjs); //遞歸調(diào)用獲取內(nèi)存 } return ret; } }; template typename DefaultAllocTemplate::obj* DefaultAllocTemplate::FreeList[FREELISTSIZE] = { 0 }; template char* DefaultAllocTemplate::startFree = 0; template char* DefaultAllocTemplate::endFree = 0; template size_t DefaultAllocTemplate::heapSize = 0; |
部分代碼解釋:
static size_t FreeListIndex(size_t bytes)//得到所需內(nèi)存塊在自由鏈表中的下標 { return ((bytes + ALIGN - 1) / ALIGN - 1); }
|
此函數(shù)就是找到需要分配的內(nèi)存塊在自由鏈表中的什么地方,((bytes + ALIGN - 1) / ALIGN - 1),把要分配的內(nèi)存大小提升一個數(shù)量級(+7,每間隔8為一個數(shù)量級),然后除以8,減1,剛好能找到對應的下標,取出一塊內(nèi)存塊給用戶。
static size_t RoundUpNum(size_t bytes) //得到內(nèi)存塊大小的向上對齊數(shù)(8的倍數(shù)) { return (bytes + ALIGN - 1)&~(ALIGN - 1); }
|
此函數(shù)是得到所需內(nèi)存塊大小的向上對齊數(shù)。在自由鏈表中,內(nèi)存塊大小總是8的倍數(shù),但是并不是每次所需內(nèi)存大小都是8的倍數(shù)。所以就要取比所需大小大或相等的內(nèi)存塊,這就是向上取整。&~(ALIGN - 1)相當于將低8位置0,只取高8位,高8位總是8的倍數(shù),正好符合題意。
很關鍵的兩個函數(shù)static void* Refill(size_t size)和static char* ChunkAlloc(size_t size, int& nobjs):
//從內(nèi)存池拿出內(nèi)存填充自由鏈表 static void* Refill(size_t size) { int nobjs = 20;//申請20個size大小的內(nèi)存塊 char* chunk = ChunkAlloc(size, nobjs); if (nobjs == 1)//只分配到一個內(nèi)存 { return chunk; }
size_t index = FreeListIndex(size); obj* cur = chunk + size; obj* next = NULL; //將剩余內(nèi)存塊掛到自由鏈表上 FreeList[index] = cur; for (int i = 1; i < nobjs-1; ++i) { next=(obj*)((char*)cur +size); cur->listLink = next; cur = next; } cur->listLink = NULL; return chunk; } |
當在自由鏈表的下標處沒有內(nèi)存塊時,我們就必須調(diào)用refill去填充自由鏈表。申請時一般一次性申請20個內(nèi)存塊大小的內(nèi)存。通過移動startFree指針將內(nèi)存池內(nèi)的一段內(nèi)存給“切割”出來,然后切成小塊掛在自由鏈表下面。返回第一塊內(nèi)存塊給用戶,其余的都掛在自由鏈表下,方便下次分配,根據(jù)局部性原理,這將極大地提升了分配內(nèi)存空間的效率。
//從內(nèi)存池中分配大塊內(nèi)存 static char* ChunkAlloc(size_t size, int& nobjs) { char* ret = NULL; size_t Leftbytes = endFree - startFree; //剩余的內(nèi)存塊 size_t Needbytes = size * nobjs; //所總共需要的內(nèi)存塊 if (Leftbytes >= Needbytes) { ret = startFree; startFree += Needbytes; } else if (Leftbytes >= size) //不夠分配總size大小,但是夠分配單個size大小的 { ret = startFree; nobjs = Leftbytes / size; startFree += nobjs*size; } else //一個內(nèi)存塊都分配不出來 { if (Leftbytes > 0) { size_t index = FreeListIndex(Leftbytes); ((obj*)startFree)->listLink = FreeList[index]; FreeList[index] = (obj*)startFree; startFree = NULL; } //向操作系統(tǒng)申請2倍Needbytes加上已分配的heapsize/8的內(nèi)存到內(nèi)存池 size_t getBytes = 2 * Needbytes + RoundUpNum(heapSize >> 4); startFree = (char*)malloc(getBytes); if (startFree == NULL) //從系統(tǒng)堆中分配內(nèi)存失敗 { //到后面更大的自由鏈表中去取 for (int i = size; i < MAX_BYTES; i += ALIGN) { size_t index = FreeList[FreeListIndex(i)]; if (FreeList[index]) { startFree = FreeList[index]; FreeList[index] = FreeList[index]->listLink; endFree = startFree + size; return ChunkAlloc(size, nobjs); } } //山窮水盡 //最后的一根救命稻草,找一級空間配置器分配內(nèi)存 //(其他進程歸還內(nèi)存,調(diào)用自定義的句柄處理函數(shù)釋放內(nèi)存) startFree = MallocAllocTemplate::Allocate(getBytes); } heapSize += getBytes; //從系統(tǒng)堆分配的總字節(jié)數(shù)(可以用于下次分配時進行調(diào)節(jié)) endFree = startFree + getBytes; return ChunkAlloc(size, nobjs); //遞歸調(diào)用獲取內(nèi)存 } return ret; } |
ChunkAlloc要做的就是去找操作系統(tǒng)要內(nèi)存,一次性要20個,但是要考慮很多情況:
(1)內(nèi)存池里有足夠20塊大的內(nèi)存
(2)內(nèi)存池里有小于20塊大于等于1塊的內(nèi)存大小
(3)內(nèi)存池里連1塊內(nèi)存那么大的都沒有
具體這樣做:
(1)如果有足夠的內(nèi)存,那么一次性就給20塊,返回第一塊給用戶,其余的掛在自由鏈表上。
(2)只有一塊或者多塊,返回一塊給用戶。
(3) 沒有內(nèi)存了,找操作系統(tǒng)要。
(4)操作系統(tǒng)沒有了,啟用最后一根救命稻草,調(diào)用一級空間配置器,通過句柄函數(shù)釋放內(nèi)存,分配內(nèi)存。
另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn,海內(nèi)外云服務器15元起步,三天無理由+7*72小時售后在線,公司持有idc許可證,提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案,具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢,專為企業(yè)上云打造定制,能夠滿足用戶豐富、多元化的應用場景需求。
網(wǎng)站題目:STL-空間配置器-創(chuàng)新互聯(lián)
本文鏈接:
http://weahome.cn/article/dpodcd.html