操作系统实验—动态分区分配算法

操作系统实验报告实验2动态分区分配算法报告日期：2016-6-15姓名：学号：班级：任课教师：05k10k14k26k32k512k实验2动态分区分配算法一、实验内容编写一个内存动态分区分配模拟程序，模拟内存的分配和回收的完整过程。二、实验目的一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。三、实验原理模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：操作系统作业1作业3空闲区作业2空闲区为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：起址长度状态第一栏14K12K未分配第二栏32K96K未分配其中，起址——指出一个空闲区的主存起始地址。长度——指出从起始地址开始的一个连续空闲的长度。状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。(2)当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。(3)采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。(4)当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。(5)请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业，现按下面序列进行内存的申请与释放：作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K，作业4申请30K，作业5申请40K，作业6申请60K，作业4释放30K。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。四、实验报告1.画出算法流程图。2.源代码#define_CRT_SECURE_NO_WARNINGS1#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=511;kongxian[0].length=512;}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,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;}3.程序运行时的初值和运行结果。初始：装入实验要求作业一：装入作业二：作业1释放300k：作业三申请150k作业4申请30k：作业5申请40k：作业6申请60k：作业4释放30k：5.如果在要申请一个100K的作业空间，能否满足？可以满足！五、实验小结通过本次实验，我对操作系统中首次适应的内存分配方法有了深刻的理解，对理论学习有了很好的促进作用，本次的实验难度比实验一难一些，也对考验了我的编程能力，重要的还是要理解算法。