STL:空间配置器

为了解决内存碎片的问题,设计了双层级配置器:

第一级直接使用malloc和free配置与释放空间。

第二级采取两种模式:若请求配置区块大于128bytes,则使用第一级配置器的方式;若小于等于128bytes,为了减少内存碎片,使用内存池的方式。

根据_USE_MALLOC定义决定是采取第一级配置器还是第二级配置器。

因为第二级配置器实际上包括了第一级配置器的内容,因此下面以第二级配置器进行分析:

在请求n个块的内存时,首先转入到一个接口类simple_alloc,simple_allco中有只有四个静态函数,前两个为配置内存,后两个为释放内存,无论第一级配置器还是第二级配置器,他们都使用这个模板接口类进行接口调用,simple_alloc通过它的模板的第二个参数class Alloc来决定它使用哪一级内存配置器的版本。

先是大内存块的情况:

此时相当于使用第一级配置器的方式配置内存
请求n个块的内存时,直接用malloc申请n*sizeof(T)个字节的方式,T为每个块的数据类型。当申请失败返回NULL时,转而使用“内存不足处理例程”,处理后循环再度申请。

然后是小内存块的情况:
是小于128bytes,的情况。此时,第二级配置器维护16个空闲块链表,它们各自管理不同大小的小额区块,且区块值为8的倍数。8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128.

每个空闲块链表中维护着若干个相同大小的内存块,彼此间以链表的形式相连。

当通过simple_alloc调用申请内存的接口函数时,接口allocate首先判断区块大小,如果sizeof(T)大于128,转头调用第一级配置器,小于128则使用第二级。在小于128bytes时,首先检查是否在空闲块链表中有合适的区块,如果有,调拨n个出去给与使用。如果没有,则需要调用refill为对应大小的这个空闲块链表填充一些空闲块,这些空闲块来自于内存池。

关于refill:

调用refill为对应8倍数大小的空闲块链表上填充内存块,新的空间来自于内存池。默认读取20个内存区块。

内存池(memory pool)技术:

在内存池中申请内存时,根据内存池大小分为不同情况:

1).内存池十分充裕:此时申请内存,返回给refill(),中,经由refill将这些内存切分为n个块并以链表的形式串起来后返回给第二级配置器。

2).内存池不能满足需求,但能供应一个以上的区块:将剩余的能供的块尽量都供出去给refill()。

3).内存池连一个块都供不起了:首先在空闲块链表中,找一些空闲的,且较大的内存块,看看能不能满足要求。然后从堆中申请空间来补充内存池。如果还不行只能抛出异常了。

空间释放:

空间释放相对简单,如果块大小大于128bytes,则以第一级配置器的方式释放空间,直接free()掉。

如果小于128bytes,则以第二级配置器的方式释放空间,寻找对应空闲块的小的空闲块链表,将区块回收入free list.

原文地址:https://www.cnblogs.com/lxy-xf/p/11061039.html