1. 伙伴系统(伙伴算法)

1.1 概览

伙伴系统(buddy system)或者称伙伴算法主要应用在操作系统的内存分配中。在操作系统课程中也是必提的概念。
该算法主要好处是:

  1. 搜索分配内存块较为快速,O(logN)时间复杂度
  2. 外部碎片概率较低: 按2的幂划分,可以理解为一种分层次的Best fit

1.2 分配和释放内存过程

维基百科有个例子可以参考:https://en.wikipedia.org/wiki/Buddy_memory_allocation

总体思想就是:分配内存的时候按照基本内存块大小,按照2的幂来分裂,直到best fit满足; 释放内存就是个字底向上的的判断过程,做内存块合并

1.3 实现方式

通过其算法思想,很容易联想到用完全二叉树来实现。


图片引用自:https://coolshell.cn/articles/10427.html

2. slab机制

参考资料:https://en.wikipedia.org/wiki/Slab_allocation
在伙伴系统中,slab机制主要用于解决kernel objects的频繁创建和销毁造成的内存内部碎片问题。外部碎片通过伙伴算法已经大大减少了。

主要思想

对OS层面的内存分配采用“对象池化”的思路,这样内存分配时kernel object的初始化和销毁过程可以省略了。实际上就是根据object type来做预分配,从资源池按类型分配内存,大大减少了内部碎片。

slab allocator负责分配内存,它会提前准备内核对象池供使用时分配。