深入理解伙伴算法及其改进

       今天遇到很好的一个腾讯面试官，进一步探讨了伙伴算法，面试官非常nice，对伙伴算法的优缺点详细给我讲了一下，发现这个算法值得深入研究一波~

看了很多资料，下面整理资料，然后谈谈自己的理解。

• 体会

　　Linux操作系统主要的内存分配算法是伙伴系统（Buddy算法），机制是按照2的幂次方进行分块，然后根据需求分配差不多的内存块给使用者，伙伴系统是一个结合了2的方幂个分配器和空闲缓冲区合并计技术的内存分配方案。分配和释放机制十分强大。

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

• 伙伴系统和slab机制[1]

伙伴系统

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

 Buddy算法的释放原理：

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

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 分配器还可以支持硬件缓存对齐和着色，这允许不同缓存中的对象占用相同的缓存行，从而提高缓存的利用率并获得更好的性能。

[1]伙伴系统和slab机制。https://blog.csdn.net/zhouwei1221q/article/details/48242535

[2]Randal E.Bryant,深入理解计算机系统,[M].机械工业出版社