操作系统课程设计-可变分区存储管理算法模拟.doc

课程设计课程名称操作系统题目名称可变分区存储管理算法模拟专业班级2013级软件工程学生姓名学 号指导教师二一五年五月二十日目录蚌埠学院计算机科学与技术系课程设计任务书1计算机科学与技术系课程设计成绩评定标准及成绩评定表2一、引言31.1课程设计的目的31.2实验要求31.3预备知识31.4课程设计内容4二、需求分析42.1 整体思路42.2设计所才用的算法42.3内存分配与回收所使用的结构体52.4关于分配留下的内存小碎片问题52.5内存的回收5三、总体设计63.1 数据结构描述63.1.1、全局变量63.1.2、空闲分区表定义63.1.3、已分配表定义63.1.4、函数声明63.2 流程图73.2.1、系统总体流程图（如图3-1所示）73.2.2作业分配流程图83.2.3内存回收流程图9四、详细设计104.1首次适应算法104.2最佳适应算法114.3最差适应算法134.4内存回收15五、测试运行175.1、后台代码的截图175.1.1 初始化程序，使用首次适应、最优动态、最坏适应等算法进行内存分配175.1.2查看内存分配状态185.1.3上下无空闲邻接回收185.1.4上邻接空闲区回收195.1.5上下邻接区19六、心得体会20七、参考教材21附录：源代码21蚌埠学院计算机科学与技术系课程设计任务书课 程操作系统班级2013级软件工程指导教师何爱华题 目可变分区存储管理算法模拟完成时间2015年5月25日至2015年6月 21日主要内容要求完成以下功能：1能够输入作业情况和申请信息等。2能够采用不同算法实现内存分配。3能够实现内存回收。4能够显示内存分配情况。5设计良好的交互界面。6撰写课程设计报告。设计报告要求1封面：（格式附后）2课程设计任务书3课程设计报告： 系统总体方案 设计思路和主要步骤 各功能模块和流程图 设计代码 心得体会和参考资料说明：学生完成课程设计后，提交课程设计报告及软件，要求文字通畅、字迹工整（也可用以打印），文字不少于5000 字，并装订成册。版面要求1 题目用黑体三号，段后距18磅（或1行），居中对齐；2 标题用黑体四号，段前、段后距6磅（或0.3行）；3 正文用小四号宋体，行距为1.25倍行距；4 标题按“一”、“”、“1”、“”顺序编号。5 本文档材料a4纸双面打印。上机时间安排星期周次一二三四五六日第14周-第17周13软件工程1、2节13软件工程1、2节指导时间地点上机时间，多媒体技术实验室（b530、b528）计算机科学与技术系课程设计成绩评定标准及成绩评定表学生姓名：张小蒙学号：51302041034班级：13级软件工程项目分值优秀(100x90)良好(90x80)中等(80x70)及格(70x60)不及格(x60)分项得分学习态度20设计态度认真，科学作风严谨，严格保证设计时间并按任务书中规定的进度开展各项工作设计态度比较认真，科学作风良好，能按期圆满完成任务书规定的任务设计态度尚好，遵守组织纪律，基本保证设计时间，按期完成各项工作设计态度尚可，能遵守组织纪律，能按期完成任务学习马虎，纪律涣散，工作作风不严谨,不能保证设计时间和进度技术水平与实际能力30设计能力强，能独立思考问题，并主动查阅文献资料解决问题，实际动手能力强、工程制图能力强设计合理、理论分析与计算正确，有较强的实际动手能力、分析能力，文献引用、调查调研比较合理、可信设计合理，理论分析与计算基本正确，有一定的实际动手能力，主要文献引用、调查调研比较可信设计基本合理，理论分析与计算无大错，主要文献引用、调查调研比较可信设计不合理，理论分析与计算有原则错误，实际动手能力差，文献引用、调查调研有较大的问题论文撰写质量50绘图规范，结构设计合理、表达正确、清晰，绘图质量好，说明书内容详实，结构严谨，逻辑性强，层次清晰，计算正确、结论准确、撰写规范工整结构合理，符合逻辑，文章层次分明，语言准确，文字流畅，符合规范化要求，书写工整；图纸清晰、工整结构合理，层次较为分明，文理通顺，基本达到规范化要求，书写比较工整；图纸比较工整、清晰结构基本合理，逻辑基本清楚，文字尚通顺，勉强达到规范化要求；图纸比较工整绘图不规范，结构设计有较多错误，表达不清楚，绘图质量差，说明书内容空泛，有太多缺漏或错误，结构混乱，书写潦草成绩评定：指导教师签名：年月日注：本课程设计成绩评定表应装入学生课程设计资料袋作为资料保存。可变分区存储管理方式的内存分配回收一、引言1.1课程设计的目的本课题采用可变分区存储管理方式的模拟实现内存分配与回收。可变分区分配是一种重要的存储管理思想，目前流行的操作系统采用的分段存储管理的基本思想就源自该方法。本课程设计通过编程模拟可变分区分配存储管理，经过学生亲自动手编写管理程序，可以进一步加深操作系统中对可变分区分配存储管理方案设计思想的理解。1.2实验要求(1)内存分配采用首次适应算法、最佳适应算法与最差分配算法分别完成。(2)动态输入构造空闲区表,并显示构造好的空闲区表。(提示:在两种不同的内存分配算法中,空闲区在空闲区表中的登记顺序是不一样的)(3)键盘接收作业申请的内存尺寸大小。(4)根据申请,实施内存分配,并返回分配所得内存首址。(5)分配完后,调整空闲区表(即扣除分配部分),并显示调整后的空闲区表。(6)若分配失败,返回分配失败信息。(7)内存回收根据空闲区表,按内存回收的四种情况从键盘接收回收区域的内存首址与大小；回收区域,调整空闲区表(与前面空闲区相连,与后面空闲区相连,与前后空闲区相连则合并,与前后空闲区都不相连则插入该项),并显示调整后的空闲区表。1.3预备知识存储管理中可变分区的管理方式，理解掌握作业申请内存时的方法，编程实现分区回收算法，对实验列出的几种分区回收情况都应该能处理。熟练运用c+编程，采用结构体定义数组。1.4课程设计内容编写程序完成可变分区存储管理方式的内存分配与回收。具体包括：确定内存空间分配表；采用相关算法完成内存空间的分配和回收；撰写课程设计报告。二、需求分析2.1整体思路可变分区管理方式将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。2.2设计所才用的算法（1）首次适应算法，每次为作业分配内存时，总是按当前位置下一个位置搜索，查找满足作业大小的内存给予分配。（2）最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。（3）最差分配算法，每次为作业分配内存时，总是把既能满足要求、又是最大的空闲分区分配给作业。 但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值minsize，如果空闲区的大小减去作业需求长度得到的值小于等于minsize，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。2.3内存分配与回收所使用的结构体为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。2.4关于分配留下的内存小碎片问题当要装入一个作业时，从“空闲分区表”中查找标志为“1”（未分配）且满足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值小于或等于minsize，把该分区全部分配给作业，并把该空闲区的标志改为“0”（空栏目）。同时，在已分配区表中找到一个标志为“0”的栏目登记新装人作业所占用分区的起始地址，长度和作业名。若空闲区的大小与作业所需大小的差值大于minsize。则把空闲区分成两部分，一部分用来装入作业，另外一部分仍为空闲区。这时只要修改原空闲区的长度，且把新装人的作业登记到已分配区表中。2.5内存的回收在可变分区方式下回收内存空间时，先检查是否有与归还区相邻的空闲区（上邻空闲区，下邻空闲区）。若有，则将它们合件成一个空闲区。程序实现时，首先将要释放的作业在“内存分配表”中的记录项的标志改为“0”（空栏目），然后检查“空闲区表”中标志为1（未分配）的栏目，查找是否有相邻的空闲区，若有，将之合并，并修改空闲区的起始地址和长度。三、总体设计3.1 数据结构描述3.1.1全局变量floatminsize=5;int count1=0;int count2=0;#define m 10 /假定系统允许的空闲区表最大为m#define n 10 /假定系统允许的最大作业数量为m3.1.2空闲分区表定义structfloat address;/空闲区起始地址 float length;/空闲区长度，单位为字节int flag; /空闲区表登记栏标志，用0表示空栏目，用1表示未分配free_tablem; /空闲区表3.1.3已分配表定义structfloat address; /已分分区起始地址 float length; /已分分区长度，单位为字节int flag; /已分配区表登记栏标志，0表示空栏目，实验中只支持一个字符的作业名used_tablen; /已分配区表3.1.4函数声明void initialize(void);int distribute(int,float); /最优动态分配算法intshouci(int,float); /首次适应算法intzuicha(int,float); /最差适应算法int recycle(int); /内存回收void show(); /显示状态void fenpei(); /分配函数3.2 流程图3.2.1系统总体流程图（如图3-1所示，以下添加）描述：程序的总体结构方框图，如下图3-1所示主函数main（）内存回收recycle()显示遍历结果show()最差分配算法zuicha()最优分配算法distribute()首次适应算法shouci()分配表fenpei()图3-1系统总体流程图3.2.2作业分配流程图描述：作业的分配流程图如图3-2所示图3-2 作业分配流程图3.2.3内存回收流程图描述：作业回收的过程如图3-3所示图3-3内存回收流程图四、详细设计4.1首次适应算法intshouci(intname,float memory)inti,k=-1;float ads, len;int count=0;i=0;while(i=m-1) /循环找到最佳的空闲分区if(memory =free_tablei.length)k=i;break;i=i+1;if(k!=-1)if(free_tablek.length-memory)=minsize) /整个分配free_tablek.flag=0;ads=free_tablek.address;len=free_tablek.length;else/切割空闲区ads=free_tablek.address;len=memory;free_tablek.address+=memory;free_tablek.length-=memory;i=0;/循环寻找内存分配表中标志为空栏目的项while(used_tablei.flag!=0) i=i+1;if(i=n-1) /找到，在已分配区表中登记一个表项used_tablei.address=ads;used_tablei.length=len;used_tablei.flag=name;count1+;else /已分配区表长度不足if(free_tablek.flag = 0) /将已做的整个分配撤销free_tablek.flag=1;free_tablek.address=ads;free_tablek.length=len;else /将已做的切割分配撤销free_tablek.address=ads; free_tablek.length+=len;cout内存分配区已满，分配失败！n; return 0;elsecout无法为该作业找到合适分区！n;return 0;return name;4.2最佳适应算法/最优分配算法实现的动态分区int distribute(intprocess_name, float need_length)inti, k=-1;/k用于定位在空闲表中选择的未分配栏float ads, len;int count=0;i=0;while(i=m-1) /循环找到最佳的空闲分区if(free_tablei.flag=1 &need_length=free_tablei.length)count+;if(count=1|free_tablei.length free_tablek.length)k=i;i=i+1;if(k!=-1)if(free_tablek.length-need_length)=minsize) /整个分配free_tablek.flag=0;ads=free_tablek.address;len=free_tablek.length;else/切割空闲区ads=free_tablek.address;len=need_length;free_tablek.address+=need_length;free_tablek.length-=need_length;i=0;/循环寻找内存分配表中标志为空栏目的项while(used_tablei.flag!=0) i=i+1;if(i=n-1) /找到，在已分配区表中登记一个表项used_tablei.address=ads;used_tablei.length=len;used_tablei.flag=process_name;count1+;else /已分配区表长度不足if(free_tablek.flag = 0) /将已做的整个分配撤销free_tablek.flag=1;free_tablek.address=ads;free_tablek.length=len;else /将已做的切割分配撤销free_tablek.address=ads; free_tablek.length+=len;cout内存分配区已满，分配失败！n; return 0;elsecout无法为该作业找到合适分区！n;return 0;returnprocess_name;4.3最差适应算法/最差算法实现intzuicha(intname,float memory)inti, k=-1;/k用于定位在空闲表中选择的未分配栏float ads, len;int count=0;i=0;while(i=m-1) /循环找到最佳的空闲分区if(free_tablei.flag=1 & memoryfree_tablek.length)k=i;i=i+1;if(k!=-1)if(free_tablek.length-memory)=minsize) /整个分配free_tablek.flag=0;ads=free_tablek.address;len=free_tablek.length;else/切割空闲区ads=free_tablek.address;len=memory;free_tablek.address+=memory;free_tablek.length-=memory;i=0;/循环寻找内存分配表中标志为空栏目的项while(used_tablei.flag!=0) i=i+1;if(i=n-1) /找到，在已分配区表中登记一个表项used_tablei.address=ads;used_tablei.length=len;used_tablei.flag=name;count1+;else /已分配区表长度不足if(free_tablek.flag = 0) /将已做的整个分配撤销free_tablek.flag=1;free_tablek.address=ads;free_tablek.length=len;else /将已做的切割分配撤销free_tablek.address=ads; free_tablek.length+=len;cout内存分配区已满，分配失败！n; return 0;elsecout无法为该作业找到合适分区！n;return 0;return name;4.4内存回收/内存回收int recycle(intprocess_name) int y=0;floatrecycle_address, recycle_length;inti, j, k; /j栏是下邻空闲区，k栏是上栏空闲区int x; /在内存分配表中找到要回收的作业while(y=n-1&used_tabley.flag!=process_name)y=y+1;if(y=n-1) /找到作业后，将该栏的标志置为0recycle_address=used_tabley.address;recycle_length=used_tabley.length;used_tabley.flag=0;count2+;else /未能找到作业，回收失败cout=m|(k!=-1&j!=-1) /修改空闲分区表if(free_tablei.flag=1)if(free_tablei.address+free_tablei.length)=recycle_address)k=i;/判断是否有上邻接if(recycle_address+recycle_length)=free_tablei.address)j=i;/判断是否有下邻接i=i+1;/合并空闲区if(k!=-1) /回收区有上邻接if(j!=-1)/回收区也有下邻接，和上下领接合并free_tablek.length+=free_tablej.length+recycle_length;free_tablej.flag=0;/将第j栏的标记置为0else /不存在下邻接，和上邻接合并free_tablek.length+=recycle_length;else if(j!=-1) /只有下邻接，和下邻接合并free_tablej.length+=recycle_length;free_tablej.address=recycle_address; else /上下邻接都没有x=0;while(free_tablex.flag!=0)x=x+1;/在空闲区表中查找一个状态为0的栏目if(x=m-1) /找到后，在空闲分区中登记回收的内存free_tablex.address=recycle_address;free_tablex.length=recycle_length;free_tablex.flag=1;else /空闲表已满，执行回收失败used_tabley.flag=process_name;cout空闲区已满，回收失败！n;return 0;returnprocess_name;五、测试运行5.1、后台代码的截图5.1.1初始化程序（1）如图5-1所示，系统采用首次适应、最佳、最差适应算法进行内存分配（格式）图5-1 分配内存5.1.2查看内存分配状态（2）如图5-2所示，内存分配状态显示图5-2显示状态5.1.3上下无空闲邻接回收（3）如图5-3所示，回收单一分配空间图5-3无邻接回收5.1.4上邻接空闲区回收（4）如图5-4所示，回收区和上邻接区合并图5-4上邻接5.1.5上下邻接区（5）如图5-4所示，回收区和上下邻接区合并图5-5上下邻接六、心得体会设计本课程前，感觉本课程并不是那么难，很容易下手，因为主要也就是写出回收主程序、内存分配主程序就行了。但是真正实施起来确非常困难。首先，必须解决动态输入构造空闲区表的问题。刚开始的时候，我们把其他的程序都写出来了，却忘了课题还要求动态输入构造空闲区表。于是我们又花了很大的力气才实现动态输入构造空闲区表，即：可以根据自己的需要，从键盘输入空闲区表的块数，并输入每块空闲区表的大小及首地址。其次，需要解决的是首次适应算法和最佳适应算法之间的转制问题。我们做完首次适应算法的程序后不知道该从什么地方着手写最佳适应算法。最后过了几天，才想到，原来只需在首次适应算法中，每次申请空闲区前先对空闲区从小到大排序即可。第三个难题就是解决回收算法的问题。回收算法可以说是本实验最难实现的算法，因为它有四种不同的情况。刚开始我们只考虑了三种情况，即：1、要回收的区域没有与之相邻接的空闲区。2、要回收区域有上邻（与要回收区域相邻的上面有空闲区）。3、要回收的区域有下邻（与要回收的区域相邻的下面有空闲区）。当我们满怀欣喜感觉本课程设计已经完成的时候却发现，程序运行的时候，对于一个刚分配好的空闲区，如果有三个相邻的作业可以同时在此空闲区内申请到内存，并全并回收此三个作业后，此空闲区会被分割成两个空闲区显示。这时我们才意识到少考虑了一种情况：要回收的区域有上邻而且有下邻。我们又不得不再次修改程序。就这样，在写出大体程序后，我们前后大大小小修改了十多次，最后修改好的程序完全符合课程设计要求，我们的课程设计终于成功了！七、参考教材1.汤小丹.计算机操作系统，西安电子科技大学出版社.20142谭浩强c+程序设计.清华大学出版社20043郭有强等编著.c+面向对象程序设计.20094郭有强等编著.c+面向对象程序设计实验指导与课程设计.2009附录：源代码#include#include#includeusing namespace std;/全局变量floatminsize=5;int count1=0;int count2=0;#define m 10 /假定系统允许的空闲区表最大为m#define n 10 /假定系统允许的最大作业数量为m/已分配表的定义struct float address; /已分分区起始地址float length; /已分分区长度，单位为字节int flag; /已分配区表登记栏标志，0表示空栏目used_tablen; /已分配区表的对象名/空闲区表的定义structfloat address; /空闲区起始地址float length; /空闲区长度，单位为字节int flag; /空闲区表登记栏标志，用0表示空栏目，用1表示未分配free_tablem; /空闲区表对象名/函数声明void initialize(void);int distribute(int,float); /最优动态分配算法intshouci(int,float); /首次适应算法intzuicha(int,float); /最差适应算法int recycle(int); /内存回收void show(); /显示状态void fenpei(); /分配函数/主函数void main()/system(color 09); /*修改控制台的颜色信息,改为白字蓝底的模式*/ system(mode con: cols=140 lines=130); /*设置批处理运行时窗口大小的*/ int choice;boolexitflag=false;coutttt 动态分区分配方式的模拟 n;coutttt *n;cout请选择操作类型：n; initialize(); /开创空闲区和已分配区两个表while(!exitflag)coutttt*n;coutttt* 1: 分配内存 2: 回收内存 *n;coutttt* 3: 查看分配 0: 退 出 *n;coutttt*n;coutchoice;switch(choice)case 0:exitflag=true;break;case 1:fenpei(); /分配内存break;case 2:int id;coutid;recycle(id);break;case 3:show();break;/初始化两个表void initialize(void)int a;for(a=0;a=n-1;a+)used_tablea.flag=0; /已分配表的表项全部置为空表项free_table0.address=1000;free_table0.length=1024;free_table0.flag=1; /空闲区表的表项全部为未分配/分配表voidfenpei()intjob_name;floatneed_memory;boolexitflag=false;int choice;while(!exitflag)coutttt*n;coutttt* 1: 首次适应算法 2: 最优动态分配算法 *n;coutttt* 3: 最坏适应算法 4: 返回主菜单 *n;coutttt*n;coutchoice;switch(choice)case 1:coutjob_nameneed_memory;shouci(job_name,need_memory);break;case 2:coutjob_nameneed_memory;distribute(job_name,need_memory);break;case 3:coutjob_nameneed_memory;zuicha(job_name,need_memory);break;case 4:exitflag=true;/首次适应算法intshouci(intname,float memory)inti,k=-1;float ads, len;int count=0;i=0;while(i=m-1) /循环找到最佳的空闲分区if(memory =free_tablei.length)k=i;break;i=i+1;if(k!=-1)if(free_tablek.length-memory)=minsize) /整个分配free_tablek.flag=0;ads=free_tablek.address;len=free_tablek.length;else/切割空闲区ads=free_tablek.address;len=memory;free_tablek.address+=memory;free_tablek.length-=memory;i=0;/循环寻找内存分配表中标志为空栏目的项while(used_tablei.flag!=0) i=i+1;if(i=n-1) /找到，在已分配区表中登记一个表项used_tablei.address=ads;used_tablei.length=len;used_tablei.flag=name;count1+;else /已分配区表长度不足if(free_tablek.flag = 0) /将已做的整个分配撤销free_tablek.flag=1;free_tablek.address=ads;free_tablek.length=len;else /将已做的切割分配撤销free_tablek.address=ads; free_tablek.length+=len;cout内存分配区已满，分配失败！n; return 0;elsecout无法为该作业找到合适分区！n;return 0;return name;/最优分配算法实现的动态分区int distribute(intprocess_name, float need_length)inti, k=-1;/k用于定位在空闲表中选择的未分配栏float ads, len;int count=0;i=0;while(i=m-1) /循环找到最佳的空闲分区if(free_tablei.flag=1 &need_length=free_tablei.length)count+;if(count=1|free_tablei.length free_tablek.length)k=i;i=i+1;if(k!=-1)if(free_tablek.length-need_length)=minsize) /整个分配free_tablek.flag=0;ads=free_tablek.address;len=free_tablek.length;else/切割空闲区ads=free_tablek.address;len=need_length;free_tablek.address+=need_length;free_tablek.length-=need_length;i=0;/循环寻找内存分配表中标志为空栏目的项while(used_tablei.flag!=0) i=i+1;if(i=n-1) /找到，在已分配区表中登记一个表项used_tablei.address=ads;used_tablei.length=len;used_tablei.flag=process_name;count1+;else /已分配区表长度不足if(free_tablek.flag = 0) /将已做的整个分配撤销free_tablek.flag=1;free_tablek.address=ads;free_tablek.length=len;else /将已做的切割分配撤销free_tablek.address=ads; free_tablek.length+=len;cout内存分配区已满，分配失败！n; return 0;elsecout无法为该作业找到合适分区！n;return 0;returnprocess_name;/最差算法实现intzuicha(intname,float memory)inti, k=-1;/k用于定位在空闲表中选择的未分配栏float ads, len;int count=0;i=0;while(i=m-1) /循环找到最佳的空闲分区if(free_tablei.flag=1 & memoryfree_tablek.length)k=i;i=i+1;if(k!=-1)if(free_tablek.length-memory)=mi