简介操作系统课程设计“动态分区分配存储管理”是一份可直接参考的课程设计方案适合计算机专业学生在操作系统存储管理模块学习或完成课设时使用。内容涵盖设计任务、要求和目的围绕内存分配状况与进程数据结构建立、自动和手工两种进程产生方式、屏幕动态显示等核心环节展开。文档重点剖析首次适应、循环首次适应、最佳适应、最坏适应四种分配算法并结合进程释放内存场景讲解回收分区与相邻空闲区合并的四种情况以及通过移动作业实现空间拼接的紧凑算法。此外还给出了基于C与VS2012环境的程序实现思路包括内存分配状态和空闲分区链等数据结构的定义与输出方法。资源共1个doc文件压缩包大小155KB已有1661人学习下载适用于课程设计选题、算法对比或代码编写时的参考与启发。1. 动态分区分配课程设计为什么值得拆开看操作系统课程设计里动态分区分配存储管理是最容易“看着简单、写着崩”的一个题目。理论课上首次适应、最佳适应几句话就讲完了但真要用 C 去模拟内存的分配、回收、紧凑你会发现核心难点根本不在算法本身而在数据结构怎么设计、边界条件怎么不漏。这个设计用三个二维数组内存分配状态 ary1、空闲分区状态 ary2、进程分配状态 ary3撑起了整个模拟系统在 VS2012 环境下实现了四种分配算法、分区回收、紧凑算法还支持把执行过程写入磁盘文件重放。对于正在做操作系统课程设计的人这份代码能直接对照着理清“数组模拟内存”的完整套路对于已经工作的人也能从中看到教学场景里如何用最朴素的方式表达内存管理的核心逻辑。2. 内存数据结构设计三个二维数组如何模拟分区分配2.1 内存分配表 ary1 的字段设计与状态码含义动态分区分配的核心是要能描述“内存现在被切成了哪些块每块多大、从哪开始、是否被占用”。这里用了一个全局二维数组ary1[20][4]每一行代表一个内存分区四列分别存放分区号、大小、起始地址、分配状态。int ary1[20][4]; // 内存分配状态分区号 | 大小/KB | 始址/KB | 状态 int ary2[20][3]; // 空闲分区状态分区号 | 大小/KB | 起址/KB int ary3[10]; // 进程分配状态每个进程需要的内存大小状态列用整数区分三种情况0表示未分配2表示已分配。这个编码贯穿整个程序所有算法在修改内存状态时都是在改ary1[i][3]这个标志位。判断一个分区是否空闲统一用ary1[i][3] ! 2来过滤。注意ary2是从ary1派生出来的。每次分配或回收后程序都会扫描一遍ary1把所有未分配的分区重新填入ary2。这种做法虽然时间复杂度高但在数据量只有 20 个分区的教学场景里足够直观也避免了维护两个表一致性的复杂逻辑。2.2 空闲分区表的重建逻辑空闲分区表不是独立维护的而是每次变化后从内存分配表重新生成。这个设计思路值得注意教学模拟环境里数据量小重建比增量维护更不容易出错。int k 0; for (int i 0; i m; i) { if (ary1[i][3] ! 2) { // 状态不是“已分配”的分区进入空闲表 ary2[k][0] ary1[i][0]; ary2[k][1] ary1[i][1]; ary2[k][2] ary1[i][2]; k; } } n k; // 空闲分区数量这段代码的核心作用是同步ary2和ary1。m是内存分区总数每次分配或合并后分区数量会变化ary2的下标k只递增到空闲分区数n。如果分配后空闲表项前移n会减少如果切割产生了新分区m会增加n也会相应变化。这个重建逻辑在first_fit、best_fit、apply_recycle里反复出现理解它整个程序的运行轨迹就清晰了。2.3 进程产生的自动与手工两种方式进程产生方式直接影响后续分配效果。自动产生模式用rand()生成随机进程大小但程序做了一个特殊处理强制把第一个进程设为 42第二个设为 86。void create_pro() { for (int i 0; i q; i) { ary3[i] rand() % 100; if (ary3[i] 0) { i--; } // 拒绝大小为 0 的进程 } ary3[0] 42; ary3[1] 86; }这样做的意图很明确随机数可能让所有进程都偏大或偏小固定前两个值能保证即使后续随机失败也至少有一组有代表性的进程参与分配展示。手工输入模式则完全由用户指定进程数量和每个进程的大小适合做针对性的算法对比实验。3. 四种分配算法的遍历差异与实现代价3.1 首次适应从表头查找实现最直接首次适应算法是从空闲分区链的头部开始顺序查找找到第一个能满足大小要求的空闲分区就分配。如果分区大小正好等于进程需求直接把对应内存块标记为已分配并从空闲表中删除该项如果分区大于进程需求则切割分区剩余部分作为新的空闲分区留在表中。for (i 0; i q; i) { // 遍历进程队列 for (j 0; j n; j) { // 遍历空闲分区表 if (ary2[j][1] ary3[i]) { // 空闲分区大小满足进程需求 if (ary2[j][1] ary3[i]) { // 大小相等直接分配把分区状态改为已分配 ary1[ary2[j][0] - 1][3] 2; // 空闲表中删除该项后续表项前移 for (k j 1; k n; k) { ary2[k-1][0] ary2[k][0]; ary2[k-1][1] ary2[k][1]; ary2[k-1][2] ary2[k][2]; } n--; } else { // 分区大于进程切割剩余部分插入空闲表 int l ary2[j][0]; int d ary1[l-1][1]; // 保存原分区大小 ary1[l-1][1] ary3[i]; // 分配部分的大小 ary1[l-1][3] 2; // 标记已分配 m; // 内存分区数加一 // 后续分区后移为新空闲块腾出位置 for (k m; k ary2[j][0] 1; k--) { ary1[k-1][0] ary1[k-2][0] 1; ary1[k-1][1] ary1[k-2][1]; ary1[k-1][2] ary1[k-2][2]; ary1[k-1][3] ary1[k-2][3]; } // 新空闲块 原大小 - 分配大小 ary1[l][0] l 1; ary1[l][1] d - ary3[i]; ary1[l][2] ary1[l-1][1] ary1[l-1][2]; ary1[l][3] 0; // 状态未分配 } break; } } }这里有一个容易踩坑的地方ary1[ary2[j][0] - 1][3] 2的写法依赖分区号和数组下标差 1 的对应关系。物理内存块 1 对应ary1[0]物理内存块 2 对应ary1[1]。如果某次操作后分区号没有重新整理这个映射关系就会错乱。实际运行时每次切割后都会重建空闲表但ary1的分区号也需要同步更新否则后续回收时按分区号定位会出错。首次适应算法的优点是优先利用低地址的空闲分区保留了高地址的大块连续空间缺点是低地址被频繁切割后会产生大量小碎片查找时间随空闲表增长而变长。3.2 循环首次适应记录上一次分配位置循环首次适应是对首次适应的改进它维护了一个全局变量r记录上一次分配到的空闲分区位置。下次分配时从r开始向后查找而不是回到表头。int r 0; // 循环首次适应上一次查找到的空闲分区序号 void next_fit() { for (i 0; i q; i) { for (j r; j n; j) { // 从上次位置开始查找 if (ary3[i] ary2[j][1]) { // ... 分配逻辑与首次适应类似 r (r 1) % n; // 更新下次查找起点 break; } } } }要注意r (r 1) % n这行代码的位置。它只在发生切割分配时执行如果分区大小刚好相等则r保持不变。这样设计的原因是相等分配会删除一个空闲表项如果r指向的位置被删除了下次直接从r开始可能越界。循环首次适应的优势在于分配更均匀不会像首次适应那样总是从低地址开始切割缺点是降低了高地址大分区被保留的概率系统可能缺乏大空闲块。3.3 最佳适应与最坏适应扫描全表选极端最佳适应算法的思路是每次分配时在全部空闲分区中找出“能满足需求且大小最小”的分区减少大块空间的浪费。实现方式是遍历整个空闲表用一个临时变量保存当前最优解。void best_fit() { for (i 0; i q; i) { int e 9999; // 保存当前最小的“能满足需求的空闲分区大小” int j -9999; // 保存该分区的下标 for (s 0; s n; s) { if ((ary2[s][1] ary3[i]) (e ary2[s][1])) { e ary2[s][1]; j s; } } if (j 0) { // 没有找到能满足需求的空闲分区 } else { // 执行分配逻辑与首次适应相同 } } }这里有两个细节值得注意。第一e初始化为9999假设内存大小不会超过这个值如果初始值设置得比所有空闲分区都小算法会找不到解。第二j 0是判断“找不到满足条件的分区”的信号这里用负数作哨兵值。最坏适应算法与最佳适应相反每次挑选最大的空闲分区分割给作业。实现上只需要把比较条件反转// 最佳适应找最小的满足条件的分区 if ((ary2[s][1] ary3[i]) (e ary2[s][1])) { e ary2[s][1]; j s; } // 最坏适应找最大的满足条件的分区 if ((ary2[s][1] ary3[i]) (e ary2[s][1])) { e ary2[s][1]; j s; }初始值也相应从9999改为-9999保证第一个满足条件的分区一定能成为候选。最坏适应的逻辑是大分区被切割后剩余部分仍然较大可以继续容纳其他进程减少小碎片的产生。但它的问题是每次分配都会破坏最大的空闲块最终可能没有一个分区能满足大作业需求。四种算法的对比可以用一个简单的场景说明算法查找起点选择策略优点缺点首次适应表头第一个满足的简单快速低地址碎片多循环首次适应上次位置第一个满足的分配均匀大块易被破坏最佳适应全表最小的满足分区保留大块产生大量小碎片最坏适应全表最大的满足分区碎片较少大分区被快速消耗4. 分区回收的八种场景与紧凑算法4.1 回收逻辑的完整分类与代码处理分区回收是动态分区分配里最容易出 bug 的部分。进程释放内存时回收区可能和相邻分区产生合并关系。这个设计把回收场景拆成了八种情况从代码注释里可以完整看到作者的分类思路// 1. 回收区上邻接空闲盘块下邻接已分配盘块 // 2. 回收区下邻接空闲盘块上邻接已分配盘块 // 3. 回收区上下都邻接空闲盘块 // 4. 回收区上下都邻接已分配盘块独立插入 // 5. 回收区是第一个盘块向下邻接空闲盘块 // 6. 回收区是第一个盘块向下邻接已分配盘块 // 7. 回收区是最后一个盘块向上邻接空闲盘块 // 8. 回收区是最后一个盘块向上邻接已分配盘块代码对首块和尾块做了单独处理中间情况用四个if分支逐一判断。以“上邻空闲、下邻已分配”为例if ((ary1[recycle-2][3] ! 2) (ary1[recycle][3] 2)) { // 回收区上邻接着空闲盘块下连接着已分配盘块 // 上邻空闲块扩大回收区从内存表中删除 ary1[recycle-2][1] ary1[recycle-2][1] ary1[recycle-1][1]; // 后续分区前移一位 for (i recycle-1; i m; i) { ary1[i][0] ary1[i1][0] - 1; ary1[i][1] ary1[i1][1]; ary1[i][2] ary1[i1][2]; ary1[i][3] ary1[i1][3]; } m--; // 分区总数减一 // 重建空闲分区表 }这段代码容易出问题的地方在数组下标。recycle是从 1 开始的分区号而数组下标从 0 开始所以ary1[recycle-2]是上一个分区ary1[recycle-1]是回收分区本身ary1[recycle]是下一个分区。这个偏移关系如果搞混数组访问就会越界。真实场景中最常触发的是“上下都邻接空闲块”的情况。此时需要三个分区合并成一个使用上邻空闲块的起始地址、大小变为三者之和并删除下邻空闲块的表项。代码处理方式是把上邻块的大小更新为三者之和后把下邻块之后的所有分区前移两位同时m减二。这里要注意三个分区合并后回收分区的分区号也被清除了ary2重建后空闲表项数量n才会正确。4.2 紧凑算法的实现思路紧凑算法的目标是把分散的小空闲分区拼接成一个大分区。教学实现里时间复杂度是完全可以接受的做法是扫描内存表把所有已分配分区移动到低地址端连续排列把空闲空间集中到一端。// 紧凑算法流程代码中已有 c 分支去重逻辑 // 1. 找到第一个空闲分区的位置 // 2. 依次把后续已分配分区的内容向前搬运 // 3. 更新每个分区的起始地址 // 4. 重建空闲分区表紧凑算法在实际系统中需要处理一个关键问题进程在内存中的位置变更后需要同步更新所有指向它的指针。教学模拟里进程只记录大小不涉及地址引用所以紧凑实现相对简单。但在真实操作系统中紧凑必须配合地址重定位机制这也是为什么现代系统普遍采用分页而不是紧凑来解决问题。5. 把执行过程写入文件重放与算法对比验证5.1 文件输出的实现方式这个设计支持把执行过程存入磁盘文件之后读出重放。实现方式很朴素每次调用vision()打印内存状态时根据当前算法编号打开对应文件把输出内容同步写入文件。void vision() { if (id1 1) stream.open(first_fit.txt, ios::app); if (id1 2) stream.open(nextfirst_fit.txt, ios::app); if (id1 3) stream.open(best_fit.txt, ios::app); if (id1 4) stream.open(worst_fit.txt, ios::app); if (id1 5) stream.open(compact.txt, ios::app); if (id1 6) stream.open(huishou.txt, ios::app); // 把 cout 输出的内容同步写入 stream }ios::app是追加模式不会覆盖之前的内容所以同一算法多次执行的结果会累积在同一个文件里。但这也带来一个小问题如果重复运行程序旧文件内容不会清空对比实验时需要先手动删除或重命名旧文件。5.2 算法对比的验证技巧要验证四种算法的内存利用率差异可以用同一组进程数据分别跑四种算法然后对比最终的空闲分区数量和各分区大小分布。推荐的做法是手工输入内存块时设置一个包含大块和小块的混合布局例如 120KB、60KB、80KB、40KB、100KB再输入一组进程大小如 50KB、30KB、70KB、20KB分别跑四次观察分配结果。关键观察点有三个。一是分配失败次数最佳适应通常最少失败最坏适应在大进程多时容易失败。二是碎片程度首次适应和最佳适应容易在低地址产生大量小块空闲区。三是输出文件里的“匹配”记录每次匹配一行能直接看出每种算法在相同进程序列下选择了哪些分区。通过对比first_fit.txt和best_fit.txt里的匹配行能直观看到首次适应选了“第一个足够大的”最佳适应选了“最小的足够大的”这是理解算法差异最直接的方式。重放时按时间单位逐步读取文件中的内存状态快照就能还原当时的分配演进过程。本文还有配套的精品资源点击获取