动态分区存储管理

分区存储管理模拟实验一、实验目的：了解动态分区存储管理方式中的数据结构和分配算法，加深对动态分区存储管理方式及其实现技术的理解。二、实验内容：把一个新作业装入内存,须按照一定的分配算法,从空闲分区表或空闲分区链中选出一分区分配给该作业，选用的算法是：(1)首次适应算法FF。FF算法要求空闲分区链以地址递增的次序链接，在分配内存时候，从链首开始顺序查找，直至找到一个大小能够满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中；(2)采用最佳适应算法完成内存空间的分配和回收；每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。但最佳适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值minsize，如果空闲区的大小减去作业需求长度得到的值小于等于minsize，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。三、流程图：四、首次适应算法实验结果：五、首次适应算法源代码：#includestdio.hvoidmain(){intm,n,i,j,j0,k,k0,A[30][3],B[30];printf(请输入空闲分区块数:);scanf(%d,&m);printf(\n\t分区号\t\t大小\t\t起始地址\n);for(i=0;im;i++)for(j=0;j3;j++)scanf(%d,&A[i][j]);/*按地址从小到大排列(直接选择排序)*/for(i=0;im-1;i++){k0=i;for(k=i+1;km;k++)if(A[k][2]A[k0][2])k0=k;if(k0!=i){for(j=0;j3;j++){intt;t=A[k0][j];A[k0][j]=A[i][j];A[i][j]=t;}}}printf(\n----首次适应算法按地址从小到大排列后空闲区----\n);printf(\t分区号\t\t大小\t\t起始地址\n);for(i=0;im;i++)for(j=0;j3;j++){printf(\t%d\t,A[i][j]);if(j==2)printf(\n);}printf(\n请输入要分配的作业数:);scanf(%d,&n);printf(请输入作业大小:\n);for(j0=0;j0n;j0++)scanf(%d,&B[j0]);/*空闲表首址和大小变换*/i=j0=0;do{while(A[i][1]B[j0]&&im)i++;if(i==m)printf(\n内存不足,%dK大小的作业需要等待内存资源!\n,B[j0]);if(im){A[i][1]=A[i][1]-B[j0];A[i][2]=A[i][2]+B[j0];}j0++;i=0;}while(j0n);printf(\n----首次适应算法分区分配后的空闲区----\n);printf(\t分区号\t\t大小\t\t起始地址\n);for(i=0;im;i++)for(j=0;j3;j++){if(A[i][1])printf(\t%d\t,A[i][j]);if(j==2)printf(\n);}}六、最佳适应算法算法实验结果：七、最佳适应算法源程序代码：#includeiostream.h#includeiomanip.h//全局变量floatminsize=5;intcount1=0;intcount2=0;#defineM10//假定系统允许的空闲区表最大为m#defineN10//假定系统允许的最大作业数量为n//已分配表的定义struct{floataddress;//已分分区起始地址floatlength;//已分分区长度，单位为字节intflag;//已分配区表登记栏标志，0表示空栏目}used_table[N];//已分配区表对象名//空闲区表的定义：struct{floataddress;//空闲区起始地址floatlength;//空闲区长度，单位为字节intflag;//空闲区表登记栏标志，用0表示空栏目，用1表示未分配}free_table[M];//空闲区表对象名//函数声明voidinitialize(void);intdistribute(int,float);intrecycle(int);voidshow();//初始化两个表voidinitialize(void){inta;for(a=0;a=N-1;a++)used_table[a].flag=0;//已分配表的表项全部置为空表项free_table[0].address=1000;free_table[0].length=1024;free_table[0].flag=1;//空闲区表的表项全部为未分配}//最优分配算法实现的动态分区intdistribute(intprocess_name,floatneed_length){inti,k=-1;//k用于定位在空闲表中选择的未分配栏floatads,len;intcount=0;i=0;while(i=M-1)//循环找到最佳的空闲分区{if(free_table[i].flag==1&&need_length=free_table[i].length){count++;if(count==1||free_table[i].lengthfree_table[k].length)k=i;}i=i+1;}if(k!=-1){if((free_table[k].length-need_length)=minsize)//整个分配{free_table[k].flag=0;ads=free_table[k].address;len=free_table[k].length;}else{//切割空闲区ads=free_table[k].address;len=need_length;free_table[k].address+=need_length;free_table[k].length-=need_length;}i=0;//循环寻找内存分配表中标志为空栏目的项while(used_table[i].flag!=0){i=i+1;}if(i=N-1)//找到，在已分配区表中登记一个表项{used_table[i].address=ads;used_table[i].length=len;used_table[i].flag=process_name;count1++;}else//已分配区表长度不足{if(free_table[k].flag==0)//将已做的整个分配撤销{free_table[k].flag=1;free_table[k].address=ads;free_table[k].length=len;}else//将已做的切割分配撤销{free_table[k].address=ads;free_table[k].length+=len;}cout内存分配区已满，分配失败！\n;return0;}}else{cout无法为该作业找到合适分区！\n;return0;}returnprocess_name;}intrecycle(intprocess_name){inty=0;floatrecycle_address,recycle_length;inti,j,k;//j栏是下邻空闲区，k栏是上栏空闲区intx;//在内存分配表中找到要回收的作业while(y=N-1&&used_table[y].flag!=process_name){y=y+1;}if(y=N-1)//找到作业后，将该栏的标志置为'0'{recycle_address=used_table[y].address;recycle_length=used_table[y].length;used_table[y].flag=0;count2++;}else//未能找到作业，回收失败{cout该作业不存在！\n;return0;}j=k=-1;i=0;while(!(i=M||(k!=-1&&j!=-1)))//修改空闲分区表{if(free_table[i].flag==1){if((free_table[i].address+free_table[i].length)==recycle_address)k=i;//判断是否有上邻接if((recycle_address+recycle_length)==free_table[i].address)j=i;//判断是否有下邻接}i=i+1;}//合并空闲区if(k!=-1)//回收区有上邻接{if(j!=-1){//回收区也有下邻接，和上下邻接合并free_table[k].length+=free_table[j].length+recycle_length;free_table[j].flag=0;//将第j栏的标记置为'0'}else//不存在下邻接，和上邻接合并free_table[k].length+=recycle_length;}elseif(j!=-1){//只有下邻接，和下邻接合并free_table[j].length+=recycle_length;free_table[j].address=recycle_address;}else{//上下邻接都没有x=0;while(free_table[x].flag!=0)x=x+1;//在空闲区表中查找一个状态为'0'的栏目if(x=M-1){//找到后，在空闲分区中登记回收的内存free_table[x].address=recycle_address;free_table[x].length=recycle_length;free_table[x].flag=1;}else{//空闲表已满，执行回收失败used_table[y].flag=process_name;cout空闲区已满，回收失败！\n;return0;}}returnprocess_name;}voidshow()//程序执行时输出模拟的内存分配回收表{cout+++++++++++++++++++++++++++++++++++++++\n;cout+++++++空闲区+++++++\n;cout+++++++++++++++++++++++++++++++++++++++\n;for(inti=0;i=count2;i++)if(free_table[i].flag!=0)cout初始地址：free_table[i].address长度：free_table[i].length状态：free_table[i].flagendl;cout+++++++++++++++++++++++++++++++++++++++\n;cout+++++++已分配区++++++\n;cout+++++++++++++++++++++++++++++++++++++++\n;for(intj=0;jcount1;j++)if(used_table[j].flag!=0)cout初始地址：used_table[j].address长度：used_table[j].length作业名：used_table[j].flagendl;}voidmain()//主函数调用各功能函数对所有工作进行测试{intchoice;//用来选择将要进行的操作intjob_name;floatneed_memory;boolexitFlag=false;cout动态分区分配方式的模拟\n;cout**********************