动态分区分配方式的模拟实验报告材料实用模板

用于动态分区分配的仿真实验报告模板华北电力大学已核实并上报了实验名称、仿真课程名称、动态分区分配方法、计算机操作系统专业课:学生姓名:号码:成就:讲师:实验日期:I .实验目的:了解动态分区分配方法中使用的数据结构和分配算法，进一步加深对动态分区存储管理方法及其实施过程的理解。

二、实验内容:(1)使用第一自适应算法和最佳自适应算法的动态分区分配过程alloc()和恢复过程free()分别用C语言实现。

其中，空闲分区由分区链管理；在内存分配中，系统优先考虑空闲区下端的空间。

(2)假设初始状态下的可用内存空间为640K，有以下请求序列:工作1需要130千字节。

对于任务2，申请60KB。

对于任务3，申请100KB。

◎作业2释放60KB。

对于任务4，申请200千字节。

◎作业3释放100KB。

作业1释放130KB。

作业5需要140千字节。

◎任务6适用于60KB。

◎作业7适用于50KB。

◎作业6释放60KB。

请分别使用首次自适应算法和最佳自适应算法来分配和回收内存块。

要求在每次分配和回收后显示空闲内存分区链的情况。

四、设计思路和方法:第一个自适应算法(学名:号码:成就:讲师:实验日期:I .实验目的:了解动态分区分配方法中使用的数据结构和分配算法，进一步加深对动态分区存储管理方法及其实施过程的理解。

二、实验内容:(1)使用第一自适应算法和最佳自适应算法的动态分区分配过程alloc()和恢复过程free()分别用C语言实现。

其中，空闲分区由分区链管理；在内存分配中，系统优先考虑空闲区下端的空间。

(2)假设初始状态下的可用内存空间为640K，有以下请求序列:工作1需要130千字节。

对于任务2，申请60KB。

对于任务3，申请100KB。

◎作业2释放60KB。

对于任务4，申请200千字节。

◎作业3释放100KB。

作业1释放130KB。

作业5需要140千字节。

◎任务6适用于60KB。

◎作业7适用于50KB。

◎作业6释放60KB。

实验报告四动态分区分配算法班级学号姓名一、实验目的动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。

在本实验中运用了四种分配算法，分别是1.首次适应算法，2.循环首次适应算法，3.最坏适应算法4.最佳适应算法。

二、实验环境普通的计算机一台，编译环境Microsoft Visual C++ 6.0三、算法思想1．数据结构（1）分区开始地址startaddress（2）分区大小size（3）分区状态state2．功能介绍（1）首次适应算法在首次适应算法中，是从已建立好的数组中顺序查找，直至找到第一个大小能满足要求的空闲分区为止，然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空间令开辟一块新的地址，大小为原来的大小减去作业大小，若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。

（2）循环首次适应算法该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N==0时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。

（3）最坏适应算法最坏适应分配算法是每次为作业分配内存时，扫描整个数组，总是把能满足条件的，又是最大的空闲分区分配给作业。

（4）最佳适应算法最坏适应分配算法是每次为作业分配内存时，扫描整个数组，总是把能满足条件的，又是最小的空闲分区分配给作业。

四、源程序#include <stdio.h>#define L 10typedef struct LNode{int startaddress;int size;int state;}LNode;LNodeP[L]={{0,128,0},{200,256,0},{500,512,0},{1 500,1600,0},{5000,150,0}};int N=5; int f=0;void print(){ int i;printf("起始地址分区状态\n");for(i=0;i<N;i++)printf("%3d %8d %4d\n",P[i].startaddress, P[i].size,P[i].state);}void First(){ int i,l=0,m;printf("\n输入请求分配分区的大小：");scanf("%d",&m);for(i=0;i<N;i++){ if(P[i].size<m)continue;else if(P[i].size==m){ P[i].state=1;l=1;break; }else{P[N].startaddress=P[i].startaddress+m;P[N].size=P[i].size-m;P[i].size=m;P[i].state=1;l=1; N++;break; } }if(l==1||i<N){ printf("地址成功分配\n\n");printf("地址分配成功后的状态：\n");print(); }elseprintf("没有可以分配的地址空间\n"); } void CirFirst(){ int l=0,m,t=0;printf("\n输入请求分配分区的大小：");scanf("%d",&m);while(f<N){ if(P[f].size<m){ f=f+1;if(f%N==0){ f=0;t=1;}continue; }if(P[f].size==m && P[f].state!=1){ P[f].state=1;l=1; f++;break; }if(P[f].size>m && P[f].state!=1){ P[N].startaddress=P[f].startaddress+m;P[N].size=P[f].size-m;P[f].size=m;P[f].state=1;l=1; N++;f++; break; } }if(l==1){ printf("地址成功分配\n\n");printf("地址分配成功后的状态：\n");print(); }elseprintf("没有可以分配的地址空间\n"); } void Worst(){int i,t=0,l=0,m;int a[L];printf("\n输入请求分配分区的大小：");scanf("%d",&m);for(i=0;i<N;i++){ a[i]=0;if(P[i].size<m)continue;else if(P[i].size==m){ P[i].state=1;l=1; break; }elsea[i]=P[i].size-m; }if(l==0){ for(i=0;i<N;i++){ if(a[i]!=0)t=i; }for(i=0;i<N;i++){ if(a[i]!=0 && a[i]>a[t])t=i; }P[N].startaddress=P[t].startaddress+m;P[N].size=P[t].size-m;P[t].size=m;P[t].state=1;l=1; N++; }if(l==1||i<N){ printf("地址成功分配\n\n");printf("地址分配成功后的状态：\n");print(); }elseprintf("没有可以分配的地址空间\n"); } void Best(){ int i,t=0,l=0,m;int a[L];printf("\n输入请求分配分区的大小：");scanf("%d",&m);for(i=0;i<N;i++){ a[i]=0;if(P[i].size<m)continue;else if(P[i].size==m){ P[i].state=1;l=1;break;}elsea[i]=P[i].size-m; }if(l==0){ for(i=0;i<N;i++){ if(a[i]!=0)t=i; }for(i=0;i<N;i++){ if(a[i]!=0 && a[i]<a[t])t=i; }P[N].startaddress=P[t].startaddress+m;P[N].size=P[t].size-m;P[t].size=m;P[t].state=1;l=1; N++; }if(l==1||i<N){ printf("地址成功分配\n\n");printf("地址分配成功后的状态：\n");print(); }elseprintf("没有可以分配的地址空间\n"); } void main(){ int k=0;printf("动态分区分配算法：");while(k!=5){printf("\n~~~~~~~~主菜单~~~~~~~~~");printf("\n1、首次适应算法\n2、循环首次适应算法");printf("\n3、最坏适应算法\n4、最佳适应算法");printf("\n5、退出\n");printf("请选择算法：");scanf("%d",&k);switch(k){ case 1:printf("\n初始状态为：\n");print();First();continue;case 2:printf("\n初始状态为：\n");print();CirFirst();continue;case 3:printf("\n初始状态为：\n"); print();Worst();continue;case 4:printf("\n初始状态为：\n");print();Best();continue;case 5:break;default:printf("选择错误，请重新选择。

1 需求分析1）本程序要求实现对内存的动态分配与回收的模拟，同时，在内存的分配时还必须使用首次适应算法，最后，还要显示内存块分配和回收后空闲内存分区链的情况。

2）要实现对作业的内存分配，首先要有一个对作业进行创建和分配内存的模块，其中，该模块在分配内存时要使用首次适应算法；要实现对内存的回收，要有一个内存回收的模块，其中，该模块在回收内存时要考虑内存回收的四种情况；最后，还要有一个能显示内存空闲分区链的情况的模块。

2 概要设计1）首次适应算法的结构如图1：图1 首次适应算法的结构图2）数据结构：struct Fq{int size,o,no;Fq *before,*next;};其中，Fq表示结构体的名字（类型），size表示分区的可用空间大小，o表示该分区的状态（是否已分配），no表示该分区中的作业标志，*before表示该结点的向前指针，*next表示该结点的向后指针。

3）各种函数说明：void alloc(int b,int no,Fq *p)；对作业no进行内存分配的功能函数；其中，参数b表示需求的内存大小，参数no表示作业的编号，参数*p表示空闲分区链的第一个非空结点的指针；void free(Fq *c)；将地址为c的分区的内存回收；其中，参数*c表示要回收内存的结点；void create(Fq *head)；创建新作业的子函数；其中，参数*head表示空闲分区链的链首指针；要配合函数alloc（）使用；void cha(Fq *head)；查看内存中的空闲分区链的子函数；其中，参数*head表示空闲分区链的链首指针；void hui(Fq *head)；回收内存的子函数；其中，参数*head表示空闲分区链的链首指针；要配合函数free（）使用；3 运行环境1）操作系统: Windows XP ( 32位 / DirectX 11 )2）电脑: X86 兼容台式电脑处理器: 英特尔 Pentium(奔腾) 双核 E5300 @ 2.60GHz内存: 2 GB4 开发工具和编程语言1）开发工具：Visual C++ 6.0；2）编程语言：C++语言；5 详细设计1）程序结构如图2：图2 程序结构图2）●主菜单模块：void main()//主函数{Fq *head=new Fq;head->next=new Fq;head->next->size=MAXSIZE;head->next->o=0;head->next->next=NULL;int choice=0;do{cout<<"请选择你要进行的操作："<<endl;cout<<"1、创建新作业 2、查看空闲分区链 3、回收内存空间 0、退出"<<endl;cin>>choice;switch(choice){case 1: create(head);break;case 2: cha(head);break;case 3: hui(head);break;case 0: break;default: cout<<"输入错误！"<<endl;}}while(choice!=0);}●创建新作业模块：void create(Fq *head)//创建作业子函数{Fq *p=head->next;p->before=head;int no=0,b=0;cout<<"请输入要创建的作业的编号：";cin>>no;cout<<"请输入作业的需求空间大小：";cin>>b;alloc(b,no,p);//此处调用功能函数alloc()}●查看空闲分区链模块：void cha(Fq *head)//查看内存中的空闲分区链的子函数{Fq *p=head->next;p->before=head;int i=0;cout<<"空闲分区链的情况为："<<endl;while(p!=NULL){if(p->o==0){cout<<"空闲分区"<<++i<<" "<<p->size<<"K"<<endl;}p=p->next;}}●回收内存空间模块：void hui(Fq *head)//回收内存的子函数{Fq *p=head->next;p->before=head;int no=0;cout<<"请输入要回收内存的作业号：";cin>>no;while(p!=NULL){if(p->no==no){free(p);//此处调用功能函数free()cout<<"作业"<<no<<"的内存已回收！"<<endl;return ;}else p=p->next;}}●内存分配功能函数模块：void alloc(int b,int no,Fq *p)//对作业no进行内存分配的子函数{while(p!=NULL){if(p->o==1) {p=p->next;}else{if(p->size>b){if(p->size-b<=min_size){p->o=1;p->no=no;}else{Fq *q=new Fq;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 ;}else p=p->next;}}cout<<"内存分配失败！"<<endl;}●内存回收功能函数模块：void free(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;if(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;}else c->o=0;}6 调试分析1）内存分配功能函数模块：刚开始对作业分配内存时，只是将空闲分区的大小以及前后向指针进行修改，而没有对分配给作业的内存进行设置；这样，尽管内存的空闲分区大小已经变小，但是，以后却无法对已分配的内存空间以及作业进行修改；于是，我经过思考后，决定将分配给作业的内存空间也设置为一个分区，只不过不是空闲的分区，通过状态标识符o来与空闲分区进行区别。

实验五动态分区管理模拟实验报告关键问题：写一动态分区管理程序，使其内存分配采用最优适应分配算法。

设计思路：在空闲分区链中找最适合的空闲块，使内存碎片尽量的减少！根据最佳适应算法原理，在内存分配函数ffallocation()中，增加记录适合空白块的标记sp，然后拿当前空白块fp减去后jl的后的大小和它后面的另一空白块sp减去jl的大小相比较。

如果前者大于后者，且后者的空白区大于jl的大小，则当前空白块为sp,否则继续往后比较，直到空闲分区链末尾！则当前空白块为最适合的空白块！然后就把当前空白块分配给作业。

其他部分的代码与实例相同！实现的关键代码：//------------------------------------------------------------------- //有两个链:空白块链及作业链.空白块链描述空白块,链首指针freep,初始为一大块空白块.//作业链按从高址到低址的顺序链接,链首指针jobp//为作业jn分配jl大小内存，起始地址为javoid ffallocation(int jl,char jn[10],int* ja){mat* jp=NULL;//作业链当前节点mat* jp2=NULL;//新的作业节点mat* jp1=NULL;//freearea* fp=NULL;//当前空白块//修改部分 freearea* sp;//记录适合的空白块int i;*ja=-1;if (totalfree<jl) //剩余空间大小不能满足作业要求return;*ja=0;fp=freep;//取空白块链首块，将顺着链寻找第一块满足作业要求的块。

sp=freep;while (fp!=NULL){if (fp->freesize<jl){fp=fp->next;//当前空白块大小不满足要求sp=sp->next;}else //将当前空白块分配给作业{/*当当前空白块fp与它的下一块空白块sp相比较，如果它减去jl后大于下一空白块sp减去jl,且下一空白块sp大于等于jl,则当前空白块为sp;否则sp继续往后查找，直到空闲块查找完毕，然后当前空闲块为所要查找的适合空闲块！*/while(sp!=NULL){if((fp->freesize-jl>sp->freesize-jl)&(sp->freesize>=jl)){fp=sp;}else{sp=sp->next;}}// jobnumber++;totalfree=totalfree-jl;jp2=new mat;//申请一块作业节点空间//在节点上登记为该作业分配的内存空间// for (i=0;i<10;i++) (jp2->jobname)[i]=' ';i=-1;while(jn[++i])(jp2->jobname)[i]=jn[i];(jp2->jobname)[i]='\0';jp2->joblength=jl;jp2->jobaddress=fp->freeaddress;//登记该作业的起始地址*ja=jp2->jobaddress;//将节点jp2插入作业链jobp,按高址到低址的顺序。