采用首次适应算法的动态分区分配模拟课程设计实验报告

11需求分析1）本程序要求实现对内存的动态分配与回收的模拟，同时，在内存的分配时还必须使用首次适应算法，最后，还要显示内存块分配和回收后空闲内存分区链的情况。2）要实现对作业的内存分配，首先要有一个对作业进行创建和分配内存的模块，其中，该模块在分配内存时要使用首次适应算法；要实现对内存的回收，要有一个内存回收的模块，其中，该模块在回收内存时要考虑内存回收的四种情况；最后，还要有一个能显示内存空闲分区链的情况的模块。2概要设计1）首次适应算法的结构如图1：图1首次适应算法的结构图2）数据结构：structFq从链首开始顺序查找空闲分区链完否？返回分区大小所需大小？分区大小-所需大小=不可再分割大小？从该分区中划出所需大小的新分区将该整个分区从空闲分区链中移出将该分区分配给相应的作业，修改有关数据返回Y继续检索下一个表项YNNNY2{intsize,o,no;Fq*before,*next;};其中，Fq表示结构体的名字（类型），size表示分区的可用空间大小，o表示该分区的状态（是否已分配），no表示该分区中的作业标志，*before表示该结点的向前指针，*next表示该结点的向后指针。3）各种函数说明：voidalloc(intb,intno,Fq*p)；对作业no进行内存分配的功能函数；其中，参数b表示需求的内存大小，参数no表示作业的编号，参数*p表示空闲分区链的第一个非空结点的指针；voidfree(Fq*c)；将地址为c的分区的内存回收；其中，参数*c表示要回收内存的结点；voidcreate(Fq*head)；创建新作业的子函数；其中，参数*head表示空闲分区链的链首指针；要配合函数alloc（）使用；voidcha(Fq*head)；查看内存中的空闲分区链的子函数；其中，参数*head表示空闲分区链的链首指针；voidhui(Fq*head)；回收内存的子函数；其中，参数*head表示空闲分区链的链首指针；要配合函数free（）使用；3运行环境1）操作系统:WindowsXP(32位/DirectX11)2）电脑:X86兼容台式电脑处理器:英特尔Pentium(奔腾)双核E5300@2.60GHz内存:2GB4开发工具和编程语言1）开发工具：VisualC++6.0；32）编程语言：C++语言；5详细设计1）程序结构如图2：图2程序结构图2）●主菜单模块：voidmain()//主函数{Fq*head=newFq;head-next=newFq;head-next-size=MAXSIZE;head-next-o=0;head-next-next=NULL;intchoice=0;do{cout请选择你要进行的操作：endl;cout1、创建新作业2、查看空闲分区链3、回收内存空间0、退出endl;cinchoice;switch(choice){主菜单创建新作业alloc（）；内存分配查看空闲分区链free（）；内存回收程序结束退出回收内存空间4case1:create(head);break;case2:cha(head);break;case3:hui(head);break;case0:break;default:cout输入错误！endl;}}while(choice!=0);}●创建新作业模块：voidcreate(Fq*head)//创建作业子函数{Fq*p=head-next;p-before=head;intno=0,b=0;cout请输入要创建的作业的编号：;cinno;cout请输入作业的需求空间大小：;cinb;alloc(b,no,p);//此处调用功能函数alloc()}●查看空闲分区链模块：voidcha(Fq*head)//查看内存中的空闲分区链的子函数{Fq*p=head-next;p-before=head;inti=0;cout空闲分区链的情况为：endl;while(p!=NULL){if(p-o==0){cout空闲分区++ip-sizeKendl;}p=p-next;5}}●回收内存空间模块：voidhui(Fq*head)//回收内存的子函数{Fq*p=head-next;p-before=head;intno=0;cout请输入要回收内存的作业号：;cinno;while(p!=NULL){if(p-no==no){free(p);//此处调用功能函数free()cout作业no的内存已回收！endl;return;}elsep=p-next;}}●内存分配功能函数模块：voidalloc(intb,intno,Fq*p)//对作业no进行内存分配的子函数{while(p!=NULL){if(p-o==1){p=p-next;}else{if(p-sizeb){if(p-size-b=min_size)6{p-o=1;p-no=no;}else{Fq*q=newFq;Fq*r;r=p-before;r-next=q;q-before=r;q-next=p;p-before=q;q-size=b;p-size=p-size-b;q-no=no;q-o=1;}cout内存分配成功！endl;return;}elsep=p-next;}}cout内存分配失败！endl;}●内存回收功能函数模块：voidfree(Fq*c)//将地址为c的分区内存回收{if(c-before-o==0&&c-next-o==0){Fq*r=c-before,*s=c-next-next;r-size=(r-size+c-size+c-next-size);r-next=s;7if(s!=NULL)s-before=r;}if(c-before-o==0&&c-next-o!=0){c-before-size=c-before-size+c-size;c-before-next=c-next;c-next-before=c-before;}if(c-next-o==0&&c-before-o!=0){Fq*r=c-next-next;c-size=c-size+c-next-size;c-next=c-next-next;if(r!=NULL)r-before=c;c-o=0;}elsec-o=0;}6调试分析1）内存分配功能函数模块：刚开始对作业分配内存时，只是将空闲分区的大小以及前后向指针进行修改，而没有对分配给作业的内存进行设置；这样，尽管内存的空闲分区大小已经变小，但是，以后却无法对已分配的内存空间以及作业进行修改；于是，我经过思考后，决定将分配给作业的内存空间也设置为一个分区，只不过不是空闲的分区，通过状态标识符o来与空闲分区进行区别。2）回收内存空间模块：刚开始编写此模块的代码时，我有一种无从下手的感觉；因为，如果要回收某个作业的内存，那么必须知道该作业所在的内存中的位置；但是，刚开始我用的数据结构中只有表示内存状态的属性（分区可用空间大小，状态标识符，前后向指针），这样就不能对特定的作业进行操作；最后，我经过思考决定在内存的数据结构中增加一项，即作业标识符，用来保存分区中的作业信息，从而达到查找特定作业所在内存分区的目的。83）在编写代码的过程中，我还遇到了一些小的问题；比如，对链表进行操作时，老是出现错误，不能对链表进行正确的操作等；这些问题与我对链表的认识不够深入和准确有关，不过，通过这次程序的编写，进一步加深了我对链表的理解，对链表的运用也变得得心应手了。7测试结果1）测试数据：作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200KB；作业3释放100KB；作业1释放130KB；作业5申请140KB；作业6申请60KB；作业7申请50KB；作业6释放60KB2）程序运行结果如图3、4所示：图3程序运行结果图9图4程序运行结果图