伙伴算法

伙伴算法是一种将内存对半分割来尽量实现最佳匹配的内存分配算法，由哈里·马科维茨于1963年发明。

示例

在以下示例系统中，最小的内存块大小为64千字节，内存块大小的最大值为4，因此最大的可分配内存块大小为$2^{4}\times 64{\text{ K}}=1024{\text{ K}}$。下面展示了系统在经历多次内存请求后的可能状态。

步骤	64 K	64 K	64 K	64 K	64 K	64 K	64 K	64 K	64 K	64 K	64 K	64 K	64 K	64 K	64 K	64 K
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