伙伴系统和slab机制

伙伴系统

Linux内核中采用了一种同时适用于32位和64位系统的内存分页模型,对于32位系统来说,两级页表足够用了,而在x86_64系统中,用到了四级页表。四级页表分别为:

  • 页全局目录(Page Global Directory)
  • 页上级目录(Page Upper Directory)
  • 页中间目录(Page Middle Directory)
  • 页表(Page Table)

页全局目录包含若干页上级目录的地址,页上级目录又依次包含若干页中间目录的地址,而页中间目录又包含若干页表的地址,每一个页表项指向一个页框。Linux中采用4KB大小的页框作为标准的内存分配单元。

在实际应用中,经常需要分配一组连续的页框,而频繁地申请和释放不同大小的连续页框,必然导致在已分配页框的内存块中分散了许多小块的空闲页框。这样,即使这些页框是空闲的,其他需要分配连续页框的应用也很难得到满足。

 为了避免出现这种情况,Linux内核中引入了伙伴系统算法(buddy system)。把所有的空闲页框分组为11个块链表,每个块链表分别包含大小为1,2,4,8,16,32,64,128,256,512和1024个连续页框的页框块。最大可以申请1024个连续页框,对应4MB大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。

 假设要申请一个256个页框的块,先从256个页框的链表中查找空闲块,如果没有,就去512个页框的链表中找,找到了则将页框块分为2个256个页框的块,一个分配给应用,另外一个移到256个页框的链表中。如果512个页框的链表中仍没有空闲块,继续向1024个页框的链表查找,如果仍然没有,则返回错误。

页框块在释放时,会主动将两个连续的页框块合并为一个较大的页框块。

Buddy算法的优缺点:

1)尽管伙伴内存算法在内存碎片问题上已经做的相当出色,但是该算法中,一个很小的块往往会阻碍一个大块的合并,一个系统中,对内存块的分配,大小是随机的,一片内存中仅一个小的内存块没有释放,旁边两个大的就不能合并。

2)算法中有一定的浪费现象,伙伴算法是按2的幂次方大小进行分配内存块,当然这样做是有原因的,即为了避免把大的内存块拆的太碎,更重要的是使分配和释放过程迅速。但是他也带来了不利的一面,如果所需内存大小不是2的幂次方,就会有部分页面浪费。有时还很严重。比如原来是1024个块,申请了16个块,再申请600个块就申请不到了,因为已经被分割了。

3)另外拆分和合并涉及到 较多的链表和位图操作,开销还是比较大的。

Buddy(伙伴的定义):

这里给出伙伴的概念,满足以下三个条件的称为伙伴:

1)两个块大小相同;

2)两个块地址连续;

3)两个块必须是同一个大块中分离出来的;

Buddy算法的分配原理:

假如系统需要4(22)个页面大小的内存块,该算法就到free_area[2]中查找,如果链表中有空闲块,就直接从中摘下并分配出去。如果没有,算法将顺着数组向上查找free_area[3],如果free_area[3]中有空闲块,则将其从链表中摘下,分成等大小的两部分,前四个页面作为一个块插入free_area[2],后4个页面分配出去,free_area[3]中也没有,就再向上查找,如果free_area[4]中有,就将这16(2222)个页面等分成两份,前一半挂如free_area[3]的链表头部,后一半的8个页等分成两等分,前一半挂free_area[2]的链表中,后一半分配出去。假如free_area[4]也没有,则重复上面的过程,知道到达free_area数组的最后,如果还没有则放弃分配。

Buddy算法的释放原理:

内存的释放是分配的逆过程,也可以看作是伙伴的合并过程。当释放一个块时,先在其对应的链表中考查是否有伙伴存在,如果没有伙伴块,就直接把要释放的块挂入链表头;如果有,则从链表中摘下伙伴,合并成一个大块,然后继续考察合并后的块在更大一级链表中是否有伙伴存在,直到不能合并或者已经合并到了最大的块(222222222个页面)。

slab机制

slab是Linux操作系统的一种内存分配机制。其工作是针对一些经常分配并释放的对象,如进程描述符等,这些对象的大小一般比较小,如果直接采用伙伴系统来进行分配和释放,不仅会造成大量的内碎片,而且处理速度也太慢。而slab分配器是基于对象进行管理的,相同类型的对象归为一类(如进程描述符就是一类),每当要申请这样一个对象,slab分配器就从一个slab列表中分配一个这样大小的单元出去,而当要释放时,将其重新保存在该列表中,而不是直接返回给伙伴系统,从而避免这些内碎片。slab分配器并不丢弃已分配的对象,而是释放并把它们保存在内存中。当以后又要请求新的对象时,就可以从内存直接获取而不用重复初始化。 

Linux 的slab 可有三种状态:

  • 满的:slab 中的所有对象被标记为使用。
  • 空的:slab 中的所有对象被标记为空闲。
  • 部分:slab 中的对象有的被标记为使用,有的被标记为空闲。

slab 分配器首先从部分空闲的slab 进行分配。如没有,则从空的slab 进行分配。如没有,则从物理连续页上分配新的slab,并把它赋给一个cache ,然后再从新slab 分配空间。

与传统的内存管理模式相比, slab 缓存分配器提供了很多优点。

1、内核通常依赖于对小对象的分配,它们会在系统生命周期内进行无数次分配。

2、slab 缓存分配器通过对类似大小的对象进行缓存而提供这种功能,从而避免了常见的碎片问题。

3、slab 分配器还支持通用对象的初始化,从而避免了为同一目的而对一个对象重复进行初始化。

4、slab 分配器还可以支持硬件缓存对齐和着色,这允许不同缓存中的对象占用相同的缓存行,从而提高缓存的利用率并获得更好的性能。