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

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

news 2026/6/10 16:32:19

可视化拆解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 时间复杂度分析

当前实现的时间复杂度：

操作时间复杂度原因
分配O(n)需要线性扫描空闲链表
释放O(n)需要查找合并位置并维护链表顺序

4.2 可能的优化方向

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

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

  2. 分离空闲链表：

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

  3. 预分配策略：

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

4.3 其他内存分配算法对比

算法优点缺点适用场景
First-Fit实现简单，速度快容易产生外部碎片通用场景
Best-Fit内存利用率高查找速度慢，产生小碎片内存紧张系统
Buddy合并快速，无外部碎片内部碎片严重内核内存管理

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

http://www.zskr.cn/news/1398318.html

相关文章：

  • 基于CLIP与BERT的多模态假新闻检测：特征对齐与层次化融合实战
  • Burp Suite Sequencer 深度解析：从token结构识别到业务逻辑逆向
  • Tomcat请求解析歧义漏洞深度解析：Host污染与路径逃逸协同利用
  • Tableau饼图设计原理与业务可信度实践指南
  • Frida Hook JNI动态注册函数的三大实战路径
  • 07.Day 7：植入顶级大脑 —— PEAK 框架与多维 ABLE 假设工程
  • SQL去重不是删数据，而是数据治理决策链
  • O4-Mini轻量大模型API实战：边缘部署与工业诊断落地指南
  • GNURadio实战：一台电脑插两个RTL-SDR电视棒，同时收听不同FM电台的完整配置流程
  • AI集成实战指南：从战略规划到持续运维的避坑与落地
  • 工业机器人少样本故障诊断：PTFM时频混合与原型学习实战
  • 数据管道静默失败监控：从数据质量到业务价值的全方位防御体系
  • 探索型与执行型AI智能体：设计哲学、技术实现与协同工作流
  • 从iris数据集实战出发：手把手教你用Python+sklearn玩转KMeans聚类与t-SNE可视化
  • 跨模态Transformer模型：成像测井图像与常规测井曲线的特征融合及岩性分类
  • 保姆级教程：用yum downloadonly搞定Docker离线包，一份包适配麒麟V10/CentOS 8
  • PlayIntegrityFix终极指南：简单三步解决Android设备认证难题
  • EEG微状态序列分析新范式：用NLP词嵌入技术解码大脑动态语法
  • 从地理空间数据云到可游玩地图：一份给独立开发者的真实世界地形创建全流程指南
  • 观察使用Taotoken后API调用的成功率和响应时间变化
  • NVIDIA Profile Inspector技术深度解析：驱动程序配置管理架构与实践指南
  • 情感分析实战：用Python和jieba给你的微博评论自动‘打标签’（附完整代码与词典）
  • 揭秘进程管理：从PID到PCB全解析
  • AzurLaneAutoScript：5步实现碧蓝航线全自动化的终极解决方案
  • TransCAD 6.0 闪退别慌！手把手教你打补丁并搞定波士顿交通网络的最短路径分析
  • [吐槽] outlook 新版本
  • 别再只拿Amazon Review Dataset做推荐了！用Python玩转商品评论的情感分析与销量预测
  • 告别Transformer？手把手带你用Mamba搭建首个图像分类模型（附PyTorch代码）
  • Anthropic开源11个企业级插件，我全试了一遍——这是值得装的4个
  • AI Agent 认知模型与推理模式综述