算法-内存分配算法
参考文献
内存分配算法
- 常用的内存分配算法:
- 动态内存分配(
Dynamic memory allocation DMA
) - 伙伴算法
Slab
算法
- 动态内存分配(
动态内存分配(Dynamic memory allocation DMA
)
- 动态内存分配,又称堆内存分配.操作系统根据程序运行过程中需求及时分配内存,且分配的内存大小就是程序需求的大小.在大部分场景下,只有程序运行的时候才知道所需要分配的内存大小,如果提前分配可能分配的大小无法把控,分配太大会浪费空间,分配太小会无法使用.
DMA
是从一整块内存中按需分配,对于分配的内存会记录元数据,同时还会使用空闲分区链维护空闲内存,便于在内存分配时查找可用的空闲分区.常用的有三种查找策略:- 首次适应算法(
first fit
) - 循环适应算法(
next fit
) - 最佳适应算法(
best fit
)
- 首次适应算法(
首次适应算法(first fit
)
-
空闲分区链以地址递增的顺序,将空闲分区以双向链表的形式连接在一起,从空闲分区链中找到第一个满足分配条件的空闲分区,然后从空闲分区中划分一块可用内存给请求进程,剩余的空闲分区仍然保留在空闲分区链中.
-
如下图所示,P1 和 P2 的请求可以在内存块 A 中完成分配.该算法每次都从低地址开始查找,造成低地址部分会不断被分配,同时也会产生很多小的空闲分区.
循环适应算法(next fit
)
-
算法是由首次适应算法的变种,循环首次适应算法不再是每次从链表的开始进行查找,而是从上次找到的空闲分区的下⼀个空闲分区开始查找.
-
如下图所示,P1 请求在内存块 A 完成分配,然后再为 P2 分配内存时,是直接继续向下寻找可用分区,最终在 B 内存块中完成分配.该算法相比⾸次适应算法空闲分区的分布更加均匀,而且查找的效率有所提升,但是正因为如此会造成空闲分区链中大的空闲分区会越来越少.
最佳适应算法(best fit
)
-
空闲分区链以空闲分区大小递增的顺序,将空闲分区以双向链表的形式连接在一起,每次从空闲分区链的开头进行查找,这样第一个满足分配条件的空间分区就是最优解.
-
如下图所示,在 A 内存块分配完 P1 请求后,空闲分区链重新按分区大小进行排序,再为 P2 请求查找满足条件的空闲分区.该算法的空间利用率更高,但同样也会留下很多较难利用的小空闲分区,由于每次分配完需要重新排序,所以会有造成性能损耗.
伙伴算法
-
伙伴算法采用了分离适配的设计思想,将物理内存按照2的次幂进行划分,内存分配时也是按照2的次幂大小进行按需分配,例如4KB,8KB,16KB等.假设我们请求分配的内存的大小为10KB,那么使用伙伴算法会按照16KB进行分配.
-
伙伴算法把内存划分为 11 组不同的 2 次幂大小的内存块集合,每组内存块集合都用双向链表连接.链表中每个节点的内存块大小分别为 1、2、4、8、16、32、64、128、256、512 和 1024 个连续的
Page
,例如第一组链表的节点为 个连续Page
,第二组链表的节点为个连续Page
,以此类推. -
假设我们需要分配 10K 大小的内存块,看下伙伴算法的具体分配过程:
-
首先需要找到存储连续
Page
所对应的链表,即数组下标为 4; -
查找链表中是否有空闲的内存块,如果有则分配成功;
-
如果链表不存在空闲的内存块,则继续沿数组向上查找,即定位到数组下标为 5 的链表,链表中每个节点存储的连续
Page
; -
如果链表中存在空闲的内存块,则取出该内存块并将它分割为 2 个 大小的内存块,其中一块分配给进程使用,剩余的一块链接到 链表中.
-
-
以上是伙伴算法的分配过程,那么释放内存时候伙伴算法又会发生什么行为呢?当进程使用完内存归还时,需要检查其伙伴块的内存是否释放,所谓伙伴块是不仅大小相同,而且两个块的地址是连续的,其中低地址的内存块起始地址必须为 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
会被划分为一定数量的region
s,在小内存的分配场景,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
进行回收.