溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
1、STL中的空間配置器
在STL中，空間配置器分了2組，分別為一級空間配置器和二級空間配置器，但是它們都有自己各自運用的場合；一般說來，一級空間配置器一般分配的空間大于128B，二級空間配置器的分配空間為小于128B.
其中SGI 中的STL的空間配置器設計哲學如下：
(1)、向system heap要求申請空間
(2)、考慮多線程的狀態
(3)、考慮內存不足時的應變措施
(4)、考慮過多"小型區塊"可能造成的內存碎片問題
在剖析源碼時，為了將問題控制在一定的復雜度內，以下源碼皆排除多線程狀態的處理；
0：表示非多線程版本； inst : 表示不關注多線程的問題；
2、一級空間配置器
(1)、為內存不足做好準備 : (1)、拋出異常，也就是輸出一句話；(2)、調用自己設置的函數去處理(比如說是釋放一些空間，回收一些碎片的空間)；
一級空間配置器的本質：模仿實現了set_new_handler機制；
set_new_handler機制的實現：(1)、定義一個函數指針；(2)、定義一個函數；(3)、賦值比較；
(2)、抽取的代碼實現
#if 1
#include<iostream>
#include<new>
#include<malloc.h>
using namespace std;
//#define __THROW_BAD_ALLOC throw bad_alloc
#define __THROW_BAD_ALLOC cerr<<"Throw bad alloc, Out Of Memory."<<endl; exit(1) //定義異常,就是輸出一句話,并且結束程序.
#elif !defined (__THROW_BAD_ALLOC) //如果沒有定義這個異常,下面就定義
#include<iostream.h>
#define __THROW_BAD_ALLOC cerr<<"out of memory"<<endl; exit(1);
#endif
template<int inst>
class __malloc_alloc_template{
private:
static void* oom_malloc(size_t); //對申請空間失敗的處理函數
static void* oom_realloc(void *, size_t); //對擴展空間失敗處理的函數
static void(* __malloc_alloc_oom_handler)(); //定義一個函數指針
public:
static void* allocate(size_t n){ //分配空間
void *result = malloc(n);
if(0 == result)
result = oom_malloc(n); //分配空間失敗，調用oom_malloc()函數
return result; //將申請的空間的地址返回
}
static void deallocate(void *p, size_t){
free(p); //釋放空間
}
static void* reallocate(void *p, size_t, size_t new_sz){
void *result = realloc(p, new_sz); //擴展新空間;
if(0 == result) //擴展失敗
oom_realloc(p,new_sz); //調用擴展空間失敗的處理函數
return result;
}
public:
//set_new_handler(Out_Of_Memory);
static void(*set_malloc_handler(void(*f)()))(){ //這是一個指針函數,函數名稱:set_malloc_handler,參數:是一個函數指針,返回值:是一個函數指針;
void(*old)() = __malloc_alloc_oom_handler; //將原有空間的地址保存在old中;
__malloc_alloc_oom_handler = f; //將自己定義的函數地址給__malloc_alloc_oom_handler;
return old; //每次可以保存其上一次的地址.
}
};
template<int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0; //對定義的靜態函數指針初始化為0;
template<int inst>
void* __malloc_alloc_template<inst>::oom_malloc(size_t n){ //處理空間失敗的問題
void *result;
void(* my_malloc_handler)(); //定義一個函數指針;
for(;;){
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; //將地址返回;
}//那么，這個程序將會一直持續到空間分配成功才最終返回.
}
}
template<int inst>
void* __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n){
void(*my_malloc_handler)(); //函數指針
void *result;
for(;;){
my_malloc_handler = __malloc_alloc_oom_handler; //將這個給其賦值
if(0 == my_malloc_handler){ //外面沒有定義處理的函數
__THROW_BAD_ALLOC; //異常拋出,程序結束.
}
(*my_malloc_handler)(); //調用自己編寫的處理函數(一般都是回收空間之類的);
result = realloc(p, n); //再次擴展空間分配;
if(result){ //擴展成功,就返回
return result;
} //一直持續成功，知道擴展空間分配成功才返回;
}
}
typedef __malloc_alloc_template<0> malloc_alloc; //一級空間配置器:malloc_alloc;第一級空間配置器就是 : (1)、對malloc、free的簡單封裝；(2)、模擬C++的set_new_handler()已處理內存不足的情況；
總結 :
(1)、一級空間配置器其實就是先自己開辟空間，要是失敗了;
(2)、調用處理空間失敗的函數，在其內部，先看我們自己在外面有沒有寫針對這個的處理函數，要是沒寫，就是異常拋出，程序結束；
(3)、要是寫了，就調用我們自己寫的函數，在次分配空間，進入死循環中，直到空間分配成功，方可退出循環;
還要注意的是:static void(*set_malloc_handler(void(*f)()))()；這是一個指針函數;
3、二級空間配置器
(1)、當所分配的空間小于128B時，則以內存池去管理 ; 對小額區塊，自動將內存調至8的倍數,并維護16個自由鏈表,各自管理大小分別為: 8 16 24 32 40 48 56 ....128B的小額區塊;
(2)、剛開始所分配的內存空間，一半當做自由鏈表，一半當做內存池；當再次分配同樣大小的空間時，直接先從自由鏈表中分配；當再次分配其他大小空間時，先看內存池中有無空間,有的話，直接分配，掛載即可。
模型如下：
整個分配空間都是很節省化的:
其抽取代碼如下：
//二級空間配置器由自由鏈表和內存池組成;
enum {__ALIGN = 8}; //一塊鏈表8B
enum {__MAX_BYTES = 128}; //小于128B調用二級的
enum {__NFREELISTS = __MAX_BYTES / __ALIGN}; //一共分配16個自由鏈表,負責16種次分配能力.
template<bool threads, int inst> //不考慮多線程狀態;
class __default_alloc_template{
public:
static void* allocate(size_t n); //分配空間
static void deallocate(void *p, size_t n); //銷毀空間
static void* reallocate(void *p, size_t, size_t new_sz); //擴展空間
private:
static size_t ROUND_UP(size_t bytes){ //向上調整函數;
return (((bytes) + __ALIGN-1) & ~(__ALIGN-1)); //調為當前字節是8的整數倍.
}
private:
union obj{ //共用體
union obj * free_list_link; //自由鏈表的指向
char client_data[1];
};
private:
static obj* volatile free_list[__NFREELISTS]; //定義了一個指針數組;
static size_t FREELIST_INDEX(size_t bytes){ //求當前字節的自由鏈表的下標;
return ((bytes)+__ALIGN-1) / __ALIGN-1;
}
private:
static char *start_free; //開始空間的下標
static char *end_free; //結束空間的下標
static size_t heap_size; //堆空間大小
static void *refill(size_t n); //填充函數
static char* chunk_alloc(size_t size, int &nobjs); //
};
template<bool threads, int inst> //以下都是對靜態變量的初始化,都為0;
char* __default_alloc_template<threads, inst>::start_free = 0;
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::end_free = 0;
template<bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;
template<bool threads, int inst>
typename __default_alloc_template<threads, inst>::obj* volatile
__default_alloc_template<threads, inst>::free_list[__NFREELISTS] =
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
template<bool threads, int inst>
void* __default_alloc_template<threads, inst>::allocate(size_t n){ //分配空間的函數
obj * volatile *my_free_list;
obj *result;
if(n > __MAX_BYTES){ //分配空間的大小大于128B的話，就調用一級空間配置器
return malloc_alloc::allocate(n);
}
my_free_list = free_list + FREELIST_INDEX(n); //free_list是二維數組名稱,找往哪個鏈下掛；
result = *my_free_list; //取出其值,因為my_free_list是二階指針;
if(result == 0){ //沒有內存池空間;
void *r = refill(ROUND_UP(n)); //調用refill()函數
return r;
}
*my_free_list = result->free_list_link; //進行掛載連接;
return result;
}
template<bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n){ //沒有可用區塊時,就調用refill()函數;
int nobjs = 20;//就是要分20塊;
char *chunk = chunk_alloc(n, nobjs); //調用內存池函數;
obj * volatile *my_free_list;
obj *result;
obj *current_obj, *next_obj;
int i;
if(1 == nobjs){ //當分配到只有一塊空間時,直接返回.
return chunk;
}
my_free_list = free_list + FREELIST_INDEX(n); //找到對應的下標，進行連接的工作;
result = (obj*)chunk;
*my_free_list = next_obj = (obj*)(chunk+n);
for(i=1; ; ++i){
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj+n);
if(nobjs - 1 == i){ //進行連接工作;
current_obj->free_list_link = 0;
break;
}else{
current_obj->free_list_link = next_obj;
}
}
return result;
}
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int &nobjs){ //內存池函數
char *result; //關鍵要明白以下的各種情況;
size_t total_bytes = size * nobjs; //這里的size已經是上調過的字節;求取20*size個字節的大小
size_t bytes_left = end_free - start_free; //剛開始，遺留字節為0;
if(bytes_left >= total_bytes){ //不成立
result = start_free;
start_free += total_bytes;
return result;
}else if(bytes_left >= size){ //不成立
nobjs = bytes_left / size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return result;
}else{ //走的就是下面的這條路線
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4); //申請2倍的total_bytes；
if(bytes_left > 0){ //遺留字節數=0,所以這條語句不成立;
obj * volatile * my_free_list = free_list + FREELIST_INDEX(bytes_left);
((obj*)start_free)->free_list_link = *my_free_list;
*my_free_list = (obj *)start_free;
}
start_free = (char *)malloc(bytes_to_get); //申請空間;
if(0 == start_free){
int i;
obj * volatile *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 = 0;
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); //上去在此調用這個函數;
}
}nobjs = 20; 這個是經驗值，開辟空間留有余地，方便直接查找，以后就不用再次開辟空間了，提高了效率;
這個我們自己給不同的字節情況(小于128B的)，就會知道其中發生了什么;
SGI第二級空間配置器：
(1)、維護16個自由鏈表，分別有16種小型區塊的配置能力；如果內存不足，調用一級空間配置器(那里有處理程序);
(2)、如果申請空間的需求大于128B,就調用一級空間配置器.
總結:
(1)、二級空間配置器(最后山窮水盡)--->調用一級空間配置器---->(1)、拋出異常 (2)、調用自己編寫的處理函數；
STL內存配置思想：C++STL是兩級配置內存的，具體來說：第一級負責管理大塊內存，要保證有類似new-handler的機制；第二級負責管理小塊內存，為了更好的管理內存碎片，建立16個鏈表，每個鏈表“穿”著一塊一塊固定大小的內存，這16個鏈表（0至15）分別“穿”的內存是8、16、24…128倍數關系。需要內存時，從“合適”的鏈表取走(因為這里情況比較多，不能一一說道了)，如果“合適”的鏈表內存不夠用了，從內存池里拿，如果內存池不夠用了，從運行時heap里拿，如果heap也溢出了，就交給第一級配置器，因為它有set_new-handler機制。所以，當堆上的東西用完之后，的趕緊還回來。
4、完整代碼、測試代碼、測試結果
(1)、抽取出來的完整代碼
#if 1
#include<iostream>
#include<new>
#include<malloc.h>
using namespace std;
//#define __THROW_BAD_ALLOC throw bad_alloc
#define __THROW_BAD_ALLOC cerr<<"Throw bad alloc, Out Of Memory."<<endl; exit(1) //定義異常,就是輸出一句話,并且結束程序.
#elif !defined (__THROW_BAD_ALLOC) //如果沒有定義這個異常,下面就定義
#include<iostream.h>
#define __THROW_BAD_ALLOC cerr<<"out of memory"<<endl; exit(1);
#endif
template<int inst>
class __malloc_alloc_template{
private:
static void* oom_malloc(size_t); //對申請空間失敗的處理函數
static void* oom_realloc(void *, size_t); //對擴展空間失敗處理的函數
static void(* __malloc_alloc_oom_handler)(); //定義一個函數指針
public:
static void* allocate(size_t n){ //分配空間
void *result = malloc(n);
if(0 == result)
result = oom_malloc(n); //分配空間失敗，調用oom_malloc()函數
return result; //將申請的空間的地址返回
}
static void deallocate(void *p, size_t){
free(p); //釋放空間
}
static void* reallocate(void *p, size_t, size_t new_sz){
void *result = realloc(p, new_sz); //擴展新空間;
if(0 == result) //擴展失敗
oom_realloc(p,new_sz); //調用擴展空間失敗的處理函數
return result;
}
public:
//set_new_handler(Out_Of_Memory);
static void(*set_malloc_handler(void(*f)()))(){ //這是一個指針函數,函數名稱:set_malloc_handler,參數:是一個函數指針,返回值:是一個函數指針;
void(*old)() = __malloc_alloc_oom_handler; //將原有空間的地址保存在old中;
__malloc_alloc_oom_handler = f; //將自己定義的函數地址給__malloc_alloc_oom_handler;
return old; //每次可以保存其上一次的地址.
}
};
template<int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0; //對定義的靜態函數指針初始化為0;
template<int inst>
void* __malloc_alloc_template<inst>::oom_malloc(size_t n){ //處理空間失敗的問題
void *result;
void(* my_malloc_handler)(); //定義一個函數指針;
for(;;){
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; //將地址返回;
}//那么，這個程序將會一直持續到空間分配成功才最終返回.
}
}
template<int inst>
void* __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n){
void(*my_malloc_handler)(); //函數指針
void *result;
for(;;){
my_malloc_handler = __malloc_alloc_oom_handler; //將這個給其賦值
if(0 == my_malloc_handler){ //外面沒有定義處理的函數
__THROW_BAD_ALLOC; //異常拋出,程序結束.
}
(*my_malloc_handler)(); //調用自己編寫的處理函數(一般都是回收空間之類的);
result = realloc(p, n); //再次擴展空間分配;
if(result){ //擴展成功,就返回
return result;
} //一直持續成功，知道擴展空間分配成功才返回;
}
}
typedef __malloc_alloc_template<0> malloc_alloc; //一級空間配置器:malloc_alloc;
/////////////////////////////////////////////////////////////////////////////////////
//二級空間配置器由自由鏈表和內存池組成;
enum {__ALIGN = 8}; //一塊鏈表8B
enum {__MAX_BYTES = 128}; //小于128B調用二級的
enum {__NFREELISTS = __MAX_BYTES / __ALIGN}; //一共分配16個自由鏈表,負責16種次分配能力.
template<bool threads, int inst> //不考慮多線程狀態;
class __default_alloc_template{
public:
static void* allocate(size_t n); //分配空間
static void deallocate(void *p, size_t n); //銷毀空間
static void* reallocate(void *p, size_t, size_t new_sz); //擴展空間
private:
static size_t ROUND_UP(size_t bytes){ //向上調整函數;
return (((bytes) + __ALIGN-1) & ~(__ALIGN-1)); //調為當前字節是8的整數倍.
}
private:
union obj{ //共用體
union obj * free_list_link; //自由鏈表的指向
char client_data[1];
};
private:
static obj* volatile free_list[__NFREELISTS]; //定義了一個指針數組;
static size_t FREELIST_INDEX(size_t bytes){ //求當前字節的自由鏈表的下標;
return ((bytes)+__ALIGN-1) / __ALIGN-1;
}
private:
static char *start_free; //開始空間的下標
static char *end_free; //結束空間的下標
static size_t heap_size; //堆空間大小
static void *refill(size_t n); //填充函數
static char* chunk_alloc(size_t size, int &nobjs); //
};
template<bool threads, int inst> //以下都是對靜態變量的初始化,都為0;
char* __default_alloc_template<threads, inst>::start_free = 0;
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::end_free = 0;
template<bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;
template<bool threads, int inst>
typename __default_alloc_template<threads, inst>::obj* volatile
__default_alloc_template<threads, inst>::free_list[__NFREELISTS] =
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
template<bool threads, int inst>
void* __default_alloc_template<threads, inst>::allocate(size_t n){ //分配空間的函數
obj * volatile *my_free_list;
obj *result;
if(n > __MAX_BYTES){ //分配空間的大小大于128B的話，就調用一級空間配置器
return malloc_alloc::allocate(n);
}
my_free_list = free_list + FREELIST_INDEX(n); //free_list是二維數組名稱,找往哪個鏈下掛；
result = *my_free_list; //取出其值,因為my_free_list是二階指針;
if(result == 0){ //沒有內存池空間;
void *r = refill(ROUND_UP(n)); //調用refill()函數
return r;
}
*my_free_list = result->free_list_link; //進行掛載連接;
return result;
}
template<bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n){ //沒有可用區塊時,就調用refill()函數;
int nobjs = 20;//就是要分20塊;
char *chunk = chunk_alloc(n, nobjs); //調用內存池函數;
obj * volatile *my_free_list;
obj *result;
obj *current_obj, *next_obj;
int i;
if(1 == nobjs){ //當分配到只有一塊空間時,直接返回.
return chunk;
}
my_free_list = free_list + FREELIST_INDEX(n); //找到對應的下標，進行連接的工作;
result = (obj*)chunk;
*my_free_list = next_obj = (obj*)(chunk+n);
for(i=1; ; ++i){
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj+n);
if(nobjs - 1 == i){ //進行連接工作;
current_obj->free_list_link = 0;
break;
}else{
current_obj->free_list_link = next_obj;
}
}
return result;
}
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int &nobjs){ //內存池函數
char *result; //關鍵要明白以下的各種情況;
size_t total_bytes = size * nobjs; //這里的size已經是上調過的字節;求取20*size個字節的大小
size_t bytes_left = end_free - start_free; //剛開始，遺留字節為0;
if(bytes_left >= total_bytes){ //不成立
result = start_free;
start_free += total_bytes;
return result;
}else if(bytes_left >= size){ //不成立
nobjs = bytes_left / size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return result;
}else{ //走的就是下面的這條路線
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4); //申請2倍的total_bytes；
if(bytes_left > 0){ //遺留字節數=0,所以這條語句不成立;
obj * volatile * my_free_list = free_list + FREELIST_INDEX(bytes_left);
((obj*)start_free)->free_list_link = *my_free_list;
*my_free_list = (obj *)start_free;
}
start_free = (char *)malloc(bytes_to_get); //申請空間;
if(0 == start_free){
int i;
obj * volatile *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 = 0;
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); //上去在此調用這個函數;
}
}(2)、測試代碼
#include<iostream>
#include<stdlib.h>
#include"stl_alloc.h"
using namespace std;
int main(){
int *p = (int *)__default_alloc_template<0,0>::allocate(sizeof(int));
int *s = (int *)__default_alloc_template<0,0>::allocate(sizeof(int) * 4);
int *t = (int *)__default_alloc_template<0,0>::allocate(sizeof(int) * 80);
int *m = (int *)__default_alloc_template<0,0>::allocate(sizeof(double) * 10);
int *n = (int *)__default_alloc_template<0,0>::allocate(sizeof(int) * 100);
int *u = (int *)__default_alloc_template<0,0>::allocate(sizeof(int));
int *k = (int *)__default_alloc_template<0,0>::allocate(sizeof(int) *2);
return 0;
}
/*
void Out_Of_Memory(){
cout<<"Out Of Memory."<<endl;
exit(1);
}
int main(){
//__malloc_alloc_template<0>::set_malloc_handler(OMG);
//set_new_handler()
//int *p = (int*)malloc(sizeof(int)*10);
void (*pfun)() = __malloc_alloc_template<0>::set_malloc_handler(Out_Of_Memory);
int *p = (int*)__malloc_alloc_template<0>::allocate(sizeof(int) * 2073741824);
__malloc_alloc_template<0>::set_malloc_handler(pfun);
if(p == NULL)
{
cout<<"Error."<<endl;
exit(1);
}
cout<<"OK"<<endl;
return 0;
}
*/(3)、測試結果
5、STL中的不成文規定
__打頭的是內部函數
一般都是前插
指最后的下一個
fill_n() 系統函數，填充空間;
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
