课程设计2 内存管理子系统一、课程设计目的通过模拟操作系统的可变分区存储管理方式的内存分配回收的实现。加深对可变分区存储管理方式原理的理解，进一步采用可变分区存储管理方式的内存分配回收的实现方法，并可练习合作完成系统的团队精神和提高程序设计能力。二、预备知识存储管理中可变分区的管理方式。三、小组人数建议3人为一组共同完成模拟系统的实现。四、课程设计内容编写程序完成可变分区存储管理方式的内存分配回收。实验具体包括：首先确定内存空间分配表；然后采用最优适应算法完成内存空间的分配和回收；最后编写主函数对所做工作进行测试。五、提示与讲解可变分区管理方式预先将内存划分成几个区域.而将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。实现可变分区的分配和回收，主要考虑的问题有3个，第一，设计记录内存使用情况数据表格，用来记录空闲区和作业占用的区域，第二，在设计的数据表格基础上设计内存分配算法；第三，在设计的数据表格基础上设计内存回收算法。首先，专虑第一个问题:由于可变分区的大小是由作业需求量决定的。故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化.数据表格的设计必须和这个特点相适应。由于分区长度不同。因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区-空闲区和已分分区，在回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作烦琐。可在分配内存时查找空闲区进行分配，然后填写已分配区表。主要操作在空闲区；某个作业执行完后。将该分区变成空闲区。并将其与相邻的空闲区合并，主要操作也在空闲区：由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收。就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“已分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种:一种是链表形式。一种是顺序表形式，在实验中，采用顺序表形式。用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”，必须事先确定长度.且这一长度必须是系统可能的最大项数，这样系统在运行过程中才不会出错，因而在多数情况下，无论是“已分分区表”还是“空闲区表”都有空闲栏目。“已分分区表”中，除了分区起始地址、长度外，至少还要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；“空闲区表”中除了分区起始地址、长度外，也要有一顶“标志”，如果是空闲栏目，内容为“空”。如果为某个空闲区的登记项.内容为“未分配”。在实际系统中。这两个表格的内容可能还要多，实验中仅仅使用上述必须的数据，为此，“己分分区表”和“空闲区表”在实验中有如下的结构定义。 已分配区表的定义：#define n 10 /假定系统允许的最大作业数量为n struct float address; /已分分区起始地址float length; /已分分区长度，单位为字节int flag; /已分分区表登记栏标志。“0”表示空栏目，试验中只支持一个字符used_tablen； /已分分区表空闲区表的定义：#define m 10 /假定系统允许的最大作业数量为m struct float address; /空闲区起始地址float length; /空闲区长度，单位为字节int flag; /空闲区表登记栏标志。“0”表示空栏目，“1”表示未分配free_tablem； /空闲区表其中分区起始地址和长度数值太大，超出了整型表达范围，所以采用了float类型。下面讲解如何在设计的数据表格上进行内存的分配：当要装入一个作业时，从空闲区表中查找标志为“未分配”的空闲区，从中找到能容纳该文件的空闲区，如果找到的空闲区正好等于该作业的长度，这时应该把该空闲区的登记项标志改为“空”，同时。在已分配区表中找到一个标志为“空”的栏目登记新装人作业所占用分区的起始地址，长度和作业名。如果找到的空闲区大于作业长度。则把空闲区分成两部分，一部分用来装入作业，另外一部分仍为空闲区。这时只要修改原空闲区的长度，且把新装人的作业登记到已分配区表中。实验中内存分配算法采用“最优适应”算法：最优适应算法是按作业要求挑选一个能满足作业要求的最小空闲区。这样保证可以不去分割一个大的区域.使较入大作业时比较容易得到满足，但是，最优适应算法容易出现找到的一个分区可能只比作业所要求的长度略大一点的情况.这时，空闲区分割后剩下的空闲区就很小。这种很小的空闲区住往无法再使用，影响了内存的使用。为了在一定程度上解决这个问题。如果空闲区的大小比作业要求的长度略大一点，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区分配给作业。在实现最优适应算法时。可把空闲区按长度以递增方式登记在空闲区表中。分配时顺序查找空闲表，查找到的第一个空闲区就是满足作业要求的最小分区，这样查找速度快.但是为使空闲区按长度以递增顺序登记在空闲表中，就必须在分配回收时进行空闲区表的调整实验中不采用空闲区有序登记在空闲表中的方法: 可变分区方式的内存分配流程如图2-3-1所示。下面讲解可变分区方式下的内存回收问题：在可变分区方式下回收内存空间时，应该检查是否有与归还区相邻的空闲区。若有，则应该合件成一个空闲区。一个归区还可能有上邻空闲区，也可能有下邻空闲区。或者既有上邻空闲区又有下邻空闲区，或者既无上邻空闲区也无下邻空闲区.在实验回收时.首先将作业归还的区域在已分配表中找到将该栏目的状态变为“空“;然后，检查空闲区表中标志为“未分配的栏目。查找是否有相邻空闲区;最后，合并空闲区，修改空闲区表。假定作业归还的分区起始地址为S，长度为L，则：1、归还区有下邻空闲区 如果S+L正好等于空闲区表中某个登记栏目(假定为第j栏)的起始地址，则表明归还区有一个下邻空闲区。这时只要修改第j栏登记项的内容： 起始地址=S；第j栏长度=第j栏长度+L；则第j栏指示的空闲区是归还区和下邻空闲区合并后的大空闲区。2、归还区有上邻空闲区如果空闲区表中某个登记栏目(假定为第k栏)的“起始地址+长度”正好等于S。则表明归还区有一个上邻空闲区.这时要修改第k栏登记项的内容(起始地址不变):第k栏长度=第k栏长度+L；于是第k栏指示的空闲区是归还区和上邻空闲区合并后的大空闲区。3、归还区既有上邻空闲区又有下邻空闲区如果S+L正好等于空闲区表中某个登记拦目(假定为第j栏)的起始地址，同时还有某个登记栏目(假定为第k栏)的“起始地址+长度”正好等于S，这表明归还区既有一个上邻空闲区又有一个下邻空闲区。此时对空闲区表的修改如下：第k栏长度=第k栏长度+第j栏长度+L(第k栏起始地址不变)第j栏状态=“空”(将第j栏登记项删除)这样，第k栏指示的空闲区是归还区和上、下邻空闲区合并后的大空闲区。原来的下邻空闲区登记项(第j栏)被删除。置为“空”。开始作业j申请xk大小的内存空间i=k；k=-1i是空区表中一栏（i=m）?第i栏标记为“未分配”且满足作业需求xk？第i栏空闲区为第一个满足需求的或第i栏空闲区长度小于第k栏空闲区长度？i=i+1是否找到满足需求的分区k？内存分配失败结束第k栏长度-作业需求minsize分配整个分区：第k栏状态为“空”ad=第k栏起始地址xk=第k栏长度切割空闲区：第k栏长度减去xkad=第k栏起始地址第k栏长度i=0第i栏是已分配区表中一栏且第i栏状态不为空？i=i+1第i栏是是否为已分配表中的一栏？填写已分分区表：第j栏起始地址=ad第j栏长度=xk第j栏状态=作业名j空闲区表第k栏状态为空？空闲区表状态未分配空闲区表第k栏长度+xk已分分区表长度不足，分配失败结束图2-3-1 可变分区最优分配算法流程NYNYNYNNk=1=1YNYNYN4、归还区既无上邻空闲区又无下邻空闲区如果在检查空闲区表时，无上述三种情况出现，则决表明归还区既无上邻空闲区又无下邻空闲区。这时，应该在空闲区表中查找一个状态为“空”的栏目(假定查到的是第t栏)。则第t栏的内容修改如下：第t栏起始地址=S；第t栏长度=L；第t栏状态=“未分配“;这样，第t栏指示的空闲区是归还区。按照上述方法归还内存区域的流程如图2-3-2所示。 由于是实验，没有真正的内存分配，所以在实验中，首先应建立一张空闲区表，初始状态只有一个空闲登记项(假定的内存空闲区)和一张所有状态都为“空”的已分配区表，假定内存空间110KB，操系系统占用10KB,其余为空闲区;然后，可以选择进行内存分配或内存回收。如果是分配。要求输入作业名和所需内存空间大小，如果是回收，输入回收作业的作业名.循环进行内存分配和回收。如果需要，则显示两张表的内容。以检查内存的分配和回收是否正确。开始作业j归还空间s=0已分分区表第s栏状态为作业j(s=n)?s=s+1s为已分配区表中一栏？S=已分分区表第s栏起始地址L=已分分区表第s栏长度已分分区表第s栏状态为空假设下邻空闲区在第j栏j=-1假设上邻空闲区在第k栏k=-1i=0未找到作业，回收失败结束第i栏状态为“未分配”？第i栏不是空闲区表中一栏或回收分区的上下邻空闲区均找到？第t栏为空闲表中非空栏？第i栏为回收分区的下邻？i=i+1j=ij=i回收分区有下邻？回收分区有下邻？和上下邻三项合并：第k栏长度=第k栏长度+第j栏长度+L第j栏状态=“空”回收分区有上邻？和上邻合并：第k栏长度=第k栏长+Lt=0和上邻合并：第j栏长度=第j栏长+L第j栏起始地址=slanqishi的第i栏为回收分区的上邻？t=t+1已分分区表第s栏状态为j，空闲区表长度不足，回收失败归还分区填入空闲区表：第t栏起始地址=s第t栏状态长度=L第t栏状态=“未分配”第t栏是空闲表中一栏？结束NYNYYYYYNYNNYYNNNYNYYN图2-3-2 可变分区回收流程六、参考程序 略