操作系统首次适应算法动态分配C语言代码

实验名称：操作系统动态分配姓名：杨秀龙学号：1107300432专业班级：创新实验班111指导老师：霍林实验题目内存动态分区的分配与回收内存实验目的有利于我们更好的了解内存动态分区分配的操作情况，掌握可变分区首次适应算法的原理以及其编程实现。设计思想可变分区分配是根据进程的实际需求，动态地为之分配内存空间。首次适应算法要求空闲空间链以地址递增的次序链接。进行内存分配时，从链表头部开始依次检索，找到第一个不小于请求空间大小的空闲空间进行分配。分配时需考虑碎片问题，若分配会导致碎片产生则将整块分区分配。内存的回收需要考虑四种情况：⑴收分区前后两个分区都空闲，则需要和前后两个分区合并；⑵回收分区只有前一分区空闲，则与前一分区合并；⑶回收分区只有后一分区空闲，则和后一分区合并；⑷回收分区独立，不考虑合并主要数据结构主要的数据结构有两个：空闲分区表结构和表的链结构。根据空闲分区的作用，空闲分区表结构必须包括（分区号、分区起始地址、分区状态、分区数据大小）。由于采用的是双向链表的结果，所以表的链结构包括（空闲分区表的信息、首指针、尾指针）结构程序代码如下：typedefstructBody{intID;intsize;intaddress;intsign;};typedefstructNode{Bodydata;structNode*prior;structNode*next;}*DLinkList;流程图退出选0输入有误3or0选择0-3操作操作界面开始选3显示内存分配选2回收内存选1分配内存运行结果图（1）主界面图（2）分配3个分区后的分配情况图（3）回收1、3分区后的分配情况图（4）再次分配4分区后的分配情况附录：源代码如下：#includeiostream.h#includestdio.h#defineFree0//空闲#defineZhanyong1//占用#defineFINISH1//完成#defineERROR0//出错#definememory512//最大内存#definemin10//碎片值typedefstructBody{intID;intsize;intaddress;intsign;};typedefstructNode{Bodydata;structNode*prior;structNode*next;}*DLinkList;DLinkListhead;//头结点DLinkListtou;//尾结点intCreate()//初始化{head=(DLinkList)malloc(sizeof(Node));tou=(DLinkList)malloc(sizeof(Node));head-prior=NULL;head-next=tou;tou-prior=head;tou-next=NULL;tou-data.address=0;tou-data.size=memory;tou-data.ID=0;tou-data.sign=Free;returnFINISH;}intFirstFit(intID,intspace)//首次适应算法{DLinkListNewNode=(DLinkList)malloc(sizeof(Node));//新建作业的结点NewNode-data.ID=ID;NewNode-data.size=space;NewNode-data.sign=Zhanyong;Node*p=head;while(p){if(p-data.sign==Free&&p-data.size==space)//剩余大小恰好满足{{p-data.sign=Zhanyong;p-data.ID=ID;returnFINISH;break;}if(p-data.sign==Free&&p-data.sizespace&&(p-data.size-spacemin))//满足需求且有剩余且不产生碎片{NewNode-prior=p-prior;NewNode-next=p;NewNode-data.address=p-data.address;p-prior-next=NewNode;p-prior=NewNode;p-data.address=NewNode-data.address+NewNode-data.size;p-data.size=p-data.size-space;returnFINISH;break;}if(p-data.sign==Free&&p-data.sizespace&&p-data.size-space=min)//产生碎片时{p-data.sign=Zhanyong;p-data.ID=ID;returnFINISH;break;}p=p-next;//若已有分配，P指针后移}returnERROR;}intAllocation()//内存分配{intID,space;printf(请输入分区号（不能输入相同的两个分区号）：);scanf(%d,&ID);printf(输入分配内存大小(单位:KB)：);scanf(%d,&space);if(space0||space==0){printf(分配的内存大小必须是正整数！\n);returnERROR;}if(FirstFit(ID,space)==FINISH)printf(分配成功！\n);elseprintf(内存不足，分配失败！\n);}intRecycle(intID)//shifangzuoye{Node*p=head;while(p){if(p-data.ID==ID){p-data.sign=Free;//p-data.ID=Free;if((p-prior-data.sign==Free)&&(p-next-data.sign==Free))//与前后的空闲块相连{p-prior-data.size=p-prior-data.size+p-data.size+p-next-data.size;p-prior-next=p-next-next;if(p-next-next==NULL)//****若p-next是最后一个结点{p-prior-data.ID=Free;p-next=NULL;}else{p-next-next-prior=p-prior;}break;}if(p-prior-data.sign==Free)//与前面的空闲块相连{p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;break;}if(p-next-data.sign==Free)//与后面的空闲块相连{p-data.size+=p-next-data.size;if(p-next-next==NULL)//若p-next是最后一个结点p-next=NULL;else{p-next-next-prior=p;p-next=p-next-next;}break;}break;}p=p-next;}printf(分区号为%d的内存回收成功\n,ID);returnFINISH;}voidshow(){printf(************************当前内存分配情况*************************\n);Node*p=head-next;while(p){printf(分区号：);if(p-data.ID==Free)printf(未分配);elseprintf(%6d,p-data.ID);printf(始地址：%4d,p-data.address);printf(分区大小：%4dKB,p-data.size);printf(状态：);if(p-data.sign==Free)printf(空闲\n);elseif(p-data.sign==Zhanyong)printf(已分配\n);p=p-next;}printf(\n);}intmain(){Create();intchoice;inti;for(i=0;;i++){printf(请选择操作：\n);printf(1.分配内存\n);printf(2.回收内存\n);printf(3.显示内存分配情况\n);printf(0.退出程序\n);scanf(%d,&choice);if(choice==1)Allocation();elseif(choice==2){intID;printf(输入要回收的分区号：);scanf(%d,&ID);Recycle(ID);}elseif(choice==3)show();elseif(choice==0)break;else{printf(输入有误！\n);continue;}}}