首页 > 代码库 > 重温《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源码剖析》笔记 第二章