合肥工业大学操作系统课程设计动态分区分配算法

### 合肥工业大学操作系统课程设计之动态分区分配算法

#### 设计背景与目标
为了帮助学生深入了解计算机存储器管理的不同分配策略，特别是连续分配方式下的动态分区分配机制，合肥工业大学的操作系统课程设计项目旨在让学生通过实际编程练习掌握这些概念。此项目不仅强化了理论知识的理解，还提升了学生的实践技能。

#### 数据结构的选择与定义
在实现动态分区分配的过程中，选择了链表作为主要的数据结构来表示空闲分区列表[^1]。每个节点代表一个空闲分区，包含了起始地址、长度以及指向下一个节点的指针等信息。这种结构便于管理和操作不同大小的内存区域，并支持高效的插入和删除操作。

typedef struct FreeBlock {
    int start;      // 分区起始位置
    int size;       // 分区大小
    struct FreeBlock *next;
} FreeBlock;

#### 首次适应法(FIRST FIT)的具体实现
首次适应法则是在寻找合适的空闲分区时按照顺序遍历整个空闲分区链表直到找到第一个满足需求的空间为止。这种方法简单直观，但在长期运行过程中可能会导致碎片化问题加剧。

当接收到新的内存请求时，程序会从头到尾扫描空闲分区链表，一旦发现某个空闲分区内有足够的剩余空间，则将其分割成两部分：一部分用于当前请求，另一部分继续留在空闲队列中等待后续使用；如果正好匹配则直接移除该条目即可[^2]。

对于回收操作而言，需要考虑多种情形，例如被释放的区块可能位于现有任意两个已知空闲区间之间或紧邻其一端点等情况。此时应检查相邻边界是否存在其他未占用片段并与之合并形成更大的连续块以减少外部碎片数量。

// 查找适合的空闲分区并进行分配
FreeBlock* firstFit(int reqSize, FreeBlock **head){
    FreeBlock *p = (*head);
    
    while (p != NULL && p->size < reqSize)
        p = p->next;

    if(p == NULL || p->size >= reqSize){  
        // 找到了合适的位置
        ...
    }
}

#### 最佳适应法(BEST FIT)的应用场景探讨
相比之下，最佳适应法会在所有候选者当中挑选出最小的那个刚好可以容纳新任务的对象来进行安置。虽然这种方式能够在一定程度上缓解因频繁创建细碎的小型可用单元所带来的负面影响，但由于每次都需进行全面检索所以效率较低，在某些情况下甚至可能导致性能瓶颈出现[^3].

针对上述两种典型算法特点及其优缺点进行了详细的对比分析之后，建议初学者可以从较为简单的首次适配入手学习，待熟悉基本流程后再尝试更复杂的优化版本如最优适配或其他变体形式。