首次适应算法实验报告(共8页).docx

精选优质文档-倾情为你奉上操作操作系统大作业题目：首次适应算法分配内存学 号： 学生姓名： 张鲁云 班 级：计科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<iostream.h>#include<stdlib.h>#include<stdio.h>#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("分配成功！"); elseprintf("内存不足，分配失败！"); 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;elsereturn 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状态nn"); while(p) printf("%d ",flag);flag+;printf("%d t",p->data.address);printf("%dKB t",p->data.size); if(p->data.state=Free) printf("空闲nn"); elseprintf("已分配nn"); p=p->next; printf("+nn"); /主函数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，作业运行完成离开系统时，系统如何进行内存回收，采用的是首次适应算法，应用的数据结构是双向链表。实际上整个程序是比较简单的，但是由于自己对链表的应用不熟悉，查阅课本文库才实现内存分配这简单的功能，这个程序的缺陷就是在进行操作选择时没有进行分配空间的情况下回收空间会出现错误。本次试验使我对链表有了一定的了解但是还需继续学习。专心-专注-专业