我們在之前的文章學(xué)習(xí)了編寫malloc_allocator膝但，它是一個借助malloc分配內(nèi)存的分配器冲九，并且實現(xiàn)了在C++11標準中的接口。同時malloc_allocator可以幫助我們實現(xiàn)另一個分配器free_list_allocator跟束。
free_list_allocator是我們整個項目真正要使用的分配器莺奸。在說明具體的代碼之前，先來說說為什么要用分配器而不直接使用 new 與 delete 進行內(nèi)存的分配與釋放冀宴。如果有學(xué)習(xí)過操作系統(tǒng)的相關(guān)知識的話應(yīng)該有所了解: 頻繁的進行內(nèi)存申請時將產(chǎn)生大量的內(nèi)存碎片且降低性能灭贷。
舉個例子， 假設(shè)我們有10個單位的連續(xù)內(nèi)存區(qū)域略贮，范圍 0 - 9甚疟。我們首先申請 4 個單位的空間， 那么將分配區(qū)域 0 - 3逃延。然后我們再申請 4 單位內(nèi)存览妖， 分配區(qū)域 4 - 7。現(xiàn)在我們只有8 - 9的位置是空閑的揽祥， 然而如果以后申請的內(nèi)存都大于 2 個單位, 那么只能從別的內(nèi)存段分配內(nèi)存讽膏，區(qū)域 8 - 9永遠用不上了，成為碎片拄丰。
為了避免碎片的產(chǎn)生府树，我們才使用分配器定義容器的分配策略。那么分配器采用什么方法避免內(nèi)存碎片的產(chǎn)生呢料按？malloc_alloctor雖說是分配器奄侠，但它只是簡單的封裝了malloc()函數(shù)進行內(nèi)存分配而已.。 malloc()對偶發(fā)的大量內(nèi)存分配做了優(yōu)化站绪，所以此時malloc_alloctor的效率良好。然而在需要頻繁分配少量內(nèi)存的情況下效率低下丽柿，且容易產(chǎn)生內(nèi)存碎片恢准。
有鑒于此，在這一情況下甫题，人們常使用基于內(nèi)存池的分配器來解決頻繁少量分配問題馁筐。與默認的“按需分配”方式不同，在使用基于內(nèi)存池的分配器時坠非，程序會預(yù)先為之分配大塊內(nèi)存（即“內(nèi)存池”）敏沉，而后在需要分配內(nèi)存時，自定義分配器只需向請求方返回一個指向池內(nèi)內(nèi)存的指針即可；而在對象析構(gòu)時盟迟，并不需實際解除分配內(nèi)存秋泳，而是延遲到內(nèi)存池的生命周期完結(jié)時才真正解除分配。這樣不僅能減少內(nèi)存碎片的產(chǎn)生也避免了對系統(tǒng)頻繁的內(nèi)存申請攒菠。
我們要實現(xiàn)free_list_allocator正是此類分配器迫皱。free_list_allocator的整體思想是: 如果要分配的內(nèi)存大于 128 bytes（即分配大量內(nèi)存) ，就交給malloc_allocator處理辖众。否則由 memory pool(內(nèi)存池) 負責(zé)分配與回收卓起。
我們先來了解free_list_allocator的聲明:
template<typename T>
class free_list_allocator
{
private:
static const std::size_t ALIGN = 8;
static const std::size_t MAX_BLOCK_SIZE = 128;
static const std::size_t FREE_LIST_NUM = MAX_BLOCK_SIZE / ALIGN;
struct obj
{
obj *free_list_link;
};
static obj *free_list[FREE_LIST_NUM];
//內(nèi)存池起始位置
static char *start_pool;
//內(nèi)存池結(jié)束位置
static char *end_pool;
static std::size_t heap_size;
//將byte上調(diào)至8的倍數(shù)
static std::size_t round_up(std::size_t byte)
{
return ((byte) + ALIGN - 1) & ~(ALIGN - 1);
}
//由所需內(nèi)存大小決定free_list的索引
static std::size_t free_list_index(std::size_t byte)
{
return byte / (ALIGN + 1);
}
//為free_list加入新的塊
static T *refill(std::size_t block_size);
//分配 num 個 block_size 的空間
static char *chunk_alloc(std::size_t block_size, std::size_t& num);
public:
typedef T value_type;
free_list_allocator() {}
template<typename U>
free_list_allocator(const free_list_allocator<U>&) {}
static T *allocate(std::size_t num);
static void deallocate(T *p, std::size_t num);
};
template<typename T>
typename free_list_allocator<T>::obj *
free_list_allocator<T>::free_list[FREE_LIST_NUM] = {
0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0
};
template<typename T>
char *free_list_allocator<T>::start_pool = nullptr;
template<typename T>
char *free_list_allocator<T>::end_pool = nullptr;
template<typename T>
std::size_t free_list_allocator<T>::heap_size = 0;
free_list_allocator的核心有兩部分： free_list 與 memory pool， free_list 從 memory pool 中獲取空間并添加內(nèi)存塊凹炸。那么所謂的free_list到底是什么戏阅？
struct obj
{
obj *free_list_link;
};
static obj *free_list[FREE_LIST_NUM];
free_list 被聲明為一個大小為 FREE_LIST_NUM 的數(shù)組， 且數(shù)組元素為一個指向 struct obj 的指針啤它。實際上每個 free_list 的元素分別指向區(qū)塊大小為 8, 16, 24, 32, 40, 48 ..... 120, 128 的鏈表奕筐。
上圖只顯示了8個free_list（實際有16個）。按照之前所說蚕键，3號free_list 指向大小為 32 bytes 的內(nèi)存塊救欧。其中每個內(nèi)存塊的開始部分儲存一個 obj 結(jié)構(gòu)，每個 obj 都有一個指向下一個內(nèi)存塊的指針（即 free_list_link）锣光。每當用戶需要申請內(nèi)存時笆怠， free_list_allocator 便從free_list中找到相應(yīng)大小的塊并且以返回內(nèi)存塊首地址的方式分配出去（即 obj 的地址）。
再了解了 free_list_allocator 的基本原理后誊爹，我們終于能看看具體實現(xiàn)了蹬刷。
- free_list_index(std::size_t byte)
//由所需內(nèi)存大小決定free_list的索引
static std::size_t free_list_index(std::size_t byte)
{
return byte / (ALIGN + 1);
}
free_list_index 用來查找目標 free_list 的索引。比如需要 20 字節(jié)的內(nèi)存時我們應(yīng)該去 free_list[ 2 ] 中取得內(nèi)存塊频丘。
- allocate(std::size_t num)
template<typename T>
T *free_list_allocator<T>::allocate(std::size_t num)
{
if (num * sizeof(T) > MAX_BLOCK_SIZE) {
return malloc_allocator<T>::allocate(num);
}
obj *result;
auto target_free_list = free_list + free_list_index(num * sizeof(T));
result = *target_free_list;
if (result == nullptr) {
return refill(round_up(num * sizeof(T)));
}
//將free_list內(nèi)的元素指向第2個內(nèi)存塊
*target_free_list = result->free_list_link;
return reinterpret_cast<T*>(result);
}
同樣办成， allocate(num) 負責(zé)分配 num 個元素的內(nèi)存。 它首先計算所需總內(nèi)存是否大于最大塊的大新（128 bytes）迂卢，如果是的話就調(diào)用 malloc_allocator<T>::allocate 分配內(nèi)存。想想之前提過的桐汤， malloc 適合進行大量內(nèi)存的分配而克。然后借助 free_list_index 找到具有合適大小的塊的 free_list。
接著對target_free_list解除引用獲取第一個內(nèi)存塊的地址怔毛。如果 result == nullptr, 則說明此 free_list 為空员萍，沒有指向的內(nèi)存塊。此時我們需要調(diào)用 refill() 重新為這個 free_list 添加內(nèi)存塊拣度。（refill 的具體實現(xiàn)要留到下次了）
如果我們成功獲取第一個內(nèi)存塊的地址話碎绎， 我們還需要將 free_list 的指針重新設(shè)置為第二個內(nèi)存塊的地址（這個時候第二個內(nèi)存塊就變成第一個了）螃壤。最后再類型轉(zhuǎn)換返回結(jié)果就行了。
- deallocate(T *p, std::size_t num)
template<typename T>
void free_list_allocator<T>::deallocate(T *p, std::size_t num)
{
/*
p為需要回收的內(nèi)存區(qū)域的首指針筋帖，num代表區(qū)域內(nèi)元素的個數(shù)
*/
std::size_t size = num * sizeof(T);
if (size > MAX_BLOCK_SIZE) {
malloc_allocator<T>::deallocate(p, num);
return;
}
//被回收的內(nèi)存將被加入target_free_list指向的鏈表
auto target_free_list = free_list + free_list_index(size);
obj *target_block = reinterpret_cast<obj*>(p);
target_block->free_list_link = *target_free_list;
*target_free_list = target_block;
}
deallocate 的思想與 allocate 對應(yīng)：allocate 是獲取第一個內(nèi)存塊奸晴，將 free_list 指向第二個內(nèi)存塊。而 deallocate 把需要回收的內(nèi)存塊指向當前第一個內(nèi)存塊幕随，將free_list 指向這個被回收的塊蚁滋。
我們現(xiàn)在已經(jīng)可以使用 allocate 與 deallocate 分配釋放內(nèi)存，但還有 refill(）和 chunk_alloc() 沒有實現(xiàn)赘淮。限于文章的篇幅辕录，那就只能等到下次了。再見~
下一篇： STL in C++11 (Allocator 5)
最后附上本篇文章的代碼地址：free_list_allocator.h
以及github地址：https://github.com/Puppas/STL-in-Cpp11
