操作系统专业课程设计方案报告动态分区分配.doc

青岛理工大学操作系统课程设计报告院（系）： 计算机工程学院 专业： 计算机科学与技术专业 学生姓名： 牛利利 班级： 计算073 学号： 07106 题目： 动态分区别配模仿 起迄日期： 7月5日至7月16日 设计地点： 2号实验楼402室 指 导 教 师： 李 兰 第 2 学期完毕日期： 年 7 月 16 日一、 课程设计目操作系统是最重要计算机系统软件，同步也是最活跃学科之一。计算机系统由硬件和软件两某些构成。操作系统是配备在计算机硬件上第一层软件，是对硬件初次扩充。本次课程设计重要目是在学习操作系统理论知识基本上，对操作系统整体一种模仿。也是对本学期所学知识一种总体检测，使理论知识应用到实际编程中，依照理论算法来实现详细编程操作。同步通过本次课程设计加深对操作系统理论知识各个某些管理功能感性结识，进一步分析和理解各个某些之间联系和功能，最后达到对完整系统理解。同步，可以提高运用操作系统知识和解决实际问题能力；并且锻炼自己编程能力、创新能力以及开发软件能力；还能提高自己调查研究、查阅文献、资料以及编写软件设计文档能力并提高分析问题能力。操作系统课程设计重要任务是研究计算机操作系统基本原理和算法，掌握操作系统存储器管理、设备管理、文献管理和进程管理基本原理和算法。使学生掌握基本原理和办法，最后达到对完整系统理解。二、 课程设计内容仿真实现动态可变分区存储管理模仿系统。内存调度方略可采用初次适应算法、循环初次适应算法和最佳适应法等，并对各种算法进行性能比较。为了实现分区别配，系统中必要配备相应数据构造，用来描述空闲区和已分派区状况，为分派提供根据。惯用数据构造有两种形式：空闲分区表和空闲分区链。为把一种新作业装入内存，须按照一定算法，从空闲分区表或空闲分区链中选出一种分区别配给该作业。三、 系统分析与设计1、系统分析：动态分区别配是依照进程实际需要，动态地为之分派内存空间。在实现可变分区别配时，将涉及到分区别配中所用数据构造、分区别配算法和分区别配和回收操作这样三个问题。为了实现分区别配，系统中必要配备相应数据构造，用来描述空闲区和已分派区状况，为分派提供根据。惯用数据构造有两种形式：空闲分区表和空闲分区链。为把一种新作业装入内存，须按照一定算法，从空闲分区表或空闲分区链中选出一种分区别配给该作业。当前惯用分派算法有：初次适应算法、循环初次适应算法、最佳适应算法、最坏适应算法和迅速适应算法。在动态分区存储管理方式中，重要操作是分派内存和回收内存。2、系统设计： 系统运用某种分派算法，从空闲分区表中找到所需大小分区。设祈求分区大小为u.size，表中每个空闲分区大小可表达为m.size，若 m.size-u.sizesize（size为事先规定不再切割剩余分区大小）成立，则阐明多余某些太小，可不再切割，将整个分区别配给祈求者；否则，从该分区中按祈求大小划分出一块内存空间分派出去，余下某些留在空闲区表中，然后将分派区首址返回给调用者。当进程运营完毕释放内存时，系统依照回收区首址，从空闲区表中找到相应插入点，并且按照四种状况进行插入。3、模块设计：(1) 空闲区阐明表构造：把空闲区定义为构造体变量，涉及空闲区始址，空闲区大小和空闲区状态，用0表达空表目，1为可用空闲块。struct freearea int startaddress;/*空闲区始址*/ int size;/*空闲区大小*/ int state;/*空闲区状态:0为空表目，1为可用空闲块*/freeblockN= 1,20,20,1,2,80,50,1,3,150,30,1,4,300,30,1,5,500,10,1；(2) 为作业分派主存空间函数alloc()，三个算法分别相应三个分派主存空间算法。applyarea为作业申请量，tag为检查与否有满足作业需要空闲区标志。初次适应算法:检查空闲区阐明表与否有满足作业规定空闲区时,如果不不大于作业规定,则分派给作业,修改地址和空闲区大小,并将tag置“1”,表达有满足作业规定空闲区,返回为作业分派主存地址.程序如下所示：if(freeblocki.state=1&freeblocki.sizeapplyarea)freeblocki.startaddress=freeblocki.startaddress+applyarea; freeblocki.size=freeblocki.size-applyarea; tag=1; return freeblocki.startaddress-applyarea;如果空闲区等于作业规定，则分派给作业,修改地址和空闲区大小,并将tag置“1”,表达有满足作业规定空闲区,返回为作业分派主存地址.if(freeblocki.state=1&freeblocki.size=applyarea) freeblocki.state=0; tag=1; return freeblocki.startaddress;如果没有满足条件空闲区，分派不成功，返回-1if(tag=0)return -1;循环初次适应算法alloc()函数与初次适应算法alloc()函数区别在于从哪里开始找与否有满足作业规定空闲区，它是从上次找到空闲区下一种空闲分区开始找，只需要变化for循环条件即可。for(i=s;iN;i+)最佳适应算法：该算法总是把满足规定、又是最小空闲区别配给作业。检查空闲区阐明表与否有满足作业规定空闲区，也分为三种状况：不不大于，等于，不大于。若检查到有“等于”状况，就可以直接分派，若没有，则继续检查与否有“不不大于”状况：if(freeblocki.state=1&freeblocki.size=applyarea) freeblocki.state=0; tag=1; return freeblocki.startaddress; 检查“不不大于”状况：先把所有不不大于所规定空闲区放入数组,for(i=0;iapplyarea)aj+=i;再从数组中挑出最小那个：果数组中元素不不大于一种，则需要一种个比较过去，然后取出最小那个分派给作业：if(j1) h=a0; min=freeblockh; for(k=1;kj;k+) h=ak; if(freeblockh.sizemin.size) mid.size=freeblockh.size; mid.state=freeblockh.state; mid.startaddress=freeblockh.startaddress; freeblockh.size=min.size; freeblockh.state=min.state; freeblockh.startaddress=min.startaddress; min.size=mid.size; min.state=mid.state; min.startaddress=mid.startaddress; min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea; tag=1; return min.startaddress-applyarea; 如果数组中只有一种元素，则直接分派给作业：if(j=1) h=a0; min=freeblockh; min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea; tag=1; return min.startaddress-applyarea; 如果没有满足条件空闲区，分派不成功，返回-1if(tag=0)return -1; (3) 主存回收函数setfree()：tag1代表释放区高地址与否邻接一种空闲区，tag2代表释放区高低地址与否都邻接一种空闲区，tag3代表释放区低地址与否邻接一种空闲区。分为四种状况：回收分区上邻和下邻分区都不是空闲，则直接将回收区有关信息记录在空闲区表中。if(tag3=0)for(j=0;ju.size?m.size-u.sizesize？从该分区中划出u.size大小分区将该分区别配给祈求者并修改关于数据构造返回返回继续检索下一种表项将该分区从表中移出 内存分派流程 是否是否是是否是否否是是开始ch=1?First_fit()ch=2?Next_fit()ch=3?Best_fit()Choice=0?choice=1?分派内存Choice=2?回收内存Choice=3?查看空闲区表结束 主函数流程图四、 模块调试与系统测试1、模块调试l 输入形式和输入值范畴 一方面打开主界面输入整形常数选取所要使用算法，再依照界面上提示内容进行输入整形常数选取所要进行操作，重要涉及作业申请量、释放起始地址、释放区大小。l 输出形式 输出形式重要涉及空闲区表状态、申请作业起始地址和作业申请量。l 程序所能达到功能 程序所能达到功能重要涉及：初始化空闲区表状态，按照初次适应算法、循环初次适应算法和最佳适应算法对内存空间进行分派，对内存空间进行回收并输出进行各项操作后空闲区表状态。2、系统测试l 测试办法本系统采用黑盒测试办法进行测试。l 测试数据及测试报告试用例数据预测成果实际成果与否相符合法：输入13进行算法选取成功进入下一步成功进入下一步相符非法：输入13以外数据显示出错提示“有误，请重新输入”显示出错提示“有误，请重新输入”相符合法：输入03选取操作成功选取所要进行操作成功选取所要进行操作相符非法：输入13以外数据显示“输入有误，请重试”显示“输入有误，请重试”相符合法：输入分派内存操作下申请量为20显示：申请作业起始地址、申请量和内存分派成功显示：申请作业起始地址、申请量和内存分派成功相符非法：输入内存分派操作下申请量为60显示：作业申请量过大，分派失败显示：作业申请量过大，分派失败相符3、调试分析：在调试过程中定义为作业分派主存空间函数alloc2()时程序浮现错误，重要因素是由于for循环编写浮现错误，由于alloc2()与alloc()重要差别就在于for循环，最后通过查阅课本从主线上理解了初次适应算法和循环初次适应算法本质区别，最后使错误得以解决程序对的运营。在编写alloc3()时，引入数组将总体状况分为大两种，并在数组中又分为两种小状况。但是在考虑所有不不大于所规定空闲区放入数组时，落拉了只有一种数组状况，最后通过自己仔细检查和同窗协助使错误得以解决。在编写主存回收函数setfree()时由于对在空闲表中恰当位置进行插入时状况考虑不全面，使得其中一种状况落拉导致编程浮现错误，最后通过仔细阅读课本和同窗协助并在网上收索有关知识使得错误得以解决。在编写对空闲区表中空闲区调节函数adjust（）时也多次浮现 错误，最后通过同窗协助和在网上收索有关知识，借鉴别人算法使得错误得以解决。五、 顾客手册本系统是用C+语言编写，使用Microsoft Visual C+平台开发，不需要安装。经运营验证本程序可正常运营。详细使用环节如下：（1） 通过编译、链接无误后便可正常运营，浮现主界面 依照主界面上显示选取所要使用动态分区别配算法。（2） 选取所要使用算法之后就会显示所要进行各项操作如下 若选取1分派内存则依照界面提示输入作业申请量则会弹出申请作业起始地址和作业申请量 若选取2回收内存则界面提示输入释放区起始地址和释放区大小，输入之后则会自动显示空闲区表状态 若选取3查看空闲区表则输入3之后界面就会自动显示当前空闲区表状态 若选取0退出则系统会回到刚开始初始界面状态重新选取动态分区别配算法六、 程序清单/*动态分区别配与回收演示程序*/#include #include #define N 5int start;/存储首址 struct freearea/*定义一种空闲区阐明表构造，并初始化变量*/ int ID;/*分区号*/ int startaddress;/*空闲区始址*/ int size;/*空闲区大小*/ int state;/*空闲区状态:0为空表目，1为可用空闲块*/freeblockN=1,20,20,1,2,80,50,1,3,150,30,1,4,300,30,1,5,500,10,1;/*定义为作业分派主存空间函数alloc(),给初次适应算法调用*/int alloc(int applyarea) int i,tag=0;/*applyarea为作业申请量,tag为检查与否有满足作业需要空闲区标志*/ for(i=0;iapplyarea) freeblocki.startaddress=freeblocki.startaddress+applyarea; freeblocki.size=freeblocki.size-applyarea; tag=1;/*有满足条件空闲区时，tag置1*/ return freeblocki.startaddress-applyarea； /*返回为作业分派主存地址*/elseif(freeblocki.state=1&freeblocki.size=applyarea) freeblocki.state=0; tag=1;/*有满足条件空闲区时，tag置1*/ return freeblocki.startaddress;/*返回为作业分派主存地址*/if(tag=0)return -1;/*没有满足条件空闲区，分派不成功，返回-1*/*定义为作业分派主存空间函数alloc2(),给循环初次适应算法调用*/int alloc2(int applyarea,int s)/*applyarea为作业申请量*/ int i,tag=0;/*tag为检查与否有满足作业需要空闲区标志*/ for(i=s;iapplyarea) freeblocki.startaddress=freeblocki.startaddress+applyarea; freeblocki.size=freeblocki.size-applyarea; tag=1;/*有满足条件空闲区时，tag置1*/ start=freeblocki.startaddress-applyarea; return i;else if(freeblocki.state=1&freeblocki.size=applyarea) freeblocki.state=0; tag=1;/*有满足条件空闲区时，tag置1*/ start=freeblocki.startaddress;/*返回为作业分派主存地址*/ return i; if(tag=0)return -1;/*没有满足条件空闲区，分派不成功，返回-1*/ /*定义为作业分派主存空间函数alloc3(),给最佳适应算法调用*/int alloc3(int applyarea)/*applyarea为作业申请量*/ int i,k,h,flag,tag=0,j=0;/*tag为检查与否有满足作业需要空闲区标志*/ int aN; struct freearea min; struct freearea mid; for(i=0;iN;i+)/*检查空闲区阐明表与否有满足作业规定空闲区*/ if(freeblocki.state=1&freeblocki.size=applyarea)/大小刚好相等 freeblocki.state=0; tag=1;/*有满足条件空闲区时，tag置1*/ return freeblocki.startaddress;/*返回为作业分派主存地址*/ for(i=0;iapplyarea)aj+=i; if(j1) h=a0; min=freeblockh; /min.startaddress=freeblockh.startaddress; /min.size=freeblockh.size; /min.state=freeblockh.stat for(k=1;kj;k+) h=ak; if(freeblockh.sizemin.size) mid.size=freeblockh.size; mid.state=freeblockh.state; mid.startaddress=freeblockh.startaddress; freeblockh.size=min.size; freeblockh.state=min.state; freeblockh.startaddress=min.startaddress; min.size=mid.size; min.state=mid.state; min.startaddress=mid.startaddress; min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea; tag=1;/*有满足条件空闲区时，tag置1*/ return min.startaddress-applyarea; else if(j=1) h=a0; min=freeblockh; min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea; tag=1;/*有满足条件空闲区时，tag置1*/ return min.startaddress-applyarea; if(tag=0)return -1;/*没有满足条件空闲区，分派不成功，返回-1*/*定义主存回收函数：setfree()tag1代表释放区高地址与否邻接一种空闲区，tag2代表释放区高低地址与否都邻接一种空闲区，tag3代表释放区低地址与否邻接一种空闲区*/void setfree() int s,l,tag1=0,tag2=0,tag3=0,i,j; printf(请输入释放区起始地址:); scanf(%d,&s);/*输入释放区开始地址*/ printf(请输入释放区大小:); scanf(%d,&l);/*输入释放区大小*/ printf(*回收内存后空闲区表状态如下*n); for(i=0;iN;i+) if(freeblocki.startaddress=s+l&freeblocki.state=1) l=l+freeblocki.size; tag1=1;/*有与释放区高地址邻接空闲区，tag1置1*/ for(j=0;jN;j+) if(freeblockj.startaddress+freeblockj.size=s&freeblockj.state=1) freeblocki.state=0; freeblockj.size=freeblockj.size+l; tag2=1;/*有与释放区上下都邻接空闲区，tag2置1*/ break;if(tag2=0)/*无与释放区高低地址邻接空闲区*/freeblocki.startaddress=s;freeblocki.size=l;break; if(tag1=0)/*无与释放区高地址邻接空闲区，并检查与否低地址有邻接空闲区*/ for(i=0;iN;i+)if(freeblocki.startaddress+freeblocki.size=s&freeblocki.state=1)freeblocki.size=freeblocki.size+l;tag3=1;/*有与释放区低地址邻接空闲区*/break; if(tag3=0)/*无与释放区低地址邻接空闲区*/ for(j=0;jN;j+) if(freeblockj.state=0)/*找一种空表目，将释放区放入表中*/ freeblockj.startaddress=s; freeblockj.size=l; freeblockj.state=1; break;/*定义对空闲区表中空闲区调节函数adjust(),使空闲区按始地址从小到大排列，空表目放在最背面*/void adjust() int i,j; struct freearea middata; for(i=0;iN;i+)/*将空闲区按始地址顺序在表中排列*/ for(j=0;jfreeblockj+1.startaddress) middata.startaddress=freeblockj.startaddress; middata.size=freeblockj.size; middata.state=freeblockj.state; freeblockj.startaddress=freeblockj+1.startaddress; freeblockj.size=freeblockj+1.size; freeblockj.state=freeblockj+1.state; freeblockj+1.startaddress=middata.startaddress; freeblockj+1.size=middata.size; freeblockj+1.state=middata.state;for(i=0;iN;i+)/*将空表目放在表背面*/for(j=0;jN;j+)if(freeblockj.state=0&freeblockj+1.state=1) middata.startaddress=freeblockj.startaddress; middata.size=freeblockj.size; middata.state=freeblockj.state; freeblockj.startaddress=freeblockj+1.startaddress; freeblockj.size=freeblockj+1.size; freeblockj.state=freeblockj+1.state; freeblockj+1.startaddress=middata.startaddress; freeblockj+1.size=middata.size; freeblockj+1.state=middata.state;/*定义打印空闲区阐明表函数：print()*/void print() int i; printf(|-|n); printf(| ID start size state |n); printf(|-|n); for(i=0;iN;i+)printf(| %3d %3d %3d %3d |n, freeblocki.ID,freeblocki.startaddress,freeblocki.size,freeblocki.state);printf(|-|n); /初次void First_fit() int applyarea,start; printf(请输入作业申请量:); scanf(%d,&applyarea);/*输入作业申请量*/ start=alloc(applyarea);/*调用alloc()函数为作业分派空间，start为返回始地址*/ if(start=-1)/*alloc()分派不成功时，返回-1*/ printf(作业申请量过大，空闲区表中存储空间无法满足，分派失败n); else adjust(); printf(申请作业起始地址为:%dn,start); printf(作业申请量为:%dn,applyarea); printf(内存分派成功n); /循环初次void Next_fit() int appl