伙伴系统：一种有效的动态内存管理方法
2021-07-036.7k 阅读
伙伴系统概述
在操作系统的内存管理中，动态内存分配是一项关键任务。它需要在程序运行时高效地分配和回收内存块，以满足不同程序的内存需求。伙伴系统（Buddy System）作为一种有效的动态内存管理方法，被广泛应用于操作系统内核以及一些特定的内存分配场景中。
伙伴系统的基本思想是将内存空间按照一定的规则进行划分和合并。内存空间被视为一个完整的大内存块，然后根据需求逐步分割成较小的块来满足内存分配请求。当内存块被释放时，如果其伙伴也处于空闲状态，那么这两个伙伴块可以合并成一个更大的块，以提高内存的利用率。
伙伴系统的内存划分
伙伴系统首先将可用内存划分为不同大小的内存块。通常，内存块的大小是 2 的幂次方，例如 2^0、2^1、2^2、2^3 等等。这种划分方式使得内存块的管理和合并变得更加简单和高效。
假设我们有一个初始大小为 2^n 的内存块，它可以被划分为两个大小为 2^(n - 1) 的子块。这两个子块就被称为伙伴。同样，每个大小为 2^(n - 1) 的子块又可以继续划分为两个大小为 2^(n - 2) 的子块，以此类推。
例如，初始内存块大小为 1024 字节（2^10），它可以被划分为两个 512 字节（2^9）的伙伴块。每个 512 字节的块又可以进一步划分为两个 256 字节（2^8）的伙伴块，依此类推。
伙伴系统的数据结构
为了实现伙伴系统，需要设计合适的数据结构来管理内存块。常见的数据结构包括链表和数组。
- 链表结构：可以使用链表来存储不同大小的空闲内存块。每个链表节点表示一个空闲内存块，节点中包含内存块的大小、地址以及指向下一个节点的指针。不同大小的内存块分别存储在不同的链表中，这样在分配和回收内存时，可以快速定位到合适大小的空闲块。
// 链表节点结构体
typedef struct FreeBlock {
size_t size;
void *address;
struct FreeBlock *next;
} FreeBlock;
// 不同大小内存块的链表头
FreeBlock *freeLists[LOG2_MAX_SIZE];
- 数组结构：数组也可以用于存储空闲内存块的信息。数组的每个元素可以对应一个特定大小的内存块集合。数组元素可以是指向该大小空闲内存块链表的头指针，或者直接存储内存块的地址和状态信息。
// 数组存储空闲内存块信息
struct {
size_t size;
void *address;
int isFree;
} memoryBlocks[NUM_BLOCKS];
伙伴系统的内存分配
当程序请求分配内存时，伙伴系统需要找到一个合适大小的空闲内存块来满足请求。
分配算法步骤
- 确定所需内存块大小：根据程序的内存请求大小，确定所需内存块的最小 2 的幂次方大小。例如，如果请求 100 字节的内存，由于 64（2^6） < 100 < 128（2^7），则需要一个大小为 128 字节的内存块。
- 查找空闲链表：在对应的空闲链表中查找是否有合适大小的空闲内存块。如果找到了，则直接分配该内存块，并从空闲链表中移除。
- 分割内存块：如果对应的空闲链表为空，则需要从更大的空闲内存块中进行分割。从较大的空闲内存块链表中找到一个合适的块，将其分割成两个伙伴块，一个用于分配，另一个放入相应大小的空闲链表中。如果分割后的伙伴块仍然太大，可能需要继续分割，直到得到合适大小的内存块。
代码示例
以下是一个简单的 C 语言示例，演示伙伴系统的内存分配过程：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LOG2_MAX_SIZE 10
#define MAX_SIZE (1 << LOG2_MAX_SIZE)
typedef struct FreeBlock {
size_t size;
void *address;
struct FreeBlock *next;
} FreeBlock;
FreeBlock *freeLists[LOG2_MAX_SIZE];
// 初始化伙伴系统
void initBuddySystem() {
for (int i = 0; i < LOG2_MAX_SIZE; i++) {
freeLists[i] = NULL;
}
// 初始化最大内存块
FreeBlock *initialBlock = (FreeBlock *)malloc(sizeof(FreeBlock));
initialBlock->size = MAX_SIZE;
initialBlock->address = (void *)malloc(MAX_SIZE);
initialBlock->next = NULL;
freeLists[LOG2_MAX_SIZE - 1] = initialBlock;
}
// 查找所需内存块大小的索引
int findIndex(size_t size) {
int index = 0;
while (size > (1 << index)) {
index++;
}
return index;
}
// 分配内存
void *buddyAlloc(size_t size) {
int index = findIndex(size);
FreeBlock *block = freeLists[index];
if (block!= NULL) {
freeLists[index] = block->next;
return block->address;
} else {
for (int i = index + 1; i < LOG2_MAX_SIZE; i++) {
if (freeLists[i]!= NULL) {
FreeBlock *largerBlock = freeLists[i];
freeLists[i] = largerBlock->next;
size_t blockSize = largerBlock->size;
while (blockSize > (1 << index)) {
blockSize /= 2;
FreeBlock *newBlock = (FreeBlock *)malloc(sizeof(FreeBlock));
newBlock->size = blockSize;
newBlock->address = (char *)largerBlock->address + blockSize;
newBlock->next = freeLists[i - 1];
freeLists[i - 1] = newBlock;
i--;
}
return largerBlock->address;
}
}
}
return NULL;
}
伙伴系统的内存回收
当程序释放不再使用的内存块时，伙伴系统需要将这些内存块正确地回收并合并，以提高内存利用率。
回收算法步骤
- 确定回收内存块的大小：根据回收内存块的地址，查找其在内存空间中的位置和大小信息。
- 查找伙伴内存块：根据内存块的大小和地址，计算其伙伴内存块的地址。如果伙伴内存块也处于空闲状态，则将这两个伙伴块合并成一个更大的块。
- 合并和插入空闲链表：将合并后的内存块插入到相应大小的空闲链表中。如果合并后的块还可以与其他空闲伙伴块继续合并，则重复合并操作，直到无法合并为止。
代码示例
以下是回收内存的代码示例：
// 计算伙伴内存块地址
void *getBuddyAddress(void *address, size_t size) {
char *baseAddress = (char *)address;
char *buddyAddress = baseAddress ^ size;
return (void *)buddyAddress;
}
// 回收内存
void buddyFree(void *address) {
for (int i = 0; i < LOG2_MAX_SIZE; i++) {
for (FreeBlock *block = freeLists[i]; block!= NULL; block = block->next) {
if (block->address == address) {
size_t size = block->size;
void *buddyAddress = getBuddyAddress(address, size);
int buddyIndex = findIndex(size);
for (FreeBlock *buddyBlock = freeLists[buddyIndex]; buddyBlock!= NULL; buddyBlock = buddyBlock->next) {
if (buddyBlock->address == buddyAddress) {
// 合并伙伴块
FreeBlock *newBlock = (FreeBlock *)malloc(sizeof(FreeBlock));
newBlock->size = size * 2;
newBlock->address = (char *)address < (char *)buddyAddress? address : buddyAddress;
newBlock->next = freeLists[buddyIndex + 1];
freeLists[buddyIndex + 1] = newBlock;
// 移除伙伴块链表节点
if (buddyBlock == freeLists[buddyIndex]) {
freeLists[buddyIndex] = buddyBlock->next;
} else {
FreeBlock *prev = freeLists[buddyIndex];
while (prev->next!= buddyBlock) {
prev = prev->next;
}
prev->next = buddyBlock->next;
}
free(buddyBlock);
// 移除当前块链表节点
if (block == freeLists[i]) {
freeLists[i] = block->next;
} else {
FreeBlock *prev = freeLists[i];
while (prev->next!= block) {
prev = prev->next;
}
prev->next = block->next;
}
free(block);
// 递归合并
buddyFree(newBlock->address);
return;
}
}
// 没有找到伙伴块，直接插入空闲链表
FreeBlock *newBlock = (FreeBlock *)malloc(sizeof(FreeBlock));
newBlock->size = size;
newBlock->address = address;
newBlock->next = freeLists[i];
freeLists[i] = newBlock;
return;
}
}
}
}
伙伴系统的优缺点
优点
- 高效的内存分配和回收：伙伴系统通过将内存划分为 2 的幂次方大小的块，并采用链表或数组等数据结构进行管理，使得内存分配和回收操作的时间复杂度相对较低。在分配内存时，可以快速定位到合适大小的空闲块或通过分割较大块来满足需求；在回收内存时，可以高效地合并伙伴块，提高内存利用率。
- 减少内存碎片：由于内存块的大小是 2 的幂次方，并且在回收时能够合并伙伴块，因此伙伴系统能够有效地减少外部碎片的产生。与其他动态内存管理方法相比，伙伴系统可以更好地保持内存的连续性，使得较大的内存请求更容易得到满足。
- 简单易实现：伙伴系统的原理和算法相对简单，易于理解和实现。其数据结构和操作逻辑较为清晰，在操作系统内核或特定应用场景中实现伙伴系统的成本较低。
缺点
- 内部碎片问题：由于内存块的大小必须是 2 的幂次方，当程序请求的内存大小不是 2 的幂次方时，会分配比实际需求大的内存块，从而产生内部碎片。例如，程序请求 50 字节的内存，伙伴系统可能会分配 64 字节的内存块，导致 14 字节的内部碎片。
- 内存块大小限制：伙伴系统中内存块的大小被限制为 2 的幂次方，这可能无法满足某些对内存大小有特殊要求的应用场景。例如，某些应用可能需要固定大小为 100 字节的内存块，伙伴系统无法直接提供这样大小的块，可能需要进行额外的处理。
- 链表管理开销：如果采用链表结构来管理空闲内存块，链表节点的维护和遍历会带来一定的开销。特别是在内存块数量较多时，链表操作的时间复杂度会增加，影响内存管理的性能。
伙伴系统在操作系统中的应用
伙伴系统在许多操作系统内核中都有应用，例如 Linux 内核。
Linux 内核中的伙伴系统
Linux 内核的内存管理子系统使用伙伴系统来管理物理内存。它将物理内存划分为不同大小的页框（通常为 4KB），并通过伙伴系统算法来分配和回收页框。
- 内存区域划分：Linux 内核将物理内存划分为不同的内存区域，如 ZONE_DMA、ZONE_NORMAL 和 ZONE_HIGHMEM。每个区域都有自己的伙伴系统实例，用于管理该区域内的内存。
- 数据结构：Linux 内核使用数组和链表相结合的数据结构来管理伙伴系统。每个内存区域都有一个 struct zone 结构体，其中包含了不同大小空闲页框链表的指针。
- 分配和回收操作：当内核需要分配内存时，会调用伙伴系统的分配函数，根据请求的页框数量找到合适大小的空闲页框块。如果没有合适大小的块，则会从较大的块中进行分割。在回收内存时，内核会将释放的页框块合并到伙伴系统中，以提高内存利用率。
其他操作系统中的应用
除了 Linux 内核，其他操作系统如 Windows 内核也在一定程度上借鉴了伙伴系统的思想来优化内存管理。虽然具体的实现细节可能有所不同，但基本的动态内存分配和回收原理是相似的。
在一些嵌入式操作系统中，由于资源有限，伙伴系统的简单高效特性使其成为一种理想的内存管理方法。嵌入式系统可以根据具体需求对伙伴系统进行定制化实现，以满足特定应用场景的内存管理需求。
伙伴系统的改进和扩展
为了克服伙伴系统的一些缺点，研究人员提出了许多改进和扩展方法。
改进内部碎片问题
- 可变大小块分配：一种改进方法是允许分配非 2 的幂次方大小的内存块。可以在伙伴系统的基础上，结合其他内存分配算法，如 slab 分配器。当程序请求的内存大小不是 2 的幂次方时，先尝试从伙伴系统中分配一个稍大的 2 的幂次方大小的块，然后使用 slab 分配器在这个块内进行更细粒度的分配，以减少内部碎片。
- 自适应块大小调整：根据内存使用情况动态调整内存块的大小。例如，可以统计不同大小内存请求的频率，对于频繁请求的非 2 的幂次方大小，创建特定大小的内存块池，以满足这些请求，从而减少内部碎片。
优化链表管理开销
- 哈希表辅助：可以使用哈希表来辅助链表管理空闲内存块。通过哈希表可以快速定位到可能包含合适大小空闲块的链表，减少链表的遍历次数，提高内存分配和回收的效率。
- 分层链表结构：采用分层链表结构，将空闲内存块按照不同的范围进行分层管理。例如，将较小的内存块放在一层链表中，较大的内存块放在另一层链表中。这样在查找和合并内存块时，可以减少链表的长度和遍历时间。
扩展功能
- 支持内存映射：在伙伴系统的基础上扩展支持内存映射功能，使得程序可以将文件或设备映射到内存中。这可以通过在伙伴系统的数据结构中增加对内存映射区域的管理来实现。
- 多线程支持：对于多线程环境，改进伙伴系统以支持并发的内存分配和回收操作。可以采用锁机制或无锁数据结构来确保多线程访问伙伴系统时的一致性和正确性。
总结伙伴系统与其他内存管理方法的比较
与固定分区分配的比较
- 内存利用率：固定分区分配将内存划分为固定大小的分区，容易产生内部碎片，特别是当程序的内存需求与分区大小不匹配时。而伙伴系统通过动态分割和合并内存块，能够更好地适应不同大小的内存请求，减少内部碎片，提高内存利用率。
- 灵活性：固定分区分配在系统运行前就确定了分区的大小和数量，缺乏灵活性。伙伴系统则可以根据程序的实际需求动态分配和回收内存块，更加灵活。
- 实现复杂度：固定分区分配的实现相对简单，而伙伴系统由于需要管理不同大小的内存块以及进行分割和合并操作，实现复杂度较高。
与可变分区分配的比较
- 碎片问题：可变分区分配虽然可以根据程序需求分配任意大小的内存块，但容易产生外部碎片。伙伴系统通过采用 2 的幂次方大小的内存块和伙伴合并机制，能有效减少外部碎片。
- 分配效率：可变分区分配在分配内存时需要遍历整个空闲分区表来找到合适的分区，时间复杂度较高。伙伴系统通过链表或数组等数据结构，可以更快速地定位到合适大小的空闲块，分配效率相对较高。
- 回收复杂度：可变分区分配在回收内存时，需要处理与相邻空闲分区的合并问题，操作较为复杂。伙伴系统的回收操作相对简单，只要找到伙伴块并进行合并即可。
与 slab 分配器的比较
- 应用场景：slab 分配器主要用于频繁分配和释放相同大小对象的场景，通过预先创建对象缓存来提高分配效率。伙伴系统更适用于对不同大小内存块有动态分配和回收需求的场景。
- 内存管理粒度：slab 分配器在对象级别进行内存管理，粒度更细；伙伴系统在内存块级别进行管理，粒度相对较粗。
- 结合使用：在实际的操作系统中，常常将伙伴系统和 slab 分配器结合使用。伙伴系统负责分配较大的内存块，然后 slab 分配器在这些块内进行更细粒度的对象分配，以充分发挥两者的优势。
伙伴系统作为一种有效的动态内存管理方法，在操作系统的内存管理中具有重要地位。虽然它存在一些缺点，但通过改进和与其他内存管理方法的结合，可以更好地满足不同应用场景的内存管理需求。