参考文献

内存分配算法

  • 常用的内存分配算法:
    • 动态内存分配(Dynamic memory allocation DMA)
    • 伙伴算法
    • Slab算法

动态内存分配(Dynamic memory allocation DMA)

  • 动态内存分配,又称堆内存分配.操作系统根据程序运行过程中需求及时分配内存,且分配的内存大小就是程序需求的大小.在大部分场景下,只有程序运行的时候才知道所需要分配的内存大小,如果提前分配可能分配的大小无法把控,分配太大会浪费空间,分配太小会无法使用.
  • DMA是从一整块内存中按需分配,对于分配的内存会记录元数据,同时还会使用空闲分区链维护空闲内存,便于在内存分配时查找可用的空闲分区.常用的有三种查找策略:
    • 首次适应算法(first fit)
    • 循环适应算法(next fit)
    • 最佳适应算法(best fit)

首次适应算法(first fit)

  • 空闲分区链以地址递增的顺序,将空闲分区以双向链表的形式连接在一起,从空闲分区链中找到第一个满足分配条件的空闲分区,然后从空闲分区中划分一块可用内存给请求进程,剩余的空闲分区仍然保留在空闲分区链中.

  • 如下图所示,P1 和 P2 的请求可以在内存块 A 中完成分配.该算法每次都从低地址开始查找,造成低地址部分会不断被分配,同时也会产生很多小的空闲分区.

    img

循环适应算法(next fit)

  • 算法是由首次适应算法的变种,循环首次适应算法不再是每次从链表的开始进行查找,而是从上次找到的空闲分区的下⼀个空闲分区开始查找.

  • 如下图所示,P1 请求在内存块 A 完成分配,然后再为 P2 分配内存时,是直接继续向下寻找可用分区,最终在 B 内存块中完成分配.该算法相比⾸次适应算法空闲分区的分布更加均匀,而且查找的效率有所提升,但是正因为如此会造成空闲分区链中大的空闲分区会越来越少.

    img

最佳适应算法(best fit)

  • 空闲分区链以空闲分区大小递增的顺序,将空闲分区以双向链表的形式连接在一起,每次从空闲分区链的开头进行查找,这样第一个满足分配条件的空间分区就是最优解.

  • 如下图所示,在 A 内存块分配完 P1 请求后,空闲分区链重新按分区大小进行排序,再为 P2 请求查找满足条件的空闲分区.该算法的空间利用率更高,但同样也会留下很多较难利用的小空闲分区,由于每次分配完需要重新排序,所以会有造成性能损耗.

    img

伙伴算法

  • 伙伴算法采用了分离适配的设计思想,将物理内存按照2的次幂进行划分,内存分配时也是按照2的次幂大小进行按需分配,例如4KB,8KB,16KB等.假设我们请求分配的内存的大小为10KB,那么使用伙伴算法会按照16KB进行分配.

  • 伙伴算法把内存划分为 11 组不同的 2 次幂大小的内存块集合,每组内存块集合都用双向链表连接.链表中每个节点的内存块大小分别为 1、2、4、8、16、32、64、128、256、512 和 1024 个连续的 Page ,例如第一组链表的节点为 202^0 个连续 Page,第二组链表的节点为212^1个连续 Page,以此类推.

  • 假设我们需要分配 10K 大小的内存块,看下伙伴算法的具体分配过程：

    • 首先需要找到存储242^4连续 Page 所对应的链表,即数组下标为 4;

    • 查找242^4链表中是否有空闲的内存块,如果有则分配成功;

    • 如果242^4链表不存在空闲的内存块,则继续沿数组向上查找,即定位到数组下标为 5 的链表,链表中每个节点存储252^5的连续 Page;

    • 如果252^5链表中存在空闲的内存块,则取出该内存块并将它分割为 2 个242^4 大小的内存块,其中一块分配给进程使用,剩余的一块链接到242^4 链表中.

  • 以上是伙伴算法的分配过程,那么释放内存时候伙伴算法又会发生什么行为呢？当进程使用完内存归还时,需要检查其伙伴块的内存是否释放,所谓伙伴块是不仅大小相同,而且两个块的地址是连续的,其中低地址的内存块起始地址必须为 2 的整数次幂.如果伙伴块是空闲的,那么就会将两个内存块合并成更大的块,然后重复执行上述伙伴块的检查机制.直至伙伴块是非空闲状态,那么就会将该内存块按照实际大小归还到对应的链表中.频繁的合并会造成 CPU 浪费,所以并不是每次释放都会触发合并操作,当链表中的内存块个数小于某个阈值时,并不会触发合并操作.

  • 由此可见,伙伴算法有效地减少了外部碎片,但是有可能会造成非常严重的内部碎片,最严重的情况会带来 50% 的内存碎片.

Slab算法

  • 因为伙伴算法都是以Page 为最小管理单位,在小内存的分配场景,伙伴算法并不适用,如果每次都分配一个 Page 岂不是非常浪费内存,因此 Slab 算法应运而生了.Slab 算法在伙伴算法的基础上,对小内存的场景专门做了优化,采用了内存池的方案,解决内部碎片问题.
  • Linux内核使用的就是Slab算法,因为内核需要频繁地分配小内存,所以 Slab 算法提供了一种高速缓存机制,使用缓存存储内核对象,当内核需要分配内存时,基本上可以通过缓存中获取.此外 Slab 算法还可以支持通用对象的初始化操作,避免对象重复初始化的开销.
  • 在 Slab 算法中维护着大小不同的 Slab 集合,在最顶层是cache_chain,cache_chain 中维护着一组 kmem_cache引用,kmem_cache 负责管理一块固定大小的对象池.通常会提前分配一块内存,然后将这块内存划分为大小相同的slot,不会对内存块再进行合并,同时使用位图bitmap 记录每个slot的使用情况.
  • kmem_cache中包含三个 Slab 链表：完全分配使用slab_full、部分分配使用slab_partial和完全空闲 slabs_empty,这三个链表负责内存的分配和释放.每个链表中维护的 Slab 都是一个或多个连续 Page,每个 Slab 被分配多个对象进行存储.Slab 算法是基于对象进行内存管理的,它把相同类型的对象分为一类.当分配内存时,从 Slab 链表中划分相应的内存单元;当释放内存时,Slab 算法并不会丢弃已经分配的对象,而是将它保存在缓存中,当下次再为对象分配内存时,直接会使用最近释放的内存块.
  • 单个 Slab 可以在不同的链表之间移动,例如当一个 Slab 被分配完,就会从slab_partial移动到 slabs_full,当一个 Slab 中有对象被释放后,就会从slab_full再次回到slab_partial,所有对象都被释放完的话,就会从slab_partial移动到slab_empty

jemalloc

  • arena是jemalloc最重要的部分,内存由一定数量的arenas负责管理.每个用户线程都会被绑定到一个arena上,线程采用round-robin轮询的方式选择可用的arena进行内存分配,为了减少线程之间的锁竞争,默认每个CPU会分配4个arena.

  • bin用于管理不同档位的内存单元,每个bin管理的内存大小是按分类依次递增.因为jemalloc中小内存的分配是基于Slab算法完成的,所以会产生不同类别的内存块.

  • chunk 是负责管理用户内存块的数据结构,chunk 以Page 为单位管理内存,默认大小是4M,即1024个连续Page.每个chunk 可被用于多次小内存的申请,但是在大内存分配的场景下只能分配一次.

  • run实际上是chunk 中的一块内存区域,每个bin管理相同类型的run,最终通过操作run完成内存分配.run结构具体的大小由不同的bin决定,例如8字节的bin对应的run只有一个Page,可以从中选取8字节的块进行分配.

  • region是每个run中的对应的若干个小内存块,每个run会将划分为若干个等长的region,每次内存分配也是按照region进行分发.

  • tcache是每个线程私有的缓存,用于small和large场景下的内存分配,每个tcahe会对应一个arena,tcache本身也会有一个bin数组,称为tbin.与arena中bin不同的是,它不会有run的概念.tcache每次从arena申请一批内存,在分配内存时首先在tcache查找,从而避免锁竞争,如果分配失败才会通过run执行内存分配.

  • 它们之间的关系：

    • 内存是由一定数量的arenas负责管理,线程均匀分布在arenas当中;
    • 每个arena都包含一个bin数组,每个bin管理不同档位的内存块;
    • 每个arena被划分为若干个chunks,每个chunk 又包含若干个runs,每个run由连续的Page组成,run才是实际分配内存的操作对象;
    • 每个run会被划分为一定数量的regions,在小内存的分配场景,region相当于用户内存;
    • 每个tcache对应一个arena,tcache中包含多种类型的bin.

  • jemalloc的整体内存分配和释放流程,主要分为Samll,Large和Huge三种场景

    • Samll场景,如果请求分配内存的大小小于arena中的最小的bin,那么优先从线程中对应的tcache中进行分配.首先确定查找对应的tbin中是否存在缓存的内存块,如果存在则分配成功,否则找到tbin对应的arena,从arena中对应的bin中分配region保存在tbin的avail数组中,最终从availl数组中选取一个地址进行内存分配,当内存释放时也会将被回收的内存块进行缓存.
    • Large场景的内存分配与Samll类似,如果请求分配内存的大小大于arena中的最小的bin,但是不大于tcache中能够缓存的最大块,依然会通过tcache进行分配,但是不同的是此时会分配chunk 以及所对应的run,从chunk 中找到相应的内存空间进行分配.内存释放时也跟Samll场景类似,会把释放的内存块缓存在tacache的tbin中.此外还有一种情况,当请求分配内存的大小大于tcache中能够缓存的最大块,但是不大于chunk 的大小,那么将不会采用tcache机制,直接在chunk 中进行内存分配
    • Huge场景,如果请求分配内存的大小大于chunk 的大小,那么直接通过mmap进行分配,调用munmap进行回收.