从零到一：手把手教你实现 uCore Lab 2 物理内存管理（附避坑指南）

从零构建uCore物理内存管理：手把手实现First-Fit算法与页表映射

在操作系统开发的学习过程中，物理内存管理是最基础也最关键的模块之一。本文将带你从零开始实现uCore Lab 2的物理内存管理功能，不仅涵盖First-Fit算法的完整实现，还会深入讲解页表映射机制。不同于普通的实验报告，本教程将采用"问题驱动+代码实战"的方式，让你真正理解每一行代码背后的设计思想。

1. 实验环境搭建与工程初始化

在开始编码之前，我们需要确保开发环境正确配置。推荐使用Ubuntu 20.04 LTS作为开发系统，这是uCore官方支持的环境。

环境准备清单：

• Ubuntu 20.04 LTS（物理机或虚拟机）
• GCC交叉编译工具链
• QEMU模拟器（版本5.0以上）
• Git版本控制工具

安装依赖命令：

sudo apt update sudo apt install build-essential git qemu-system-x86

获取uCore实验代码：

git clone https://github.com/chyyuu/ucore_os_lab.git cd ucore_os_lab/labcodes/lab2

常见环境问题解决方案：

1. 当遇到make: Nothing to be done for 'TARGETS'错误时：

make clean && make

2. 如果QEMU无法启动，检查是否安装了正确的包：

sudo apt install qemu-system-x86

2. First-Fit内存分配算法实现

First-Fit是最基础的内存分配算法，其核心思想是维护一个空闲内存块链表，分配时找到第一个足够大的块进行分配。

2.1 关键数据结构解析

在uCore中，物理内存管理涉及几个核心数据结构：

// 物理页帧结构 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;

关键点说明：

• property字段只在空闲块的第一个页（Head Page）有效
• flags的低位用于标记页状态：
  • PG_reserved: 页是否被保留
  • PG_property: 页是否空闲

2.2 算法实现步骤详解

初始化函数实现

default_init函数初始化空闲链表：

static void default_init(void) { list_init(&free_list); nr_free = 0; }

内存映射初始化

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; }

内存分配实现

default_alloc_pages实现First-Fit分配：

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; }

内存释放实现

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)); }

算法优化思考：

• 当前实现的时间复杂度为O(n)，可以考虑使用平衡二叉树优化查找效率
• 对于特定大小的分配请求，可以维护多个分离的空闲链表

3. 页表映射机制实现

uCore采用二级页表结构实现虚拟地址到物理地址的转换。本节将实现关键的页表项操作函数。

3.1 页表项获取函数实现

get_pte函数获取或创建页表项：

pte_t *get_pte(pde_t *pgdir, uintptr_t la, bool create) { pde_t *pdep = &pgdir[PDX(la)]; if (!(*pdep & PTE_P)) { if (!create) return NULL; struct Page *page = alloc_page(); if (page == NULL) return NULL; set_page_ref(page, 1); uintptr_t pa = page2pa(page); memset(KADDR(pa), 0, PGSIZE); *pdep = pa | PTE_U | PTE_W | PTE_P; } return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)]; }

3.2 页表项释放函数实现

page_remove_pte释放页表项：

static inline void page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) { if (*ptep & PTE_P) { struct Page *page = pte2page(*ptep); if (page_ref_dec(page) == 0) { free_page(page); } *ptep = 0; tlb_invalidate(pgdir, la); } }

3.3 页表项与页目录项详解

页目录项(PDE)结构：

页表项(PTE)结构：

4. 调试技巧与常见问题

在实现内存管理时，调试是必不可少的环节。以下是几个实用的调试技巧：

4.1 打印内存信息

添加调试函数查看内存状态：

void print_meminfo() { cprintf("Free memory pages: %d\n", nr_free); list_entry_t *le = &free_list; while ((le = list_next(le)) != &free_list) { struct Page *p = le2page(le, page_link); cprintf("Page at 0x%08x, size: %d\n", page2pa(p), p->property); } }

4.2 常见问题排查

1. 页表项设置错误：

   • 确保设置了PTE_P标志
   • 检查物理地址是否正确对齐

2. 内存泄漏检测：

   • 定期检查nr_free是否异常减少
   • 实现简单的内存审计功能

3. 链表操作错误：

   • 使用list.h提供的宏安全操作链表
   • 在修改链表前后检查链表完整性

4.3 测试建议

编写测试用例验证功能：

void test_first_fit() { struct Page *p0, *p1, *p2; p0 = alloc_pages(1); p1 = alloc_pages(2); p2 = alloc_pages(1); print_meminfo(); free_pages(p1, 2); free_pages(p0, 1); print_meminfo(); p0 = alloc_pages(3); // 测试合并是否成功 assert(p0 != NULL); free_pages(p0, 3); }

5. 进阶思考与扩展

5.1 其他内存分配算法

除了First-Fit，还可以实现以下算法：

1. Best-Fit：选择最适合请求大小的空闲块
2. Worst-Fit：选择最大的空闲块进行分配
3. Buddy System：基于2的幂次方的高效分配算法

5.2 虚拟地址与物理地址等值映射

要实现虚拟地址等于物理地址，需要：

1. 修改链接脚本，将内核加载地址改为物理地址
2. 关闭分页机制或设置恒等映射
3. 调整内存初始化代码

5.3 性能优化方向

1. Slab分配器：针对小对象分配优化
2. 延迟分配：按需分配物理页
3. 大页支持：减少TLB缺失

在完成基础实验后，可以尝试实现扩展练习中的Buddy System或Slub分配算法，这将让你对内存管理有更深入的理解。