《动态分区分配算法要点》由会员分享，可在线阅读，更多相关《动态分区分配算法要点（16页珍藏版）》请在金锄头文库上搜索。
1、动态分区分配算法一实验内容与要求内容：动态分区分配是根据进程的实际需要，动态地为之分配内存空间， 而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区 分配给该作业。在本实验中运用了三种分配算法，分别是1.首次适应算法，2. 循环首次适应算法，3.最佳适应算法。要求：动态分区算法也称为可变分区分配算法，常见的空闲区查找算法有 首次适应算法，循环首次适应算法，最佳适应算法。特别注意分区回收时，相邻 空闲分区需要合并。(1) 参考操作系统教材理解这3种分配算法以及回收算法。(2) 实现3种分配算法以及回收算法。已知作业申请内存和释放内存的序列，给出内存的使用情况。(4) 作业申请
2、内存和释放内存的序列可以存放在文本文件中。(5) 设计简单的交互界面，演示所设计的功能。(可以使用MFC进行界面的设计)(6) 可根据自己能力，在完成以上基本要求后，对程序功能进行适当扩充。二、需求分析本次实验通过用C语言进行编程并调试、运行，形象地表现出动态分区的分 配方式，直观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之 间的区别。加深了我们对两种算法优缺点的理解，帮助我们了解一些数据结构和 分配算法，进一步加深我们对动态分区存储器管理方式及其实现过程的理解。主 要的问题在于，如何解决两种算法对内存的释放和回收空间的表示。动态分区分配：又称为可变分区分配，这种分配方式并不事先
3、先将主存划分 成一块块的分区，而是在作业进入主存时，根据作业的大小动态地建立分区。并 使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数 目也是可变的。分区分配算法：1. 首次适应法：为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空 白块，就把该空白块分配给该作业。特点：优先利用内存中底地址部分的空闲分区（将所有空闲区，按其地址递增的 顺序链接）2. 循环首次适应算法该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从 第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找， 直至找到第一个能满足要求的空闲分区，从中划出一块
4、与请求大小相等的内存空 间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N=0 时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。3. 最佳适应算法：接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配； 为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。三、概要设计动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用 情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条 链，每个分区的结构如下所示：typedef struct freearea/定义一个空闲区说明表结构int ID; /分区号l
5、ong size;/分区大小long address; /分区地址int state; /状态ElemType;typedef struct DuLNode /double linked listElemType data;struct DuLNode *prior; /前趋指针struct DuLNode *next; 后继指针DuLNode,*DuLinkList;前向指针和后向指针分别用于与当前分区的前后分区相链接，address用于为1时表示已分配，说明当前分区的起始地址，状态字为0时表示当前分区空闲 id为分配的作业号，size表示分配的内存大小。流程图:四、详细设计#include
6、 #include#include #includeusing namespace std;#define Free 0 /空闲状态#define Busy 1 已用状态#define OK 1/完成#define ERROR 0 /出错#define MAX_length 640 /最大内存空间为 640KB typedef int Status;typedef struct freearea/定义一个空闲区说明表结构 int ID;/分区号long size;/分区大小long address; /分区地址int state;/状态ElemType;/ 线性表的双向链表存储结构 typed
7、ef struct DuLNode /double linked listElemType data;struct DuLNode *prior; /前趋指针struct DuLNode *next; 后继指针 DuLNode,*DuLinkList;DuLinkList block_first; /头结点 DuLinkList block_mid;DuLinkList block_last; / 尾结点Status alloc(int);/ 内存分配Status alloc2(int);/内存分配 2Status free(int); 内存回收Status First_fit(int,int
8、);首次适应算法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=(DuLinkList)mall
9、oc(sizeof(DuLNode);block_first-prior=NULL;block_first-next=block_mid;block_mid-next=block_last;block_mid-prior=block_first;block_last-prior=block_mid;block_last-next=NULL;block_mid-data.address=0;block_mid-data.size=MAX_length;block_mid-data.ID=0;block_mid-data.state=Free;return OK;/分配主存Status alloc
10、(int ch)if(request0 |request=0)cout分配大小不合适，请重试！ endl;return ERROR;switch(ch)case 1:if(First_fit(ID,request)=OK) cout分配成功！ endl;else cout内存不足，分配失败！ endl;ID=0;request=0;return OK;break;case 2:if(CycleFirst_fit(ID,request)=OK) cout分配成功！ endl;else cout内存不足，分配失败！ endl;ID=0;request=0;return OK;break;case
11、3:if(Best_fit(ID,request)=OK) cout分配成功！ endl;else cout内存不足，分配失败！ endl;ID=0;request=0;return OK;break;default:cout*ERROR!*;Status alloc2(int ch)int ID,request;coutID;coutrequest;if(request0 |request=0)cout分配大小不合适，请重试！ endl;return ERROR;switch(ch)case 1:if(First_fit(ID,request)=OK) cout分配成功！ endl;else
12、 cout内存不足，分配失败！ endl;return OK;break;case 2:if(CycleFirst_fit(ID,request)=OK) cout分配成功！ endl;else cout内存不足，分配失败！ endl;return OK;break;case 3:if(Best_fit(ID,request)=OK) cout分配成功！ endl;else cout内存不足，分配失败！ endl;return OK;break;default:coutdata.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode
13、*p=block_first-next;while(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.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;return ERROR;/循环首次适应算法Status CycleFirst_fit(int ID,
