前言
根據之前的學習，C++的記憶體申請的基本操作就是： 調用::operator new()；釋放記憶體的操作就是：調用 ::operator delete()。而二者是通過malloc() 和 free() 實作的。是以SGI空間配置器就是使用malloc() 和 free() 來代替C++的記憶體操作實作的記憶體管理。
正文
1.空間配置器的要求
SGI 對于空間配置器的設計提出了以下幾點：
1.向 system heap 要求空間
2.考慮多線程狀态
3.考慮記憶體不足時的應變措施
4.考慮過多“小型區塊”可能造成的記憶體碎片問題
以下給出的代碼和問題的探讨皆排除多線程狀态。
2.SGI空間配置器的雙層設計
SGI空間配置器設計了兩層配置器，第一級配置器直接使用malloc() 和 free()來配置記憶體。第二級配置器分情況采取不同的政策：當需要申請的記憶體大于128位元組時，視之為足夠大，直接調用第一級配置器的接口；當需要申請的記憶體小于128位元組時，為了避免多餘的空間浪費（主要是cookie的空間），采用複雜的memory pool來管理記憶體。
一二級空間配置器的調用關系：
3.一級空間配置器
typedef void(*H)();
template<int inst> //一級空間配置器
class __malloc_alloc_template
{
private :
//用來處理記憶體不足時的情況
static void* oom_malloc(size_t); //oom:out of memory
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);
return result;
}
static void deallocate(void* p,size_t)
{
if (p)
free(p);
}
static void* reallocate(void* p, size_t, size_t new_sz)
{
void* result = realloc(p, new_sz);
if (0 == result)
result = oom_realloc(p, new_sz);
return result;
}
// 仿真C++的set_new_handler
static H set_malloc_handler(H f)
{
H old = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return old;
}
};
//template<int inst>
//void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
template<int inst>
H __malloc_alloc_template<inst>::__malloc_alloc_oom_handler = 0;
template<int inst>
void*__malloc_alloc_template<inst>::oom_malloc(size_t n)
{
H my_malloc_handler;
void* result;
while (1) //不斷嘗試釋放，配置
{
my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == __malloc_alloc_oom_handler) //沒有設定釋放記憶體回調函數直接抛出異常
{
std::cerr << "out of memory" << std::endl;
exit(1);
}
(*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)
{
H my_malloc_handler;
void* result;
while (1)
{
my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == __malloc_alloc_oom_handler)
{
std::cerr << "out of memory" << std::endl;
exit(1);
}
(*my_malloc_handler)();
result = realloc(p,n);
if (result)
return result;
}
}
typedef __malloc_alloc_template<0> malloc_alloc;
第一級空間配置器隻是對malloc() 和 free() 進行了一層封裝并且通過模拟C++中的 new_handler 機制來接解決記憶體不足的問題。
以allocate函數為例，會先調用malloc來直接配置記憶體，如果配置失敗調用oom_malloc，在oom_malloc中，如果有設定__malloc_alloc_oom_handler，則不斷循環調用該回調并配置記憶體直到成功，否則直接抛出異常。
set_malloc_handler函數與C++ 中的_set_new_handler函數功能一緻。
總體來說，第一級空間配置器就是對C++中的記憶體配置和釋放機制的淺封裝。
4.二級空間配置器
#define __ALIGN 8
#define __MAX_BYTES 128
#define __NFREELISTS __MAX_BYTES/__ALIGN
#define __OBJNUM 20
template<int inst>
class __default_alloc_template //二級空間配置器
{
private:
static size_t ROUND_UP(size_t bytes) //将bytes調至8的倍數
{
return ((bytes)+__ALIGN - 1) & ~(__ALIGN - 1);
}
struct obj //嵌入式指針
{
struct obj* free_list_link;
};
public:
static obj* free_list[__NFREELISTS]; //根據大小區分的空閑記憶體區塊
static size_t FREELIST_INDEX(size_t bytes) //根據位元組确定區塊索引
{
return ((bytes)+__ALIGN - 1)/(__ALIGN - 1);
}
static void* refill(size_t n);
static char* chunk_alloc(size_t size, int &nodjs);
static char* start_free; //記憶體池初始位置
static char* end_free; //結束位置
static size_t heap_size;
public:
static void* allocate(size_t n);
static void deallocate(void* p, size_t n);
//static void* reallocate(void* p, size_t old_sz, size_t new_sz);
};
typedef __default_alloc_template<0> alloc;
template<int inst>
char* __default_alloc_template<inst>::start_free = 0;
template<int inst>
char* __default_alloc_template<inst>::end_free = 0;
template<int inst>
size_t __default_alloc_template<inst>::heap_size = 0;
template<int inst> typename
__default_alloc_template<inst>::obj*
__default_alloc_template<inst>::free_list[__NFREELISTS]
= { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
二級空間配置器維護着16個連結清單，由一個靜态的指針數組來存儲。其中每一個元素都是一個連結清單的頭。每一個連結清單中挂着相應大小的記憶體塊若幹（數量不定，<=20，可以為空），并且每一次申請的空間必須滿足8位元組的倍數，不足的由 ROUND_UP函數調整到8位元組的倍數。
（一）allocate函數
template<int inst>
void* __default_alloc_template<inst>::allocate(size_t n) //申請記憶體
{
obj** my_free_list;
obj* result;
if (n > (size_t)__MAX_BYTES) //大于128調用一級空間配置器
{
return malloc_alloc::allocate(n);
}
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if (0 == result) //沒有可用的free list，使用refill函數填充
{
void* r = refill(ROUND_UP(n));
return r;
}
*my_free_list = result->free_list_link; //result 和 *my_free_list 此時指向同一塊記憶體
return (result);
}
二級空間配置器的allocate有兩種決策：當申請記憶體大于128位元組時，直接調用一級配置器的allocate；當小于128位元組的時候，找到相應大小位元組的連結清單頭（由FREELIST_INDEX算出目标元素與指針數組首位址的偏移量）。如果此時連結清單中由元素，直接傳回第一塊，并更新連結清單頭。否則調用refill函數填充連結清單後傳回第一塊。
（二）deallocate函數
template<int inst>
void __default_alloc_template<inst>::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;
}
my_free_list = free_list + FREELIST_INDEX(n);
q->free_list_link = *my_free_list;
*my_free_list = q;
}
同樣的，對于deallcoate函數，先判斷釋放記憶體的大小，如果大于128字就調用一級配置器的接口，否則将該記憶體塊歸還到相應的連結清單中，更新連結清單頭。
（三）refill函數
template<int inst>
void* __default_alloc_template<inst>::refill(size_t n)
{
int nobjs = __OBJNUM;
char* chunk = chunk_alloc(n, nobjs);
obj** my_free_list;
obj* result;
obj* current_obj;
obj* next_obj;
if (1 == nobjs) //隻獲得1塊，直接傳回，不向free_list 中新加節點
return chunk;
my_free_list = free_list + FREELIST_INDEX(n);
result = (obj*)chunk;
//讓my_free_list指向第二個節點（因為第一個節點要被傳回，不用添加進free_list）
*my_free_list = next_obj = (obj*)(chunk + n);
for (int i = 1;i<nobjs-1; i++)
{
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj + n);
current_obj->free_list_link = next_obj;
}
next_obj->free_list_link = 0;
return result;
}
先調用chunk_alloc函數從記憶體池中擷取一定數量記憶體塊（最大不超過__OBJNUM塊），擷取到的塊數由nobjs傳回，如果隻擷取到了一塊，直接将記憶體傳回給上一層，不用将之添加到連結清單中；若是多餘一塊，将剩餘的記憶體塊添加到連結清單中。
（四）chunk_alloc函數
template<int inst>
char* __default_alloc_template<inst>::chunk_alloc(size_t size, int& nobjs)
{
char* result;
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free; //記憶體池剩餘空間
if (bytes_left >= total_bytes) //剩餘空間足夠滿足全部需求
{
result = start_free;
start_free += total_bytes;
return result;
}
else if (bytes_left >= size) //剩餘空間不夠滿足全部需求，但是可以滿足一個或以上的區塊（不到20個）
{
nobjs = bytes_left / size;
total_bytes = nobjs * size;
result = start_free;
start_free += total_bytes;
return result;
}
else //剩餘空間一塊都滿足不了
{
//存在小的記憶體碎片，将之挂到相應大小的free_list上
//（因為每次都是以8的倍數拿取，是以可以在free_list中找到同樣大小的塊）
if (bytes_left > 0)
{
obj** my_free_list;
my_free_list = free_list + FREELIST_INDEX(bytes_left);
((obj*)start_free)->free_list_link = *my_free_list;
*my_free_list = (obj*)start_free;
}
//申請堆記憶體來填充記憶體池
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
start_free = (char*)malloc(bytes_to_get);
if (0 == start_free) //配置設定失敗
{
obj** my_free_list;
obj* p;
for (int i = size; i <= __MAX_BYTES; i += __ALIGN) //尋找比size大的區塊
{
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (p) //如果由空閑的free_list取出一塊給記憶體池
{
*my_free_list = p->free_list_link;
start_free = (char*)p;
end_free = start_free + i;
return chunk_alloc(size, nobjs); //遞歸調用，修正nobjs的值
}
}
//沒有拿到合适的區塊，轉而調用一級空間配置器
//嘗試使用out of memory 機制釋放一部分記憶體
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);
}
}
chunk_alloc函數是整個配置器中的難點和精髓部分。首先檢測記憶體池中剩餘空間是否滿足全部需求（__OBJNUM塊的記憶體），如果滿足直接把記憶體傳回給上一層，并更新記憶體池的剩餘量。如果不能滿足全部需求（大于等于1，小于__OBJNUM塊），但可以滿足一塊或者以上，就傳回可以傳回的最大塊數的記憶體。但是如果連一塊記憶體都滿足不了的情況，回先将記憶體池中剩餘小的區塊（此時可以視之為記憶體碎片）挂載到相應的連結清單上。然後用malloc申請堆記憶體來填充記憶體池，此時的申請的記憶體總量等于需求量的二倍，加上追加量，并調到8位元組的倍數。這時候如果malloc失敗的話，就在連結清單中找到一個比需求區塊大并且相差最小的連結清單，從中拿出一塊放回記憶體池後遞歸調用chunk_alloc來修正nobjs。但是若是出現最差的情況，所有的連結清單表中都沒有符合的空閑記憶體可以用時，就會調用一級配置器中的allocate來嘗試oom機制是否可以解決這個問題，就會出現上述一級配置器中成功傳回和抛出異常的結果。（如果__malloc_alloc_oom_handler設計的不好可能出現死循環，也就是不斷地待用回調，但還是配置設定不到空間）
4.一二級配置器統一封裝的接口
想要在STL标準的容器中使用需要滿足标準的接口，下面的封裝實作了配置器接口的轉調用。
template<class T,class Alloc>
class simple_alloc
{
public:
static T* allocate(size_t n) //申請多個時調用接口
{
return 0 == n ? n : (T*)Alloc::allocate(n * sizeof(T));
}
static T* allocate(void) //申請一個時調用接口
{
return (T*)Alloc::allocate(sizeof(T));
}
static void deallocate(T* p, size_t n) //釋放多個時調用接口
{
if (0 != n)
Alloc::deallocate(p, n * sizeof(T));
}
static void deallocate(T* p) //釋放一個時調用接口
{
Alloc::deallocate(p);
}
};
5.測試
#include<stdlib.h>
#include<iostream>
namespace wlj
{
typedef void(*H)();
//封裝的統一接口
template<class T,class Alloc>
class simple_alloc
{
public:
static T* allocate(size_t n) //申請多個時調用接口
{
return 0 == n ? n : (T*)Alloc::allocate(n * sizeof(T));
}
static T* allocate(void) //申請一個時調用接口
{
return (T*)Alloc::allocate(sizeof(T));
}
static void deallocate(T* p, size_t n) //釋放多個時調用接口
{
if (0 != n)
Alloc::deallocate(p, n * sizeof(T));
}
static void deallocate(T* p) //釋放一個時調用接口
{
Alloc::deallocate(p);
}
};
//==================================================================================================
template<int inst> //一級空間配置器
class __malloc_alloc_template
{
private :
//用來處理記憶體不足時的情況
static void* oom_malloc(size_t); //oom:out of memory
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);
return result;
}
static void deallocate(void* p,size_t)
{
if (p)
free(p);
}
static void* reallocate(void* p, size_t, size_t new_sz)
{
void* result = realloc(p, new_sz);
if (0 == result)
result = oom_realloc(p, new_sz);
return result;
}
// 仿真C++的set_new_handler
static H set_malloc_handler(H f)
{
H old = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return old;
}
};
//template<int inst>
//void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
template<int inst>
H __malloc_alloc_template<inst>::__malloc_alloc_oom_handler = 0;
template<int inst>
void*__malloc_alloc_template<inst>::oom_malloc(size_t n)
{
H my_malloc_handler;
void* result;
while (1) //不斷嘗試釋放，配置
{
my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == __malloc_alloc_oom_handler) //沒有設定釋放記憶體回調函數直接抛出異常
{
std::cerr << "out of memory" << std::endl;
exit(1);
}
(*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)
{
H my_malloc_handler;
void* result;
while (1)
{
my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == __malloc_alloc_oom_handler)
{
std::cerr << "out of memory" << std::endl;
exit(1);
}
(*my_malloc_handler)();
result = realloc(p,n);
if (result)
return result;
}
}
typedef __malloc_alloc_template<0> malloc_alloc;
//====================================================================================
#define __ALIGN 8
#define __MAX_BYTES 128
#define __NFREELISTS __MAX_BYTES/__ALIGN
#define __OBJNUM 20
template<int inst>
class __default_alloc_template //二級空間配置器
{
private:
static size_t ROUND_UP(size_t bytes) //将bytes調至8的倍數
{
return ((bytes)+__ALIGN - 1) & ~(__ALIGN - 1);
}
struct obj //嵌入式指針
{
struct obj* free_list_link;
};
public:static obj* free_list[__NFREELISTS]; //根據大小區分的空閑記憶體區塊
static size_t FREELIST_INDEX(size_t bytes) //根據位元組确定區塊索引
{
return ((bytes)+__ALIGN - 1)/(__ALIGN - 1);
}
static void* refill(size_t n);
static char* chunk_alloc(size_t size, int &nodjs);
static char* start_free; //記憶體池初始位置
static char* end_free; //結束位置
static size_t heap_size;
public:
static void* allocate(size_t n);
static void deallocate(void* p, size_t n);
//static void* reallocate(void* p, size_t old_sz, size_t new_sz);
};
typedef __default_alloc_template<0> alloc;
template<int inst>
char* __default_alloc_template<inst>::start_free = 0;
template<int inst>
char* __default_alloc_template<inst>::end_free = 0;
template<int inst>
size_t __default_alloc_template<inst>::heap_size = 0;
template<int inst> typename
__default_alloc_template<inst>::obj*
__default_alloc_template<inst>::free_list[__NFREELISTS]
= { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
template<int inst>
void* __default_alloc_template<inst>::allocate(size_t n) //申請記憶體
{
obj** my_free_list;
obj* result;
if (n > (size_t)__MAX_BYTES) //大于128調用一級空間配置器
{
return malloc_alloc::allocate(n);
}
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if (0 == result) //沒有可用的free list，使用refill函數填充
{
void* r = refill(ROUND_UP(n));
return r;
}
*my_free_list = result->free_list_link; //result 和 *my_free_list 此時指向同一塊記憶體
return (result);
}
template<int inst>
void __default_alloc_template<inst>::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;
}
my_free_list = free_list + FREELIST_INDEX(n);
q->free_list_link = *my_free_list;
*my_free_list = q;
}
template<int inst>
void* __default_alloc_template<inst>::refill(size_t n)
{
int nobjs = __OBJNUM;
char* chunk = chunk_alloc(n, nobjs);
obj** my_free_list;
obj* result;
obj* current_obj;
obj* next_obj;
if (1 == nobjs) //隻獲得1塊，直接傳回，不向free_list 中新加節點
return chunk;
my_free_list = free_list + FREELIST_INDEX(n);
result = (obj*)chunk;
//讓my_free_list指向第二個節點（因為第一個節點要被傳回，不用添加進free_list）
*my_free_list = next_obj = (obj*)(chunk + n);
for (int i = 1;i<nobjs-1; i++)
{
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj + n);
current_obj->free_list_link = next_obj;
}
next_obj->free_list_link = 0;
return result;
}
template<int inst>
char* __default_alloc_template<inst>::chunk_alloc(size_t size, int& nobjs)
{
char* result;
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free; //記憶體池剩餘空間
if (bytes_left >= total_bytes) //剩餘空間足夠滿足全部需求
{
result = start_free;
start_free += total_bytes;
return result;
}
else if (bytes_left >= size) //剩餘空間不夠滿足全部需求，但是可以滿足一個或以上的區塊（不到20個）
{
nobjs = bytes_left / size;
total_bytes = nobjs * size;
result = start_free;
start_free += total_bytes;
return result;
}
else //剩餘空間一塊都滿足不了
{
//存在小的記憶體碎片，将之挂到相應大小的free_list上
//（因為每次都是以8的倍數拿取，是以可以在free_list中找到同樣大小的塊）
if (bytes_left > 0)
{
obj** my_free_list;
my_free_list = free_list + FREELIST_INDEX(bytes_left);
((obj*)start_free)->free_list_link = *my_free_list;
*my_free_list = (obj*)start_free;
}
//申請堆記憶體來填充記憶體池
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
start_free = (char*)malloc(bytes_to_get);
if (0 == start_free) //配置設定失敗
{
obj** my_free_list;
obj* p;
for (int i = size; i <= __MAX_BYTES; i += __ALIGN) //尋找比size大的區塊
{
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (p) //如果由空閑的free_list取出一塊給記憶體池
{
*my_free_list = p->free_list_link;
start_free = (char*)p;
end_free = start_free + i;
return chunk_alloc(size, nobjs); //遞歸調用，修正nobjs的值
}
}
//沒有拿到合适的區塊，轉而調用一級空間配置器
//嘗試使用out of memory 機制釋放一部分記憶體
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);
}
}
}
template<class T,class Alloc = wlj::alloc>
class A
{
protected:
typedef wlj::simple_alloc<T, Alloc> data_allocator;
public:
T* get_instance(T n)
{
T* result = data_allocator::allocate();
*result = n;
return result;
}
};
int main()
{
A<int>a;
int* val = a.get_instance(10);
std::cout << *val << std::endl;
}
整體的測試一下。
6. 總結與思考
1.采用二層配置的機制，在不同記憶體需求的情況下采取不同的政策。造成記憶體浪費的主要原因是由于作業系統需要通過cookie來管理配置設定出去的記憶體，用malloc每次配置設定記憶體都會額外的有8位元組的開銷用于存放cookie，相較于大的區塊，8位元組所占的比例很小，記憶體的浪費可以接受，但是對于大量的小區塊，cookie的開銷就顯得格外龐大。能過通過記憶體池的方式管理記憶體的客觀條件就是我們在釋放記憶體時不需要通路cookie就已經知道了此次需要釋放的記憶體大小，也就無需cookie，是以對于所有的小區塊進行了調整，讓其滿足于8位元組的倍數，在釋放時通過簡單的計算就可以直接定位到相應的連結清單并歸還。
2.在處理記憶體碎片問題上，直接将目前的碎片挂在到相應連結清單中去。
3.在chunk_alloc 無法 malloc 到記憶體時，隻是找尋比需求記憶體大的連結清單，就會出現一種情況：大的連結清單都沒有空閑的記憶體，但是比之小的連結清單其實還有很多記憶體，引出一個思考：小的區塊是不是也可以用呢？
答案是很難實作，因為連結清單的區塊與區塊之間并不一定是真正連續的，即使多塊總和滿足需求，但是不連續是沒用的。
4.在chunk_alloc 調用 malloc 時隻以bytes_to_get為大小調用了一次，沒有再次嘗試改變bytes_to_get（将之變小）後調用malloc，其實這樣的方式也是解決的一種辦法，但是SGI空間配置器中并沒有進行這樣的設計，原因是：對于多程序的系統來說，如果某一個程序将所有能用的記憶體都占用，對于其他程序是災難性的，避免竭澤而漁是一種很睿智的舉動。
![C語言第四章自述2第四章 選擇結構程式設計[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)