1. 动态分区分配实验概述
内存管理是操作系统最核心的功能之一，而动态分区分配又是内存管理中最基础也最经典的实现方式。这次实验让我有机会亲手实现两种经典的动态分区分配算法——首次适应算法(First-Fit)和最佳适应算法(Best-Fit)，通过代码层面的实现，我对操作系统底层的内存管理机制有了更深入的理解。
动态分区分配的核心思想是根据进程实际需要的内存大小，在内存空间中动态地划分分区。与固定分区分配相比，这种方式显著提高了内存利用率，但也带来了内存碎片的问题。实验中我们需要处理的关键问题包括：如何高效地管理空闲分区、如何选择合适的分配策略、如何处理内存回收时的分区合并等。
2. 实验环境与工具准备
2.1 硬件与软件环境
实验在普通PC上完成，配置要求不高：
- CPU：任意x86架构处理器
- 内存：4GB以上（实际实验仅需几十KB内存空间）
- 操作系统：Windows 10或Linux发行版
- 开发工具：GCC编译器、VS Code编辑器
2.2 开发语言选择
使用C语言实现有几个重要优势：
- 可以直接操作内存，更贴近系统底层
- 指针操作方便实现链表等数据结构
- 执行效率高，适合系统级编程
- 跨平台性好，代码可移植性强
提示：如果使用Windows系统，建议安装MinGW或Cygwin来获取GCC编译环境；Linux系统通常已自带GCC。
3. 数据结构设计与实现
3.1 核心数据结构
实验中设计了三个主要结构体来管理系统状态：
c复制// 作业控制块
struct Jobs {
int jobID; // 作业标识符
int addr_start; // 占用内存起始地址
int addr_end; // 占用内存结束地址
struct Jobs *next;// 指向下一个作业的指针
};
// 空闲分区描述块
struct Unoccupied_block {
struct Unoccupied_block *previous; // 前驱指针
int addr_start; // 分区起始地址
int addr_end; // 分区结束地址
struct Unoccupied_block *next; // 后继指针
};
// 阻塞队列节点
struct Blocking_queue {
int jobID; // 被阻塞作业ID
int space; // 请求内存大小
struct Blocking_queue *next; // 队列指针
};
这种设计将系统状态清晰地分为三个部分：已分配的内存区域、空闲内存区域和因内存不足而阻塞的作业队列。
3.2 内存初始化
系统启动时，我们需要初始化一个640KB的连续内存空间：
c复制void initialize_memory() {
ubhead = (struct Unoccupied_block *)malloc(sizeof(struct Unoccupied_block));
struct Unoccupied_block *first = (struct Unoccupied_block *)malloc(sizeof(struct Unoccupied_block));
first->addr_start = 0; // 起始地址为0
first->addr_end = 640; // 结束地址为640KB
first->next = NULL;
first->previous = ubhead;
ubhead->next = first;
ubhead->previous = NULL;
ubhead->addr_start = -1; // 头节点特殊标记
ubhead->addr_end = -1;
}
这种初始化方式创建了一个包含整个可用内存的空闲分区，后续的分配操作都将基于这个初始状态进行。
4. 内存分配算法实现
4.1 首次适应算法(First-Fit)
首次适应算法的核心思想是顺序搜索空闲分区链，找到第一个能满足请求大小的分区就进行分配。
c复制bool first_fit_allocate(int jobID, int size) {
struct Unoccupied_block *current = ubhead->next;
while(current != NULL) {
int block_size = current->addr_end - current->addr_start;
if(block_size >= size) {
// 分配内存
struct Jobs *newJob = create_job(jobID, current->addr_start, size);
insert_job(newJob);
// 更新空闲分区
if(block_size == size) {
// 整块分配，移除空闲节点
remove_free_block(current);
} else {
// 部分分配，调整起始地址
current->addr_start += size;
}
return true;
}
current = current->next;
}
return false; // 分配失败
}
首次适应算法的优点是实现简单、分配速度快，但缺点是容易在低地址区域产生大量小碎片。
4.2 最佳适应算法(Best-Fit)
最佳适应算法需要遍历所有空闲分区，选择能满足请求且大小最接近的分区进行分配。
c复制bool best_fit_allocate(int jobID, int size) {
struct Unoccupied_block *current = ubhead->next;
struct Unoccupied_block *best_block = NULL;
int min_diff = INT_MAX;
// 寻找最佳分区
while(current != NULL) {
int block_size = current->addr_end - current->addr_start;
int diff = block_size - size;
if(diff >= 0 && diff < min_diff) {
best_block = current;
min_diff = diff;
}
current = current->next;
}
if(best_block != NULL) {
// 分配内存
struct Jobs *newJob = create_job(jobID, best_block->addr_start, size);
insert_job(newJob);
// 更新空闲分区
if(min_diff == 0) {
remove_free_block(best_block);
} else {
best_block->addr_start += size;
}
return true;
}
return false; // 分配失败
}
最佳适应算法虽然能减少外部碎片，提高内存利用率，但需要遍历整个空闲分区链，时间复杂度较高。
5. 内存回收与碎片合并
5.1 内存回收流程
当作业完成释放内存时，系统需要将对应的内存区域重新标记为空闲，并尝试与相邻的空闲分区合并：
c复制void free_memory(int jobID) {
// 1. 从作业队列中查找并移除指定作业
struct Jobs *job = find_and_remove_job(jobID);
if(job == NULL) return;
// 2. 创建新的空闲分区
struct Unoccupied_block *new_block = create_free_block(job->addr_start, job->addr_end);
// 3. 将新空闲分区插入到合适位置
insert_free_block_sorted(new_block);
// 4. 尝试合并相邻空闲分区
merge_adjacent_blocks(new_block);
free(job); // 释放作业结构体
}
5.2 碎片合并实现
合并相邻空闲分区是减少外部碎片的关键操作：
c复制void merge_adjacent_blocks(struct Unoccupied_block *block) {
// 尝试与前驱分区合并
if(block->previous != ubhead &&
block->previous->addr_end == block->addr_start) {
block->previous->addr_end = block->addr_end;
block->previous->next = block->next;
if(block->next != NULL) {
block->next->previous = block->previous;
}
struct Unoccupied_block *to_free = block;
block = block->previous;
free(to_free);
}
// 尝试与后继分区合并
if(block->next != NULL &&
block->addr_end == block->next->addr_start) {
block->addr_end = block->next->addr_end;
struct Unoccupied_block *to_free = block->next;
block->next = to_free->next;
if(to_free->next != NULL) {
to_free->next->previous = block;
}
free(to_free);
}
}
合并操作需要仔细处理链表指针关系，确保在合并分区后链表结构仍然保持正确。
6. 实验结果与分析
6.1 测试用例设计
我们设计了以下作业序列来测试算法行为：
- 作业1申请130KB
- 作业2申请60KB
- 作业3申请100KB
- 作业2释放60KB
- 作业4申请200KB
- 作业3释放100KB
- 作业1释放130KB
- 作业5申请140KB
- 作业6申请60KB
- 作业7申请50KB
- 作业6释放60KB
6.2 首次适应算法结果
code复制------------------------------------
Current unoccupied blocks:
1 0 130
2 190 640
------------------------------------
------------------------------------
Current unoccupied blocks:
1 0 130
2 250 640
------------------------------------
------------------------------------
Current unoccupied blocks:
1 0 60
2 130 250
3 350 640
------------------------------------
可以看到首次适应算法在低地址区域产生了较多小碎片。
6.3 最佳适应算法结果
code复制------------------------------------
Current unoccupied blocks:
1 130 190
2 290 640
------------------------------------
------------------------------------
Current unoccupied blocks:
1 130 290
2 490 640
------------------------------------
------------------------------------
Current unoccupied blocks:
1 0 130
2 130 290
3 490 640
------------------------------------
最佳适应算法产生的碎片较少，内存利用率更高，但分配时需要更多的搜索时间。
7. 实验经验与优化建议
7.1 实现中的关键点
-
边界条件处理：要特别注意分配正好等于空闲分区大小的情况，此时需要移除整个空闲节点。
-
链表操作安全：在插入、删除节点时，必须确保前驱和后继指针的正确性，特别是头节点和尾节点的处理。
-
内存释放顺序：作业释放内存的顺序会影响碎片情况，实际系统中可以采用某些策略来优化释放顺序。
7.2 可能的优化方向
-
使用平衡树管理空闲分区：可以将空闲分区按大小组织成平衡二叉树，这样最佳适应算法的搜索时间可以从O(n)降到O(log n)。
-
定期碎片整理：当碎片达到一定阈值时，可以暂停系统进行内存紧缩(compaction)，将已分配分区向一端移动，合并所有空闲分区。
-
改进的分配策略：可以考虑实现Next-Fit或Worst-Fit算法，比较不同策略在特定负载下的表现。
-
添加内存分配统计：记录分配成功率、平均搜索长度等指标，帮助评估算法性能。
8. 存储管理深度思考
通过本次实验，我对操作系统的存储管理有了更深入的认识：
-
时空权衡无处不在：首次适应算法速度快但碎片多，最佳适应算法碎片少但速度慢，这种时空权衡在系统设计中非常普遍。
-
局部性原理的应用：首次适应算法实际上利用了内存访问的局部性原理，新分配的内存倾向于集中在低地址区域。
-
数据结构决定算法效率：选择链表还是树结构来管理空闲分区，会极大影响分配算法的效率。
-
实际系统的复杂性：真实的操作系统内存管理要考虑页表、TLB、交换空间等多层机制，比我们的实验模型复杂得多。
-
性能评估的多样性：不能仅看内存利用率，还要考虑分配速度、实现复杂度等多维指标。