操作系统实验-可变分区内存分配首次适应算法模拟

题目可变分区内存分配首次适应算法模拟姓名：学号：专业：学院：指导教师：林夕二零一八年十一月一、实验目的主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。二、实验内容及原理编写一个内存动态分区分配模拟程序，模拟内存的分配和回收的完整过程。模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。当进程运行完毕释放内存，系统根据回收区的首址，从空闲区链表中找到相应的插入点，此时可能出现以下4种情况之一：1.回收区与插入点的前一个空闲分区F1相邻接，此时将两个分区合并2.回收区与插入点的后一个空闲分区F2相邻接，此时将两个分区合并3.回收区与插入点的前，后两个空闲分区相邻接，此时将三个分区合并4.回收区既不与F1相邻接，又不与F2相邻接，此时应为回收区单独建立一个新表项三、程序设计1.算法流程3.详细设计（1）定义两个结构体structkongxian//空闲分区{intstart;//起址intend;//结束intlength;//长度}kongxian[N];structzuoye//作业分区{intstart;//起址intend;//结束intlength;//长度}zuoye[N];（2）init()//初始化函数kongxian结构体为010231024print1()//打印空闲分区print2()//打印作业分区main（）中具体实现算法：printf(请输入作业的占用空间的长度);scanf(%d,&len);flag=0;for(i=0;in1;i++){if(kongxian[i].length=len)//首次适应算法{flag=1;break;}}if(!flag){printf(内存分配失败\n);}else{//将该作业加入作业区里zuoye[n2].start=kongxian[i].start;zuoye[n2].end=zuoye[n2].start+len;zuoye[n2].length=len;n2++;//作业数加1if(kongxian[i].length==len)//该分区全部用于分配，删除该空闲分区{for(j=i;jn1-1;j++){kongxian[j].start=kongxian[j+1].start;kongxian[j].end=kongxian[j+1].end;kongxian[j].length=kongxian[j+1].length;}n1--;}else//该空闲分区部分用于分配，剩余的留在空闲分区中{kongxian[i].start+=len;kongxian[i].length-=len;}}（3）回收作业：printf(输入要回收的作业ID);scanf(%d,&id);front=middle=behind=0;for(i=0;in1;i++){if(kongxian[i].startzuoye[id].end)break;if(kongxian[i].end==zuoye[id].start)//待回收的作业上面有空闲分区{front=1;t1=i;}if(kongxian[i].start==zuoye[id].end)//待回收的作业下面有空闲分区{behind=1;t2=i;}四、实验结果五、实验小结在设计的过程中，有很多问题不是很清楚，所以做起来就就很困难，刚开始的时候都有点无从下手的感觉。很多时候在遇到问题时，基本知识都了解，但是就不知道怎么才能把它们都整合到一块，也就是说知识都是很零散的，没有一个完整的系统。而且，又由于基础知识不牢固，使得我在这次的课程设计中感到更加力不从心。在设计的过程中，每走一步就会发现，思路想出来很容易，但涉及到实现的时候，总是有点手无足措。对于本次的课程设计，里面还有很多需要改进的地方。一个程序的顺利出炉，少不了反复地调试和修改。在调试的过程中，总是会发生很多错误，但在解决这些错误的时候，开始很模糊的概念就会变得越来越清晰。其实很多错误都是很类似的，只要解决了一个，其余的就会迎刃而解了。#includestdio.h#includestring.h#includestdlib.h#includemath.h#defineN10000intn1;//空闲分区的个数intn2;//作业区的个数structkongxian{intstart;//起址intend;//结束intlength;//长度}kongxian[N];structzuoye{intstart;//起址intend;//结束intlength;//长度}zuoye[N];intcmp1(constvoid*a,constvoid*b){return(*(structkongxian*)a).start-(*(structkongxian*)b).start;}intcmp2(constvoid*a,constvoid*b){return(*(structzuoye*)a).start-(*(structzuoye*)b).start;}voidinit(){n1=1;//初始时只有一个空闲区n2=0;//初始没有作业kongxian[0].start=0;kongxian[0].end=1023;kongxian[0].length=1024;}voidprint1()//打印空闲分区{inti;for(i=0;in1;i++)printf(空闲分区ID:%d起止:%d结束:%d长度:%d\n,i,kongxian[i].start,kongxian[i].end,kongxian[i].length);}voidprint2()//打印作业分区{inti;for(i=0;in2;i++)printf(作业分区ID：%d起止:%d结束:%d长度:%d\n,i,zuoye[i].start,zuoye[i].end,zuoye[i].length);}intmain(){inti,j,k,t,len,flag,id;intfront,middle,behind;intt1,t2;init();print1();printf(输入1装入新作业，输入0回收作业，输入-1结束\n);while(scanf(%d,&t)!=EOF){if(t==1)//装入新作业{printf(请输入作业的占用空间的长度);scanf(%d,&len);flag=0;for(i=0;in1;i++){if(kongxian[i].length=len)//首次适应算法{flag=1;break;}}if(!flag){printf(内存分配失败\n);}else{//将该作业加入作业区里zuoye[n2].start=kongxian[i].start;zuoye[n2].end=zuoye[n2].start+len;zuoye[n2].length=len;n2++;//作业数加1if(kongxian[i].length==len)//该分区全部用于分配，删除该空闲分区{for(j=i;jn1-1;j++){kongxian[j].start=kongxian[j+1].start;kongxian[j].end=kongxian[j+1].end;kongxian[j].length=kongxian[j+1].length;}n1--;}else//该空闲分区部分用于分配，剩余的留在空闲分区中{kongxian[i].start+=len;kongxian[i].length-=len;}}}elseif(t==0){printf(输入要回收的作业ID);scanf(%d,&id);front=middle=behind=0;for(i=0;in1;i++){if(kongxian[i].startzuoye[id].end)break;if(kongxian[i].end==zuoye[id].start)//待回收的作业上面有空闲分区{front=1;t1=i;}if(kongxian[i].start==zuoye[id].end)//待回收的作业下面有空闲分区{behind=1;t2=i;}}if(!front&&!behind)//待回收的作业上下均没有空闲分区{kongxian[n1].start=zuoye[id].start;kongxian[n1].end=zuoye[id].end;kongxian[n1].length=zuoye[id].length;n1++;//空闲分区增加一个qsort(kongxian,n1,sizeof(structkongxian),cmp1);//插入空闲分区后排序for(j=id;jn2-1;j++)//在作业分区中删除该作业{zuoye[j].start=zuoye[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}if(front&&behind)//待回收的作业上下均有空闲分区middle=1;if(front&&!middle)//合并待回收的作业和上面的空闲分区{kongxian[t1].end+=zuoye[id].length;kongxian[t1].length+=zuoye[id].length;for(j=id;jn2-1;j++)//在作业分区中删除该作业{zuoye[j].start=zuoye[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}if(middle)//合并待回收的作业和上下的空闲分区{kongxian[t1].end=kongxian[t2].end;kongxian[t1].length+=(zuoye[id].length+kongxian[t2].length);//删除空闲分区t2for(j=t2;jn1-1;j++){kongxian[j].start=kongxian[j+1].start;kongxian[j].end=kongxian[j+1].end;kongxian[j].length=kongxian[j+1].length;}n1--;for(j=id;jn2-1;j++)//在作业分区中删除该作业{zuoye[j].start=zuoye[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}if(behind&&!middle)//合并待回收的作业和下面的分区{kongxian[t2].start-=zuoye[id].length;kongxian[t2].length+=zuoye[id].length;for(j=id;jn2-1;j++)//在作业分区中删除该作业{zuoye[j].start=zuoye[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}}else{printf(操作结束\n);break;}print1();print2();}return0;}