Browsed by
标签: Buddy

伙伴分配器的一个极简实现

伙伴分配器的一个极简实现

(感谢网友 @我的上铺叫路遥 投稿)

提起buddy system相信很多人不会陌生,它是一种经典的内存分配算法,大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现,而仅仅是将该算法抽象提取出来,同时给出一份及其简洁的源码实现,以便定制扩展。

伙伴分配的实质就是一种特殊的“分离适配”,即将内存按2的幂进行划分,相当于分离出若干个块大小一致的空闲链表,搜索该链表并给出同需求最佳匹配的大小。其优点是快速搜索合并(O(logN)时间复杂度)以及低外部碎片(最佳适配best-fit);其缺点是内部碎片,因为按2的幂划分块,如果碰上66单位大小,那么必须划分128单位大小的块。但若需求本身就按2的幂分配,比如可以先分配若干个内存池,在其基础上进一步细分就很有吸引力了。

可以在维基百科上找到该算法的描述,大体如是:

分配内存:

1.寻找大小合适的内存块(大于等于所需大小并且最接近2的幂,比如需要27,实际分配32)

1.如果找到了,分配给应用程序。
2.如果没找到,分出合适的内存块。

1.对半分离出高于所需大小的空闲内存块
2.如果分到最低限度,分配这个大小。
3.回溯到步骤1(寻找合适大小的块)
4.重复该步骤直到一个合适的块

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (19 人打了分,平均分: 4.21 )
Loading...