STL中的内存管理机制(原)

    前段时间看了一下侯捷先生《STL源码剖析》空间配置器(allocator)。知道了STL进行空间分配的时候采用的策略。现在总结一下：

    SGI STL的每一个容器都已经指定了缺省的空间配置器为alloc。下面来分析一下这个缺省的空间配置器。

alloc空间分配的策略

    考虑到小型区块可能造成的内存的碎片的问题，SGI设计了双层的配置器，第一层的配置器直接使用的是malloc()和free(),第二层配置器则视情况采用不同的策略。当配置区块超过128字节(Bytes)的时候，视为足够大，调用第一级的配置器；当相应的配置区块小于128bytes时视为过小，为了减少内存碎片，采用相应的Memory pool的方式。

memory pool的管理方式：

(1)free-list:一个类似单链表结构的数据结构，链表中的每一个小的区块都是没有正在被用户使用的(正在使用的将会断开和free-list的连接)。

(A)当用户向系统提出使用的需求(M个区块的内存)的时候，系统从free-list中未被使用的区块的得到M个区块的内存，交给用户，并将其断开和区块的连接

(B)当用户向系统归还(N个区块的内存)的时候，系统将这N个区块连接到相应的free-list上。

(2)为了管理上的方便，SGI第二层配置器会主动的将任何的小额的区块的内存需求上调为8的倍数并维护16个free-lists，各自管理大小分别8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128bytes的小额区块。