空間配置器
1.什么是空間配置器
為各個容器高效的管理空間(空間的申請與回收)的
2.為什么需要空間配置器
各種容器----->可以存放元素---->底層需要空間
new 申請空間
- operator new ---->malloc
- 調用構造函數------完成對象的構造
動態內存管理總結
前面的容器中，每次開辟空間都用的是new，但是用new有一些不好的地方
- 空間申請與釋放需要用戶自己管理，容易造成內存泄漏
- 頻繁向系統申請小塊內存塊，容易造成內存碎片例如:結點
- 頻繁向系統申請小塊內存，影響程序運行效率
- 直接使用malloc與new進行申請，每塊空間前有額外空間浪費 (malloc會在申請的空間前后添加新的東西)
- 申請空間失敗怎么處理
- 代碼結構比較混亂，代碼復用率不高
- 未考慮線程安全問題
高效的內存管理方式
3.SGI–STL空間配置器如何實現
小塊內存
- 大于128字節----->大塊內存
- 小于等于128字節----->小塊內存
- 一級空間配置器處理大塊內存，
- 二級空間配置器處理小塊內存。
一級空間配置器
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
- 接受函數指針(調用set_new_handle)
- 驗證該函數指針是否為空
- 是：直接拋異常
- 調用該函數指針對應的函數
- 調用malloc繼續申請空間
- 申請成功：直接返回
- 申請失敗：循環繼續
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;}// 如果設置，執行用戶提供的空間不足應對措施(*my_malloc_handler)();// 繼續申請空間，可能就會申請成功result = malloc(n);if (result)return(result);}
}
set_new_handle
返回值類型以及參數類型都是void*()函數指針
// 該函數的參數為函數指針，返回值類型也為函數指針
// 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);
}
二級空間配置器
頻繁向系統申請小的內存塊造成的缺陷
SGI—STL采用了內存池的技術來提高申請空間的速度以及減少額外空間的浪費，采用哈希桶的方式來提高用戶獲取空間的速度與高效管理。
內存池
內存池就是：先申請一塊比較大的內存塊已做備用，當需要內存時，直接到內存池中去去，當池中空間不夠時，再向內存中去取，當用戶不用時，直接還回內存池即可。避免了頻繁向系統申請小塊內存所造成的效率低、內存碎片以及額外浪費的問題
char* _start,*finish
申請空間
- 現在已經歸還的內存塊中找合適的塊
- 找到---->是否需要分割---->不需要---->直接分配
需要----->再對內存塊進行分割 - 未找到----->去內存池中申請
申請空間的缺陷
- 鏈表查找合適內存塊，需要遍歷，效率低
- 分割
注意問題
- 當用戶需要空間時，能否直接從內存池中大塊空間中直接截取？為什么？
答:優先從鏈表中選，先從大塊中拿，如果用戶需要大塊的空間，可能就給不了了 - 對用戶歸還的空間能否直接拼接在大塊內存前？
答:不行 - 對用戶歸還的空間如何進行管理？
答:用鏈表連接起來 - 不斷切割會有什么后果？
答:內存碎片
二級空間配置器的設計
SGI-STL中的二級空間配置器使用了內存池技術，但沒有采用鏈表的方式對用戶已經歸還的空間進行管理(因為用戶申請空間時在查找合適的小塊內存時效率比較低)，而是采用了哈希桶的方式進行管理效率更高。那是否需要128桶個空間來管理用戶已經歸還的內存塊呢？答案是不需要，因為用戶申請的空間基本都是4的整數倍，其他大小的空間幾乎很少用到。因此：SGI-STL將用戶申請的內存塊向上對齊到了8的整數倍
32位系統用4的倍數
64位系統用8的倍數
每個鏈表中肯定必須有一個指針，32位指針是4個字節，64位下是8個字節
template <int inst>
class __default_alloc_template
{
private:enum { __ALIGN = 8 }; // 如果用戶所需內存不是8的整數倍，向上對齊到8的整數倍enum { __MAX_BYTES = 128 }; // 大小內存塊的分界線enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; // 采用哈希桶保存小塊內存時所需桶的個數// 如果用戶所需內存塊不是8的整數倍，向上對齊到8的整數倍static size_t ROUND_UP(size_t bytes){return (((bytes)+__ALIGN - 1) & ~(__ALIGN - 1));}
private:// 用聯合體來維護鏈表結構----同學們可以思考下此處為什么沒有使用結構體union obj{union obj * free_list_link;char client_data[1]; /* The client sees this. */};
private:static obj * free_list[__NFREELISTS];// 哈希函數，根據用戶提供字節數找到對應的桶號static size_t FREELIST_INDEX(size_t bytes){return (((bytes)+__ALIGN - 1) / __ALIGN - 1);}// start_free與end_free用來標記內存池中大塊內存的起始與末尾位置static char *start_free;static char *end_free;// 用來記錄該空間配置器已經想系統索要了多少的內存塊static size_t heap_size;// ...跨平臺操作，封裝鎖，申請空間方式等
};
二級空間配置器的管理空間
void allocate(size_t n)
{
if(n>128)
; //調用一級空間配置器
1. 用n計算桶號
2. 檢測該桶中是否有結點(內存塊)
有:使用頭刪法將第一個內存塊返回
沒有：return refill(Round_up(n));
}
void refill(size_t/已經是8的整數倍/)
{
size_t nobjs =20;
char* chunk = chunk_alloc(n,nobjs);
if(nobjs == 1) //只要了一塊
return chunk;
//1<nobjs<=20
將第一個內存保存，最后要返回給外部用戶
將剩余nobjs-1個內存塊掛接到對應的桶中
}
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) //內存池空間足以提供20
{res = start;start+=totalBytes;return res;}
else if(leftBytes>=size)//不夠20至少提供1塊
{nobjs =leftBytes/size;res=start;start+=nobjssize;return res;}//實際能提供多少塊
else //內存池的空間也不足，連一塊也提供不了
{
//1.將內存池中剩余的內存—>掛接到相應桶中
//total_get = 2total_bytes+RoundUP(heap_size>>4);
}
}
- 申請空間
// 函數功能：向空間配置器索要空間
// 參數n: 用戶所需空間字節數
// 返回值：返回空間的首地址
static void * allocate(size_t n)
{obj * __VOLATILE * my_free_list;obj * __RESTRICT result;// 檢測用戶所需空間釋放超過128(即是否為小塊內存)if (n > (size_t)__MAX_BYTES){// 不是小塊內存交由一級空間配置器處理return (malloc_alloc::allocate(n));}// 根據用戶所需字節找到對應的桶號my_free_list = free_list + FREELIST_INDEX(n);result = *my_free_list;// 如果該桶中沒有內存塊時，向該桶中補充空間if (result == 0){// 將n向上對齊到8的整數被，保證向桶中補充內存塊時，內存塊一定是8的整數倍void *r = refill(ROUND_UP(n));return r;}// 維護桶中剩余內存塊的鏈式關系*my_free_list = result->free_list_link;return (result);
};
- 回收空間
二級空間配置器中沒有釋放空間
// 函數功能：用戶將空間歸還給空間配置器
// 參數：p空間首地址 n空間總大小
static void deallocate(void *p, size_t n)
{obj *q = (obj *)p;obj ** my_free_list;// 如果空間不是小塊內存，交給一級空間配置器回收if (n > (size_t)__MAX_BYTES) //超過128，按照一級空間配置進行釋放{malloc_alloc::deallocate(p, n);return;}//沒到128// 找到對應的哈希桶，將內存掛在對應哈希桶中my_free_list = free_list + FREELIST_INDEX(n);q->free_list_link = *my_free_list;*my_free_list = q;
}
- 向內存中補充空間
template <int inst>
char* __default_alloc_template<inst>::chunk_alloc(size_t size, int& nobjs)
{// 計算nobjs個size字節內存塊的總大小以及內存池中剩余空間總大小char * result;size_t total_bytes = size * nobjs;size_t bytes_left = end_free - start_free;// 如果內存池可以提供total_bytes字節，返回if (bytes_left >= total_bytes){result = start_free;start_free += total_bytes;return(result);}else if (bytes_left >= size){// nobjs塊無法提供，但是至少可以提供1塊size字節內存塊，提供后返回nobjs = bytes_left / size;total_bytes = size * nobjs;result = start_free;start_free += total_bytes;return(result);}else{// 內存池空間不足，連一塊小塊村內都不能提供// 向系統堆求助，往內存池中補充空間// 計算向內存中補充空間大小：本次空間總大小兩倍 + 向系統申請總大小/16size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);// 如果內存池有剩余空間(該空間一定是8的整數倍)，將該空間掛到對應哈希桶中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;}// 通過系統堆向內存池補充空間，如果補充成功，遞歸繼續分配start_free = (char *)malloc(bytes_to_get);if (0 == start_free){// 通過系統堆補充空間失敗，在哈希桶中找是否有沒有使用的較大的內存塊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;// 如果有，將該內存塊補充進內存池，遞歸繼續分配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作用是標記內存池空間的末尾start_free = (char *)malloc_alloc::allocate(bytes_to_get);}// 通過系統堆向內存池補充空間成功，更新信息并繼續分配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++中，用戶所需空間可能是任意類型的，有單個對象空間，有連續空間，每次讓用戶自己計算所需空間總大小不是很友好，因此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決定將空間申請釋放和對象的構造析構兩個過程分離開，因為有些對象的構造不需要調用析構函數，銷毀時不需要調用析構函數，將該過程分離開可以提高程序的性能：
// 歸還空間時，先先調用該函數將對象中資源清理掉
template <class T>
inline void destroy(T* pointer)
{pointer->~T();
}
// 空間申請好后調用該函數：利用placement-new完成對象的構造
template <class T1, class T2>
inline void construct(T1* p, const T2& value)
{new (p)T1(value);
}
