首次适应算法实验报告记录

《首次适应算法实验报告记录》由会员分享，可在线阅读，更多相关《首次适应算法实验报告记录（10页珍藏版）》请在装配图网上搜索。

1、首次适应算法实验报告记录作者：日期：2操作操作系统大作业题目：首次适应算法分配内存学号： 1207300142学生姓名：张鲁云班级：计科1213首次适应算法分配内存一、问题描述在内存分配中，动态分区是根据实际的进程需求，动态地为之分配空间。而首次适应算法分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分配给用户。可利用空间表本身既不按节点的初始地址有序，也不按节点的大小有序。用户释放内存，回收时只是将空闲块插入在链表的表头即可，此算法比较节省时间。二、运行环境VC6.0三、算法思想 。首次适应算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始

2、查找，直到找到一个大小能满足要求的空闲分区为止；然后按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲区仍留在空闲链中。若从链首到链尾都不能找到一个能满足要求的分区，则此次分配失败。四、实验目的在计算机系统中，为了提高内存区的利用率，必须给电脑内存区进行合理的分配。本实验通过对内存区分配方法首次适应算法的使用，来了解内存分配的模式。五、首次适应算法分配内存算法概要（ 1） 结构体Typedef struct freearea/定义一个空闲区说明表结构long size;/分区大小long address; /分区地址int state;/状态ElemType; /线性表的双向链表

3、存储结构Typedef struct DuLNodeElemType 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-n

4、ext=block_last;/头结点的后继指针指向尾结点block_last-prior=block_first;/尾结点的前驱指针指向头结点block_last-next=NULL;/尾结点的后继指针指向空block_last-data.address=0;/尾结点的地址是 04block_last-data.size=MAX_length;/分区大小是最大分区block_last-data.state=Free;/状态是空return OK; （2）主要函数说明：void alloc()；进行内存分配的功能函数。Status free(int flag)将地址为 flag的分区的内存回收

5、。Status First_fit(int request)创建进程空间的子函数；其中，参数request 表示空闲分区链的链首指针；要配合函数alloc （）使用。void show()查看内存中的分区情况。六、 流程图输入内存空间大小开辟内存空间内存分配情况显示输入操作序列号Alloc1输入分配区间大小request0T分配成功！配大小不合适，请重试！分区回收输入回收区号free(fla其他数输入有误，请重试！F3退出First_TF内存不足，分配失败！25七、代码实现#include#include#include#define Free 0 / 空闲状态#define Busy 1 /

6、 已用状态#define OK 1/ 完成#define ERROR 0 /出错/#define MAX_length 640 /最大内存空间为640KBtypedefint Status;int flag;typedefstructfreearea/定义一个空闲区说明表结构long size;/ 分区大小long address; / 分区地址int state;/ 状态ElemType;/线性表的双向链表存储结构typedefstructDuLNodeElemType data;structDuLNode *prior; /前趋指针structDuLNode *next;/ 后继指针 Du

7、LNode,*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=(D

8、uLinkList)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;/ 尾结点的地址是0block_last-data.size=MAX_length;/ 分区大小是最大分区block_last-data.state=Free;/ 状态

9、是空return OK;/ 分配主存6Status alloc() int request = 0;printf( 请输入需要分配的主存大小(单位 :KB)：);scanf(%d,&request);if(requestdata.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-

10、data.sizerequest)/ 有空闲块能满足需求且有剩余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;7return ERROR;/ 主存回收Status free(int flag) DuLNode *p=block_first;for(inti= 0; i

11、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

12、-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(%dt,p-data.address);printf(%dKBt

13、,p-data.size);if(p-data.state=Free)8printf( 空闲 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( 请输入您的操作：);print

14、f(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;9printf(&n);八、运行截图九、思考这次试验模拟内存分配，模拟了操作系统是如何通过作业调度选择作业进入内存以及系统是如何为进入内存的作业分配内存空间，实现多道作业同时驻留内存，就绪进程队列中的多个进程是如何以分式方式共享CPU，作业运行完成离开系统时，系统如何进行内存回收，采用的是首次适应算法，应用的数据结构是双向链表。实际上整个程序是比较简单的，但是由于自己对链表的应用不熟悉，查阅课本文库才实现内存分配这简单的功能，这个程序的缺陷就是在进行操作选择时没有进行分配空间的情况下回收空间会出现错误。本次试验使我对链表有了一定的了解但是还需继续学习。10