动态内存分配和回收

1、实验五 可变分区存储管理方式的内存分配和回收一实验目的通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储 管理的内存分配和回收。二实验属性设计三实验内容1确定内存空间分配表；2采用最优适应算法完成内存空间的分配和回收； 3编写主函数对所做工作进行测试。四实验背景材料实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录内存使用情况的 数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计内存分 配算法；第三，在设计的数据表格基础上设计内存回收算法。首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占 用的区域。由于可

2、变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的 个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必 须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地 址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时， 可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格 操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某 个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。 由此可见，内存的分配和回收主要是对

3、空闲区的操作。这样为了便于对内存空间的分配和回 收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”； 一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一 种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固 定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是 系统可能的最大项数。“已分分区表”的结构定义#define n 10 /假定系统允许的最大作业数量为 nstruct float address; /已分分区起始地址float length; /已分分区长度、单位为字节in

4、t flag; /已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业 名used_tablen; /已分分区表“空闲区表”的结构定义#define m 10 /假定系统允许的空闲区最大为 mstruct float address; /空闲区起始地址float length; /空闲区长度、单位为字节int flag; /空闲区表登记栏标志，“0”表示空栏目，“1”表示未分配free_tablen; /空闲区表 第二，在设计的数据表格基础上设计内存分配。装入一个作业时，从空闲区表中查找满足作业长度的未分配区，如大于作业，空闲区划 分成两个分区，一个给作业，一个成为小空闲分区。实

5、验中内存分配的算法采用“最优适应”算法，即选择一个能满足要求的最小空闲分区 可变分区方式的内存分配流程如图。第i栏标志为、 未分配”且满足 、作业需求xk?/是否找到满足需 、求的分区k? 主存分配失败第i栏标志为、 未分配”且满足 、作业需求xk?/是否找到满足需 、求的分区k? 主存分配失败/第k栏、长度-作业需求 Wminsize?结束/第i栏空闲区为、第一个满足需求的或第i栏空闲区长度、小于第k栏空闲区z长度？ /分配整个分区：第k栏状态为“空” ad=鎗k档趙始地址 xk=宙k栏长应切割空闲区：第k栏长度减去xk ad=第k栏起始地址- 第k栏长度开始作业J申请xk大小的内存空间i是

6、空闲区表中 一栏(i=m) ?空闲区表状 态未分配空闲区表第空闲区表状 态未分配空闲区表第k 栏状态为空？i=0i=i+：栏是己分配区表旷W栏且笫i栏状态不为空2填写已分分区表： 第j栏起始地址=ad 鎗j栏长度=xk 第j栏状态=作业名J空闲区表第k栏长度加xk已分分区表长度不足，分配失败第三，在设计的数据表格基础上设计内存回收问题内存回收时若相邻有空闲分区则合 并空闲区，修改空闲区表。.可变分区方式的内存回收流程如图。开始NYi=0NNNNYt=0NYNN结束未找到作业 回收失败第i栏为回收 分区的上邻？回收分 区有上邻?和上邻合并： 第k栏长度= 第k栏长度+L回收分 区有下邻3二为已分配 区表中一栏? t栏、 是空闲表中区有下邻？第i栏为回收 分区的下邻j第i栏状态为 二未分配”7咗栏,已分分区表第s栏4T 态为作业J (s=n) ?/第i栏不是空闲、Y 区表中一栏或回收分区一 、上下邻空闲区均/才 找到？S=已分分区表第s栏起始地址 L=已分分区表第s栏长度 已分分区表第s栏状态为空已分分区表第Ns栏状态为J： 空闲区表长度不 足，回收失败归还分区填入空闲区 表.第t栏起始地址=S第t栏长度=L第t栏状态=未分配和上下邻三项合并： 第k栏长度=第丘栏 长度+第j栏长度+L 第j栏状走=空和下邻合并：第j栏长度=第)栏