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

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

2、e 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; /前趋指针 struct DuLNode *next

3、; /后继指针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); block_last=(DuLinkL

4、ist)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 OK;/- 分 配 主 存 -Status alloc() int ID,request; cout

5、ID; coutrequest; if(request0 |request=0) cout分配大小不合适，请重试！endl; return ERROR; if(First_fit(ID,request)=OK) cout分配成功！endl; else cout内存不足，分配失败！data.ID=ID; 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.

6、state=Busy; p-data.ID=ID; return OK; break; if(p-data.state=Free & p-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;

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

8、-data.size;if(p-next-next=NULL)p-next=NULL;else p-next-next-prior=p; p-next=p-next-next; break; p=p-next; cout分区：ID回收成功endl; return OK;/ /- 显示主存分配情况 -void show() cout+n; cout+ 主 存 分 配 情 况 +n; coutnext; while(p) coutdata.ID=Free) coutFreeendl; else coutdata.IDendl; cout起始地址：data.address; cout 分区大小：da

9、ta.size KB; coutdata.state=Free) cout空 闲endl; else cout已分配next; /- 主 函 数-void main() Initblock(); int choice; int i; for(i=0;i+) cout+n; cout+动态分区分配方式的模拟一+n; cout+首次适应算法+n; cout +n; cout + 1: 分配内存 2: 回收内存 +n; cout + 3: 查看分配 0: 退 出 +n; cout +n; coutchoice; if(choice=1)/ 分配内存 alloc(); else if(choice=2)/ 内存回收 int ID; coutID; free(ID); else if(choice=3)/显示主存 show(); else if(choice=0)/退出 break; else /输入操作有误 cout输入有误，请重试！endl; continue; 四、案例测试 初始空闲区作业1进入空闲区后的状态作业2进入空闲区后的状态作业3进入空闲区后的状态作业4进入空闲区后的状态100k20K1K1K1K50k50k50k50k14k60k60k60k0k0k18k18k18k18k18k180k180k180k180k180k45k45k45k45k45k