内存分配[二] - Buddy系统的原理

术道经纬 2020-04-17

442

说明：如果对文章有什么疑问，可通过“阅读原文”链接在知乎上给我留言。

上文介绍了内存池，它的分配快速，但这种“事先就划分好”的方法对系统的适应性较差，不同「尺寸」的内存池之间不能“互通有无”。

而buddy分配系统在普通内存池的基础上，允许两个大小相同且相邻的内存块合并，合并之后的内存块的「尺寸」增大，因而将被移动到另一个内存池的free list上。

来看下面这个例子，内存共有1024字节，由32, 64, 128, 256, 512字节为「尺寸」的5个free list组织起来，最小分配单位为32字节（对应位图中的1个bit）。

假设现在0到448字节的内存已使用，448到1024字节的内存为空闲（字母编号从A开始，表示分配顺序）。

那么将A'划分为256字节的E和E'，再将内存块E划分成128字节的F和F'，内存块F即是我们需要的内存。之后，在此过程中产生的E'和F'将分别被挂接到「尺寸」为256字节和128字节的free list上，位图中bits的值也会相应变化。

接下来释放128字节的内存块C，由于C相邻的两个内存块都不是空闲状态，因此不能合并，之后C也将被挂接到「尺寸」为128字节的free list上。

按理合并后的空闲内存块C'为128字节，应该被添加到「尺寸」为128字节的free list上，但因为左侧的C也是空闲的，且C和C'的大小相同，因此C和C'还将合并形成B'，合并后的空闲内存块将被挂接到「尺寸」为256字节的free list上。

但是实现合并有一个前提，就是内存块的尺寸必须是2的幂次方（称为"order"），这也是buddy系统划分内存块的依据。此外，每次内存释放都要查找左右的buddy是否可以合并，还可能需要在free list之间移动，也是一笔不小的开销。

下文将基于Linux内核，介绍buddy内存分配器在一个操作系统中的具体实现。

文章转载自术道经纬，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。