首页 > 代码库 > 重温《STL源码剖析》笔记 第二章

重温《STL源码剖析》笔记 第二章

第二章:空间配置器 allocator

  SGI特殊的空间配置器,std::alloc

  SGI是以malloc()和free()完成内存的配置与释放。

  SGI设计了双层级配置器:

      第一级配置器直接使用malloc()和free();  _malloc_alloc_template

      第二级配置器则视情况采用不用的策略: _default_alloc_template

        当配置区块超过128bytes时,视之为“足够大”,便调用第一级配置器;

        当配置区块小于128bytes时,视之为“过小”,为了降低额外负担,便采

        用复杂的memory pool 整理方式,而不再求助于第一级配置器。

  SGI包装的接口:simple_alloc

  

1 template<class T, class Alloc> 2 class simp_alloc { 3 public: 4     static T *allocate(size_t n) { 5         return 0 ==n ? 0 : (T*)Alloc:: allocate(n * sizeof(T)); 6     } 7     static T *allocate(void) { 8         return (T*)Alloc::allocate(n * sizeof(T)); 9     }10     static void deallocate(T *p, size_t n) {11         if(0 !=n) Alloc::deallocate(p, n* sizeof(T));12     }13 static T *deallocate(T *p) {14         Alloc::deallocate(p * sizeof(T));15     }    16 }17 18 template<class T, class Alloc = alloc) 19 class vector {20     typedef simp_alloc<value_type, Alloc> data_allocator;    21     void deallocate() {22     if(...)23         data_allocator::deallocate(start,end_of_storage - start);24     }25     ...26 }

 

   SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数(例如客户端要求 30bytes,

  就自动调整为32bytes),并维护16个free-lists,各自管理大小分别为8, 16, 24,32, 40, 48, 56,

  64,72, 80, 88, 96, 104, 112, 120, 128的小额区块。

  freelist的节点结构如下:

union obj {    union obj* free_list_link;    char client_data[1];};

 

  重新填充free lists .当发现free list 中没有可用区块时,就调用refill(),准备为free list 重新填充空间。

  新的空间将取自内存池(经由chunk_alloc()完成)。缺省取得20个新节点(新区块),但万一内存池

  空间不足,获得的节点数(区块数)可能小于20。

  

  分配策略:

    假设程序一开始,客户端就调用chunk_alloc(32,20),于是malloc()配置40个32bytes区块,其中第

    一个交出(供使用,因为有请求),另19个交给free list[3]维护,余20个留给内存池。接下来客户

    端调用chunk_alloc(64,20)此时free_list[7]空空如也,必须向内存池要求支持。内存池只够供应

    (32*20)/64 =10个64bytes区块,就把这10个区块返回,第一个交给客户端,余9个由free_list[11]

    维护。此时内存池全空。接下来再调用chunk_alloc(96,20),此时free_list[11]空空如也,必须向内存

    池要求支持,而内存池也是空的,于是以malloc()配置 40+n(附加量)个96bytes区块,其中第一个

    交出,另19个交给free_list[11]维护,余20+你(附加量)个区块留给内存池。

  万一山穷水尽,整个system heap空间都不够了,malloc()将会行动失败,chunk_alloc()就四处寻找有无

  “尚有未用区块,且区块够大”之free lists.找到就交出,找不到就调用第一级配置器。第一级配置器也是使用

  的malloc()来配置内存,但是他有out-of-memory处理机制。或许会有机会释放别地的内存已使用,否则发

  出bad_alloc异常。

 

重温《STL源码剖析》笔记 第二章