当前位置：首页 > news >正文

超越first-fit：从ucore Lab 2出发，聊聊伙伴系统（Buddy System）与SLUB分配器的设计与实现思路

news 2026/6/1 19:56:31

从First-Fit到伙伴系统：现代内存管理算法的深度解析

在操作系统的核心组件中，内存管理子系统扮演着至关重要的角色。从早期简单的连续内存分配策略到现代操作系统采用的复杂分层机制，内存管理算法的演进反映了计算机系统对效率和资源利用率的不懈追求。本文将带您深入探索从基础实验到生产级系统的内存管理技术演进路径。

1. 从ucore实验看内存管理基础

在ucore Lab 2实验中，first-fit算法作为物理内存管理的入门实现，展示了最基础的内存分配策略。这个算法维护一个按地址排序的空闲内存块链表，当收到分配请求时，它会沿着链表扫描，找到第一个足够大的空闲块来满足请求。

first-fit的核心数据结构包括：

struct Page { int ref; // 页帧引用计数器 uint32_t flags; // 描述页帧状态的标志位 unsigned int property; // 空闲块中的页数 list_entry_t page_link; // 空闲链表链接 }; typedef struct { list_entry_t free_list; // 链表头 unsigned int nr_free; // 空闲页总数 } free_area_t;

这种实现虽然简单直观，但存在明显的效率问题：

分配和释放操作的时间复杂度为O(n)，随着内存块数量增加性能下降明显
容易产生外部碎片，虽然通过合并相邻空闲块可以缓解，但无法完全消除
对大块内存的分配效率较低，需要遍历大量小块

有趣的是，这种简单算法在某些特定场景下仍然有其用武之地，特别是在资源极度受限的嵌入式系统中，它的低开销和可预测性反而成为优势。

2. 伙伴系统：高效的内存管理艺术

伙伴系统(Buddy System)算法是现代操作系统中广泛采用的内存管理技术，它通过巧妙的完全二叉树结构实现了高效的内存分配与回收。

2.1 伙伴系统的核心思想

伙伴系统将内存划分为大小均为2的n次幂的块，形成一个分层的管理结构。这种设计带来了几个关键优势：

快速合并与分割：只需要简单的位操作即可完成
高效搜索：通过二叉树结构实现O(logN)的搜索复杂度
低外部碎片：最佳适配策略减少了内存浪费

伙伴系统的关键操作：

操作类型	处理逻辑	时间复杂度
分配	从合适大小的块开始查找，若无则分裂大块	O(logN)
释放	释放后检查伙伴块是否空闲，是则合并	O(logN)

2.2 完全二叉树的管理机制

伙伴系统使用数组形式的完全二叉树来管理内存块，这种设计极具巧思：

每个节点代表一个内存块
高层节点对应大块，低层节点对应小块
节点标记指示块的使用状态

// 简化的伙伴系统数据结构 struct buddy { unsigned size; // 管理的内存总大小 unsigned longest[1]; // 扩展数组，记录各块的空闲状态 };

分配示例：

请求3单位内存 → 实际分配4单位块
从16单位块开始，对半分割两次得到4单位块
标记相应节点为已分配

释放示例：

释放4单位块
检查其伙伴块(相邻的4单位块)是否空闲
若空闲则合并为8单位块，并递归检查更高层

2.3 内部碎片与优化策略

伙伴系统最大的缺点是可能产生内部碎片，特别是当请求大小不是2的幂时。例如请求66单位内存，必须分配128单位块，浪费62单位。

缓解策略：

slab分配器：在伙伴系统基础上构建更细粒度的分配
大小分级：将相近大小归类到同一级别
预分配：针对常见大小预先准备特定块

3. SLUB分配器：小对象的高效管理

SLUB分配器作为Linux内核默认的内存分配器，构建在伙伴系统之上，专门优化小内存对象的分配效率。

3.1 两层架构设计

SLUB采用分层管理策略：

底层：伙伴系统负责页框级分配
上层：SLUB管理对象级分配

核心数据结构：

struct kmem_cache { struct kmem_cache_cpu __percpu *cpu_slab; // 每CPU缓存 unsigned long flags; // 标志位 int size; // 对象大小 int object_size; // 实际对象大小 struct kmem_cache_node *node[MAX_NUMNODES]; // 节点数据 }; struct kmem_cache_cpu { void **freelist; // 空闲对象指针 struct page *page; // 当前活动的slab页 };

3.2 分配与释放流程

分配路径：

首先尝试从CPU本地freelist获取对象
若本地无可用对象，从partial slab补充
若无partial slab，则从伙伴系统分配新slab

释放路径：

对象返回到CPU本地freelist
当slab完全空闲时，考虑返还给伙伴系统
维护partial slab列表以平衡内存使用

3.3 性能优化技巧

SLUB通过多种技术实现高效管理：

每CPU缓存：减少锁争用
slab状态跟踪：
- Full：无空闲对象
- Partial：部分使用
- Empty：完全空闲
指针复用：利用空闲对象空间存储管理信息

4. 从理论到实践：在ucore中实现高级分配器

将伙伴系统或SLUB集成到ucore中，需要对现有框架进行多方面的扩展。

4.1 框架修改要点

数据结构扩展：
- 添加buddy或slub特定的管理结构
- 修改page结构增加必要字段
接口适配：

struct pmm_manager { const char *name; void (*init)(void); void (*init_memmap)(struct Page *base, size_t n); struct Page *(*alloc_pages)(size_t n); void (*free_pages)(struct Page *base, size_t n); size_t (*nr_free_pages)(void); };