图解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页(start0x1000, property16)] - NULL2.2 分配4个页面当请求分配4个页面时算法执行流程从链表头开始扫描发现块A有16页满足需求将块A拆分为两部分分配的4页0x1000-0x13FF剩余的12页形成新块B0x1400开始分配后状态空闲链表 [块B:12页(start0x1400, property12)]2.3 再分配6个页面接下来请求分配6个页面扫描发现块B有12页满足需求将块B拆分为分配的6页0x1400-0x19FF剩余的6页形成块C0x1A00开始状态变化空闲链表 [块C:6页(start0x1A00, property6)]2.4 释放第一个4页块当释放最初分配的4页块0x1000-0x13FF时系统检查相邻区域前驱无0x1000是起始地址后继0x1400开始的6页正在使用由于没有相邻空闲块直接将这4页作为新块D插入链表链表状态空闲链表 [块D:4页(start0x1000, property4)] - [块C:6页]2.5 释放6页块后的合并当释放0x1400-0x19FF的6页块时检查相邻区域前驱0x1000开始的4页空闲块D后继0x1A00开始的6页空闲块C执行合并操作先将块D与当前释放的6页合并为10页块再与块C合并为16页大块最终状态恢复初始空闲链表 [块E:16页(start0x1000, property16)]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; }关键操作遍历所有页面清除保留标志和引用计数设置头页的property字段为总页数将头页的page_link插入空闲链表更新全局空闲页计数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; }执行流程遍历空闲链表找到第一个满足大小的块从链表中移除该块如果块大于需求拆分剩余部分重新插入链表更新空闲页计数返回分配块的首页指针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)); }合并逻辑检查释放块的前后是否有相邻空闲块如果发现相邻块合并它们成为一个更大的块将合并后的块按地址顺序插入空闲链表更新全局空闲页计数4. 算法优化与扩展思考虽然First-Fit实现简单但在性能和内存利用率方面仍有改进空间。4.1 时间复杂度分析当前实现的时间复杂度操作时间复杂度原因分配O(n)需要线性扫描空闲链表释放O(n)需要查找合并位置并维护链表顺序4.2 可能的优化方向引入平衡二叉搜索树将空闲块按大小组织在树中可将分配时间复杂度降至O(log n)分离空闲链表为不同大小的请求维护多个空闲链表例如2^n大小的专用链表预分配策略为常用大小的请求保留专用内存池减少频繁分配释放的开销4.3 其他内存分配算法对比算法优点缺点适用场景First-Fit实现简单速度快容易产生外部碎片通用场景Best-Fit内存利用率高查找速度慢产生小碎片内存紧张系统Buddy合并快速无外部碎片内部碎片严重内核内存管理在实际系统设计中通常会根据具体需求组合使用多种算法。例如Linux内核就同时使用了伙伴系统(Buddy System)和slab分配器来管理不同大小的内存请求。