操作操作系统大作业题目：初次适应算法分派内存学 号： 学生姓名： 张鲁云 班 级：计科121 初次适应算法分派内存一、 问题描述在内存分派中，动态分区是根据实际的进程需求，动态地为之分派空间而初次适应算法分派时从表头指针开始查找可运用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分派给用户可运用空间表自身既不按节点的初始地址有序，也不按节点的大小有序用户释放内存，回收时只是将空闲块插入在链表的表头即可，此算法比较节省时间二、 运营环境 VC6.0三、 算法思想初次适应算法规定空闲分区链以地址递增的顺序链接在分派内存时，从链首开始查找，直到找到一个大小能满足规定的空闲分区为止；然后按照作业大小，从该分区中划出一块内存空间分派给请求者，余下的空闲区仍留在空闲链中若从链首到链尾都不能找到一个能满足规定的分区，则本次分派失败四、 实验目的在计算机系统中，为了提高内存区的运用率，必须给电脑内存区进行合理的分派本实验通过对内存区分派方法初次适应算法的使用，来了解内存分派的模式五、 初次适应算法分派内存算法概要 （1） 结构体Typedef struct freearea//定义一个空闲区说明表结构{ long size; //分区大小 long address; //分区地址 int state; //状态}ElemType; // 线性表的双向链表存储结构Typedef struct DuLNode{ ElemType data; structDuLNode *prior; //前趋指针 structDuLNode *next; //后继指针} DuLNode,*DuLinkList;Status Initblock(intMAX_length)//开创带头结点的内存空间链表{ block_first=(DuLinkList)malloc(sizeof(DuLNode)); block_last=(DuLinkList)malloc(sizeof(DuLNode)); block_first->prior=NULL; //头结点的前驱指针指向空 block_first->next=block_last; //头结点的后继指针指向尾结点 block_last->prior=block_first; //尾结点的前驱指针指向头结点 block_last->next=NULL; //尾结点的后继指针指向空 block_last->data.address=0; //尾结点的地址是0 block_last->data.size=MAX_length; //分区大小是最大分区 block_last->data.state=Free; //状态是空 return OK; } （2）重要函数说明：void alloc()；进行内存分派的功能函数。
Status free(int flag)将地址为flag的分区的内存回收Status First_fit(int request)创建进程空间的子函数；其中，参数request表达空闲分区链的链首指针；要配合函数alloc（）使用void show()查看内存中的分区情况输入内存空间大小六、 流程图开辟内存空间内存分派情况显示输入操作序列号其他数输入有误，请重试！1Alloc输入分派区间大小3退出FFirst_fit request<0 ||request==0FTT分派成功！内存局限性，分派失败！配大小不合适，请重试！输入回收区号分区回收2free(flag)七、 代码实现#include#include#include#define Free 0 //空闲状态#define Busy 1 //已用状态#define OK 1 //完毕#define ERROR 0 //犯错//#define MAX_length 640 //最大内存空间为640KB typedefint Status; int flag; typedefstructfreearea//定义一个空闲区说明表结构{ long size; //分区大小 long address; //分区地址 int state; //状态}ElemType; // 线性表的双向链表存储结构typedefstructDuLNode{ ElemType data; structDuLNode *prior; //前趋指针 structDuLNode *next; //后继指针} DuLNode,*DuLinkList; DuLinkListblock_first; //头结点DuLinkListblock_last; //尾结点Status alloc(int);//内存分派Status free(int); //内存回收Status First_fit(int);//初次适应算法void show();//查看分派Status Initblock();//开创空间表Status Initblock(intMAX_length)//开创带头结点的内存空间链表{ block_first=(DuLinkList)malloc(sizeof(DuLNode)); block_last=(DuLinkList)malloc(sizeof(DuLNode)); block_first->prior=NULL; //头结点的前驱指针指向空 block_first->next=block_last; //头结点的后继指针指向尾结点 block_last->prior=block_first; //尾结点的前驱指针指向头结点 block_last->next=NULL; //尾结点的后继指针指向空 block_last->data.address=0; //尾结点的地址是0 block_last->data.size=MAX_length; //分区大小是最大分区 block_last->data.state=Free; //状态是空 return OK; } //分派主存Status alloc() { int request = 0; printf("请输入需要分派的主存大小(单位:KB)："); scanf("%d",&request); if(request<0 ||request==0) { printf("配大小不合适，请重试！"); return ERROR; } { if(First_fit(request)==OK) printf("分派成功！"); else printf("内存局限性，分派失败！"); return OK; } } //初次适应算法Status First_fit(int request) { //为申请作业开辟新空间且初始化 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next; while(p) { if(p->data.state==Free && p->data.size==request) {//有大小恰好合适的空闲块 p->data.state=Busy; return OK; break; } if(p->data.state==Free && p->data.size>request) {//有空闲块能满足需求且有剩余 temp->prior=p->prior; temp->next=p; temp->data.address=p->data.address; p->prior->next=temp; p->prior=temp; p->data.address=temp->data.address+temp->data.size; p->data.size-=request; return OK; break; } p=p->next; } return ERROR; } //主存回收Status free(int flag) { DuLNode *p=block_first; for(inti= 0; i<= flag; i++) if(p!=NULL) p=p->next;else return ERROR; p->data.state=Free; if(p->prior!=block_first&& p->prior->data.state==Free)//与前面的空闲块相连 { p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior; p=p->prior; } if(p->next!=block_last&& p->next->data.state==Free)//与后面的空闲块相连 { p->data.size+=p->next->data.size; p->next->next->prior=p; p->next=p->next->next; } if(p->next==block_last&& p->next->data.state==Free)//与最后的空闲块相连 { p->data.size+=p->next->data.size; p->next=NULL; } return OK; } //显示主存分派情况void show() { int flag = 0; printf("主存分派情况:\n"); DuLNode *p=block_first->next; printf("分区号\t起始地址\t分区大小\t状态\n\n"); while(p) { printf("%d ",flag); flag++; printf("%d \t",p->data.address); printf("%dKB \t",p->data.size); if(p->data.state==Free) printf("空闲\n\n"); else printf("已分派\n\n"); p=p->next; } printf("++++++++++++++++++++++++++++++++++++++++++++++\n\n"); } //主函数void main() { int c=1; intMAX_length;//算法选择标记 printf("初次适应算法内存分派算法：\n"); printf("input MAX_length:\n"); scanf("%d",&MAX_length); Initblock(MAX_length); //开创空间表 int choice;//操作选择标记 while(c=1) { show(); printf("请输入您的操作："); printf("\n1: 分派内存\n2: 回收内存\n0: 退出\n"); scanf("%d",&choice); { if(choice==1) { alloc(); // 分派内存 c=1; } else if(choice==2) // 内存回收 { int flag; printf("请输入您要释放的分区号：\n"); scanf("%d",&flag); free(flag); c=1; } else if(choice==0) {break; //退出 } else //输入操作有误 { printf("输入有误，请重试！\n"); c=1; } } printf("&&&&&&&\n");}}八、 运营截图九、 思考Jiesuo()成功解除死锁这次实验模拟内存分派，模拟了操作系统是如何通过作业调度选择作业进入内存以及系统是如何为进入内存的作业分派内存空间，实现多道作业同时驻留内存，就绪进程队列中的多个进程是如何以分式方式共享CPU，作业运营完毕离开系统时，系统如何进行内存回收，采用的是初次适应算法，应用的数据结构是双向链表。
事实上整个程序是比较简朴的，但是由于自己对链表的应用不熟悉，查阅课本文库才实现内存分派这简朴的功能，这个程序的缺陷就是在进行操作选择时没有进行分派空间的情况下回收空间会出现错误本次实验使我对链表有了一定的了解但是还需继续学习。