本文共 5027 字，大约阅读时间需要 16 分钟。

尝试把自己对内存池的理解写出来；

alloc 是STL管理内存的一种方式，属于一种策略，是对malloc的一种优化。

内存池是一个非常基础也非常关键的底层库，一般大型框架自己都带有一个内存池库，如STL、MFC。即使在目前内存比较便宜的今天，内存资源也是最宝贵的系统资源之一，设计一个优秀的内存池对提高系统的效率和稳定性都非常有帮助，尤其是设计专门针对小内存对象的分配器非常重要，因为这样对象分配和释放都非常频繁，只用简单的malloc和free来处理非常影响效率，不是一个优秀的设计。

空间分配是STL的基础，为了更好的减小空间碎片(并不可避免，由于直接调用malloc可能会因为对齐等原因造成申请的内存较大于使用的)和提高效率(调用较小空间时，可直接从内存池中配置而不用使用malloc)，STL的配置流程为：

以vector为例：

注：vector配置时如果初始化为vector<int>v1(10,0)则意味着申请十个类型为int的空间

申请为40bytes，由于是8的倍数，不用补齐。

补齐函数为BOUND_UP(size_t bytes){return （(bytes+7)&~7）;}

注: 通过malloc分配的地址不连续：32位中需要8bytes来对齐(已验证)

由于初始内存池空间为0，首先需要构造内存池，通过malloc申请。

关于STL中内存池的流程理解：

以vector为例，首先调用40bytes配置内存池，40对应index=4，nobjs=20，即需要申请800bytes大小的空间，分配给free_list[4]，此时会从堆空间申请1600bytes大小的空间，剩下的800bytes用于下次申请是配置空间。

默认nobjs=20;

工作流程：1. 外部调用allocate向内存池申请内存

          2. allocate通过内存对齐方式在free_list找到合适的内存块链头表

          3. 判断链表头是否为NULL，为NULL则表示没有此规格空闲的内存，如果不为NULL，则返回那块内存地址，并将此块内存地址移除它对应的链表。

          4. 如果为NULL,则调用refill在freelist上挂载20个此规格的内存空间(形成链表用union实现，省内存),保证了此规格的内存空间下次请求时够用。

          5. refill的内部调用了chunk_alloc函数，chunk_alloc的职责就是负责内存池所有内存的生产，在生产的时候，为了保证下次能有内存用，所以会将空间*2，所以这次申请流程的总内存消耗为：(需求规格内存对齐后的大小)*20*2

 

重要：

对free_list的理解：

设计一个free_list[16]数组，负责管理从8bytes到128bytes不同大小的内存块，每一个内存块都由连续的固定大小的很多块组成，并用指针链表串接起来。比如说

freelist[3]->start_notuse->next_notuse->next_notuse->.......->end_notuse;

当用户要获取此大小的内存时，就在free_list的链表找一个最近的free chunk回传给用户，同时将此chunk从free_list删除，即把此chunk前后指针链接起来。当用户使用完释放的时候，则把此chunk放回到free_list中，应该是放到最前面start_free的位置。这样经过若干次alloc和dealloc后，free_list中的链表可能并不像初始的时候那么chunk是按内存位置依次链接的。假如free_list中不够时，allocator会自动再分配一块新的较大的内存区块来加入到free_list链表中。

在free_list中使用union代替struct的原因：

union obj{

     obj *next;

     char client[1];

};

如果采用struct方式，我们需要维护两条链表，一条链表是，已分配内存空间链表，另一条是未分配(空闲)空间链表。而我们使用索引表和union结构体，只需要维护一条链表，即未分配空间链表。具体如下：

索引表的作用有两条 1：如上所说，维护16条空闲链表；2：变相记录每条链表空间的大小，比如下标为3的索引表内维持着大小为24字节的空闲链表。这样我们通过索引表减少在结构体内记录p所指空间大小的iSize变量。从而减少4个字节(如果使用struct，需要增加isize变量来记录大小)。

Union的特性是，结构体内的变量是互斥存在的。在运行状态下，只存在一种变量类型，因此sizeof(Obj)=4,难道这里我们也需要把这4字节加入到用户申请空间去？其实不是，如果这样，我们便抹杀了union的特性。

当我们构建空闲地址分配链表时，我们通过next指向下一个union结构体，这样我们不使用p指针。当把这个这个结构体分配出去时，我们直接返回client地址，此时client正好指向申请空间的首字节。所以这样，我们不用在申请空间添加任何东西。

 

所需参考：1: malloc、free的应用

          2: 字节对齐

现在处理器(文献中指的是power pc)缺少对未对齐硬件的支持,对于每一次的未对齐内存访问，都会抛出一个异常。操作系统抓住此异常后，帮助系统做内存对齐，所以耗时会骤生。

补齐操作在结构体添加了一些实际上没有用的空间，目的就是为了保证其中的各个字段都能处于我们期望的地址。

字节对齐：简单来讲CPU要求对齐，因为CPU访问内存一般来讲并不是单字节访问，而是一块一块的访问。

举个例子：

struct{

char c1；

int i;

}

CPU以双子访问，1 + 3 +4；

这样访问i时只需一步，如果没有对齐的话，有的处理器会需要分割，合并，多次访问，有的就直接报错。

举个例子：对应struct对于int为四字节存储。

c1	i	i	i
i

单字对齐之后

c1
i	i	i	i

 

当单字节访问i时，需要访问两次；对齐之后，只需一次访问。

兼容性：主要指处理器的方式(其实也和对其相关，取决于处理器默认的对齐方式):内存访问粒度的大小(如果为双字访问，未对齐的话就会出现兼容性方面的问题)

 

关于free_list的结构验证需要在string中进行验证

经过多次的alloc和dealloc的结构示意图为：STL P61

 

 

关键代码的掌握：

alloc

dealloc

refill

malloc_chunk

 

内存池真的是C++的奇思妙想，虽然不能说对内存的利用做到了极致，也是对内存有了很高的利用率。

alloc、dealloc很基础、refill代码属于建立free_list的空闲结构？

最重要的是chunk_alloc，侯捷先生在STL源码中已经解释的很详细了，不过本人天生愚钝，结合调试工具才把代码大致搞懂；下面说一下自己的理解。

有一点是需要注意的，free_list中保存的是空闲的块，如果被使用完，则为0；

char *alloc::chunk_alloc(size_t bytes, size_t& nobjs){

char *result = 0;

size_t total_bytes = bytes*nobjs;

size_t bytes_left = end_free - start_free;

if (bytes_left >= total_bytes)//内存池剩余空间完全满足需求

{

result = start_free;

start_free += total_bytes;

return result;

}

//内存池剩余空间不能完全满足名单足够满足一个或一个以上的区块，在这里调整了nobjs

对应于refill中的nobjs=1。此nobjs的修改在下面程序中会被调用。

else if (bytes_left >= bytes){

nobjs = bytes_left / bytes;

total_bytes = bytes*nobjs;

result = start_free;

start_free += total_bytes;

return result;

}

else{

//内存池剩余空间连一个区块大小都无法提供，(heap_size>>4)是为了随配置量不断增大的附加量

size_t bytes_to_get = 2 * total_bytes + (heap_size >> 4);

if (bytes_left > 0){

内存池还有一些空间零头，分配给适当的free_list，这一部分在下一次有效的块申请的时候可能会用到。这一步主要是配置。

obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);

//调整free_list，将内存池的残余空间编入，寻找到参与空间，把它挂到链表的头部

((obj*)(start_free))->next = *(my_free_list);

*my_free_list = (obj*)(start_free);

}

start_free = (char*)malloc(bytes_to_get);

if (!start_free){

STL中不准备配置较小的区块，最小为从所申请的块的大小开始，对应代码到for循环中的i=size，原因：会导致在多线程机器上引发灾难？？

obj **my_free_list = 0, *p = 0;

for (int i = bytes; i <= MAXBYTES; i += 8)

{

my_free_list = free_list + FREELIST_INDEX(bytes);

p = *my_free_list;

if (p != 0)

{

p!=0意味着free_list有未用块，这一步如果申请到了空间，一定会被配置。

*my_free_list = p->next;

start_free = (char*)p;

end_free = start_free + i;

递归调用自己，同时修正nobjs。

return chunk_alloc(bytes, nobjs);

注意，任何残余零头终将被编入适当的free_list中备用，(调用次数足够多的话)

}

}

如果出现意外(完全没有内存可用了)，调用第一级配置器的out_of_memory机制。

out_of_memory会抛出异常或使得内存不足情况改善

end_free = 0;

start_free = (char*)malloc(bytes_to_get);

}

heap_size += bytes_to_get;

end_free = start_free + bytes_to_get;

递归调用自己，为了修正nobjs；

return chunk_alloc(bytes, nobjs);

}

}

 

内存池的实际操练结果: STL P69

 

TinySTL中没有使用out_of_memory机制

out_of_memory机制类似于C++中的handle机制。

所谓C++handle机制是，你可以要求系统在内存配置需求无法被满足时，调用一个指定的函数。一旦operator new无法完成任务，在丢出bad_alloc之前，会先调用客端指定的处理例程，该处理例程通常称为new_handle。new_handle解决内存有特定的模式。SGI第一级配置器的allocate()和reallocate()都是在调用malloc和realloc不成功后，改调用oom_malloc()和oom_realloc(),后两者都有内循环，不断调用”内存不足处理例程”，期望在某次调用之后，获得足够多的内存圆满完成任务。不过内存不足处理例程需要被客端设定，oom_malloc和oom_realloc便调用_THROW_BAD_ALLOC,丢出bad_alloc异常信息，或利用exit(1)终止程序。

具体见：STL57

关于自己所设定的内存处理机制，以后了解一下。

 

//关于最后的图片，由链表指向的首个指针应该指向第二个nobj，原因是第一块会传回给客端。

 

 

 

 

转载地址：https://blog.csdn.net/tling11/article/details/52839293 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！