实验报告-动态分区分配算法.doc

. 南昌大学实验报告学生姓名： 马江涛 学 号： 8000612091 专业班级： 计算机软件121班 实验类型：验证综合设计创新 实验日期： 2014-05-08 实验成绩： 【实验要求】1、编程实现首次适应算法和最佳适应算法的动态分区分配的分配过程和回收过程。其中，空闲分区通过分区链来管理；在进行内存分配时，系统优先使用空闲区低端的空间。2、假设初始状态下，可用内存空间为640K，并依次有下列请求序列：1) 作业1申请130KB。2) 作业2申请60KB。3) 作业3申请100KB。4) 作业2释放60KB。5) 作业4申请200KB。6) 作业3释放100KB。7) 作业1释放130KB。8) 作业5申请140KB。9) 作业6申请60KB。10) 作业7申请50KB。11) 作业6释放60KB。请分别用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况【可参考后文的实验提示】。3、上机时认真的进行测试，输入不同的资源分配请求，写出实验结果；4、具体要求：（1）对你的程序关键代码处进行注释。（2）给出实验数据，对结果进行分析，说明对相关知识点的理解。【实验目的】了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。【实验思路】首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。【实验结果分析】【实验提示】你的动态分区的分配与回收，程序运行结果要可视化。可参考如下运行结果的模式。请分析如下这个结果来自于哪一种动态分配算法？实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计内存分配算法；第三，在设计的数据表格基础上设计内存回收算法。首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占用的区域。由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：Free起始地址：130分区大小：60 KB状 态：空 闲分 区 号：3起始地址：190分区大小：100 KB状 态：已分配分 区 号：Free起始地址：290分区大小：350 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：4请输入需要分配的主存大小(单位:KB)：200分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：Free起始地址：130分区大小：60 KB状 态：空 闲分 区 号：3起始地址：190分区大小：100 KB状 态：已分配分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：2请输入您要释放的分区号：3* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：Free起始地址：130分区大小：160 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：2请输入您要释放的分区号：1* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：Free起始地址：0分区大小：290 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：5请输入需要分配的主存大小(单位:KB)：140分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：5起始地址：0分区大小：140 KB状 态：已分配分 区 号：Free起始地址：140分区大小：150 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：6请输入需要分配的主存大小(单位:KB)：60分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：5起始地址：0分区大小：140 KB状 态：已分配分 区 号：6起始地址：140分区大小：60 KB状 态：已分配分 区 号：Free起始地址：200分区大小：90 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：7请输入需要分配的主存大小(单位:KB)：50分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：5起始地址：0分区大小：140 KB状 态：已分配分 区 号：6起始地址：140分区大小：60 KB状 态：已分配分 区 号：7起始地址：200分区大小：50 KB状 态：已分配分 区 号：Free起始地址：250分区大小：40 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：2请输入您要释放的分区号：6* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：5起始地址：0分区大小：140 KB状 态：已分配分 区 号：Free起始地址：140分区大小：60 KB状 态：空 闲分 区 号：7起始地址：200分区大小：50 KB状 态：已分配分 区 号：Free起始地址：250分区大小：40 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：0Press any key to continue【首次适应算法】1.作业1申请130KB。作业2申请60KB。作业3申请100KB。具体分配情况如下：2.作业2释放60KB。3.作业4申请200KB。4. 作业3释放100KB。5. 作业1释放130KB。6. 作业5申请140KB。作业6申请60KB。作业7申请50KB。7. 作业6释放60KB。【最佳适应算法】1.作业1申请130KB。作业2申请60KB。作业3申请100KB。2.作业2释放60KB。作业4申请200KB。3.作业3释放100KB。4.作业1释放130KB。5.作业5申请140KB。作业6申请60KB。作业7申请50KB。6.作业6释放60KB。【代码实现】/*/* 动态分区分配方式的模拟 */* 制作者：马江涛 */* 学号： 8000612091 */* 班级：计算机软件121班 */* #include#include #define 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 listElemType data; struct DuLNode *prior; /前趋指针struct DuLNode *next; /后继指针DuLNode,*DuLinkList; DuLinkList block_first; /头结点DuLinkList block_last; /尾结点 Status alloc(int);/内存分配Status free(int); /内存回收Status First_fit(int,int);/首次适应算法Status Best_fit(int,int); /最佳适应算法void show();/查看分配Status Initblock();/开创空间表 Status Initblock()/开创带头结点的内存空间链表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_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 OK; /- 分 配 主 存 -Status alloc(int ch)int ID,request;coutID;coutrequest;if(request0 |request=0) cout分配大小不合适，请重试！endl;return ERROR; if(ch=2) /选择最佳适应算法if(Best_fit(ID,request)=OK) cout分配成功！endl;else cout内存不足，分配失败！endl;return OK;else /默认首次适应算法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.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 Best_fit(int ID,int request)int ch; /记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.ID=ID; temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; /记录最佳插入位置while(p) /初始化最小空间和最佳位置if(p-data.state=Free &(p-data.sizerequest | p-data.size=request) )q=p;ch=p-data.size-request;break;p=p-next;while(p)if(p-data.state=Free & p-data.size=request)/空闲块大小恰好合适p-data.ID=ID;p-data.state=Busy;return OK;break;if(p-data.state=Free & p-data.sizerequest)/空闲块大于分配需求if(p-data.size-requestdata.size-request;/更新剩余最小值q=p;/更新最佳位置指向p=p-next;if(q=NULL) return ERROR;/没有找到空闲块else/找到了最佳位置并实现分配temp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;return OK; /- 主 存 回 收 -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-data.size;p-next-next-prior=p;p-next=p-next-next;break;p=p-next;return OK; /- 显示主存分配情况 -void show()cout+n;cout+ 主 存 分 配 情 况 +n;coutnext;while(p)coutdata.ID=Free) coutFreeendl;else coutdata.IDendl;cout起始地址：data.addressendl;cout分区大小：data.size KBendl;coutdata.