内存分配实战：用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"); }
在实际项目中使用这种内存管理方案时，建议添加完善的日志系统记录分配/释放操作，这对调试内存相关问题非常有帮助。