首页 > 代码库 > 堆管理算法中的Buddy System(伙伴系统)算法
堆管理算法中的Buddy System(伙伴系统)算法
在一个Buddy System算法中,堆管理者只分配特定大小的内存块,成为permitted size。针对每个permitted size,都有一个空闲链表来维护。
一般这些大小会选择2的幂次方,或者斐波那契数列。因为这样会方便地将除最小的那个数之外的其它数都分为两个permitted size之和。
当负责分配内存的堆管理者接受到请求s大小的内存请求时,会讲s对齐到一个permitted size。然后从那个permitted size的空闲链表中分配一块内存给他。如果没有在那个空闲链表中找到内存,就在大一级的内存中找一块内存分配给用户,然后将剩余的另一半挂到这个permitted size的空闲链表中。
这个算法中的空闲链表一般采用位图(bitmap)算法来实现。因为这样会使内存回收合并变得很高效。
在Zend引擎中的堆管理算法中就使用到了伙伴系统算法,我们来看一下zend_mm_heap结构中相关的数据结构:
zend_mm_free_block *free_buckets[ZEND_MM_NUM_BUCKETS*2];
这个 free_buckets 就是一个空闲链表的二位数组。ZEND_MM_NUM_BUCKETS 定义了分配时最大的幂值。每一个幂值都对应一个 *free_buckets,就是一个空闲链表。
堆管理算法中的Buddy System(伙伴系统)算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。