动态分区存储管理

《操作系统》课程实验报告实验名称：动态分区存储管理班级：****************学号：*************姓名：**************指导老师：***************成绩：一、实验目的：1.熟悉并掌握动态分区分配的各种算法。2.熟悉并掌握动态分区中分区回收的各种情况，并能够实现分区合并。二、实验内容：用高级语言模拟实现动态分区存储管理，要求：1、分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。2、分区的初始化——可以由用户输入初始分区的大小。（初始化后只有一个空闲分区，起始地址为0，大小是用户输入的大小）3、分区的动态分配过程：由用户输入作业号和作业的大小，实现分区过程。4、分区的回收：用户输入作业号，实现分区回收，同时，分区的合并要体现出来。（注意：不存在的作业号要给出错误提示！）5、分区的显示：任何时刻，可以查看当前内存的情况（起始地址是什么，大小多大的分区时空闲的，或者占用的，能够显示出来）三、实验代码#includestdio.h#includestdlib.h#defineSIZE800//内存初始大小#defineMINSIZE5//碎片最小值enumSTATE{Free,Busy};structsubAreaNode{intaddr;//起始地址intsize;//分区大小inttaskId;//作业号STATEstate;//分区状态subAreaNode*pre;//分区前向指针subAreaNode*nxt;//分区后向指针}subHead;//初始化空闲分区链voidintSubArea(){//分配初始分区内存subAreaNode*fir=(subAreaNode*)malloc(sizeof(subAreaNode));//给首个分区赋值fir-addr=0;fir-size=SIZE;fir-state=Free;fir-taskId=-1;fir-pre=&subHead;fir-nxt=NULL;//初始化分区头部信息subHead.pre=NULL;subHead.nxt=fir;}//首次适应算法intfirstFit(inttaskId,intsize){subAreaNode*p=subHead.nxt;while(p!=NULL){if(p-state==Free&&p-size=size){//找到要分配的空闲分区if(p-size-size=MINSIZE){//整块分配p-state=Busy;p-taskId=taskId;}else{//分配大小为size的区间subAreaNode*node=(subAreaNode*)malloc(sizeof(subAreaNode));node-addr=p-addr+size;node-size=p-size-size;node-state=Free;node-taskId=-1;//修改分区链节点指针node-pre=p;node-nxt=p-nxt;if(p-nxt!=NULL){p-nxt-pre=node;}p-nxt=node;//分配空闲区间p-size=size;p-state=Busy;p-taskId=taskId;}printf(内存分配成功！\n);return1;}p=p-nxt;}printf(找不到合适的内存分区，分配失败...\n);return0;}//最佳适应算法intbestFit(inttaskId,intsize){subAreaNode*tar=NULL;inttarSize=SIZE+1;subAreaNode*p=subHead.nxt;while(p!=NULL){//寻找最佳空闲区间if(p-state==Free&&p-size=size&&p-sizetarSize){tar=p;tarSize=p-size;}p=p-nxt;}if(tar!=NULL){//找到要分配的空闲分区if(tar-size-size=MINSIZE){//整块分配tar-state=Busy;tar-taskId=taskId;}else{//分配大小为size的区间subAreaNode*node=(subAreaNode*)malloc(sizeof(subAreaNode));node-addr=tar-addr+size;node-size=tar-size-size;node-state=Free;node-taskId=-1;//修改分区链节点指针node-pre=tar;node-nxt=tar-nxt;if(tar-nxt!=NULL){tar-nxt-pre=node;}tar-nxt=node;//分配空闲区间tar-size=size;tar-state=Busy;tar-taskId=taskId;}printf(内存分配成功！\n);return1;}else{//找不到合适的空闲分区printf(找不到合适的内存分区，分配失败...\n);return0;}}//回收内存intfreeSubArea(inttaskId){intflag=0;subAreaNode*p=subHead.nxt,*pp;while(p!=NULL){if(p-state==Busy&&p-taskId==taskId){flag=1;if((p-pre!=&subHead&&p-pre-state==Free)&&(p-nxt!=NULL&&p-nxt-state==Free)){//情况1：合并上下两个分区//先合并上区间pp=p;p=p-pre;p-size+=pp-size;p-nxt=pp-nxt;pp-nxt-pre=p;free(pp);//后合并下区间pp=p-nxt;p-size+=pp-size;p-nxt=pp-nxt;if(pp-nxt!=NULL){pp-nxt-pre=p;}free(pp);}elseif((p-pre==&subHead||p-pre-state==Busy)&&(p-nxt!=NULL&&p-nxt-state==Free)){//情况2：只合并下面的分区pp=p-nxt;p-size+=pp-size;p-state=Free;p-taskId=-1;p-nxt=pp-nxt;if(pp-nxt!=NULL){pp-nxt-pre=p;}free(pp);}elseif((p-pre!=&subHead&&p-pre-state==Free)&&(p-nxt==NULL||p-nxt-state==Busy)){//情况3：只合并上面的分区pp=p;p=p-pre;p-size+=pp-size;p-nxt=pp-nxt;if(pp-nxt!=NULL){pp-nxt-pre=p;}free(pp);}else{//情况4：上下分区均不用合并p-state=Free;p-taskId=-1;}}p=p-nxt;}if(flag==1){//回收成功printf(内存分区回收成功...\n);return1;}else{//找不到目标作业，回收失败printf(找不到目标作业，内存分区回收失败...\n);return0;}}//显示空闲分区链情况voidshowSubArea(){printf(当前的内存分配情况如下：\n);printf(\n);printf(起始地址\t空间大小\t工作状态\t作业号\n);subAreaNode*p=subHead.nxt;while(p!=NULL){printf(\n);printf(%dk\t,p-addr);printf(%dk\t,p-size);printf(%s\t,p-state==Free?Free:Busy);if(p-taskId0){printf(%d,p-taskId);}else{printf();}printf(\n);p=p-nxt;}}intmain(){intoption,ope,taskId,size;//初始化空闲分区链intSubArea();//选择分配算法while(1){printf(请选择要模拟的分配算法：0表示首次适应算法，1表示最佳适应算法\n);scanf(%d,&option);if(option==0){printf(你选择了首次适应算法，下面进行算法的模拟\n);break;}elseif(option==1){printf(你选择了最佳适应算法，下面进行算法的模拟\n);break;}else{printf(错误：请输入0/1\n\n);}}//模拟动态分区分配算法while(1){printf(\n);printf(*********************************************\n);printf(1:分配内存2:回收内存0:退出\n);printf(*********************************************\n);scanf(%d,&ope);if(ope==0)break;if(ope==1){//模拟分配内存printf(请输入作业号：);scanf(%d,&taskId);printf(请输入需要分配的内存大小(KB)：);scanf(%d,&size);if(size=0){printf(错误：分配内存大小必须为正值\n);continue;}//调用分配算法if(option==0){firstFit(taskId,size);}else{bestFit(taskId,size);}//显示空闲分区链情况showSubArea();}elseif(ope==2){//模拟回收内存printf(请输入要回收的作业号：);scanf(%d,&taskId);freeSubArea(taskId);//显示空闲分区链情况showSubArea();}else{printf(错误：请输入0/1/2\n);}}printf(分配算法模拟结束\n);return0;}四、实验结果1、选择操作界面2、选择操作分配内存3、回收内存；4、模拟首次适应算法（NF）5.模拟最佳适用算法五、实验总结根据实验得出结论，首次适用算法是从空闲分区表的头指针开始查找，把最先能够满足要求的空闲区分配给作业。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区，此算法比较节省时间。最佳适用算法将可利用空闲表中一个不小于“请求”且最接近请求的空闲区的一部分分配给用户。分配与回收都需要对可利用空闲表从头至尾查询一遍。在分配时容易产生太小而无法利用的内存碎片，同时这种做法也保留了那些很大的内存块以备响应将来发生的内存量较大的用户的请求。这种分配算法适合请求分配内存大小范围较广的系统，此算法最费时间。