空間配置器

1.什么是空間配置器

為各個容器高效的管理空間(空間的申請與回收)的

2.為什么需要空間配置器

各種容器----->可以存放元素---->底層需要空間

new 申請空間

operator new ---->malloc

調用構造函數(shù)------完成對象的構造

動態(tài)內(nèi)存管理總結

前面的容器中，每次開辟空間都用的是new，但是用new有一些不好的地方

• 空間申請與釋放需要用戶自己管理，容易造成內(nèi)存泄漏
• 頻繁向系統(tǒng)申請小塊內(nèi)存塊，容易造成內(nèi)存碎片例如:結點
• 頻繁向系統(tǒng)申請小塊內(nèi)存，影響程序運行效率
• 直接使用malloc與new進行申請，每塊空間前有額外空間浪費 (malloc會在申請的空間前后添加新的東西)
• 申請空間失敗怎么處理
• 代碼結構比較混亂，代碼復用率不高
• 未考慮線程安全問題

高效的內(nèi)存管理方式

3.SGI–STL空間配置器如何實現(xiàn)

小塊內(nèi)存

大于128字節(jié)----->大塊內(nèi)存

小于等于128字節(jié)----->小塊內(nèi)存

• 一級空間配置器處理大塊內(nèi)存，
• 二級空間配置器處理小塊內(nèi)存。

一級空間配置器

malloc+free----->set_new_handle

_malloc_alloc_template:

申請空間

void * allocate(size_t n) {// 申請空間成功，直接返回，失敗交由oom_malloc處理void * result =malloc(n);if(nullptr == result)result = oom_malloc(n);return result; }

釋放空間

static void deallocate(void *p, size_t /* n */) { free(p); }

malloc失敗后的處理oom_malloc

接受函數(shù)指針(調用set_new_handle)

驗證該函數(shù)指針是否為空

• 是：直接拋異常

調用該函數(shù)指針對應的函數(shù)

調用malloc繼續(xù)申請空間

• 申請成功：直接返回
• 申請失敗：循環(huán)繼續(xù)

template <int inst> void * __malloc_alloc_template<inst>::oom_malloc(size_t n) {void (* my_malloc_handler)();void *result;for (;;){// 檢測用戶是否設置空間不足應對措施，如果沒有設置，拋異常，模式new的方式my_malloc_handler = __malloc_alloc_oom_handler;if (0 == my_malloc_handler){__THROW_BAD_ALLOC;}// 如果設置，執(zhí)行用戶提供的空間不足應對措施(*my_malloc_handler)();// 繼續(xù)申請空間，可能就會申請成功result = malloc(n);if (result)return(result);} }

set_new_handle

返回值類型以及參數(shù)類型都是void*()函數(shù)指針

// 該函數(shù)的參數(shù)為函數(shù)指針，返回值類型也為函數(shù)指針 // void (* set_malloc_handler( void (*f)() ) )() static void (* set_malloc_handler(void (*f)()))() {void (* old)() = __malloc_alloc_oom_handler;__malloc_alloc_oom_handler = f;return(old); }

二級空間配置器

頻繁向系統(tǒng)申請小的內(nèi)存塊造成的缺陷
SGI—STL采用了內(nèi)存池的技術來提高申請空間的速度以及減少額外空間的浪費，采用哈希桶的方式來提高用戶獲取空間的速度與高效管理。

內(nèi)存池

內(nèi)存池就是：先申請一塊比較大的內(nèi)存塊已做備用，當需要內(nèi)存時，直接到內(nèi)存池中去去，當池中空間不夠時，再向內(nèi)存中去取，當用戶不用時，直接還回內(nèi)存池即可。避免了頻繁向系統(tǒng)申請小塊內(nèi)存所造成的效率低、內(nèi)存碎片以及額外浪費的問題

char* _start,*finish

申請空間

現(xiàn)在已經(jīng)歸還的內(nèi)存塊中找合適的塊

找到---->是否需要分割---->不需要---->直接分配
需要----->再對內(nèi)存塊進行分割

未找到----->去內(nèi)存池中申請

申請空間的缺陷

鏈表查找合適內(nèi)存塊，需要遍歷，效率低

分割

注意問題

當用戶需要空間時，能否直接從內(nèi)存池中大塊空間中直接截取？為什么？
答:優(yōu)先從鏈表中選，先從大塊中拿，如果用戶需要大塊的空間，可能就給不了了

對用戶歸還的空間能否直接拼接在大塊內(nèi)存前？
答:不行

對用戶歸還的空間如何進行管理？
答:用鏈表連接起來

不斷切割會有什么后果？
答:內(nèi)存碎片

二級空間配置器的設計

SGI-STL中的二級空間配置器使用了內(nèi)存池技術，但沒有采用鏈表的方式對用戶已經(jīng)歸還的空間進行管理(因為用戶申請空間時在查找合適的小塊內(nèi)存時效率比較低)，而是采用了哈希桶的方式進行管理效率更高。那是否需要128桶個空間來管理用戶已經(jīng)歸還的內(nèi)存塊呢？答案是不需要，因為用戶申請的空間基本都是4的整數(shù)倍，其他大小的空間幾乎很少用到。因此：SGI-STL將用戶申請的內(nèi)存塊向上對齊到了8的整數(shù)倍

32位系統(tǒng)用4的倍數(shù)
64位系統(tǒng)用8的倍數(shù)

每個鏈表中肯定必須有一個指針，32位指針是4個字節(jié)，64位下是8個字節(jié)

template <int inst> class __default_alloc_template { private:enum { __ALIGN = 8 }; // 如果用戶所需內(nèi)存不是8的整數(shù)倍，向上對齊到8的整數(shù)倍enum { __MAX_BYTES = 128 }; // 大小內(nèi)存塊的分界線enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; // 采用哈希桶保存小塊內(nèi)存時所需桶的個數(shù)// 如果用戶所需內(nèi)存塊不是8的整數(shù)倍，向上對齊到8的整數(shù)倍static size_t ROUND_UP(size_t bytes){return (((bytes)+__ALIGN - 1) & ~(__ALIGN - 1));} private:// 用聯(lián)合體來維護鏈表結構----同學們可以思考下此處為什么沒有使用結構體union obj{union obj * free_list_link;char client_data[1]; /* The client sees this. */}; private:static obj * free_list[__NFREELISTS];// 哈希函數(shù)，根據(jù)用戶提供字節(jié)數(shù)找到對應的桶號static size_t FREELIST_INDEX(size_t bytes){return (((bytes)+__ALIGN - 1) / __ALIGN - 1);}// start_free與end_free用來標記內(nèi)存池中大塊內(nèi)存的起始與末尾位置static char *start_free;static char *end_free;// 用來記錄該空間配置器已經(jīng)想系統(tǒng)索要了多少的內(nèi)存塊static size_t heap_size;// ...跨平臺操作，封裝鎖，申請空間方式等 };

二級空間配置器的管理空間

void allocate(size_t n)
{
if(n>128)
; //調用一級空間配置器
1. 用n計算桶號
2. 檢測該桶中是否有結點(內(nèi)存塊)
有:使用頭刪法將第一個內(nèi)存塊返回
沒有：return refill(Round_up(n));
}

void refill(size_t/已經(jīng)是8的整數(shù)倍/)
{
size_t nobjs =20;
char* chunk = chunk_alloc(n,nobjs);
if(nobjs == 1) //只要了一塊
return chunk;
//1<nobjs<=20
將第一個內(nèi)存保存，最后要返回給外部用戶
將剩余nobjs-1個內(nèi)存塊掛接到對應的桶中
}

void * chunk_alloc(size_t size,size_t& nobjs//20)
{
size_t totalBytes = nobjs*size;
size_t leftBytes = finish-start;

void * res =null;
if(leftBytes > = totalBytes) //內(nèi)存池空間足以提供20
{res = start;start+=totalBytes;return res;}
else if(leftBytes>=size)//不夠20至少提供1塊
{nobjs =leftBytes/size;res=start;start+=nobjssize;return res;}//實際能提供多少塊
else //內(nèi)存池的空間也不足，連一塊也提供不了
{
//1.將內(nèi)存池中剩余的內(nèi)存—>掛接到相應桶中
//total_get = 2total_bytes+RoundUP(heap_size>>4);
}
}

申請空間

// 函數(shù)功能：向空間配置器索要空間 // 參數(shù)n: 用戶所需空間字節(jié)數(shù) // 返回值：返回空間的首地址 static void * allocate(size_t n) {obj * __VOLATILE * my_free_list;obj * __RESTRICT result;// 檢測用戶所需空間釋放超過128(即是否為小塊內(nèi)存)if (n > (size_t)__MAX_BYTES){// 不是小塊內(nèi)存交由一級空間配置器處理return (malloc_alloc::allocate(n));}// 根據(jù)用戶所需字節(jié)找到對應的桶號my_free_list = free_list + FREELIST_INDEX(n);result = *my_free_list;// 如果該桶中沒有內(nèi)存塊時，向該桶中補充空間if (result == 0){// 將n向上對齊到8的整數(shù)被，保證向桶中補充內(nèi)存塊時，內(nèi)存塊一定是8的整數(shù)倍void *r = refill(ROUND_UP(n));return r;}// 維護桶中剩余內(nèi)存塊的鏈式關系*my_free_list = result->free_list_link;return (result); };

回收空間

二級空間配置器中沒有釋放空間

// 函數(shù)功能：用戶將空間歸還給空間配置器 // 參數(shù)：p空間首地址 n空間總大小 static void deallocate(void *p, size_t n) {obj *q = (obj *)p;obj ** my_free_list;// 如果空間不是小塊內(nèi)存，交給一級空間配置器回收if (n > (size_t)__MAX_BYTES) //超過128，按照一級空間配置進行釋放{malloc_alloc::deallocate(p, n);return;}//沒到128// 找到對應的哈希桶，將內(nèi)存掛在對應哈希桶中my_free_list = free_list + FREELIST_INDEX(n);q->free_list_link = *my_free_list;*my_free_list = q; }

向內(nèi)存中補充空間

template <int inst> char* __default_alloc_template<inst>::chunk_alloc(size_t size, int& nobjs) {// 計算nobjs個size字節(jié)內(nèi)存塊的總大小以及內(nèi)存池中剩余空間總大小char * result;size_t total_bytes = size * nobjs;size_t bytes_left = end_free - start_free;// 如果內(nèi)存池可以提供total_bytes字節(jié)，返回if (bytes_left >= total_bytes){result = start_free;start_free += total_bytes;return(result);}else if (bytes_left >= size){// nobjs塊無法提供，但是至少可以提供1塊size字節(jié)內(nèi)存塊，提供后返回nobjs = bytes_left / size;total_bytes = size * nobjs;result = start_free;start_free += total_bytes;return(result);}else{// 內(nèi)存池空間不足，連一塊小塊村內(nèi)都不能提供// 向系統(tǒng)堆求助，往內(nèi)存池中補充空間// 計算向內(nèi)存中補充空間大小：本次空間總大小兩倍 + 向系統(tǒng)申請總大小/16size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);// 如果內(nèi)存池有剩余空間(該空間一定是8的整數(shù)倍)，將該空間掛到對應哈希桶中if (bytes_left > 0){// 找對用哈希桶，將剩余空間掛在其上obj ** my_free_list = free_list + FREELIST_INDEX(bytes_left);((obj *)start_free)->free_list_link = *my_free_list;*my_ree_list = (obj *)start_free;}// 通過系統(tǒng)堆向內(nèi)存池補充空間，如果補充成功，遞歸繼續(xù)分配start_free = (char *)malloc(bytes_to_get);if (0 == start_free){// 通過系統(tǒng)堆補充空間失敗，在哈希桶中找是否有沒有使用的較大的內(nèi)存塊int i;obj ** my_free_list, *p;for (i = size; i <= __MAX_BYTES; i += __ALIGN){my_free_list = free_list + FREELIST_INDEX(i);p = *my_free_list;// 如果有，將該內(nèi)存塊補充進內(nèi)存池，遞歸繼續(xù)分配if (0 != p){*my_free_list = p->free_list_link;start_free = (char *)p;end_free = start_free + i;return(chunk_alloc(size, nobjs));}}// 山窮水盡，只能向一級空間配置器求助// 注意：此處一定要將end_free置空，因為一級空間配置器一旦拋異常就會出問題end_free = 0;//end_free作用是標記內(nèi)存池空間的末尾start_free = (char *)malloc_alloc::allocate(bytes_to_get);}// 通過系統(tǒng)堆向內(nèi)存池補充空間成功，更新信息并繼續(xù)分配heap_size += bytes_to_get;end_free = start_free + bytes_to_get;return(chunk_alloc(size, nobjs));} }

空間配置器的默認選擇

SGI-STL默認使用一級還是二級空間配置器，通過USE_MALLOC宏進行控制：

#ifdef __USE_MALLOCtypedef malloc_alloc alloc;typedef malloc_alloc single_client_alloc; #else// 二級空間配置器定義 #endif

在SGI_STL中該宏沒有定義，因此：默認情況下SGI_STL使用二級空間配置器

空間配置器的再次封裝

在C++中，用戶所需空間可能是任意類型的，有單個對象空間，有連續(xù)空間，每次讓用戶自己計算所需空間總大小不是很友好，因此SGI-STL將空間配置器重新再封裝了一層：

template<class T, class Alloc> class simple_alloc { public:// 申請n個T類型對象大小的空間static T *allocate(size_t n){return 0 == n ? 0 : (T*)Alloc::allocate(n * sizeof (T));}// 申請一個T類型對象大小的空間static T *allocate(void){return (T*)Alloc::allocate(sizeof (T));}// 釋放n個T類型對象大小的空間static void deallocate(T *p, size_t n){if (0 != n)Alloc::deallocate(p, n * sizeof (T));}// 釋放一個T類型對象大小的空間static void deallocate(T *p){Alloc::deallocate(p, sizeof (T));} };

對象構造與釋放

一切為了效率考慮，SGI-STL決定將空間申請釋放和對象的構造析構兩個過程分離開，因為有些對象的構造不需要調用析構函數(shù)，銷毀時不需要調用析構函數(shù)，將該過程分離開可以提高程序的性能：

// 歸還空間時，先先調用該函數(shù)將對象中資源清理掉 template <class T> inline void destroy(T* pointer) {pointer->~T(); } // 空間申請好后調用該函數(shù)：利用placement-new完成對象的構造 template <class T1, class T2> inline void construct(T1* p, const T2& value) {new (p)T1(value); }

總結

以上是生活随笔為你收集整理的详解STL中的空间配置器(SGI版本)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。