操作系统实验报告存储器管理学院电信学院专业计算机科学与技术班级 14级计科一班实验题目动态分区分配实验组别第三组指导老师曹华一、实验目的了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。

二、实验内容用Ｃ语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。

其中，空闲分区通过分区链来管理，在进行内存分配时，系统优先使用空闲区低端的空间。

请分别用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。

三、实验主要仪器设备软件环境：ＶＣ＋＋６编程环境四、实验原理及设计方案1.实验原理：可变分区调度算法有：最先适应分配算法，循环首次适应算法，最佳适应算法，最坏适应算法。

首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。

只要找到第一个足以满足要求的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改区分大小和分区始址。

用户提出内存空间的申请：系统根据申请者的要求，按照一定的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者；当程序执行完毕或主动归还内存资源时，系统要收回它所占用的内存空间或它归还的部分内存空间。

最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。

然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。

内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空，并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。

每当一个进程被创建时，内存分配程序首先要查找空闲内存分区链，从中寻找一个合适的空闲块进行划分，并修改空闲内存分区链，系统根据回收区的首址，从空闲区链中找到相应的插入点，此时出现如下四种情况：(１)回收区与插入点的前一个空闲区Ｆ１相邻接，此时可将回收区直接与Ｆ１合并，并修改Ｆ１的大小；(２)回收区与插入点的后一个空闲分区Ｆ２相邻接，此时可将回收区直接与Ｆ２合并，并用回收区的首址作为新空闲区的首址，大小为二者之和；(３)回收区同时与插入点的前后两个空闲分区邻接，此时需将三者合并；(４)回收区不与任何一个空闲区邻接，此时应建一新的表项2.主要数据结构的说明定义一个空闲区说明表结构struct freearea {int ID; //分区号long size; //分区大小long address; //分区地址int state; //状态}ElemType;线性表的双向链表存储结构Struct DuLNode//double linked list{ElemType data;struct DuLNode *prior; //前趋指针struct DuLNode *next; //后继指针｝DuLNode,*DuLinkList;算法；首次适应算法：是在分配内存时，从链首开始顺序查找，直到找到一个大小能够满足要求的分区，即进行分配。

最佳适应算法：是在分配内存时，从链首开始顺序查表，查找到链尾，并记录一个大小不小于要求的分区的最小分区，在查找完毕后进行分配。

3.程序流程图首次适应算法最佳适应算法4.实验程序首次适应算法#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #define N 10000 int n1;//空闲分区的个数int n2;//作业区的个数struct kongxian{int start; //起址int end; //结束int length; //长度}kongxian[N];struct zuoye{int start; //起址int end; //结束int length; //长度}zuoye[N];int cmp1(const void *a,const void *b){return (*(struct kongxian *)a).start-(*(struct kongxian *)b).start;}int cmp2(const void *a,const void *b){return (*(struct zuoye *)a).start-(*(struct zuoye *)b).start;}void init(){n1=1; //初始时只有一个空闲区n2=0; //初始没有作业kongxian[0].start=0;kongxian[0].end=1023;kongxian[0].length=1024;}void print1() //打印空闲分区{int i;for(i=0;i<n1;i++)printf("空闲分区ID:%d 起止:%d 结束:%d 长度:%d\n",i,kongxian[i].start,kongxian[i].end,k ongxian[i].length);}void print2() //打印作业分区{int i;for(i=0;i<n2;i++)printf("作业分区ID：%d 起止:%d 结束:%d 长度:%d\n",i,zuoye[i].start,zuoye[i].end,zuoye[i] .length);}int main(){int i,j,t,len,flag,id;int front,middle, behind;int t1,t2;init();print1();printf("输入1装入新作业，输入0回收作业，输入-1结束\n");while(scanf("%d",&t)!=EOF){if(t==1) //装入新作业{printf("请输入作业的占用空间的长度");scanf("%d",&len);flag=0;for(i=0;i<n1;i++){if(kongxian[i].length>=len) //首次适应算法{flag=1;break;}}if(!flag){printf("内存分配失败\n");}else{zuoye[n2].start=kongxian[i].start;zuoye[n2].end=zuoye[n2].start+len;zuoye[n2].length=len;n2++; //作业数加1if(kongxian[i].length==len) //该分区全部用于分配，删除该空闲分区{for(j=i;j<n1-1;j++){kongxian[j].start=kongxian[j+1].start; kongxian[j].end=kongxian[j+1].end; kongxian[j].length=kongxian[j+1].length;}n1--;}else //该空闲分区部分用于分配，剩余的留在空闲分区中{kongxian[i].start+=len;kongxian[i].length-=len;}}}else if(t==0){printf("输入要回收的作业ID ");scanf("%d",&id);front=middle=behind=0;for(i=0;i<n1;i++){if(kongxian[i].start>zuoye[id].end)break;if(kongxian[i].end==zuoye[id].start) //待回收的作业上面有空闲分区{front=1;t1=i;}if(kongxian[i].start>zuoye[id].end){behind=1;t2=i;}}if(!front&&!behind){kongxian[n1].start=zuoye[id].start;kongxian[n1].end=zuoye[id].end;kongxian[n1].length=zuoye[id].length;n1++;qsort(kongxian,n1,sizeof(struct kongxian),cmp1);for(j=id;j<n2-1;j++){zuoye[j].start=kongxian[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}if(front&&behind)middle=1;if(front&&!behind){kongxian[t1].end+=zuoye[id].length;kongxian[t1].length+=zuoye[id].length;for(j=id;j<n2-1;j++){zuoye[j].start=zuoye[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}if(middle){kongxian[t1].end=kongxian[t2].end;kongxian[t1].length+=(zuoye[id].length+ko ngxian[t2].length);for(j=t2;j<n1-1;j++){kongxian[j].start=kongxian[j+1].start;kongxian[j].end=kongxian[j+1].end;kongxian[j].length=kongxian[j+1].length;}n1--;for(j=id;j<n2-1;j++){zuoye[j].start=kongxian[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}if(front&&!behind){kongxian[t1].end-=zuoye[id].length;kongxian[t1].length+=zuoye[id].length;for(j=id;j<n2-1;j++){zuoye[j].start=zuoye[j+1].start; zuoye[j].end=zuoye[j+1].end; zuoye[j].length=zuoye[j+1].length;}n2--;}}else{printf("操作结束\n");break;}print1();print2();}return 0;}最佳适应算法#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>struct kongkuai{ int startaddr;int size;int flag;}kongxq[6]={{10,30,1},{100,60,1},{200,80,1},{3 00,60,1},{400,180,1},{700,200,1}};int allocate(int jobsize){int i;int t=0;for(i=0;i<6;i++)if(kongxq[i].flag==1&&kongxq[i].size>job size){kongxq[i].startaddr+=jobsize;kongxq[i].size-=jobsize;t=1;returnkongxq[i].startaddr-jobsize;}elseif(kongxq[i].flag==1&&kongxq[i].size==jo bsize){kongxq[i].flag=0;t=1;returnkongxq[i].startaddr;}if(t==0)return 0;return 1;}void circle(){int i,j;struct kongkuai temp;for(i=0;i<6;i++)for(j=0;j<6;j++)if(kongxq[j].size>kongxq[j+1].size){temp.startaddr=kongxq[j].startaddr;temp.size=kongxq[j].size;temp.flag=kongxq[j].flag;kongxq[j].startaddr=kongxq[j+1].startadd r;kongxq[j].size=kongxq[j+1].size;kongxq[j].flag=kongxq[j+1].flag;kongxq[j+1].startaddr=temp.startaddr;kongxq[j+1].size=temp.size;kongxq[j+1].flag=temp.flag;}for(i=0;i<6;i++)for(j=0;j<6;j++)if(kongxq[j].flag==0&&kongxq[j+1].flag== 1){temp.startaddr=kongxq[j].startaddr;temp.size=kongxq[j].size;temp.flag=kongxq[j].flag;kongxq[j].startaddr=kongxq[j+1].startadd r;kongxq[j].size=kongxq[j+1].size;kongxq[j].flag=kongxq[j+1].flag;kongxq[j+1].startaddr=temp.startaddr;kongxq[j+1].size=temp.size;kongxq[j+1].flag=temp.flag;}}void callback(){int s,len,t1=0,t2=0,t3=0,i,j;printf("请输入回收区的起始地址:\n");scanf("%d",&s);printf("请输入回收区的大小:\n");scanf("%d",&len);for(i=0;i<6;i++){if((kongxq[i].startaddr==s+len)&&(kongxq[i].fl ag==1)){len+=kongxq[i].size;t1=1;for(j=0;j<6;j++)if((kongxq[j].startaddr+kongxq[j].size==s) &&(kongxq[j].flag==1)){kongxq[i].flag=0;kongxq[j].size=kongxq[j+1].size+len;t2=1;break;}if(t2==0){kongxq[i].startaddr=s;kongxq[i].size=len;break;}}}if(t1==0){for(i=0;i<6;i++){if((kongxq[i].startaddr+kongxq[i].size==s) &&(kongxq[i].flag==1)){kongxq[i].size+=len;t3=1;break;}if(t3==0)for(j=0;j<6;j++)if(kongxq[j].flag==0){kongxq[j].startaddr=s;kongxq[j].size=len;kongxq[j].flag=1;break;}}}}void print(){int i;printf("\n 起始地址| 大小|是否空闲\n\n");for(i=0;i<6;i++){printf(" %3d | %3d | %3d \n",kongxq[i].startaddr,kongxq[i].size,kongxq [i].flag);}printf("\n");}main(){int jobsize,start;char end;printf("\n是否有作业请求空闲区?Y or N:");while(end=getchar()=='y'){printf("初始空闲区状态:\n");circle();print();printf("请输入请求空闲区的作业大小:");scanf("%d",&jobsize);start=allocate(jobsize);circle();printf("分配后空闲区状态:\n");print();if(!start)printf("没有适合的空闲区大小!\n");elseprintf("作业起始地址: %d\n",start);printf("作业大小: %d\n",jobsize);callback();print();printf("是否有其他作业的请求? Y or N:");end=getchar();}return 0;}五、算法及运行结果及分析1.运行结果：首次适应算法最佳适应算法2．实验总结：通过运行内存分配和回收模拟的程序对内存管理理解加深了，在动态分区管理方式中，能灵活地根据作业需要，动态地为之分配内存空间，其中关键是分区分配算法，一旦内存块使用完毕，可以回收给系统以分配给其他的作业使用。