实验四动态分区分配算法实验报告及程序

1、精选优质文档-倾情为你奉上实验报告四 动态分区分配算法班级 学号 姓名 一、 实验目的动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了四种分配算法，分别是1.首次适应算法，2.循环首次适应算法，3.最坏适应算法4.最佳适应算法。二、 实验环境普通的计算机一台，编译环境Microsoft Visual C+ 6.0三、 算法思想1 数据结构（1） 分区开始地址startaddress（2） 分区大小size（3） 分区状态state2 功能介绍（1） 首次适应算法在首次适应算法中，是从已

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

3、求的分区，则此次内存分配失败。（3） 最坏适应算法最坏适应分配算法是每次为作业分配内存时，扫描整个数组，总是把能满足条件的，又是最大的空闲分区分配给作业。（4） 最佳适应算法最坏适应分配算法是每次为作业分配内存时，扫描整个数组，总是把能满足条件的，又是最小的空闲分区分配给作业。四、 源程序专心-专注-专业#include <stdio.h>#define L 10typedef struct LNode int startaddress; int size; int state; LNode;LNode PL=0,128,0,200,256,0,500,512,0,1500,160

4、0,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 %4dn",Pi.startaddress,Pi.size,Pi.state);void First() int i,l=0,m; printf("n输入请求分配分区的大小："); scanf("%d",&m); for(i=0;i<N;i+) if(Pi.size<m) con

5、tinue; else if(Pi.size=m) Pi.state=1; l=1; break; else PN.startaddress=Pi.startaddress+m; PN.size=Pi.size-m; Pi.size=m;Pi.state=1; l=1; N+; break; if(l=1|i<N) printf("地址成功分配nn"); printf("地址分配成功后的状态：n"); print(); else printf("没有可以分配的地址空间n"); void CirFirst() int l=0,m,

6、t=0; printf("n输入请求分配分区的大小："); scanf("%d",&m); while(f<N) if(Pf.size<m) f=f+1; if(f%N=0) f=0;t=1; continue; if(Pf.size=m && Pf.state!=1) Pf.state=1; l=1;f+; break; if(Pf.size>m && Pf.state!=1) PN.startaddress=Pf.startaddress+m; PN.size=Pf.size-m; Pf.si

7、ze=m; Pf.state=1; l=1; N+; f+; break; if(l=1) printf("地址成功分配nn"); printf("地址分配成功后的状态：n"); print(); else printf("没有可以分配的地址空间n"); void Worst() int i,t=0,l=0,m; int aL; printf("n输入请求分配分区的大小："); scanf("%d",&m); for(i=0;i<N;i+) ai=0; if(Pi.size<

8、m) continue; else if(Pi.size=m) Pi.state=1; l=1; break; elseai=Pi.size-m; if(l=0) for(i=0;i<N;i+) if(ai!=0) t=i; for(i=0;i<N;i+) if(ai!=0 && ai>at) t=i; PN.startaddress=Pt.startaddress+m; PN.size=Pt.size-m; Pt.size=m;Pt.state=1; l=1; N+; if(l=1|i<N) printf("地址成功分配nn");

9、printf("地址分配成功后的状态：n"); print(); else printf("没有可以分配的地址空间n"); void Best() int i,t=0,l=0,m; int aL; printf("n输入请求分配分区的大小："); scanf("%d",&m); for(i=0;i<N;i+) ai=0; if(Pi.size<m) continue; else if(Pi.size=m) Pi.state=1; l=1; break; elseai=Pi.size-m; if(

10、l=0) for(i=0;i<N;i+) if(ai!=0) t=i; for(i=0;i<N;i+) if(ai!=0 && ai<at) t=i; PN.startaddress=Pt.startaddress+m; PN.size=Pt.size-m; Pt.size=m;Pt.state=1; l=1; N+; if(l=1|i<N) printf("地址成功分配nn"); printf("地址分配成功后的状态：n"); print(); else printf("没有可以分配的地址空间n&quo

11、t;); 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初始状态为：

12、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("选择错误，请重新选择。n"); 五、 运行

13、结果运行效果如下所示，首先列出主菜单，如图1所示，初始状态为已定义好的数组，首先采用首次适应算法，输入的分区大小为500，从图2可以看出，第一个满足条件的起始地址为500，分区大小为512，分配后，起始地址为500的状态设为1，将其余的分区令开辟空间存储。 (1) (2)然后采用算法2即循环首次适应算法，在第一次的分配作业大小为1500，则系统就会将地址为1500的分区进行分配，剩余分区令开辟空间，如图3所示；在第二次的分配作业大小为200，依照算法可得，地址为200的分区复合要求，则将其分配给作业，如图4所示。 (3) (4) (5) (6)在算法3中，采用的是最坏适应算法，设分配作业大小为

14、20，由初始状态可知，分区最大且没有被分配的起始地址为5000，大小为150，分配后的状态如图5所示。在算法4中，采用的是最优适应算法，设分配大小为10，由初始状态可知，分区最小且没有被分配的起始地址为1000，大小为12，分配后的状态如图6所示。最后选择5，则结束程序的运行，效果如图7所示。(7) 六、 实验总结在一开始老师布置这次的实验题目时，自己根本不知道要干什么，因为在上课时对动态分区分配这节内容不是太了解，所以在上机时不知道如何下手，后来，将本章内容反复的看了几遍之后，终于有了自己的思路。在程序的编写过程中，我并没有按照书上所说的定义了双向链表来实现各种算法的执行，我只简单的运用了结构体数组，通过这种方法比较容易理解与编写，在这几个算法中，只有循环首次适应算法