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

实验报告实验二动态分区分配与回收算法一、实验目的了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。二、实验原理算法思想：1．分区的个数和大小不是固定不变的，而是可变的，随装入的作业动态划分，且不会产生内部碎片。2.外部碎片：若存储块长度为N，在该系统所采用的调度算法下较长时间内无法选出一道长度不超过该块的进程，则称该块为外部碎片。3.首次适应算法（FF）:FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。4.最佳适应算法（BF）：每次为作业分配内存时，BF总是把能满足要求、又是最小的空闲分区分配给作业，避免大材小用。为了加速寻找，该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。分区分配中的内存回收有四种情况：(1)回收区与插入点的前一个空闲分区相邻接。(2)回收区与插入点的后一空闲分区相邻接。(3)回收区同时与插入点的前、后两个空闲分区邻接。(4)回收分区既不与前一个分区邻接，也不与后一个分区邻接。另外，最佳适应算法不需要考虑多个进程，而首次适应算法需要考虑多道程序的大小，所以前两个程序只需要输入一个进程的信息，后者因为考虑多个程序的原因，所以需要输入两个进程的信息。三、实验步骤、数据记录及处理1、算法流程抽象数据类型的定义：空闲分区结构体类型和结构体链表typedefstructfreespace{intnum;//分区号intsize;//分区大小intaddress;//分区首地址statusstate;//分区状态，FREE和BUSY};typedefstructnode{freespacedata;node*head;node*next;}*Linklist;主程序的流程以及各程序模块之间的层次(调用)关系：主函数中先调用初始化函数，再调用菜单函数引导用户选择操作和相应的算法，用switch多选择结构来判断调用firstAlloc()，bestAlloc()，display()还是recycle()。程序流程图：2、运行结果分析：首次适应算法：分配结束后的空闲分区大小和起始地址与结果相同。大小起始地址30K150K20K280K112K400K最佳适应算法：分配结束后的空闲分区大小和起始地址与结果相同。大小起始地址30K400K42K470K90K210K四、总结与体会附录：源代码#includeiostream#includestdlib.husingnamespacestd;#defineMAXSIZE512enumstatus{FREE,BUSY};//枚举类型typedefstructfreespace{intnum;//分区号intsize;//分区大小intaddress;//分区首地址statusstate;//分区状态，FREE和BUSY};typedefstructnode{freespacedata;node*head;node*next;}*Linklist;Linklistfirst,last;voidinit(){first=newnode;last=newnode;first-head=NULL;first-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空闲区起始地址：p-data.address终止地址：p-data.address+p-data.size分区大小：p-data.sizeKB状态:空闲endl;}else{coutp-data.num;cout起始地址：p-data.address终止地址：p-data.address+p-data.size分区大小：p-data.sizeKB状态:;if(p-data.state==FREE)cout空闲endl;elseif(p-data.state==BUSY)cout占用endl;}p=p-next;}cout**********************************************endlendl;}intfirstAlloc()//首次分配{intnum,size;cout请输入作业号和分配的主存大小KB：endl;;cinnumsize;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-data.state==FREE&&p-data.sizesize)//有大小比他大的空闲块{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;}display();return0;}intbestAlloc()//最佳分配{intnum,size;cout请输入作业号和分配的主存大小KB：endl;;cinnumsize;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-data.sizesize||p-data.size==size)&&p-data.state==FREE){if(p-data.size-sizemin_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-next=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;cinnum;node*p=first;while(p){if(p-data.num==num){p-data.state=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;p-next=p-next-next;}break;}p=p-next;}display();return1;}voidmenu(){cout********************内存分配系统********************endl;cout1.首次适应算法分配内存endl;cout2.最佳适应算法分配内存endl;cout3.查看主存分配情况endl;cout4.回收主存endl;cout请选择：endl;}voidmain(){init();intchoose;menu();while(1){//menu();cinchoose;switch(choose){case1:firstAlloc();break;case2:bestAlloc();break;case3:display();break;case4:recycle();break;default:cout输入错误！endl;break;}}}