内存分配实战：用C语言手把手实现首次适应算法（附完整代码）

内存分配实战用C语言手把手实现首次适应算法附完整代码在操作系统内存管理的众多算法中首次适应算法因其简单高效而广受青睐。本文将带你从零开始用C语言完整实现这一经典算法。不同于纸上谈兵的理论讲解我们将通过可运行的代码示例深入探讨双向链表在内存管理中的应用以及如何处理内存分配与回收中的各种边界情况。1. 首次适应算法核心原理首次适应算法(First-Fit Algorithm)是动态分区分配中最基础的策略之一。它的工作原理可以概括为顺序搜索从内存低地址开始依次检查每个空闲分区首次匹配选择第一个足够大的空闲分区进行分配分割剩余如果分区大于需求将剩余部分作为新的空闲分区这种算法的优势在于实现简单搜索速度快。但缺点也明显低地址端容易产生大量小碎片而大空闲分区往往集中在内存高地址端。关键数据结构我们使用带头节点的双向链表来管理内存分区struct areaNode { int ID; // 分区标识 int size; // 分区大小 int address; // 起始地址 int flag; // 使用状态(0:空闲 1:已分配) }; typedef struct DuNode { struct areaNode data; struct DuNode *prior; struct DuNode *next; }*DuLinkList;2. 内存分配函数实现首次适应算法的分配过程需要处理以下关键步骤遍历空闲分区链寻找第一个满足大小的分区精确匹配时直接分配整个分区分区较大时分割出所需大小剩余部分保留更新链表指针关系以下是核心代码实现bool first_fit(int id, int m_size) { DuLinkList p m_head; while(p ! m_last) { DuLinkList n p-next; if(!n-data.flag n-data.size m_size) { // 创建新节点记录分配信息 DuLinkList t new DuNode(); t-data.ID id; t-data.size m_size; t-data.address n-data.address; t-data.flag 1; // 调整剩余空间 n-data.address m_size; n-data.size - m_size; // 插入链表 t-prior p; t-next n; p-next t; n-prior t; return true; } p n; } return false; // 分配失败 }注意实际工程中应添加参数校验如检查m_size是否为正数id是否合法等3. 内存回收的四种边界情况内存回收比分配更为复杂需要处理四种可能的邻接情况。我们通过图示和代码结合的方式详细说明3.1 与前空闲分区相邻[F1空闲][回收区] → 合并到F1代码处理if(prev-data.flag 0) { prev-data.size curr-data.size; prev-next curr-next; curr-next-prior prev; delete curr; }3.2 与后空闲分区相邻[回收区][F2空闲] → 合并到F2代码处理if(next-data.flag 0) { next-data.address curr-data.address; next-data.size curr-data.size; curr-prior-next next; next-prior curr-prior; delete curr; }3.3 同时与前后空闲分区相邻[F1空闲][回收区][F2空闲] → 三者合并代码处理if(prev-data.flag 0 next-data.flag 0) { prev-data.size curr-data.size next-data.size; prev-next next-next; next-next-prior prev; delete curr; delete next; }3.4 独立不邻接[已分配][回收区][已分配] → 创建新空闲项代码处理curr-data.flag 0; curr-data.ID 0; // 保持链表原有结构不变4. 完整代码实现与测试以下是整合后的完整实现包含初始化、分配、回收和打印功能#include stdio.h #include stdlib.h const int Max_length 55; // 内存总大小 // 分区结构体定义 struct areaNode { int ID; int size; int address; int flag; }; // 双向链表节点 typedef struct DuNode { struct areaNode data; struct DuNode *prior; struct DuNode *next; }*DuLinkList; DuLinkList m_head new DuNode, m_last new DuNode; void init() { m_head-prior NULL; m_head-next m_last; m_last-prior m_head; m_last-next NULL; m_head-data.size 0; m_last-data.address 0; m_last-data.size Max_length; m_last-data.ID 0; m_last-data.flag 0; } void show() { DuNode *p m_head-next; printf(\n); while (p) { printf(分区号%s\n, p-data.ID 0 ? FREE : p-data.ID); printf(起始地址%d\n, p-data.address); printf(大小%d KB\n, p-data.size); printf(状态%s\n, p-data.flag ? 已分配 : 空闲); printf(——————————————————\n); p p-next; } } // 首次适应分配算法前面已给出此处省略 void recycle(int id) { DuLinkList p m_head; while(p ! m_last) { DuLinkList curr p-next; if(curr-data.ID id) { curr-data.flag 0; curr-data.ID 0; DuLinkList prev curr-prior; DuLinkList next curr-next; // 检查前驱节点是否空闲 if(prev ! m_head prev-data.flag 0) { prev-data.size curr-data.size; prev-next next; next-prior prev; delete curr; curr prev; // 当前节点指向前驱 } // 检查后继节点是否空闲 if(next ! m_last next-data.flag 0) { curr-data.size next-data.size; curr-next next-next; next-next-prior curr; delete next; } return; } p curr; } } int main() { init(); printf(初始状态\n); show(); printf(\n分配作业1请求15KB\n); first_fit(1, 15); show(); printf(\n分配作业2请求30KB\n); first_fit(2, 30); show(); printf(\n释放作业1的15KB\n); recycle(1); show(); printf(\n分配作业3请求8KB\n); first_fit(3, 8); show(); printf(\n分配作业4请求6KB\n); first_fit(4, 6); show(); printf(\n释放作业2的30KB\n); recycle(2); show(); // 清理链表 DuNode *p m_head; while(p ! NULL) { DuNode *temp p; p p-next; delete temp; } return 0; }5. 算法优化与扩展建议虽然基础实现已经完整但在实际项目中还可以考虑以下优化碎片整理定期合并相邻小碎片void defragment() { DuLinkList p m_head-next; while(p ! m_last) { DuLinkList next p-next; if(!p-data.flag !next-data.flag) { p-data.size next-data.size; p-next next-next; next-next-prior p; delete next; } else { p p-next; } } }分配策略改进下次适应记录上次查找位置减少低地址碎片快速适应维护多个空闲链表按大小分类内存保护机制添加越界检查实现内存访问权限控制可视化工具void visual() { DuLinkList p m_head-next; while(p ! m_last) { printf(|%3dK %s, p-data.size, p-data.flag ? [已分配] : [空闲]); p p-next; } printf(\n); }在实际项目中使用这种内存管理方案时建议添加完善的日志系统记录分配/释放操作这对调试内存相关问题非常有帮助。