动态分区分配与回收算法试验报告

1、实验报告实验二动态分区分配与回收算法一、实验目的了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。二、实验原理算法思想：1 .分区的个数和大小不是固定不变的，而是可变的，随装入的作业动态划分，且不会产生内部碎片。2 .外部碎片：若存储块长度为N,在该系统所采用的调度算法下较长时间内无法选出一道长度不超过该块的进程，则称该块为外部碎片。3 .首次适应算法（FF）:FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分

2、的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。4 .最佳适应算法（BF）:每次为作业分配内存时，BF总是把能满足要求、又是最小的空闲分区分配给作业，避免大材小用。为了加速寻找，该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区分区分配中的内存回收有四种情况：(1)回收区与插入点的前一个空闲分区相邻接。(2)回收区与插入点的后一空闲分区相邻接。(3)回收区同时与插入点的前、后两个空闲分区邻接。(4)回收分区既不与前一个分区邻接，也不与后一个分区邻接。另外，最佳适应算法不需要考虑多

3、个进程，而首次适应算法需要考虑多道程序的大小，所以前两个程序只需要输入一个进程的信息，后者因为考虑多个程序的原因，所以需要输入两个进程的信息。三、实验步骤、数据记录及处理1、算法流程抽象数据类型的定义：空闲分区结构体类型和结构体链表typedefstructfreespace(intnum;/分区号intsize;/分区大小intaddress;/分区首地址statusstate;/分区状态,FREE?口BUSY;typedefstructnode(freespacedata;node*head;node*next;*Linklist;主程序的流程以及各程序模块之间的层次(调用)关系：主函数中

4、先调用初始化函数，再调用菜单函数引导用户选择操作和相应的算法，用switch多选择结构来判断调用firstAlloc(),bestAlloc(),display()还是recycle()。程序流程图：2、运行结果分析：首次适应算法：分配结束后的空闲分区大小和起始地址与结果相同大小起始地址30K150K20K280K112K400K4请输入你要回收内存的作业号,*主内存分配，青况*率*分区号;4起始地址工。曾正姬址150分区大小1150KB状态:占用分区号工空闲区起始地址：150终止地由1X0分区关小130KB默态:空闲分区号：6起始地址：180终止地距220分区大小：40KB状态:占用分区号:

5、7起赌册止工220终止城苑280分区大小60KB状态:占同分区号.空闲区起殆地址：及0终止地址：300分区大小：20KB状态:空闲分区号：2起始地址：300终止地址7400分区大小：100KB状态；占用各区号工空闲区起始地址r400终止地址1512分区大小：112KB状态:空闲*最佳适应算法：分配结束后的空闲分区大小和起始地址与结果相同大小起始地址30K400K42K470K90K210K2 .里佳适隹算法-互配内存3 .强育王正芬配宿况4 .回收主存请选择：2请输入作业号和分配的主存大小KB：J_2OJ2I4情输入你要回收内存的作业号;*主内存分'酉己情彳兄*分区号14起始地址，0我

6、正+岫b15Q分区大小：150KB状态:占用分区号.7起始地址:150终止地址；210分区大小；60KB状态:占用区号工空闲区段许正tk210终止电灯300为区大小：90KB技态:空闱分区号：2起始地址：300终止地距400分区大小：100KB状态;占用_阶区号:空闲区藏&土砒L400终止地由430分区大小30KB状卷:空闲分区号工6起始地址二430终止地址：470分区大小：40KB状态:占用务区号.空闲区起始地址；470终止地址512分区大小.42KB状态:空闲西安工业大学实验报告四、总结与体会附录：源代码#include<iostream>#include<std

7、lib.h>usingnamespacestd;#defineMAXSIZE512enumstatusFREE,BUSY;/枚举类型typedefstructfreespaceintnum;/分区号intsize;/分区大小intaddress;/分区首地址statusstate;/分区状态，FRE臣口BUSY;typedefstructnodefreespacedata;node*head;node*next;*Linklist;Linklistfirst,last;voidinit()first=newnode;last=newnode;first->head=NULL;fir

8、st->next=last;last->head=first;last->next=NULL;last->data.address=0;last->data.size=MAXSIZE;last->data.num=0;last->data.state=FREE;voiddisplay()cout<<"*主内存分配情况*”<<endl;node*p=first->next;while(p)(cout<<"分区号："if(p->data.num=0)(cout<<&q

9、uot;空闲区"<<""<<"起始地址："<<p->data.address<<""<<"终止地址："<<p->data.address+p->data.size<<""<<"分区大小："<<p->data.size<<"KB"<<""<<"状态：空闲

10、"<<endl;)else(cout<<p->data.num;cout<<""<<"起始地址："<<p->data.address<<""<<"终止地址:"<<p->data.address+p->data.size<<"""分区大小："<<p->data.size<<"KB"<

11、<""<<"状态："；if(p->data.state=FREE)cout<<"空闲"<<endl;elseif(p->data.state=BUSY)cout<<"占用"<<endl;p=p->next;)cout<<*<<endl<<endl;intfirstAlloc()/首次分配(intnum,size;cout<<"请输入作业号和分配的主存大小KB："&l

12、t;<endl;cin>>num>>size;Linklistlist=newnode;list->data.num=num;list->data.size=size;list->data.state=BUSY;node*p=first->next;while(p)(if(p->data.state=FREE&&p->data.size=size)/有大小刚好合适的空闲块(p->data.state=BUSY;p->data.num=num;display();return1;if(p->dat

13、a.state=FREE&&p->data.size>size)/有大小比他大的空闲块(list->head=p->head;list->next=p;list->data.address=p->data.address;p->head->next=list;p->head=list;p->data.address=list->data.address+list->data.size;p->data.size-=size;display();return1;p=p->next;displa

14、y();return0;intbestAlloc()/最佳分配(intnum,size;cout<<"请输入作业号和分配的主存大小KB："<<endl;cin>>num>>size;intmin_space=MAXSIZE;Linklistlist=newnode;list->data.num=num;list->data.size=size;list->data.state=BUSY;node*p=first->next;node*q=NULL;while(p)/找到最佳位置(if(p->dat

15、a.size>size|p->data.size=size)&&p->data.state=FREE)(if(p->data.size-size<min_space)(q=p;min_space=p->data.size-size;)p=p->next;)if(q=NULL)(return0;)else(if(min_space=0)(q->data.num=num;q->data.state=BUSY;display();return1;)else(list->head=q->head;list->nex

16、t=q;list->data.address=q->data.address;q->head->next=list;q->head=list;q->data.address+=size;q->data.size-=size;display();return1;)intrecycle。/碎片整理(intnum;cout<<"请输入你要回收内存的作业号："<<endl;cin>>num;node*p=first;while(p)(if(p->data.num=num)(p->data.st

17、ate=FREE;p->data.num=0;if(p->head->data.state=FREE)/与前一块空闲区相邻，则合并(p->head->data.size+=p->data.size;p->head->next=p->next;p->next->head=p->head;if(p->next->data.state=FREE)/与后一块空闲区相邻，则合并(p->data.size+=p->next->data.size;p->next->next->head=p

18、;p->next=p->next->next;break;p=p->next;display();return1;voidmenu()cout<<”*内存分配系统*”<<endl;cout<<"1.首次适应算法分配内存"<<endl;cout<<"2.最佳适应算法分配内存"<<endl;cout<<"3.查看主存分配情况"<<endl;cout<<"4.回收主存"<<endl;cout<<"请选择："<<endl;voi