【总结笔记】内存池技术讲解

参考链接：https://github.com/Winter-Win/ConcurrentMemoryPool
参考链接：https://www.jb51.net/article/217288.htm
参考链接：https://www.jb51.net/article/223461.htm
后续看：https://blog.csdn.net/qq_42270373/article/details/89244796

1、池化技术

池化技术是一种常见的提高资源利用率的优化技巧。池化技术先向系统申请程序经常需要使用的核心资源，将这些资源置于“池”中。常见的池化技术包括内存池、线程池、连接池等。

2、内存池

备注：在 Linux 中，一页即 4KB，即最小的内存块不能小于 4KB
（1）未使用内存池情况下，频繁通过new/delete、malloc/free 向系统申请/释放内存，必然会导致大量的外碎片出现，增加系统开销，降低程序和操作系统的性能。【内碎片无法避免，只能尽可能地降低】
（2）内存池原理：先向系统申请分配一大块内存作为内存池留作备用，若申请内存，则从池中取出一块；若释放内存，将内存放回内存池，并且尽量与周边的空闲内存块合并。若内存池不够时，则向操作系统申请更大的内存池。

3、几种内存分配方式

3.1 极简单链表内存分配器【用符号标记内存块是否空闲】

分配一块大的内存块，将内存块切割成大小不一的小内存块，并将其串起来形成一个单链表。申请内存就从链表取出一块，释放内存则将内存放回链表，并做好合并。使用符号内存块是否被申请。这里涉及如何查找最适合大小的内存块。若想减少内存碎，可以使用伙伴算法，。
优点：实现简单
缺点：分配搜索内存块效率低，且释放内存进行合并消耗大，实际用处不大。

伙伴算法的实现原理：
【概念】页块：页块大小必须是 2^k；页框：所申请的内存统一称为页框；页大小单位：4KB
为便于页面维护，将多个页面组成内存块，每个内存块有 2^k个页。当向内存请求分配一定数目的页框时，在页块链表查找处于空闲状态且 最小能够满足页框大小 的页块。【如页框为 3KB，应寻找大小为 4KB 的空闲页块，若无，则依次找 8KB、16KB 的空闲页块】当分配的页块有多余的页框时，伙伴算法将页块分裂成大小相同的两部分，直至所分配页块无多余页框【假设页框为 3KB，寻找分配的空闲页块为 16KB，则将 16KB=> 4KB + 4KB + 8KB】。释放内存块时，需将空闲的 2 个伙伴内存块进行合并。
```
参考链接：https://www.bilibili.com/video/BV1jL411N7sK?spm_id_from=333.1007.top_right_bar_window_history.content.click
```

3.2 定长内存分配器

即实现一个 FreeList。
假设固定内存分配器所分配的固定大小内存块为 32B，每个分配器维护 2 个链表。1个链表存储未分配的空闲内存块，1 个链表存储已分配的内存块。每次申请时就从未分配链表取出能满足页框大小的最小 k 块添加到已分配链表【如申请页框为 58B，则取 2 块固定内存】，释放时就将已分配链表的 k 块内存移回到未分配链表。
优点：实现简单，且分配与释放效率高
缺点：功能单一只能解决定长内存需求

参考链接：https://zhuanlan.zhihu.com/p/84505429
// 核心代码
while (idx + itemsize <= blocksize) {
    blockitem_t *item = (blockitem_t*)(block->buffer + idx);
    item->next = alloc->freeitem;
    item->flag = 0;
    alloc->freeitem = item;
    idx += itemsize;
}

3.3 哈希映射的FreeList 池

在定长分配器基础上，按照不同对象大小（8、16、24、32 ... 64K、128K）【SGI STL 的二级空间分配器以 8 的倍数对齐】构造十多个固定内存分配器。分配内存时根据要根据申请内存大小进行对齐，然后查询哈希表，决定由哪个分配器负责。
分配后要在内存头部的 header 处写上 cookie，表示该块内存由哪个分配器负责，释放时就将其归还到相应分配器。若所申请的页框大于 128K，则直接用系统的 malloc 作为分配【SGI STL 的一级空间分配器】。
优点：本质是定长内存池的改进，分配和释放的效率高
缺点：定长分配器 FreeList 占用了大量内存，即使后面不用，也无法支援到其他内存不够的 FreeList，达不到分配均衡的效果。
应用场景：SGI STL 的空间分配器就是这种设计实现。参考链接： https://blog.csdn.net/LF_2016/article/details/53511648`

补充：malloc 原理【malloc 原理应该也是哈希映射的FreeList 池？】 参考链接：https://blog.csdn.net/hudazhe/article/details/79535220 https://blog.nowcoder.net/n/de03980b2ab746ccad65fcb38bee59c3`

3.4 并发内存池

参考链接：

Thread Cache 层：线程缓存层。每个线程有独享的线程缓存【此处设计为小于 64KB】，因此申请无需加锁，因此能实现并发高效的作用
Central Cache 层：中央缓存层。所有线程共享中央缓存层，它起着承上启下的作用，其内存对象称为 Span【1 个 Span 有 k 个页】。Thread Cache 是按需向 Central Cache 中申请缓存，因此 Central Cache 需要有平衡多个线程按需调度的功能。它既可以将内存对象分配给Thread Cache，又可以将线程归还回来的内存进行管理。由于线程之前对 Central Cache 存在竞争，因此需要加锁，但锁的粒度可以很小。
Page Cache 层：页缓存层。以页【1 页大小4KB】为单位进行存储与分配。Central Cache没有内存对象(Span)时，从Page cache分配出一定数量的Page，并切割成 定长大小 的小块内存，分配给Central Cache。Page Cache 会回收 Central Cache 满足条件的Span **(使用计数为0) ** 对象，并且合并相邻的页，组成更大的页，缓解内存碎片的问题。

3.4.1 Thread Local Storage （TLS）

为了避免加锁带来的效率降低问题，在Thread Cache中使用 thread local storage （tls）保存每个线程本地的Thread Cache的指针，这样Thread Cache在申请释放内存是不需要锁的。因为每一个线程都拥有了自己唯一的一个全局变量。
静态 TLS：直接定义
动态 TLS：调用系统的API创建
项目所用 TLS 属于静态 TLS。

TLS概念
线程局部存储（TLS），是一种变量的存储方法，这个变量在它所在的线程内是全局可访问的，但是不能被其他线程访问到，这样就保持了数据的线程独立性。而熟知的全局变量，是所有线程都可以访问的，这样就不可避免需要锁来控制，增加了控制成本和代码复杂度。
实现方式： __thread 关键字 参考链接：https://blog.csdn.net/yusiguyuan/article/details/22938671

3.5 设计 Thread Cache

3.6 设计 Central Cache

（1）Central Cache本质是由一个哈希映射的Span对象自由双向链表构成
（2）为了保证全局只有唯一的 Central Cache，这个类被可以设计成了单例模式
（3）单例模式采用饿汉模式，避免高并发下资源的竞争
单例模式详解参考：https://zhuanlan.zhihu.com/p/37469260#:~:text=C%2B%2B,%E5%8D%95%E4%BE%8B%E6%A8%A1%E5%BC%8F%20SingletonSingleton%E4%BF%9D%E8%AF%81%E4%B8%80%E4%B8%AA%E7%B1%BB%E4%BB%85%E6%9C%89%E4%B8%80%E4%B8%AA%E5%AE%9E%E4%BE%8B%EF%BC%8C%E5%B9%B6%E6%8F%90%E4%BE%9B%E4%B8%80%E4%B8%AA%E8%AE%BF%E9%97%AE%E5%AE%83%E7%9A%84%E5%85%A8%E5%B1%80%E8%AE%BF%E9%97%AE%E7%82%B9%E3%80%82

单例模式写法之懒汉式
实例在用到的时候才去创建，用的时候才去检查有没有实例，如果有则返回，没有则新建。
优点：单例只有在使用时才被实例化，一定程度上节约了资源。
单例模式写法之饿汉式
实例在初始化的时候就已经建好了，不管你有没有用到，都先建好了再说。
优点：获取对象的速度快
缺点：耗内存

申请内存

（1）当 Thread Cache 没有内存时，会向 Central Cache 申请一些内存对象。Central Cache 也有一个哈希映射的 freeList，freeList挂着 span，从 span 中取出对象给 Thread Cache 这个过程是需要加锁的；
（2）当 Central Cache 中无非空的 span 时，则将空的 span 链在一起，向 Page Cache 申请一个 span 对象。一个 span 含有 k 个页，并切成所需的等长内存大小且连接起来；
（3）Central Cache 的 span 有一个计数变量_usecount，记录当前 span 有多少个对象已经分配给 Thread Cache 。

释放内存

（1）当Thread Cache过长或者线程销毁，则会将内存释放回 Central Cache 中，释放回来时--_usecount；
（2）当_usecount减到0时则表示所有对象都回到了 span，则将 Span释放回 Page Cache，Page Cache中会对前后相邻的空闲页进行合并。

页号-Span 哈希映射

维护一个页号-Span 映射哈希，当 Page Cache 分配一个 Span 给 Central Span 时，将组成 span 的 k 页的页号与 span 的映射关系用该哈希表进行存储。当 Thread Cache 归还给 Central Cache 时，可以通过该哈希表找到对应的 span。

3.7 设计 Page Cache

（1）Page Cache 是一个以页为单位的 span FreeList（1Page、2Page、3Page、4Page、... 、128Page）；
（2）全局只有唯一的 Page Cache，因此该类可以被设计为单例模式；
（3）本单例模式采用饿汉模式

申请内存

（1）当 Central Cache 向 Page Cache 申请内存时，Page Cache 自上而下找大于等于页框【所申请的页数】的 span。若 span 页数比页框大，则将 span 划分为 2 部分。

【总结笔记】内存池技术讲解

1、池化技术

2、内存池

3、几种内存分配方式

3.1 极简单链表内存分配器【用符号标记内存块是否空闲】

3.2 定长内存分配器

3.3 哈希映射的FreeList 池

3.4 并发内存池

3.4.1 Thread Local Storage （TLS）

3.5 设计 Thread Cache

3.6 设计 Central Cache

申请内存

释放内存

页号-Span 哈希映射

3.7 设计 Page Cache

申请内存

相关

标签