动态内存分配(C语言).doc

实验报告 实验课程名称 动态内存分配算法 专 业 计算机科学与技术 班 级 姓 名 学 号 实验学时 指导教师 成 绩 年12月1日 实验报告 专业 计算机科学 与技术 班级姓名学号 实验课 程 操作系统 指导教 师 实验日 期 同实验 者 实验项 目 动态内存分配算法 实验设 备及器 材 PC机一台 VC 6 0 一 实验内容与要求 动态分区分配又称为可变分区分配 它是根据进程的实际需要 动态地为之分 配内存空间 在实验中运用了三种基于顺序搜索的动态分区分配算法 分别是1 首次适应算法2 循环首次适应算法3 最佳适应法3 最坏适应法分配主存空间 二 需求分析 本次实验通过C语言进行编程并调试 运行 显示出动态分区的分配方式 直 观的展示了首次适应算法循环首次适应算法 最佳适应算法和最坏适应算法对 内存的释放和回收方式之间的区别 首次适应算法 要求空闲分区链以地址递增的次序链接 在分配内存时 从链首开始顺序查找 直至找到一个大小能满足要求的空闲分区为止 然后在按照作业的大小 从 该分区中划出一块内存空间 分配给请求者 余下的空余分区仍留在空链中 优点 优先利用内存中低址部分的空闲分区 从而保留了高址部分的大空闲区 为以后到达的大作业分配大的内存空间创造了条件 缺点 低址部分不断被划分 会留下许多难以利用的 很小的空闲分区即碎片 而每次查找又都是从低址部分开始的 这无疑又会增加查找可用空闲分区时 的开销 循环首次适应算法 在为进程分配内存空间时 不是每次都从链首开始查找 而是从上次找到的空 闲分区的下一个空闲分区开始查找 直到找到一个能满足要求的空闲分区 优点 该算法能使内存中的空闲分区分布得更均匀 从而减少了查找空闲分区 时的开销 最佳适应算法 该算法总是把能满足要求 又是最小的空闲分区分配给作业 避免大材小用 该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链 缺点 每次分配后所切割下来的剩余部分总是最小的 这样 在存储器中会留 下许多难以利用的碎片 最坏适应算法 最坏适应算法选择空闲分区的策略正好与最佳适应算法相反 它在扫描整个空 闲分区或链表时 总会挑选一个最大的空闲区 从中切割一部分存储空间给作 业使用 该算法要求 将所有的空闲分区 按其容量以大到小的顺序形成一空 闲分区链 查找时 只要看第一个分区能否满足作业要求即可 优点 可使剩下的空闲区不至于太小 产生碎片的可能性最小 对中小作业有 利 同时 最坏适应算法查找效率很高 缺点 导致存储器中缺乏大的空闲分区 三 数据结构 为了实现动态分区分配算法 系统中配置了相应的数据结构 用以描述空闲分 区和已分配分区的情况 常用的数据结构有空闲分区表和空闲分区链 流程图 当一个新作业要求装入主存时 必须查空闲分区表 从中找出一个足够大的空 闲区 若找到的空闲区大于作业需要量 这时应把它分成两部分 一部分为占 用区 另一部分为空闲区 当一个作业撤离时 归还的区域如果与其他空闲区相邻 则合并成一个较大的 空闲区 登录在空闲区表中 四 功能实现四 功能实现 五 心得体会 通过本次实验 对动态内存分配的相关知识有了更深的认识 中途也遇到了许 多困难 但幸运的是最终的顺利的解决并完成了此次试验 也更加熟练地掌握 了关于内存分配的使用 六 源代码六 源代码 include using namespace std int FreePartition 100 空闲分区块数组 int FirstPartition 100 首次适应算法数组 int CycleFirstPartition 100 循环首次适应算法数组 int BestPartition 100 最佳适应算法数组 int WorstPartition 100 最坏适应算法数组 int ProcessNeed 100 每个作业的大小 int PartitionNum ProcessNum 分区块数 作业数 首次适应算法 void First int i j char str for i 0 i PartitionNum i FirstPartition i FreePartition i for i 0 i ProcessNum i 找出第一块满足作业的分区 for j 0 jFirstPartition j continue else FirstPartition j ProcessNeed i 找到后把分区大小减去作业的大小 str A i cout 作业 str 在第 j 1 块分区中 endl break cout endl cout 分配之后剩余情况 endl for i 0 i PartitionNum i cout FirstPartition i cout endl endl 循环首次适应算法 void CycleFirst int i j 1 char str for i 0 i PartitionNum i CycleFirstPartition i FreePartition i for i 0 i ProcessNum i for j 0 j PartitionNum j j j 1 while jCycleFirstPartition j continue j else CycleFirstPartition j ProcessNeed i str A i cout 作业 str 在第 j 1 块分区中 endl break j cout j if j PartitionNum cout endl cout 分配之后剩余情况 endl for i 0 i PartitionNum i cout CycleFirstPartition i cout endl endl 最佳适应算法 void Best int i j k char str for i 0 i PartitionNum i BestPartition i FreePartition i for i 0 i ProcessNum i k 0 for j 0 j PartitionNum j cout BestPartition j ProcessNeed i ProcessNeed i k j break for int n 0 n PartitionNum n if BestPartition n ProcessNeed i 找最佳的 k n BestPartition k ProcessNeed i str A i cout 作业 str 在第 j 1 块分区中 endl cout endl cout 分配之后剩余情况 endl for i 0 i PartitionNum i cout BestPartition i cout endl endl 最坏适应算法 void Worst int i j k char str for i 0 i PartitionNum i WorstPartition i FreePartition i for i 0 i ProcessNum i k 0 for j 0 jWorstPartition k 找到最大的分区 k j WorstPartition k ProcessNeed i str A i cout 作业 str 在第 j 1 块分区中 endl cout endl cout 分配之后剩余情况 endl for i 0 i PartitionNum i cout WorstPartition i cout endl endl void main int i cout 输入分区块数 PartitionNum cout 输入每个分区的大小 endl for i 0 i FreePartit