从零构建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常见环境问题解决方案当遇到make: Nothing to be done for TARGETS错误时make clean make如果QEMU无法启动检查是否安装了正确的包sudo apt install qemu-system-x862. 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)结构位域名称描述31:12Page Table Address页表物理地址11:9Available操作系统可用位8Ignored忽略位7Page Size页大小标志(0表示4KB)6:5Reserved保留位4Cache Disabled缓存禁用位3Write Through写直达位2User/Supervisor用户/超级用户权限1Read/Write读写权限0Present存在位页表项(PTE)结构位域名称描述31:12Page Frame Address页帧物理地址11:9Available操作系统可用位8:7Reserved保留位6Dirty脏页标志5Accessed访问标志4:3Reserved保留位2User/Supervisor用户/超级用户权限1Read/Write读写权限0Present存在位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 常见问题排查页表项设置错误确保设置了PTE_P标志检查物理地址是否正确对齐内存泄漏检测定期检查nr_free是否异常减少实现简单的内存审计功能链表操作错误使用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还可以实现以下算法Best-Fit选择最适合请求大小的空闲块Worst-Fit选择最大的空闲块进行分配Buddy System基于2的幂次方的高效分配算法5.2 虚拟地址与物理地址等值映射要实现虚拟地址等于物理地址需要修改链接脚本将内核加载地址改为物理地址关闭分页机制或设置恒等映射调整内存初始化代码5.3 性能优化方向Slab分配器针对小对象分配优化延迟分配按需分配物理页大页支持减少TLB缺失在完成基础实验后可以尝试实现扩展练习中的Buddy System或Slub分配算法这将让你对内存管理有更深入的理解。