Allocator

一般而言，我们所习惯的C++内存配置操作和释放操作是这样的:

class Foo {}；
Foo* pf = new Foo； // 配置内存，然后构造对象
delete pf；	//将对象析构，然后释放内存

new 算式内含两阶段操作

调用 ::operator new 配置内存;
调用Foo::Foo()构造对象内容。

delete算式也内含两阶段操作:

调用Foo::〜Foo() 将对象析构；
调用operator delete 释放内存。

为了精密分工，STL allocator决定将这两阶段操作区分开来。

内存配置操作由alloc:allocate()负责，内存释放操作由alloc::deallocate()负责；对象构造操作由::construct ()负责，对象析构操作由::destroy()负责。

构造与析构

construct() 接受一个指针P和一个初值 value, 该函数的用途就是将初值设定到指针所指的空间上。

destroy() 有两个版本，第一版本接受一个指针，准备将该指针所指之物析构掉。这很简单，直接调用该对象的析构函数即可。第二版本接受first和last 两个迭代器），准备将[first, last)范围内的所有对象析构掉。

内存的配置与释放

考虑到小型区块所可能造成的内存破碎问题，SGI设计了双层级配置器.

第一级配置器

第一级配置器以malloc (), free(), realloc ()等C函数执行实际的内存配置、释放、重配置操作，并实现出类似C++new-handler的机制。是的，它不能直接运用C++new-handler机制，因为它并非使用：：operator new来配置内存。

所谓C++ new handler机制是，你可以要求系统在内存配置需求无法被满足时，调用一个你所指定的函数。换句话说，一旦 ::operator new 无法完成任务,在丢出std::bacLalloc异常状态之前，会先调用由客端指定的处理例程。该处理例程通常即被称为new-handier。

第二级配置器

SGI第二级配置器的做法是，如果区块够大，超过128 bytes时，就移交第一级配置器处理。当区块小于128bytes时，则以内存池（memorypool)管理:每次配置一大块内存，并维护对应之自由链表(free-list)下次若再有相同大小的内存需求，就直接从free-list中拨出。如果客端释还小额区块，就由配置器回收到free-list中

为了方便管理，SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数（例如客端要求30 bytes，就自动调整为32 bytes)，并维护16个free-list，各自管理大小分别为8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112,120, 128 bytes的小额区块。

free-list的节点结构如下：

union obj {
union obj * free_li st_link;
char client—data[1];	/*	The	client sees this. */
};

诸君或许会想，为了维护链表（lists)，每个节点需要额外的指针（指向下一个节点），这不又造成另一种额外负担吗？你的顾虑是对的，但早已有好的解决办法.

注意，上述obj所用的是union,由于 union 之故，从其第一字段观之,obj可被视为一个指针，指向相同形式的另一个obj.从其第二字段观之，obj可被视为一个指针，指向实际区块，

一物二用的结果是，不会为了维护链表所必须的指针而造成内存的另一种浪费。

空间配置函数allocate()

此函数首先判断区块大小，大于128 bytes就调用第一级配置器，小于128 bytes就检查对应的free-list加。如果free-list之内有可用的区块，就直接拿来用，如果没有可用区块，就将区块大小上调至8倍数边界，然后调用refill (),准备为free-list重新填充空间。

重新填充free-list

free-list填充空间需要从内存池获取,而从内存池中取空间给free-list使用,是chunk_alloc()的工作.

chunk_alloc()函数判断内存池的水量。如果水量充足，就直接调出20个区块返回给free-list。如果水量不足以提供20个区块，但还足够供应一个以上的区块，就拨出这不足20个区块的空间出去。如果内存池连一个区块空间都无法供应，对客端显然无法交待,此时便需利用 malloc() 从heap中配置内存，为内存池注入活水源头以应付需求。新水量的大小为需求量的两倍，再加上一个随着配置次数增加而愈来愈大的附加量。

假设程序一开始，客端就调用 chunk—alloc(32,20}，于是 malloc{) 配置40个32 bytes区块，其中第1个交出，另19个交给 free-list维护，余20个留给内存池。

接下来客端调用chunk_alloc(64,20)，此时free_list[7]空空如也，必须向内存池要求支持。内存池只够供应（32*20)/64=10个64 bytes区块，就把这10个区块返回，第1个交给客端，余9个由 free—list[7] 维护。此时内存池全空。

接下来再调用 chunk_alloc(96, 20)，此时 free— list[11]空空如也，必须向内存池要求支持，而内存池此时也是空的，于是以 malloc()配置40+n(附加量）个96 byte, 其中第1个交出，另19个交给free_list[11]维护，余20+n (附加量）个区块留给内存池…

万一山穷水尽，整个堆空间都不够了，malloc行动失败，chunk_alloc()就四处寻找有无“尚有未用区块，且区块够大”找到了就挖出一块交出，找不到就调用第一级配置器.

第一级配置器其实也是使用 malloc() 来配置内存，但它有out-of-memory处理机制 (类似new-handier机制），或许有机会释放其它的内存拿来此处使用。如果可以,就成功，否则发出bad_alloc异常。

空间释放函数deallocate()

deallocate() 该函数首先判断区块大小，大于128 bytes就调用第一级配置器，小于128 bytes就找出对应的free list，将区块回收。

空间配置器Allocator

文章目录