天天看點
傳回

Cpp || 空間配置器

文章目錄

      • 空間配置器
        • 一:需要空間配置器的原因
        • 二:SGI-STL空間配置器實作原理
        • 三:一級空間配置器
        • 四:二級空間配置器
          • 4.1:記憶體池
          • 4.2:SGI-STL中二級空間配置器設計
          • 4.3:申請空間
          • 4.4:填充記憶體塊
          • 4.5:向記憶體池中索要空間
          • 4.6:SGI-STL二級空間配置器之空間回收

空間配置器

  • 用途:空間配置器:為了各個容器高效的管理空間(空間的申請與回收)的,

一:需要空間配置器的原因

  • 前面在模拟實作vector、list、map、unordered_map等容器時,所需要的空間都是通過new申請的,雖然代碼可以正常運作,但是存在以下問題
  • 1.空間申請與釋放需要使用者自己管理,容易造成記憶體洩漏
  • 2.頻繁向系統申請小塊記憶體,影響程式運作效率
  • 3.頻繁向系統申請小塊記憶體,容易造成記憶體洩漏
  • 4.直接使用malloc與new進行申請,每塊空間有額外空間浪費
  • 5.申請空間失敗怎麼應對?
  • 6.代碼結構比較混亂
  • 7.未考慮線程安全問題

是以需要設計一塊高效的記憶體管理機制–>空間配置器

二:SGI-STL空間配置器實作原理

以上提到的幾點不足之處，最主要還是：頻繁向系統申請小塊記憶體造成的。那什麼才算是小塊記憶體？SGI-STL

以128作為小塊記憶體與大塊記憶體的分界線，将空間配置器其分為兩級結構，一級空間配置器處理大塊記憶體，二級空間配置器處理小塊記憶體。

三:一級空間配置器

  • 一級空間配置器原理非常簡單，直接對malloc與free進行了封裝，并增加了C++中set_new_handle思想。
  • 其中C++ new_handler機制是,你可以要求系統在記憶體配置需求無法滿足時,調用一個你所指定的函數,換句話說:一旦 ::operator new 無法完成任務,在丢出std::bad_alloc異常狀态之前,會調用由用戶端指定的處理例程,該處理例程通常既被稱為new_handler。new_handler解決了記憶體不足的做法有特定的模式,請參考《Effective C++》2e條款7 
template <int inst>
class __malloc_alloc_template
{
private:
static void *oom_malloc(size_t);
static void *oom_realloc(void *, size_t);
public:
 // 對malloc的封裝
static void * allocate(size_t n) {
 // 申請空間成功，直接傳回，失敗交由oom_malloc處理
 void *result = malloc(n);
 if (0 == result) 
 result = oom_malloc(n);
 
 return result; }
 // 對free的封裝
static void deallocate(void *p, size_t /* n */) {
 free(p);
}
 // 對realloc的封裝---該函數基本不用
static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz) {
 void * result = realloc(p, new_sz);
 if (0 == result) 
 result = oom_realloc(p, new_sz);
 return result; }
// 模拟set_new_handle
// 該函數的參數為函數指針，傳回值類型也為函數指針
// 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);
}
};
// 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);
 }
}
// 類似oom_malloc
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;

四:二級空間配置器

  • 二級空間配置器專門負責處理小于128位元組的小塊記憶體。如何才能提升小塊記憶體的申請與釋放的方式呢？SGI-STL采用了記憶體池的技術來提高申請空間的速度以及減少額外空間的浪費，采用哈希桶的方式來提高使用者擷取空間的速度與高效管理。
  • 第二層配置器的核心就是記憶體池
  • SGI-STL的記憶體池通過free_list數組來管理,數組中包含16個free list,每個free list結點大小依次為8,16,24以8的倍數遞增到128byte
  • 配置設定記憶體時(假定配置設定大小在128byte内),首先根據配置設定大小找到合适的free list, 如果該free list中沒有可用的結點,則調用refill()函數從記憶體池中取空間給該free list 用,然後傳回第一個結點的記憶體空間,并調整該free list;
  • refill預設取20個新節點(區塊),通過調用chunk_alloc(),然後根據所取的新結點的實際個數,調用相應的free list(大于1)
4.1:記憶體池
  • 記憶體池:先申請一塊比較大的記憶體塊做備用,當需要使用記憶體時,直接到記憶體池中去取,當池中空間不夠時,再向記憶體中去取,當使用者不用時,直接還回記憶體池即可.避免頻繁的向系統申請小塊記憶體所造成的效率低,記憶體碎片以及額外浪費的問題
    Cpp || 空間配置器
  • 類似與vector,使用指針來辨別記憶體池的起始位置和結束位置(有效空間包含在其中)
4.2:SGI-STL中二級空間配置器設計
  • SGI-STL中的二級空間配置器使用了記憶體池技術，但沒有采用連結清單的方式對使用者已經歸還的空間進行管理(因為使用者申請空間時在查找合适的小塊記憶體時效率比較低)，而是采用了哈希桶的方式進行管理。那是否需要128桶個空間來管理使用者已經歸還的記憶體塊呢？
  • 答案是不需要，因為使用者申請的空間基本都是4的整數倍，其他大小的空間幾乎很少用到。是以：SGI-STL将使用者申請的記憶體塊向上對齊到了8的整數倍
Cpp || 空間配置器
4.3:申請空間
  • 過程圖示
    Cpp || 空間配置器
// 函數功能：向空間配置器索要空間
// 參數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);
};
4.4:填充記憶體塊
  • 過程圖
Cpp || 空間配置器
// 函數功能：向哈希桶中補充空間
// 參數n：小塊記憶體位元組數
// 傳回值：首個小塊記憶體的首位址
template <int inst>
void* __default_alloc_template<inst>::refill(size_t n) {
 // 一次性向記憶體池索要20個n位元組的小塊記憶體
 int nobjs = 20;
 char * chunk = chunk_alloc(n, nobjs);
 
 obj ** 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);
}
4.5:向記憶體池中索要空間
  • 過程圖示
Cpp || 空間配置器
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
 {
 // 記憶體池空間不足，連一塊小塊村内都不能提供
 // 向系統堆求助，往記憶體池中補充空間
 // 計算向記憶體中補充空間大小：本次空間總大小兩倍 + 向系統申請總大小/16
 size_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;
 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));
 }
}
4.6:SGI-STL二級空間配置器之空間回收
  • 過程圖示
Cpp || 空間配置器
// 函數功能：使用者将空間歸還給空間配置器
// 參數：p空間首位址 n空間總大小
static void deallocate(void *p, size_t n) {
 obj *q = (obj *)p;
 obj ** my_free_list;
 // 如果空間不是小塊記憶體，交給一級空間配置器回收
 if (n > (size_t) __MAX_BYTES)
 {
 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; }
Cpp進階學習
上一篇: mac下flink叢集安裝
下一篇: G Data （歌德塔）