动态分区分配方式首次适应算法

1、动态分区分配方式首次适应算法 算法思路使用动态分区分配中的数据结构和分配算法，编辑动态分区存储管理方式并实现。本程序主要采用首次适应算法的动态分区分配过程alloc()和回收过程free()。 空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小分配给作业。二、算法流程图检查完否？从头开始查表YesNo与要求内存是否一致？继续查找下一个表NoYes 三、函数代码#include<iostream.h>#include<stdlib.h>#de

2、fine Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_length 640 /最大内存空间为640KBtypedef int Status;typedef struct freearea/定义一个空闲区说明表结构int ID;long size;long address;int state;ElemType;typedef struct DuLNode /double linked list ElemType data; struct DuLNode *prior; /前趋指针 s

3、truct DuLNode *next; /后继指针DuLNode,*DuLinkList;DuLinkList block_first; /头结点DuLinkList block_last; /尾结点Status alloc();/内存分配Status free(int); /内存回收Status First_fit(int,int);/首次适应算法void show();/查看分配Status Initblock();/开创空间表Status Initblock()/开创带头结点的内存空间链表block_first=(DuLinkList)malloc(sizeof(DuLNode);bl

4、ock_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; block_last->data.size=MAX_length; block_last->data.ID=0; block_last->data.state=Free; return O

5、K;/- 分 配 主 存 -Status alloc()int ID,request;cout<<"请输入作业(分区号)："cin>>ID; cout<<"请输入需要分配的主存大小(单位:KB)：" cin>>request; if(request<0 |request=0)cout<<"分配大小不合适，请重试！"<<endl;return ERROR;if(First_fit(ID,request)=OK)cout<<"分配成功！&q

6、uot;<<endl;elsecout<<"内存不足，分配失败！"<<endl;/- 首次适应算法 -Status First_fit(int ID,int request)/传入作业名及申请量/为申请作业开辟新空间且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next;w

7、hile(p)if(p->data.state=Free && p->data.size=request)/有大小恰好合适的空闲块p->data.state=Busy;p->data.ID=ID;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->

8、;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 ID)DuLNode *p=block_first;while(p)if(p->data.ID=ID)p->data.state=Free;p->data.ID=Free;if(p->pr

9、ior->data.state=Free)/与前面的空闲块相连p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior;if(p->next->data.state=Free)/与后面的空闲块相连p->data.size+=p->next->data.size;if(p->next->next=NULL)p->next=NULL;elsep->next->next-&g

10、t;prior=p;p->next=p->next->next;break;p=p->next;cout<<"分区："<<ID<<"回收成功"<<endl;return OK;/- 显示主存分配情况 -void show()cout<<"+n"cout<<"+ 主 存 分 配 情 况 +n"cout<<"+n"DuLNode *p=block_first->next;while(p)

11、cout<<"分 区 号："if(p->data.ID=Free)cout<<"Free"<<endl;elsecout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address;cout<<" 分区大小："<<p->data.size<<" KB"cout<<" 状 态："if(p

12、->data.state=Free)cout<<"空 闲"<<endl;elsecout<<"已分配"<<endl;p=p->next;/- 主 函 数-void main()Initblock();int choice;int i;for(i=0;i+) cout<<"+n"cout<<"+动态分区分配方式的模拟一+n"cout<<"+首次适应算法+n"cout<<" +n&q

13、uot;cout<<" + 1: 分配内存 2: 回收内存 +n"cout<<" + 3: 查看分配 0: 退 出 +n"cout<<" +n"cout<<"请输入您的操作 ："cin>>choice;if(choice=1)/ 分配内存alloc();else if(choice=2)/ 内存回收 int ID; cout<<"请输入您要释放的分区号：" cin>>ID;free(ID);else if(choice=3)/显示主存show();else if(choice=0)/退出break;else /输入操作