图解First-Fit算法：手把手带你实现ucore Lab 2的物理内存分配器

可视化拆解First-Fit算法：从链表操作到内存分配器实现

在操作系统的内存管理模块中，物理内存分配器是最基础的组件之一。First-Fit算法作为最简单的连续内存分配策略，其核心思想却体现了内存管理的关键问题。本文将通过图解方式，带你深入理解ucore Lab 2中物理内存分配器的实现细节。

1. 物理内存管理的核心数据结构

在ucore操作系统中，物理内存管理依赖于几个关键数据结构，它们共同构成了内存分配的基础框架。

1.1 Page结构：物理页的身份证

每个物理页面对应一个Page结构体，这是内存管理的最小单位：

struct Page { int ref; // 页帧引用计数器 uint32_t flags; // 描述页帧状态的标志位 unsigned int property; // 空闲块中的页数(用于first-fit) list_entry_t page_link; // 空闲链表链接 };

关键字段解析：

• ref：记录该物理页被页表引用的次数，当ref为0时表示页面可被回收
• flags：包含两个重要标志位
  • PG_reserved：标记为1表示该页被保留，不能被分配
  • PG_property：标记为1表示该页是空闲块的头页
• property：仅对头页有效，记录该空闲块包含的连续空闲页数
• page_link：用于将空闲页链接到双向链表中

1.2 free_area_t：空闲内存块管理器

所有空闲内存块通过free_area_t结构进行统一管理：

typedef struct { list_entry_t free_list; // 空闲链表头 unsigned int nr_free; // 空闲页的总数 } free_area_t;

这个结构维护了一个按地址排序的空闲页链表，以及当前系统中空闲页的总数。链表中的每个节点都是一个Page结构的page_link成员。

2. First-Fit算法原理图解

First-Fit算法的核心思想是：从空闲链表头部开始扫描，找到第一个足够大的空闲块进行分配。让我们通过图示来理解这一过程。

2.1 初始内存状态

假设系统初始时有16个连续空闲页，其状态如下：

空闲链表： [块A:16页]

图示表示：

[块A:16页(start=0x1000, property=16)] -> NULL

2.2 分配4个页面

当请求分配4个页面时，算法执行流程：

1. 从链表头开始扫描，发现块A有16页，满足需求
2. 将块A拆分为两部分：
   • 分配的4页（0x1000-0x13FF）
   • 剩余的12页形成新块B（0x1400开始）

分配后状态：

空闲链表： [块B:12页(start=0x1400, property=12)]

2.3 再分配6个页面

接下来请求分配6个页面：

1. 扫描发现块B有12页，满足需求
2. 将块B拆分为：
   • 分配的6页（0x1400-0x19FF）
   • 剩余的6页形成块C（0x1A00开始）

状态变化：

空闲链表： [块C:6页(start=0x1A00, property=6)]

2.4 释放第一个4页块

当释放最初分配的4页块（0x1000-0x13FF）时：

1. 系统检查相邻区域：
   • 前驱：无（0x1000是起始地址）
   • 后继：0x1400开始的6页正在使用
2. 由于没有相邻空闲块，直接将这4页作为新块D插入链表

链表状态：

空闲链表： [块D:4页(start=0x1000, property=4)] -> [块C:6页]

2.5 释放6页块后的合并

当释放0x1400-0x19FF的6页块时：

1. 检查相邻区域：
   • 前驱：0x1000开始的4页空闲（块D）
   • 后继：0x1A00开始的6页空闲（块C）
2. 执行合并操作：
   • 先将块D与当前释放的6页合并为10页块
   • 再与块C合并为16页大块

最终状态恢复初始：

空闲链表： [块E:16页(start=0x1000, property=16)]

3. 关键函数实现解析

让我们深入分析ucore中实现First-Fit算法的核心函数。

3.1 default_init_memmap：初始化内存映射

这个函数用于初始化一段连续的空闲内存区域：

static void default_init_memmap(struct Page *base, size_t n) { assert(n > 0); struct Page *p = base; for (; p != base + n; p++) { assert(PageReserved(p)); p->flags = 0; set_page_ref(p, 0); if (p == base) { p->property = n; SetPageProperty(p); } else { p->property = 0; } } list_add_before(&free_list, &(base->page_link)); nr_free += n; }

关键操作：

1. 遍历所有页面，清除保留标志和引用计数
2. 设置头页的property字段为总页数
3. 将头页的page_link插入空闲链表
4. 更新全局空闲页计数

3.2 default_alloc_pages：分配页面

这是内存分配的核心函数：

static struct Page *default_alloc_pages(size_t n) { assert(n > 0); if (n > nr_free) return NULL; struct Page *page = NULL; list_entry_t *le = &free_list; while ((le = list_next(le)) != &free_list) { struct Page *p = le2page(le, page_link); if (p->property >= n) { page = p; break; } } if (page != NULL) { list_del(&(page->page_link)); if (page->property > n) { struct Page *p = page + n; p->property = page->property - n; SetPageProperty(p); list_add(&free_list, &(p->page_link)); } nr_free -= n; ClearPageProperty(page); } return page; }

执行流程：

1. 遍历空闲链表，找到第一个满足大小的块
2. 从链表中移除该块
3. 如果块大于需求，拆分剩余部分重新插入链表
4. 更新空闲页计数
5. 返回分配块的首页指针

3.3 default_free_pages：释放页面

释放内存的核心函数实现了相邻块的合并：

static void default_free_pages(struct Page *base, size_t n) { assert(n > 0); struct Page *p = base; for (; p != base + n; p++) { assert(!PageReserved(p) && !PageProperty(p)); p->flags = 0; set_page_ref(p, 0); } base->property = n; SetPageProperty(base); list_entry_t *le = &free_list; while ((le = list_next(le)) != &free_list) { p = le2page(le, page_link); if (base + base->property == p) { base->property += p->property; ClearPageProperty(p); list_del(&(p->page_link)); } else if (p + p->property == base) { p->property += base->property; ClearPageProperty(base); base = p; list_del(&(p->page_link)); } } nr_free += n; le = &free_list; while ((le = list_next(le)) != &free_list) { p = le2page(le, page_link); if (base + base->property <= p) break; } list_add_before(le, &(base->page_link)); }

合并逻辑：

1. 检查释放块的前后是否有相邻空闲块
2. 如果发现相邻块，合并它们成为一个更大的块
3. 将合并后的块按地址顺序插入空闲链表
4. 更新全局空闲页计数

4. 算法优化与扩展思考

虽然First-Fit实现简单，但在性能和内存利用率方面仍有改进空间。

4.1 时间复杂度分析

当前实现的时间复杂度：

4.2 可能的优化方向

1. 引入平衡二叉搜索树：

   • 将空闲块按大小组织在树中
   • 可将分配时间复杂度降至O(log n)

2. 分离空闲链表：

   • 为不同大小的请求维护多个空闲链表
   • 例如2^n大小的专用链表

3. 预分配策略：

   • 为常用大小的请求保留专用内存池
   • 减少频繁分配释放的开销

4.3 其他内存分配算法对比

在实际系统设计中，通常会根据具体需求组合使用多种算法。例如Linux内核就同时使用了伙伴系统(Buddy System)和slab分配器来管理不同大小的内存请求。