动态分区分配算法要点Word下载.docx

1、三、概要设计 动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示：typedef struct freearea/定义一个空闲区说明表结构int ID; /分区号long size; /分区大小long address; /分区地址int state; /状态ElemType;typedef struct DuLNode /double linked listElemType data; struct DuLNode *prior; /前趋指针struct DuLNode *next

2、; /后继指针DuLNode,*DuLinkList;前向指针和后向指针分别用于与当前分区的前后分区相链接，address用于说明当前分区的起始地址，状态字为0时表示当前分区空闲，为1时表示已分配，id为分配的作业号，size表示分配的内存大小。流程图：四、详细设计 #include #includefstreamstdlib.husing namespace std;#define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_length 640 /最大内存空间为640KBtyp

3、edef int Status; int ID; long size; long address; int state;/- 线性表的双向链表存储结构 - ElemType data; struct DuLNode *prior; struct DuLNode *next;DuLinkList block_first; /头结点DuLinkList block_mid;DuLinkList block_last; /尾结点Status alloc（int）;/内存分配Status alloc2（int）;/内存分配2Status free（int）; /内存回收Status First_fit

4、（int,int）; /首次适应算法Status CycleFirst_fit（int,int）;/循环首次适应算法Status Best_fit（int,int）; /最佳适应算法void show（）;/查看分配Status Initblock（）;/开创空间表int ID,request;long adds=0;Status Initblock（）/开创带头结点的内存空间链表 block_first=（DuLinkList）malloc（sizeof（DuLNode）; block_last=（DuLinkList）malloc（sizeof（DuLNode）; block_mid=（D

5、uLinkList）malloc（sizeof（DuLNode）; block_first-prior=NULL;next=block_mid; block_mid-next=block_last;prior=block_first; block_last-prior=block_mid;next=NULL;data.address=0;data.size=MAX_length;data.ID=0;data.state=Free; return OK;/- 分 配 主 存 -Status alloc（int ch） if（request0 |request=0） cout分配大小不合适，请重试

6、！endl; return ERROR; switch（ch） case 1: if（First_fit（ID,request）=OK） cout分配成功！ else cout内存不足，分配失败！ ID=0; request=0; return OK; break; case 2: if（CycleFirst_fit（ID,request）=OK） cout case 3: if（Best_fit（ID,request）=OK） cout default:*ERROR!*;Status alloc2（int ch） int ID,request; coutID;请输入需要分配的主存大小（单位:

7、KB）：request;/- 首次适应算法 -Status First_fit（int ID,int request）/传入作业名及申请量 /为申请作业开辟新空间且初始化 DuLinkList temp=（DuLinkList）malloc（sizeof（DuLNode）; temp-data.ID=ID;data.size=request;data.state=Busy; DuLNode *p=block_first-next; while（p） if（p-data.state=Free & p-data.size=request） /有大小恰好合适的空闲块 p- return OK; br

8、eak; data.sizerequest） /有空闲块能满足需求且有剩余 temp-prior=p-prior;next=p;data.address=p-data.address;prior-next=temp;prior=temp;data.address=temp-data.address+temp-data.size;data.size-=request; p=p- return ERROR;/- 循环首次适应算法 -Status CycleFirst_fit（int ID,int request）/传入作业名及申请量request&p-data.address=adds） adds

9、=p- coutaddsnext-data.size&data.state=Free） if（First_fit（ID,request）=OK） return OK; /- 最佳适应算法 -Status Best_fit（int ID,int request） int ch; /记录最小剩余空间 DuLNode *q=NULL; /记录最佳插入位置 while（p） /初始化最小空间和最佳位置 （p-request | p-data.size=request） ） q=p; ch=p-data.size-request; /空闲块大小恰好合适 /空闲块大于分配需求 if（p-data.size

10、-request/更新剩余最小值 q=p;/更新最佳位置指向 if（q=NULL） return ERROR;/没有找到空闲块 else /找到了最佳位置并实现分配 temp-prior=q-next=q;data.address=q- q-data.address+=request;data.size=ch;/- 主 存 回 收 -Status free（int ID） DuLNode *p=block_first;data.ID=ID）data.ID=Free;data.state=Free&data.state=Free）/前后都有空闲块 p-data.size+=p-next=p- a

11、dds=p- cout回收成功n break;data.state=Free）/与前面的空闲块相连data.state=Free）/与后面的空闲块相连prior=p;/- 显示主存分配情况 -void show（）+n+ 主 存 分 配 情 况 +n分 区 号：data.ID=Free） coutFreedata.ID起始地址：data.address分区大小：data.size KB状 态：data.state=Free） cout空 闲已分配 if（p=block_last）/- 主 函 数-void main（） int OpNum; int Sqe100100; FILE *fp; f

12、p=fopen（input.txt,r）; if（!fp）无法打开文件input.txt exit（1）; fscanf（fp,%d,&OpNum）; for（int ii=0;iiOpNum;ii+） for（int jj=0;jj3;jj+） fscanf（fp,Sqeiijj）;/算法选择标记 动态分区分配方式的模拟 n*n* 1.首次适应算法 *n* 2.循环首次适应算法 *n* 3.最佳适应算法 *n* 0.退出程序 *n请选择分配算法：ch; if（ch=0） exit（0）; Initblock（）; /开创空间表 int choice; /操作选择标记 for（int nn=0;nnchoice; if（choice=1） ID=Sqenn0; request=Sqenn2; if（Sqenn1=0）作业ID申请requestKB内存 alloc（ch）;/操作符为0，则开始分配内存 i