1569.动态分区存储管理方式的主存分配回收《操作系统原理》课程设计.doc

《1569.动态分区存储管理方式的主存分配回收《操作系统原理》课程设计.doc》由会员分享，可在线阅读，更多相关《1569.动态分区存储管理方式的主存分配回收《操作系统原理》课程设计.doc（12页珍藏版）》请在三一办公上搜索。

1、计算机科学与技术专业03级操作系统原理课程设计课题名称：动态分区存储管理方式的主存分配回收 姓 名： 班 级： 学 号： 课程设计起止时间：2005年12月26-30日指导教师： 成绩：课程设计任务书操作系统原理课程设计任务书设计题目：动态分区存储管理方式的主存分配回收任务下达时间：2005年12月26日任务完成时间：2005年12月30日指导教师： 指导教师评语一、所得结果：二、存在问题：成绩评阅人动态分区存储管理方式的主存分配回收一、 设计说明：编写程序完成动态分区存储管理方式的主存分配回收的实现。具体任务包括：首先确定主存空间分配表；然后采用最优适应算法完成主存空间的分配和回收；最后编写

2、主函数对所做工作进行测试。实现动态分区的分配和回收，主要考虑的问题有三个：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计数据表格基础上设计主存分配算法；第三，在设计数据表格基础上设计主存回收算法。二、 工作原理：动态分区管理方式预先不将主存划分成几个区域,而把主存除操作系统占用区域外的空间看作一个大的空闲区。当作业要求装入主存时,根据作业需要主存空间的大小查询主存内各个空闲区,当从主存空间中找到一个大于或等于该作业大小的主存空闲区时,选择其中一个空闲区,按作业需求量划出一个分区装入该作业。作业执行完后,它所占的主存分区被收回,成为一个空闲区.如果该空闲区的相

3、邻分区也是空闲区,则需要将相邻空闲区合并成一个空闲区。三、 详细设计：首先,考虑第一个问题:设计记录主存使用情况的数据表格, 用来记录空闲区和作业占用的区域。由于动态分区的大小是由作业需求量决定的,故分区的长度是预先不固定的,且分区的个数也随主存分配和回收变动。总之,所有分区情况随时可能发生变化,数据表格的设计必须和这个特点相适应。由于分区长度不同,因此设计的表格应该包括分区在主存中的起始地址和长度.由于分配时空闲区有时会变成两个分区:空闲区和已分分区,回收主存分区时,可能会合并空闲分区,这样如果整个主存采用一张表格记录已分分区和空闲区,就会使表格操作繁琐。主存分配时查找空闲区进行分配,然后填

4、写已分配区表,主要操作在空闲区；某个作业执行完后,将该分区变成空闲区,并将其与相邻的空闲区合并,主要操作也在空闲区。由此可见,主存的分配和回收主要是对空闲区的操作。这样为了便于对主存空间的分配和回收,就建立两张分区表记录主存使用情况,一张表格记录作业占用分区的“已分配区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种,一种是链表形式,一种是顺序表形式。在本处,采用顺序形式,用数组模拟。由于顺序表的长度必须提前固定,所以无论是“已分配区表”还是“空闲区表”都必须事先确定长度.它们的长度必须是系统可能的最大项数,系统运行过程中才不会出错,因而在多数情况下,无论是“已分配区表”还是

5、“空闲区表”都有空闲栏目。已分配区表中除了分区起始地址,长度外,也至少还要有一项“标志”,如果是空闲栏目,内容为“空”,如果为某个作业占用分区的登记项,内容为该作业的作业名；空闲区表中除了分区起始地址,长度外,也要有一项“标志”, 如果是空闲栏目,内容为“空”,如果为某个空闲区的登记项,内容为“未分配”。为此, “已分配区表”和“空闲区表”有如下的结构定义: 已分配区表的定义: #define n 10 /假定系统允许的最大作业数量 struct float address； /已分分区起始地址 float length； /已分分区长度，单位字节 int flag； /已分配区表登记栏标志，

6、用“0”表示空栏目，本程序只支持一个字符的作业名free_tablen； /已分配区表 空闲区表的定义: #define m 10 /假定系统允许的空闲区表最大为m struct float address； /空闲区起始地址 float length； /空闲区长度，单位字节 int flag； /空闲区表登记栏标志，用“0”表示空栏目，用“1”表示未分配free_tablem； /空闲区表 其中分区起始地址和长度数值太大,超出了整型表达范围,所以采用了float类型. 然后,就要考虑如何在设计数据表格基础上设计主存分配。 当要装入一个作业时,从空闲区表中查找标志为“未分配”的空闲区,从中找

7、出一个能容纳该作业的空闲区。如果找到的空闲区正好等于该作业的长度,则把该分区全部分配给作业.这时应该把该空闲区登记栏中的标志改为“空”,同时在已分配区表中找到一个标志为“空”的栏目登记新装入作业所占用分区的起始地址,长度和作业名。如果找到的空闲区大于作业长度,则把空闲区分成两部分,一部分用来装入作业,另外一部分仍为空闲区。这时只要修改原空闲区的长度,且把新装入的作业登记到已分配区表中。 动态分区方式的主存分配流程如图1所示。 最后是动态分区方式的主存回收问题。 动态分区方式下回收主存空间时,应该检查是否有与归还区相邻的空闲区。若有,则应该合并成一个空闲区.一个归还区可能有上邻空闲区,也可能有下

8、邻空闲区,或者既有上邻空闲区又有下邻空闲区, 或者既无上邻空闲区也无下邻空闲区.在实现回收时,首先将作业归还的区域在已分配表中找到,将该栏目的状态变为“空”,然后检查空闲区表中标志为“未分配”的栏目,查找是否有相邻空闲区；最后,合并空闲区,修改空闲区表。假定作业归还的分区起始地址为s,长度为L,则: (1)归还区有下邻空闲区 如果s+L正好等于空闲区表中某个登记栏目(假定为第j栏)的起始地址,则表明归还区有一个下邻空闲区.这时只要修改第j栏登记项的内容: 起始地址=s； 第j栏长度=第j栏长度+L则第j栏指示的空闲区是归还区和下邻空闲区合并后的大空闲区。 (2) 归还区有上邻空闲区 如果空闲区

9、表中某个登记栏目(假定为第k栏)的“起始地址+长度”正好等于s,则表明归还区有一个上邻空闲区。这时要修改第k栏登记项的内容(起始地址不变): 第k栏长度=第k栏长度+L 于是第k栏指示的空闲区是归还区和上邻空闲区合并后的大空闲区。 (3) 归还区既有上邻空闲区又有下邻空闲区 如果s+L正好等于空闲区表中某个登记栏目(假定为第j栏)的起始地址,同时还有某个登记栏目(假定为第k栏)的“起始地址+长度”正好等于s,这表明归还区既有上邻空闲区又有下邻空闲区。此时对空闲区表的修改如下:第k栏长度=第k栏长度+第j栏长度+L；(第k栏起始地址不变)第j栏状态=“空”； (将第j栏登记项删除)这样, 第k栏

10、指示的空闲区是归还区和上、下邻空闲区合并后的大空闲区,原来的下邻空闲区登记项(第j栏)被删除,置为“空”。 (4) 归还区既无上邻空闲区又无下邻空闲区 如果在检查空闲区表时,无上述三种情况出现,则表明归还区既无上邻空闲区又无下邻空闲区。这时,应该在空闲区表中查找一个状态为“空” 栏目(假定查到的是第t栏),则第t栏的内容修改如下:第t栏起始地址=s；第t栏长度=L；第t栏状态=“未分配”；这样, 第t栏指示的空闲区是归还区.按上述方法归还主存区域的流程如图2所示。 由于是课程设计,没有真正的主存要分配,所以在程序中,首先应建立一张空闲区表,初始状态只有一个空闲登记项(假定的主存空闲区)和一张所

11、有状态都为“空”的已分配区表,假定主存空间110KB,操作系统占用10KB,其余为空闲区；然后,可以选择进行主存分配或主存回收,如果是分配,要求输入作业名和所需主存空间大小,如果是回收,输入回收作业的作业名,循环进行主存分配和回收后,如果需要,则显示两张表的内容,以检查主存的分配和回收是否正确。作业j申请xk大小的主存空间I=0;k=-1;I是空闲区表中一栏（I=m）? N Y是否找到满足需求的分区k？ 第i栏为“未分配”且满足作业xk? N Y继续分配 N主存分配失败第I栏空闲区为第一个满足需求的或小于第k栏长度？ N结束K=iI=I+1 图1动态分区最优分配算法流程图作业j归还空间 S=0

12、S=s+1已分配区表第s栏状态为作业j (s=n)? NS为已分配区表中一栏？ Y N未找到作业，回收失败 Y假设下邻空闲区在第j栏j=-1;假设上邻空闲区在第k栏k=-1;结束I=0第I栏状态为“未分配”？I=I+1 Y第i栏回收分区的上邻？ NJ=i第i栏回收分区的下邻？ YJ=i Y N 图2动态分区回收流程图代码部分：#define n 10 /假定系统允许的最大作业数量为n#define m 10 /假定系统允许的空闲区表最大为m#define minisize 100struct float address; /已分分区起始地址 float length; /已分分区长度，单位字节

13、 int flag; /已分配区表登记栏标志，用“0”表示空栏目，本程序只支持一个字符的作业名free_tablen; /已分配区表struct float address; /空闲区起始地址 float length; /空闲区长度，单位字节 int flag; /空闲区表登记栏标志，用“0”表示空栏目，用“1”表示未分配free_tablem; /空闲区表allocate(j,xk)/采用最优分配算法分配xk大小的空间char j;float xk;int i,k; float ad;k=-1;for (i=0;i=xk&free_tablei.flag=1)if (k=-1| free_

14、tablei.length free_tablek.length) k=i;if (k=-1) /未找到可用空闲区，返回printf(“无可用空闲区n”);return; /找到可用空闲区，开始分配；若空闲区大小与要求分配的空间差小于minisize大小，则空闲区全部分配；若空闲区大小与要求分配的空间差大于minisize大小，则从空闲区划出一部分分配if (free_tablek.length-xk=minisize)free_tablek.flag=0;ad=free_tablek.address;xk=free_tablek.length;elsefree_tablek.length=f

15、ree_tablek.length-xk; ad=free_tablek.address+ free_tablek.length;/修改已分配区表i=0;while(used_tablei.float!=0&i=n) /无表目填写已分分区pintf(“无表目填写已分分区，错误n”);/修正空闲区表if (free_tablek.flag=0) /前面找到的是整个空闲区 free_tablek.flag=1;else /前面找到的是某个空闲区的一部分 free_tablek.length=free_tablek.length+xk;return; else /修改已分配区表 used_table

16、i.address=ad; used_tablei.length=xk; used_tablei.flag=j;return;/主存分配函数结束Reclaim(j)/回收作业名为j的作业所占主存空间char j; int i,k,j,s,t; float s,l; /寻找已分配区表中对应登记项 s=0;while(used_tables.flag!=j|used_tables.flag=0)&s=n) /在已分配区表中找不到名字为j的作业printf(“找不到该作业n”); return; /修改已分配区表used_tables.flag=0;/取得归还分区的起始地址s和长度Ls=used_t

17、ables.address;L=used_tables.length;J=-1;k=-1;i=0;/寻找回收分区的上下邻空闲区，上邻表目k，下邻表目jwhile(im&(j=-1|k=-1)if (free_tablei.glag=0) if (free_tablei.address+free_tablei.length=s)k=I; /找到上邻 if (free_tablei.address=s+l)j=i; /找到下邻 i+; if(k!=-1) if (j!=-1) /上邻空闲区，下邻空闲区，三项合并 free_tablek.length= free_tablej.length+ fre

18、e_tablek.length+l;free_tablej.flag=0; else /上邻空闲区，下邻非空闲区，与上邻合并 free_tablek.length= free_tablek.length+l;else if(j!=-1) /上邻非空闲区，下邻为空闲区，与下邻合并free_tablej.address=s; free_tablej.length= free_tablej.length+l;else /上下邻均为非空闲区，回收区域直接填入 /在空闲区表中寻找空栏目 t=0; while(free_tablet.flag=1&t=m) /空闲区表满，回收空间失败，将已分配区表复原 p

19、rintf(“主存空闲表没有空间，回收空间失败n”); used_tables.flag=j; return; free_tablet.adress=s; free_tablet.length=l; free_tablet.flag=1; return(true);/主存归还函数结束main()int i,a; float xk;char j;/空闲区表初始化 free_table0.address=10240; free_table0.length=102400; free_table0.flag=1; for(i=1;im;i+) free_tablei.flag=0;/已分配区表初始化

20、for(i=0;in;i+) used_tablei.flag=0; while(1) printf(“选择功能项(0-退出,1-分配主存,2-回收主存,3-显示主存)n”); printf(“选择功项(03):”); scanf(“%d”,&a); switch(a) case 0:exit(0); / a=0程序结束 case 1: / a=1分配主存空间 printf(“输入作业名j和作业所需长度xk: ”); scanf(“%*c%c%f”,&j,&xk); allocate(j,xk); /分配主存空间 break; case 2: / a=2回收主存空间 printf(“输入要回收

21、分区的作业名”);scanf(“%*c%c”,&j);reclaim(j); /回收主存空间break;case 3: /a=3显示主存情况，输出空闲区表和已分配区表printf(“输出空闲区表:n起始地址 分区长度 标志n”); for(i=0;im;i+) printf(%5.0f%10.0%6dn”,free_tablei.address,free_tablei.length,free_tablei.flag); printf(“按任意键,输出已分配区表n”); getch(); printf(“输出已分配区表:n起始地址 分区长度 标志n”); for(i=0;in;i+) if(us

22、ed_tablei.flag!=0)printf(“%6.0%9.0f%6cn”,used_tablei.address,used_tablei.length,used_tablei.flag); elseprintf(“%6.0%9.0f%6dn”,used_tablei.address,used_tablei.length,used_tablei.flag); break; default:printf(“没有该选项n”); /case /while/main()结束四、 运行结果:由于没有可应用软件，在C+上运行后，调试错误，所以不能显示分配过程。五、 分析结果：由于是课程设计,没有真正

23、的主存要分配,所以在程序中,首先应建立一张空闲区表,初始状态只有一个空闲登记项(假定的主存空闲区)和一张所有状态都为“空”的已分配区表,假定主存空间110KB,操作系统占用10KB,其余为空闲区；然后,可以选择进行主存分配或主存回收,如果是分配,要求输入作业名和所需主存空间大小,如果是回收,输入回收作业的作业名,循环进行主存分配和回收后,如果需要,则显示两张表的内容,以检查主存的分配和回收是否正确。 六、调试步骤以及调试过程中出现的问题及解决方法 由于时间和所学知识有限，所编出的程序难免会有一些问题，希望能在以后的学习过程中加以改进。在VC中调试C语言还是有一定难度，所以我只是把错误降到最低，

24、并没有完全改正过来，这也是我知识不足的证明。通过一周的课程设计,加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对动态分区管理的内存分配回收有了更深的认识，并能够用高级语言进行模拟演示。在这短短的一周时间里，通过浏览、阅读有关的资料，学到了很多东西，同时也发现仅仅书本的知识是远远不够的，需要把知识运用到实践中去，能力才能得到提高。另外，使我体会最深的是：任何一门知识的掌握，仅靠学习理论知识是远远不够的，要与实际动手操作相结合才能达到功效。一周的课程设计就要结束了，不但对专业知识有了更深的理解，更使自己认识到实践的重要性，理论、实践相结合才能达到很好的学习效果，特别是程序语言的学习。七、参考文献： 操作系统刘振鹏 李亚平 张明 编著 中国铁道出版社 操作系统习题与解析曾 平 李春葆 编著 清华大学出版社 计算机操作系统学习指导与题解 梁红兵 汤小丹 编著 西安电子科技大学出版社 操作系统考研指导 曾 平 编著 清华大学出版社 计算机操作系统教程 张尧学 史美林 编著 清华大学出版社