深入解析Buddy分配器：原理、实现与优化

1. Buddy分配器概述

Buddy分配器是一种经典的内存管理算法，最早由Harry Markowitz在1964年提出。它通过将物理内存划分为大小相等的块，并采用"伙伴系统"的方式管理这些内存块，从而高效地处理内存分配与释放请求。这种分配器在操作系统内核中广泛应用，比如Linux内核就使用Buddy系统来管理物理页面。

Buddy分配器的核心思想是将可用内存划分为2的幂次方大小的块。当请求分配内存时，系统会寻找最适合请求大小的块。如果找不到正好大小的块，就会将一个较大的块一分为二，这两个子块就称为"伙伴"。这种分裂过程会递归进行，直到得到合适大小的块为止。

关键特性：Buddy分配器特别适合处理频繁的小内存分配请求，因为它能有效减少外部碎片，同时保持较高的分配效率。

2. Buddy分配器的工作原理

2.1 内存块的组织结构

Buddy分配器将可用内存视为一系列大小不同的块，每个块的大小都是2的幂次方（如4KB、8KB、16KB等）。这些块被组织成多个链表，每个链表对应一个特定大小的块：

• 4KB块链表
• 8KB块链表
• 16KB块链表
• ...
• 最大块链表

当系统启动时，所有可用内存最初都在最大块的链表中。随着分配请求的到来，这些大块会被不断分割成更小的块。

2.2 分配算法详解

当收到一个内存分配请求时，Buddy分配器的工作流程如下：

1. 计算请求大小的最小2的幂次方上界。例如，请求5KB内存，会向上取整到8KB。
2. 检查对应大小的空闲链表：
   • 如果有可用块，直接分配
   • 如果没有，则尝试从更大的块链表获取
3. 如果更大的块也没有，继续向上查找，直到找到可用的块
4. 将找到的大块不断二分，直到得到所需大小的块
5. 将分割后剩余的块放入相应大小的空闲链表

例如，假设系统当前只有1个16KB的块，而请求分配5KB内存：

1. 计算得到需要8KB块
2. 16KB块被分割为两个8KB伙伴
3. 其中一个8KB块被分配，另一个8KB块保留在空闲链表

2.3 释放与合并机制

当内存被释放时，Buddy分配器会尝试将释放的块与其伙伴块合并：

1. 检查释放块的伙伴块是否也在空闲状态
2. 如果是，则将两个伙伴块合并为一个大块
3. 递归检查新合并的块是否可以继续与它的伙伴合并
4. 最终将合并后的大块放入相应大小的空闲链表

这种合并机制能有效减少内存碎片，保持内存的连续性。

3. Buddy分配器的实现细节

3.1 数据结构设计

典型的Buddy分配器实现需要以下核心数据结构：

struct free_area { struct list_head free_list; // 空闲块链表 unsigned long nr_free; // 空闲块数量 }; #define MAX_ORDER 11 // 最大块大小(2^10 * PAGE_SIZE) struct zone { // ...其他字段 struct free_area free_area[MAX_ORDER]; // 各阶空闲块 };

每个free_area对应一个特定大小的块链表。MAX_ORDER定义了系统支持的最大块大小。

3.2 关键操作函数

分配函数实现

struct page *alloc_pages(gfp_t gfp_mask, unsigned int order) { struct page *page = NULL; struct zone *zone; // 遍历所有内存区域 for_each_zone(zone) { // 从请求的order开始查找 for (current_order = order; current_order < MAX_ORDER; ++current_order) { if (!list_empty(&zone->free_area[current_order].free_list)) { page = list_entry(zone->free_area[current_order].free_list.next, struct page, lru); list_del(&page->lru); zone->free_area[current_order].nr_free--; // 分割大块 while (current_order > order) { current_order--; buddy = page + (1 << current_order); list_add(&buddy->lru, &zone->free_area[current_order].free_list); zone->free_area[current_order].nr_free++; } return page; } } } return NULL; }

释放函数实现

void free_pages(struct page *page, unsigned int order) { struct zone *zone = page_zone(page); unsigned long page_idx; struct page *buddy; while (order < MAX_ORDER - 1) { page_idx = page_to_pfn(page) ^ (1 << order); buddy = pfn_to_page(page_idx); // 检查伙伴是否空闲且同阶 if (!page_is_buddy(buddy, order)) break; // 合并伙伴块 list_del(&buddy->lru); zone->free_area[order].nr_free--; if (page_idx < page_to_pfn(page)) page = buddy; order++; } // 将合并后的块加入空闲链表 list_add(&page->lru, &zone->free_area[order].free_list); zone->free_area[order].nr_free++; }

3.3 伙伴块的查找算法

伙伴块的地址可以通过简单的位运算得到：

伙伴地址 = 块地址 ^ (1 << order)

其中，order表示块的大小阶数。这个特性使得伙伴查找非常高效，不需要复杂的计算或查找操作。

4. Buddy分配器的性能优化

4.1 分配策略优化

在实际系统中，Buddy分配器可以采用多种分配策略来提高性能：

1. 首次适应：从最低阶开始查找，找到第一个可用的块
2. 最佳适应：查找最接近请求大小的可用块
3. 最差适应：总是从最大可用块开始分配

Linux内核默认采用首次适应策略，因为它实现简单且效率较高。

4.2 内存预取优化

为了减少分配延迟，可以预先分割一些大块：

void prep_new_page(struct page *page, unsigned int order) { // 预分割高阶内存块 if (order > 0) { unsigned long size = 1 << (order - 1); struct page *buddy = page + size; list_add(&buddy->lru, &zone->free_area[order-1].free_list); zone->free_area[order-1].nr_free++; } }

4.3 缓存对齐优化

对于需要缓存对齐的内存请求，可以调整分配策略：

struct page *alloc_pages_aligned(gfp_t gfp_mask, unsigned int order, unsigned int align_order) { struct page *page = alloc_pages(gfp_mask, order + align_order); if (page) { unsigned long align_mask = (1 << align_order) - 1; unsigned long aligned_addr = (page_to_pfn(page) + align_mask) & ~align_mask; struct page *aligned_page = pfn_to_page(aligned_addr); // 释放不需要的前后部分 if (aligned_page != page) free_pages(page, align_order); if (aligned_page + (1 << order) != page + (1 << (order + align_order))) free_pages(aligned_page + (1 << order), align_order); return aligned_page; } return NULL; }

5. Buddy分配器的实际应用

5.1 Linux内核中的实现

Linux内核的Buddy分配器主要管理物理页面，关键实现位于mm/page_alloc.c中。主要特点包括：

1. 支持多种内存区域（DMA、NORMAL、HIGHMEM）
2. 与每CPU页框缓存配合使用
3. 支持内存压缩和迁移
4. 实现了水位线机制防止内存耗尽

5.2 与其他内存分配器的配合

Buddy分配器通常不直接面向应用层，而是作为底层分配器为其他高级分配器提供支持：

1. Slab分配器：用于小对象分配，建立在Buddy分配的页面上
2. kmalloc：内核通用内存分配接口，底层使用Slab或Buddy
3. vmalloc：分配虚拟连续但物理不连续的内存

5.3 性能调优参数

Linux内核提供了一些sysctl参数用于调优Buddy分配器：

# 查看当前内存信息 cat /proc/buddyinfo # 调整水位线参数 sysctl -w vm.min_free_kbytes=65536 # 调整页面回收策略 sysctl -w vm.swappiness=60

6. 常见问题与解决方案

6.1 内存碎片问题

虽然Buddy系统能减少外部碎片，但仍可能产生内部碎片。解决方案包括：

1. 内存压缩：定期移动已分配页面以合并空闲块
2. 页面迁移：将页面移动到其他NUMA节点或区域
3. 内存规整：内核的kswapd和kcompactd线程

6.2 分配失败排查

当alloc_pages返回NULL时，可以采取以下步骤：

1. 检查/proc/buddyinfo确认内存碎片情况
2. 使用vmstat -s查看内存统计
3. 检查dmesg是否有OOM killer活动
4. 调整vm.min_free_kbytes增加保留内存

6.3 NUMA架构下的优化

在NUMA系统中，Buddy分配器需要特别处理：

1. 为每个NUMA节点维护独立的Buddy系统
2. 实现节点间的页面迁移
3. 优化分配策略，优先从本地节点分配

struct page *alloc_pages_node(int nid, gfp_t gfp_mask, unsigned int order) { // 优先从指定节点分配 if (node_online(nid) && node_present_pages(nid)) return __alloc_pages_node(nid, gfp_mask, order); // 回退到其他节点 return alloc_pages(gfp_mask, order); }

7. 高级话题与扩展

7.1 大页支持

现代Buddy分配器支持大页(Huge Page)分配：

struct page *alloc_huge_page(int order) { // 尝试从高阶空闲链表直接分配 for (current_order = order; current_order < MAX_ORDER; ++current_order) { if (!list_empty(&zone->free_area[current_order].free_list)) { page = list_entry(zone->free_area[current_order].free_list.next, struct page, lru); list_del(&page->lru); zone->free_area[current_order].nr_free--; return page; } } return NULL; }

7.2 内存热插拔

支持运行时内存添加/移除：

1. 内存上线：将新内存区域加入Buddy系统
2. 内存下线：将内存区域从Buddy系统移除
3. 隔离区域：将内存标记为不可分配

7.3 虚拟化环境优化

在虚拟化环境中，Buddy分配器需要：

1. 支持balloon驱动调整客户机内存
2. 优化页面回收策略
3. 实现内存超配(overcommit)

8. 实现注意事项

在实际实现Buddy分配器时，需要注意以下关键点：

1. 并发控制：分配和释放操作需要适当的锁保护
2. 错误处理：处理内存不足等边界条件
3. 性能监控：实现统计信息收集
4. 调试支持：添加调试信息和检查机制

一个健壮的实现应该包含以下安全检查：

static inline bool page_is_buddy(struct page *page, unsigned int order) { // 检查页面标志 if (PageBuddy(page) && page_order(page) == order) { // 检查页面是否在正确的空闲链表中 struct zone *zone = page_zone(page); struct free_area *area = &zone->free_area[order]; struct page *tmp; list_for_each_entry(tmp, &area->free_list, lru) { if (tmp == page) return true; } } return false; }

Buddy分配器作为操作系统内存管理的基石，其设计和实现直接影响整个系统的性能和稳定性。理解其工作原理和优化技巧，对于系统级开发人员和内核开发者都至关重要。在实际项目中，应根据具体需求调整分配策略和参数，以达到最佳的性能和资源利用率。