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

实验名称： 操作系统动态分配 姓 名： 杨秀龙 学 号： 1107300432 专业班级： 创新实验班111 指导老师： 霍林 实验题目内存动态分区的分配与回收内存实验目的有利于我们更好的了解内存动态分区分配的操作情况，掌握可变分区首次适应算法的原理以及其编程实现。设计思想可变分区分配是根据进程的实际需求，动态地为之分配内存空间。首次适应算法要求空闲空间链以地址递增的次序链接。进行内存分配时，从链表头部开始依次检索，找到第一个不小于请求空间大小的空闲空间进行分配。分配时需考虑碎片问题，若分配会导致碎片产生则将整块分区分配。内存的回收需要考虑四种情况：1 收分区前后两个分区都空闲，则需要和前后两个分区合并；2 回收分区只有前一分区空闲，则与前一分区合并；3 回收分区只有后一分区空闲，则和后一分区合并；4 回收分区独立，不考虑合并主要数据结构主要的数据结构有两个：空闲分区表结构和表的链结构。根据空闲分区的作用，空闲分区表结构必须包括（分区号、分区起始地址、分区状态、分区数据大小）。由于采用的是双向链表的结果，所以表的链结构包括（空闲分区表的信息、首指针、尾指针）结构程序代码如下：typedef struct Bodyint ID;int size;int address;int sign;typedef struct Node Body data;struct Node *prior; struct Node *next; *DLinkList;流程图退出选0输入有误3 or0选择0-3操作操作界面开始选3显示内存分配选2回收内存选1分配内存输入分区号结束合并后回收合并后回收该分区后一个分区空闲该分区前一个分区空闲合并后回收该分区前后都空闲结束将分区从空闲链移出，并修改相应数据结构整块分配判断是否会有碎片内存不足判断剩余空间是否足够输入分区大小运行结果图（1）主界面图（2）分配3个分区后的分配情况图（3）回收1、3分区后的分配情况图（4）再次分配4分区后的分配情况附录：源代码如下：#include#include#define Free 0 /空闲#define Zhanyong 1 /占用 #define FINISH 1 /完成#define ERROR 0 /出错#define memory 512 /最大内存#define min 10 /碎片值typedef struct Bodyint ID;int size;int address;int sign;typedef struct Node Body data;struct Node *prior; struct Node *next; *DLinkList;DLinkList head; /头结点DLinkList tou; /尾结点int Create()/初始化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;return FINISH;int FirstFit(int ID,int space)/首次适应算法DLinkList NewNode=(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;return FINISH;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;return FINISH;break; if(p-data.sign=Free & p-data.sizespace & p-data.size-spacedata.sign=Zhanyong;p-data.ID=ID;return FINISH;break;p=p-next;/若已有分配，P指针后移return ERROR;int Allocation()/内存分配int ID,space;printf(请输入分区号（不能输入相同的两个分区号）：);scanf(%d,&ID);printf(输入分配内存大小(单位:KB)：);scanf(%d,&space);if(spacedata.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;elsep-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;elsep-next-next-prior=p;p-next=p-next-next;break;break;p=p-next;printf(分区号为%d的内存回收成功n,ID);return FINISH;void show()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);else if(p-data.sign=Zhanyong)printf(已分配n);p=p-next;printf(n);int main()Create();int choice;int i;for(i=0;i+) printf(请选择操作：n);printf(1.分配内存 n);printf(2.回收内存 n);printf(3.显示内存分配情况 n);printf(0.退出程序n);scanf(%d,&choice