图文并茂解释内存池原理

在 C 语言的动态申请内存技术中,相比起 alloc/free 系统调用,内存池(memory pool)是与现在系统中请求一大片连续的内存空间,然后在运行时根据实际需要分配出去的技术。使用内存池的优点有:

  1. 速度远比 malloc/free 快,因为减少了系统调用的次数,特别是频繁申请/释放内存块的情况
  2. 避免了频繁申请/释放内存之后,系统的大量内存碎片
  3. 节省空间

分类

根据分配出去的内存大小,内存池可以分为两类:

Fixed-size Allocation

每次分配出去的内存单元(称为 unit 或者 cell)的大小为程序预先定义的值。释放内存块时,则只需要简单地挂回内存池链表中即可。又称为 “固定尺寸缓冲池”。

常规的做法是:将不同 unit size 的内存池整合在一起,以满足不同内存块大小的使用需求

Variable-size allocation

不分配固定长度,内存的分配只是在一大块空闲的内存上滑动。优点是分配效率很高,缺点是成批地回收内存,因为释放的内存无法直接重复利用。

使用这种需要合理规划每块内存的管理区域,所以又叫做 “基于区域的” 内存管理。使用这种做法的分配器,举例有 Apache Portable Runtime 中的 apr_pool 工具。本文不讨论这种内存池。


原理和结构

概念和数据结构

定长内存池有一些基本和必要的概念,需要定义在内存池的结构数据中。以下命名方式使用变体的匈牙利命名法,比如 nNextn表示变量类型为整形。类似地,p表示指针。

Memory Unit

每次程序调用 MemPool_Alloc 获取一个内存区域后,会获得一块连续的内存区域。管理一个这样的内存区域的单元就成为内存单元 unit,有时也称作 chunk。每个 unit 需要包含以下数据:

  1. nNext:整型数据,表示下一个可供分配的 unit 的标识号。功能请参见后问
  2. pData[]:实际的内存区域,其大小在创建时由调用方指定

Memory Block

一个内存块,内存块中保存着一系列的内存单元。

这个数据结构需要包含以下基本信息:

  1. nSize:整型数据,表示该 block 在内存中的大小
  2. nFree:整型,表示剩下有几个 unit 未被分配
  3. nFirst:整型,表示下一个可供分配的 unit 的标识号
  4. pNext:指针,指向下一个 memory block

Memory Pool

一个内存池总的管理数据结构,换句话说,是一个内存池对象。

  1. pBlock:指针,指向第一个 memory block
  2. nUnitSize:整型,表示每个 unit 的尺寸
  3. nInitSize:整型,表示第一个 block 的 unit 个数
  4. nGrowSize:整型,表示在第一个 block 之外再继续增加的每个 block 的 unit 个数

函数接口

作为一个内存池,需要实现以下一些基本的函数接口,或者说可以是对象方法:

memPoolCreate()

创建一个 memory pool,必须的参数为 unit size,可选参数为上文 memory pool 的 nInitSizenGrowSize

memPoolDestroy()

销毁整个 memory pool 并交还给操作系统。

memPoolAlloc()

从 memory pool 中分配一个 unit,其尺寸是预先定义的 unit size。

memPoolFree()

释放一个指定的 unit。


工作过程

现在我们用一个 unit size 为 1024、init size 为 4(每一个 block 有 4 个 units)的 memory pool 为例,解释一下内存池的工作原理。下文假设整型的宽度为 4 个字节。

创建 memory pool

程序开始,调用并创建一个 memory pool。此时调用的函数为 memPoolCreate(),程序会创建一个数据结构,相应的结构体成员及其取值如下:

memory pool alloc

当调用者第一次请求 memPoolAlloc() 时,内存池发现 block 链表为空,于是想系统申请内存,创建 memory block,并初始化如下(其中地址值为假设值):

其中 nSize = 4112 = sizeof(memPool) + nInitSize * sizeof(memUnit)。每一个 nNext 依次加一,各指代着跟着自己的下一个 unit。最后一个 unit 的 nNext 值无意义,因此不说明其取值。

然后返回需要的 unit 中的内存。返回内存的逻辑如下:

  1. 内存池在 block 中查询 nFree 成员
  2. 由于 nFree > 0,表示有未分配的 unit,因此继续在该 block 中查看 nFirst 成员
  3. nFirst 等于 0,表示该 block 中位置为 0 的 unit 可用。因此内存池可以将这个 unit 中的 pData 地址返回给调用方。 pData 的地址值计算方式为:pBlock + sizeof(memBlock) + nFirst * (sizeof(memUnit)) + sizeof(nNext) = 0x10010
  4. nFree 减一
  5. 修改 nFirst 的值,标记下一个可用的 unit。注意这里的 nFirst 切切不能简单地加一,而是取返回给调用方的 unit 所对应的 nNext 的值,也就是下图(2)处原来的值 1
  6. pData 的地址值返回。为便于说明,这块区域我们标记为 C_A

操作后各数据结构的状态如下:

第二次调用 alloc 的情况类似。调用后各数据结构的状态如下:

memory pool free

我们先看看结果:

  1. 首先程序会检查 C_A 的地址值,很快就会发现,地址 0x10010 位于上述第一个 block 的范围之内(0x10000 <= 0x10010 <= (0x10000 + 4112))。再计算偏移值可以很快得出其对应的 nNext 标号,也就是上图中的(2)位置。
  2. 回收 unit,此时需要标记相应的成员值以标示 unit 的回收状态。首先查看 nFirst 的值,参见上前幅图,nFirst 的值为 3,表示位置(3)处的 unit 是可用的。因此我们首先把 (2) 处的 nNext 值设置为 3,将其加回到可用 unit 的链表中
  3. nFirst 的值修改为 0,也就是代表刚刚回收回来的 unit 的标号,而(2)处的值赋值为 2,表示b(3)的 unit

其实可以看到,上面就是一个简单的链表操作。根据上面的过程,如果 C_B 也释放了的话,那么 memory pool 的状态则会变成这样:

到这个时候,由于整个 block 已经完全回收了(nFree == nInitSize),那么根据不同的策略,可以考虑将整个 block 从内存中释放掉。

block 满

我们回到 alloc 的逻辑中,可以看到内存池最开始会检查 block 的 nFree 成员。如果 nFree == 0 的时候,那么就会在该 block 的 pNext 中去找到下一个 block,再去检查 nFree。如果发现 block 链表已经结束了,那就意味着当前所有的 block 已满,必须创建新的 block。

在实际设计中,我们需要考虑选取合适的 init size 和 grow size 值。从上面的算法中可以看到,如果 alloc/free 调用非常频繁时,第一个 block 的使用效率是非常高的。


变体或改进

  1. 有些简化的版本中,可以不使用 pNext 来维护链表,也就是只有一个 block,并且内存的使用有一个明确且受控的上限值。这经常用在没有 malloc 系统调用的 RTOS 或者是一些对内存非常敏感的嵌入式系统中。
  2. 如果要用于多线程环境中,那么 memory pool 结构体需要加上锁

参考资料


本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。

原文发布于:https://cloud.tencent.com/developer/article/1361759

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我是攻城师

深入理解Java类加载器机制

Java里面的类加载机制,可以说是Java虚拟机核心组件之一,掌握和理解JVM虚拟机的架构,将有助于我们站在底层原理的角度上来理解Java语言,这也是为什么我们...

41320
来自专栏LanceToBigData

linux(四)之元字符

一直觉得linux是一个非常高深的东西,但是慢慢学过来其实就是一堆一堆的命令执行,让一个程序运行的结果。 只有你有毅力去学习,并且系统的去学习我相信没有什么恶...

28570
来自专栏coderhuo

arm平台根据栈进行backtrace的方法

嵌入式设备开发过程中,难免会遇到各种死机问题。这类问题的定位一直是开发人员的噩梦。 死机问题常见定位手段如下:

24410
来自专栏张善友的专栏

Redis应用场景

Redis开创了一种新的数据存储思路,使用Redis,我们不用在面对功能单调的数据库时,把精力放在如何把大象放进冰箱这样的问题上,而是利用Redis灵活多变的数...

25960
来自专栏积累沉淀

Python快速学习第八天

本文内容全部出自《Python基础教程》第二版 10.1 模块 现在你已经知道如何创建和执行自己的程序(或脚本)了,也学会了怎么用import从外部模...

38160
来自专栏FreeBuf

RCTF 2018 Magic题目详解

此题来自 RCTF 2018 的一道逆向题目 magic. 赛后分析许久, 看了几个 writeup, 但是始终不得要领, 大神们寥寥数语, 扔下一堆代码, 就...

17500
来自专栏闻道于事

Java多线程详解

每个运行的程序就是一个进程,当一个程序运行时,内部可能包含了多个顺序执行流,每个顺序执行流就是一个进程。

15830
来自专栏SeanCheney的专栏

Scrapy的CrawlSpider用法

rules是一组Rule对象。每条Rule定义了抓取网页的方式。如果多条规则匹配到同一链接,根据定义规则的顺序,使用第一个链接。

22330
来自专栏Java编程技术

基于rxjava的生产消费模型

最近在看springcloud的熔断机制的实现,发现底层使用的rxjava实现,就看了下rxjava的使用,发现rxjava使用可也便捷实现前面讲解的定时生产与...

10520
来自专栏kalifaの日々

GCJ 2008Round1AA 菜鸟踩坑(C++)

踩到的坑: 不同于POJ,GCJ有两个测试用例的文档,供你在本地得到输出,我开始的时候下载文档之后直接把文档中的数据复制出来,运行代码时贴上去,也就是,从标准输...

28050

扫码关注云+社区

领取腾讯云代金券