张蒙用首次适应算法模拟内存的分配和回收

采用首次适应算法实现主存的分配和回收一、目的在计算机系统中，为了提高内存区的利用率，必须给电脑内存区进行合理的分配。本实验通过对内存区分配方法首次适应算法的使用，来了解内存分配的模式。在熟练掌握计算机分区存储管理方式的原理的基础上，编程模拟实现操作系统的可变分区存储管理的功能，一方面加深对原理的理解，另一方面提高根据已有原理通过编程解决实际问题的能力，为进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。二、实验内容与数据结构：(1)可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区的个数是可以调整的。当需要装入一个作业时，根据作业需要的贮存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无，则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被分配作业占用，有的分区空闲，例如，某时刻主存空间占用情况如图所示：操作系统（10KB）空闲区2（146KB）空闲区1（20KB）作业2（45KB）作业4（25KB）作业1（10KB）0K10K45K65K110K256K为了说明哪些分区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，如下图所示。起始地址长度状态110K146KB未分配空表目空表目45K20KB未分配空表目……...(2)当有一个新作业要求装入贮存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业的需求量，这时应将空闲区一分为二。一个分给作业，另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽可能分配地地址部分的空闲区，将较大的空闲区留在高地址端，以利于大作业的装入。为此在空闲区表中，按空闲区首地址从低到高进行登记。(3)当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时，要考虑相邻空间区合并问题。作业的释放区与空闲区的邻接分以下4种情况考虑：A、释放区下邻空闲区；B、释放区上邻空闲区；C、释放区上下都与空闲区邻接；D、释放区上邻空闲区不邻接；一、实验要求1.内存大小初始化2.可以对内存区进行动态分配，采用首次适应算法来实现3.可以对已分配的内存块进行回收，并合并相邻的空闲内存块。二、实验内容把一个作业装入内存，按照首次适应算法对内存区进行分配，作业结束，回收已分配给该作业的内存块，并合并相邻的空闲内存块。三、实验结果运行效果：1.初始化内存区大小，并添加作业，选择1添加作业2.当作业大小超过存储块大小时，分配失败。3.选择3，可查看内存分配情况4.选择2回收内存5.选择1添加新作业6.回收C作业，相邻的空闲内存块合并。五、程序流程图：开始申请XK主存J=0J=J+1查看第J个表目的登记项状态为“未分配”吗？长度=XK？YN小于置状态为“空表目”将空表目向后移长度=长度-XK始址=始址+XK大于登记已分配区表和空闲区表，输出系统中各数据结构的值，返回分配给作业的主存始址。J为空闲区说明表的最后一个表目？作业等待返回YN等于六、实验源代码：//FirstFit.cpp:可变分区用首次适应算法来模拟内存回收#includeSTDIO.H#includeSTDLIB.HintMAX_SEGMENT=10;//最大碎片值structPartition//分区表目{intPar_Size;//分区大小intPar_No;//分区序号或者名字intAddr;//分区地址intIsUse;//分区使用情况,0表示空闲，1表示使用Partition*pri;//前向指针Partition*next;//后向指针};Partition*Int()//函数，返回Partition类型指针{//初始化空闲分区表Partition*list,*H,*H1;list=(structPartition*)malloc(sizeof(structPartition));list-next=NULL;H=list;if(!list){printf(\n错误,内存初始化分配失败！程序结束);exit(1);}H1=(structPartition*)malloc(sizeof(structPartition));printf(请预先输入分区总大小(以KB为单位)：);scanf(%d,&H1-Par_Size);H1-Addr=0;H1-Par_No=0;H1-IsUse=0;H1-pri=H;H1-next=NULL;H-next=H1;////list---H1returnlist;}Partition*InitFP(){//初始化已分配分区表Partition*FP,*F,*H;inti;FP=(structPartition*)malloc(sizeof(structPartition));FP-next=NULL;H=FP;for(i=0;i10;i++)//已分配区先暂定分配十个表目{F=(structPartition*)malloc(sizeof(structPartition));if(!F){printf(\n错误,内存分配失败！程序结束);exit(1);}F-Par_Size=0;F-Addr=0;F-Par_No=0;F-IsUse=0;F-next=NULL;H-next=F;F-pri=H;H=H-next;}returnFP;}Partition*New_Process(Partition*list,Partition*FP){//为新的进程分配资源Partition*H,*P,*H1;intSize,Name,L;H=list;H1=FP-next;H=H-next;printf(请输入新作业的名称和大小(整数):);scanf(%d%d,&Name,&Size);while(H){if(!H)//表目已查完，无法分配{printf(\n已无空闲分区,本次无法分配!);returnlist;}else{if(H-IsUse==0)//空表目//if(H-Par_Size=Size)//大小满足,空闲分区大小》要分配的大小if(H-Par_Size=Size)//大小满足,{booltemp=false;if((H-Par_Size-Size)=MAX_SEGMENT){//空闲分区大小-要分配的大小碎片值,会产生碎片,将整块内存大小分配出去，Size=H-Par_Size;//分配的大小为整块内存temp=true;//会产生碎片}//其他情况就分配大小为请求大小，不会产生碎片，L=H-Addr;//保存空闲分地址if(temp){printf(该次内存分配会产生碎片,将整块内存大小%d分配出去!,Size);}else{printf(该次内存分配不会产生碎片);}break;}}H=H-next;//否则，继续往下查找}if(H){if(H-Par_SizeSize)//大小满足,空闲分区大小》要分配的大小{P=(structPartition*)malloc(sizeof(structPartition));//分配新的表目，处理一条数据，分配一次内存P-IsUse=1;P-Addr=L;//指向空闲分区地址P-next=H;//修改指针H-pri-next=P;P-pri=H-pri;H-pri=P;P-Par_Size=Size;//分配大小为要请求分配的大小P-Par_No=Name;//名称H-Par_Size-=Size;//修改空闲分区,H所指区块大小减SizeH-Addr+=Size;//H所指区块地址加Size}else{H-IsUse=1;//大小相等的，把当前表项设置空表目}while(H1){if(H1-IsUse==0){H1-Par_No=Name;H1-Par_Size=Size;H1-Addr=L;//保存已分配地址H1-IsUse=1;//在已分配表中设置为已分配break;}H1=H1-next;}}elseprintf(所申请资源已大过系统所拥有的,请重新输入!\n);returnlist;}Partition*Reclaim(Partition*list,Partition*FP){//结束作业,资源回收,No为作业名，回收内存Partition*H1,*H2,*H3,*HF;//H1为释放区，H2为后分区，H3为前分区intNo;//作业名H1=list;HF=FP;//可有可无？H1=H1-next;HF=FP-next;printf(请输入您想结束的作业名:);scanf(%D,&No);while(HF)//对已分配表进行操作{if(HF-Par_No==No){HF-IsUse=0;//标志为空表目break;//这时保存着HF所指分区的信息}HF=HF-next;}if(!HF)//如果找不到该作业，则提示出错printf(所输入的作业名称不正确,请重新输入!);else{while(H1)//对空闲表进行操作{if(H1-Par_No==No){H1-IsUse=0;//标志为空表目printf(内存回收成功);break;}H1=H1-next;}H2=H1-next;//后分区H3=H1-pri;//前分区if(H2&&H2-IsUse==0)//后接分区为空闲{if(H2-next==NULL)//判断后接分区是否为尾结点{H1-Par_Size+=H2-Par_Size;//把H2合并到H1H1-next=NULL;free(H2);printf(已回收%d大小内存,H1-Par_Size);}else//后分区不为空闲，表示已经被使用{H1-Par_Size+=H2-Par_Size;H1-next=H2-next;H2-next-pri=H1;free(H2);printf(已回收%d大小内存,H1-Par_Size);}}if(H3&&H3-IsUse==0)//前分区为空闲分区，则合并去前分区{H3-Par_Size+=H1-Par_Size;H3-next=H1-next;if(H1-next!=NULL)//若H1为尾结点H1-next-pri=H3;free(H1);printf(已回收%d大小内存,H1-Par_Size);}}returnlist;}voidPrint(Partition*list,Partition*FP){//输出已分配分区和空闲分区Partition*H1,*H2;H1=list-next;H2=FP;H2=H2-next;printf(****************已分配分区表*******************\n);printf(分区序号大小始址状态\n);while(H2){printf(%d%d%d,H2-Par_No,H2-Par_Size,H2-Addr);if(H2-IsUse==1)printf(已分配\n);elseprintf(空表目\n);H2=H2-next;}printf(**************************************************\n);printf(****************总的空闲分区表*******************\n);printf(分区序号大小始址状态\n);while(H1){printf(%d%d%d,H1-Par_No,H1-Par_Size,H1-Addr);if(H1-IsUse==1)printf(已分配\n);elseprintf(空表目\n);H1=H1-next;}printf(**************************************************\n);}voidMain_Print(Partition*l