首页 » 开发 » 内存分配

Buddy memory allocation

Buddy memory allocation(伙伴内存分配器),又称为伙伴算法、伙伴系统算法等,是一种内存分配算法。分配内存时,将内存块对半切分,直到找到需要的内存块为止;释放时,如果与之配对的内存块是未使用状态,则合并为一个大块,一并回收。

来自维基百科的一个分配实例:

Step 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K 64K
1 24
2.1 23 23
2.2 22 22 23
2.3 21 21 22 23
2.4 20 20 21 22 23
2.5 A: 20 20 21 22 23
3 A: 20 20 B: 21 22 23
4 A: 20 C: 20 B: 21 22 23
5.1 A: 20 C: 20 B: 21 21 21 23
5.2 A: 20 C: 20 B: 21 D: 21 21 23
6 A: 20 C: 20 21 D: 21 21 23
7.1 A: 20 C: 20 21 21 21 23
7.2 A: 20 C: 20 21 22 23
8 20 C: 20 21 22 23
9.1 20 20 21 22 23
9.2 21 21 22 23
9.3 22 22 23
9.4 23 23
9.5 24

内存分配过程说明:

1 - 初始状态。起初总的内存块大小为 24 * 64KB = 1024KB。

2.x - 程序A要求分配34KB的内存。2.1将 24 的内存对半分,形成 2 * 22 的内存;2.2将第1个 22内存对半分,形成 2 * 21 的内存,以此类推,直到分配到最小元素1个64KB(20)的内存块时,内存分配结束。

3 - 程序B要求分配66KB的内存。21 * 64KB 的内存块适合(未分配),内存分配完成。

4 - 程序C要求分配35KB的内存。20 * 64KB 的内存块适合(未分配),内存分配完成。

5.x - 程序D要求分配67KB的内存。21 * 64KB 的内存块适合,但没有找到,因此5.1将22的内存块对半分,5.2将其中第一个分配给程序D。

内存回收过程说明:

6 - 程序B释放内存。直接标记为未使用。

7.x - 程序D释放内存。7.1将D释放的内存标记为未使用,7.2将两块连续的 21 合并为1个 22 内存。

8 - 程序A放内存。直接标记为未使用。

9.x - 程序C放内存。比较复杂的一步,合并连续未使用内存,还原为初始状态。

分享

0