操作系统实验-首次适应算法与循环首次适应算法.pdf

操作系统中的内存管理是确保系统高效运行的关键部分，尤其是在连续分区的动态存储管理方式下。本实验主要探讨了两种分配和回收内存空间的策略：首次适应算法（First Fit）和循环首次适应算法（Circular First Fit）。这两种算法都是针对可变式分区管理的方法。 首次适应算法是一种简单但有效的内存分配策略。其基本思想是从空闲分区列表的开始位置查找，找到第一个能够容纳新作业的空闲分区，并将该作业分配到这个分区中。这种方法倾向于优先使用内存中的较小空闲区域，以避免大的空闲区域过早被分割。算法流程如下： 1. 初始化空闲分区列表。 2. 接收新作业并检查其大小。 3. 从列表的第一个空闲分区开始搜索，直到找到一个足够大的空闲分区。 4. 如果找到合适的分区，分配内存并更新空闲分区列表。 5. 若找不到合适的分区，则输出“插入失败”。 循环首次适应算法则有所不同，它在首次适应算法的基础上增加了一个循环机制。当分配内存时，它不是从列表的开始，而是从上次分配内存后的位置开始查找。若找不到合适分区，它会回到列表的开头继续查找，但会记录上一次找到的最小空闲分区。这种算法可以避免内存碎片过于集中在列表的前部。流程如下： 1. 初始化空闲分区列表，记录当前空闲区指针。 2. 接收新作业并检查其大小。 3. 从当前空闲区指针开始，查找满足条件的空闲分区。 4. 若找到合适的分区，分配内存并更新空闲分区列表，更新空闲区指针。 5. 如果遍历完所有空闲分区仍未找到合适的，回到列表开头，比较每个分区与记录的最小空闲分区。 6. 若在列表开头找到满足条件的分区，分配内存并更新信息。 7. 若所有分区都不满足，输出“插入失败”。 实验中使用了数据结构来表示内存状态和作业信息。`ROM[N]`用于标记内存块的状态，`num[20]`为作业数组，`Free_room`结构体描述了空闲分区的详细信息，包括编号、起始位置、结束位置和大小。同时，`find_free_rom()`函数用于查找合适的空闲分区，`insert_pcb1()`分别实现了首次适应和循环首次适应的插入作业逻辑，而`Delete(pcb &a)`用于删除作业并更新内存状态。 通过编写程序并进行实验，学生可以深入理解这两种算法的工作原理，以及它们如何影响内存的分配和回收效率。实验报告的编写有助于巩固理论知识，提高实际操作技能，对理解操作系统内存管理有极大的帮助。