实验四 动态分区分配方式的模拟 答案

实验四 动态分区分配方式的模拟 答案

动态分区分配方式的模拟

第一部分 设计思想的说明

1 设计目标

用C语言或C++语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端空间。

预期结果：假设初始状态如下，可用的内存空间为640KB，并有下列请求序列：

作业1 申请 130KB

作业2 申请 60KB

作业3 申请 100KB

作业2 释放 60KB

作业4 申请 200KB

作业3 释放 100KB

作业1 释放 130KB

作业5 申请 140KB

作业6 申请 60KB

作业7 申请 50KB

作业6 释放 60KB

分别用首次适应算法和最佳适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。

2、设计理论

首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。

最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。

内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。