(内存分配与回收模拟).doc

操作系统课程实验报告姓名学号系计算机任课教师指导教师评阅教师实验地点综合楼B104 励耘楼A206 综合楼B102 丽泽楼C304-1 (请勾选实际实验地点)实验时间10.20实验课表现出勤和个人表现Q1(15+15（组长评分）=30分)得分：28实验总分(Q1+Q2+Q3+Q4)实验完成情况Q2(45分(组长与教师评分的加权平均)得分：40实验编号与实验名称： 内存分配与回收模拟实验目的：通过使用位图跟踪内存使用情况，模拟和评价不同的内存分配算法；熟悉内存分配和回收。实验内容及要求（详见实验讲义与实验指导书）：.实验要求： 1）要求用你熟悉的程序设计语言编写和调试一个内存分配和回收模拟程序；要求在主函数中测试。2）实验报告中必须包括：设计思想、数据定义（包括详细说明）、处理流程（详细算法描述和算法流程图）、源代码、运行结果、体会等部分。3）必须模拟该4种内存分配算法：first fit，next fit，best fit和worst fit中的至少2种。4） 需显示出每次分配和回收后的空闲分区链的情况来以及内存占用情况图，并统计各种算法产生的碎片空闲区（小于3个单元（unit）的空闲区）数。5）计算2个性能参数：碎片数、平均搜索空闲区次数实验内容 假设内存容量为256KB，并且划分成2KB大小的块，也即每个内存单元为2KB。一个进程所需要的内存为3到10个单元。同时假设一个作业在运行过程中所需内存的大小不变。 模拟包括3部分：1） 实现特定的内存分配算法2） 实现内存回收模拟3） 每种内存分配策略对应的碎片数统计实验用到的软件（：）CFee实验内容及关键步骤（代码）Q3（15分）得分：实验六：答：1各算法描述首先是首次适配算法：从第一个空闲区开始寻找，只要找到大于或者等于作业要求的空间即可，然后修改链表地址，插入链表。数据处理：选择插入空间地址，修改链表地址。假设内存容量为256KB，并且划分成2KB大小的块，也即每个内存单元为2KB。一个进程所需要的内存为3到10个单元。碎片空闲区（小于3个单元（unit）的空闲区）数。其次是最佳适配算法：寻找整个空间最小能装下作业要求的空间大小，通过比较然后将作业装入数组中。数据处理：最佳适配算法最容易产生更多的碎片，找到插入地址，修改数组，完成适配。假定最大空闲分区20个，内存中同时最多可容纳的作业数20个空闲区与作业关系空闲区地址2流程图：首次适配：空闲区地址-空闲区与作业关系-该区等于作业要求该区小于作业要求该区大于作业要求取出空闲区一块空间截取长度并修改链表无法分配返回作业分配主存的地址空闲区与作业关系空闲区地址最佳适配：空闲区地址-空闲区与作业关系-。该区等于作业要求该区大于作业要求该区小于作业要求数组是否为一个是无法分配否是否为最小是返回作业分配主存的地址3源代码首次适配和最佳适配算法实现如下：/*动态分区的分配与回收演示程序*/#include stdio.h#define N 5int start;/存放首址/*定义一个空闲区说明表结构，并初始化变量*/struct freearea int startaddress;/*空闲区始址*/ int size;/*空闲区大小*/ int state;/*空闲区状态:0为空表目，1为可用空闲块*/freeblockN=20,20,1,80,50,1,150,30,1,300,30,0,600,10,1;/*定义为作业分配主存空间的函数alloc(),给首次适应算法调用*/int alloc(int applyarea)/*applyarea为作业申请量*/ int i,tag=0;/*tag为检查是否有满足作业需要的空闲区的标志*/ for(i=0;iapplyarea) freeblocki.startaddress=freeblocki.startaddress+applyarea; freeblocki.size=freeblocki.size-applyarea; tag=1;/*有满足条件的空闲区时，tag置1*/ return freeblocki.startaddress-applyarea;elseif(freeblocki.state=1&freeblocki.size=applyarea) freeblocki.state=0; tag=1;/*有满足条件的空闲区时，tag置1*/ return freeblocki.startaddress;/*返回为作业分配的主存地址*/if(tag=0)return -1;/*没有满足条件的空闲区，分配不成功，返回-1*/*定义为作业分配主存空间的函数alloc2(),给循环首次适应算法调用*/int alloc2(int applyarea,int s)/*applyarea为作业申请量*/ int i,tag=0;/*tag为检查是否有满足作业需要的空闲区的标志*/ for(i=s;iapplyarea) freeblocki.startaddress=freeblocki.startaddress+applyarea; freeblocki.size=freeblocki.size-applyarea; tag=1;/*有满足条件的空闲区时，tag置1*/ start=freeblocki.startaddress-applyarea; return i;else if(freeblocki.state=1&freeblocki.size=applyarea) freeblocki.state=0; tag=1;/*有满足条件的空闲区时，tag置1*/ start=freeblocki.startaddress;/*返回为作业分配的主存地址*/ return i; if(tag=0)return -1;/*没有满足条件的空闲区，分配不成功，返回-1*/*定义为作业分配主存空间的函数alloc3(),给最佳适应算法调用*/int alloc3(int applyarea)/*applyarea为作业申请量*/ int i,k,h,flag,tag=0,j=0;/*tag为检查是否有满足作业需要的空闲区的标志*/ int aN; struct freearea min; struct freearea mid; for(i=0;iN;i+)/*检查空闲区说明表是否有满足作业要求的空闲区*/ if(freeblocki.state=1&freeblocki.size=applyarea)/大小刚好相等 freeblocki.state=0; tag=1;/*有满足条件的空闲区时，tag置1*/ return freeblocki.startaddress;/*返回为作业分配的主存地址*/ for(i=0;iapplyarea)aj+=i; if(j1) h=a0; min=freeblockh; /min.startaddress=freeblockh.startaddress; /min.size=freeblockh.size; /min.state=freeblockh.state; for(k=1;kj;k+) h=ak; if(freeblockh.sizemin.size) mid.size=freeblockh.size; mid.state=freeblockh.state; mid.startaddress=freeblockh.startaddress; freeblockh.size=min.size; freeblockh.state=min.state; freeblockh.startaddress=min.startaddress; min.size=mid.size; min.state=mid.state; min.startaddress=mid.startaddress; min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea; tag=1;/*有满足条件的空闲区时，tag置1*/ return min.startaddress-applyarea; else if(j=1) h=a0; min=freeblockh; min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea; tag=1;/*有满足条件的空闲区时，tag置1*/ return min.startaddress-applyarea; if(tag=0)return -1;/*没有满足条件的空闲区，分配不成功，返回-1*/*定义主存回收函数：setfree()tag1代表释放区的高地址是否邻接一个空闲区，tag2代表释放区的高低地址是否都邻接一个空闲区，tag3代表释放区的低地址是否邻接一个空闲区*/void setfree() int s,l,tag1=0,tag2=0,tag3=0,i,j; printf(input free area startaddress:n); scanf(%d,&s);/*输入释放区的开始地址*/ printf(input free area size:n); scanf(%d,&l);/*输入释放区的大小*/ for(i=0;iN;i+) if(freeblocki.startaddress=s+l&freeblocki.state=1) l=l+freeblocki.size; tag1=1;/*有与释放区高地址邻接的空闲区，tag1置1*/ for(j=0;jN;j+) if(freeblockj.startaddress+freeblockj.size=s&freeblockj.state=1) freeblocki.state=0; freeblockj.size=freeblockj.size+l; tag2=1;/*有与释放区上下都邻接的空闲区，tag2置1*/ break;if(tag2=0)/*无与释放区高低地址邻接的空闲区*/freeblocki.startaddress=s;freeblocki.size=l;break; if(tag1=0)/*无与释放区高地址邻接的空闲区，并检查是否低地址有邻接空闲区*/ for(i=0;iN;i+)if(freeblocki.startaddress+freeblocki.size=s&freeblocki.state=1)freeblocki.size=freeblocki.size+l;tag3=1;/*有与释放区低地址邻接的空闲区*/break; if(tag3=0)/*无与释放区低地址邻接的空闲区*/ for(j=0;jN;j+) if(freeblockj.state=0)/*找一个空表目，将释放区放入表中*/ freeblockj.startaddress=s; freeblockj.size=l; freeblockj.state=1; break;/*定义对空闲区表中的空闲区调整的函数adjust(),使空闲区按始地址从小到大排列，空表目放在最后面*/void adjust() int i,j; struct freearea middata; for(i=0;iN;i+)/*将空闲区按始地址顺序在表中排列*/ for(j=0;jfreeblockj+1.startaddress) middata.startaddress=freeblockj.startaddress; middata.size=freeblockj.size; middata.state=freeblockj.state; freeblockj.startaddress=freeblockj+1.startaddress; freeblockj.size=freeblockj+1.size; freeblockj.state=freeblockj+1.state; freeblockj+1.startaddress=middata.startaddress; freeblockj+1.size=middata.size; freeblockj+1.state=middata.state;for(i=0;iN;i+)/*将空表目放在表后面*/for(j=0;jN;j+)if(freeblockj.state=0&freeblockj+1.state=1) middata.startaddress=freeblockj.startaddress; middata.size=freeblockj.size; middata.state=freeblockj.state; freeblockj.startaddress=freeblockj+1.startaddress; freeblockj.size=freeblockj+1.size; freeblockj.state=freeblockj+1.state; freeblockj+1.startaddress=middata.startaddress; freeblockj+1.size=middata.size; freeblockj+1.state=middata.state;/*定义打印空闲区说明表函数：print()*/void print() int i; printf(|-|n); printf(| start size state |n); printf(|-|n); for(i=0;iN;i+)printf(| %3d %3d %3d |n, freeblocki.startaddress,freeblocki.size,freeblocki.state);printf(|-|n); /首次void shouci() int applyarea,start,i,j; char end; getchar(); printf(n is there any job request memory? y or n:); while(end=getchar()=y) printf(at first the free memory is this:n); adjust();/*对空闲区表中的空闲区调整的函数*/ print();/*打印空闲区表的初始状态*/ printf(input request memory size:); scanf(%d,&applyarea);/*输入作业的申请量*/ start=alloc(applyarea);/*调用alloc()函数为作业分配空间，start为返回的始地址*/ if(start=-1)/*alloc()分配不成功时，返回-1*/ printf(there is no fit memory,please waitn); else adjust(); printf(after allocation,the free memory is this:n); print();/*打印空闲区表*/ printf(jobs memory start address is:%dn,start); printf(job size is:%dn,applyarea); printf(job is running.n); printf(job is terminated.n); for(j=1;j100000;j+);/*延迟时间*/ setfree();/*主存回收函数*/ adjust();/*调整空闲区说明表*/ print();/*打印空闲区表函数*/ printf(is there any job that is waiting? y/n:); end=getchar();/*是否有作业等待？有(Y)无(N)*/ /循环首次void xunhuan() int applyarea,i=0,j; char end; getchar(); printf(n is there any job request memory? y or n:); while(end=getchar()=y) printf(at first the free memory is this:n); adjust();/*对空闲区表中的空闲区调整的函数*/ print();/*打印空闲区表的初始状态*/ printf(input request memory size:); scanf(%d,&applyarea);/*输入作业的申请量*/ if(i=N-1) i=alloc2(applyarea,i); if(i=-1)i=0; else if(iN-1) i=alloc2(applyarea,i); /start=alloc2(applyarea,start);/*调用alloc2()函数为作业分配空间，start为返回的始地址*/ if(i=-1)/*alloc2()分配不成功时，返回-1*/ printf(there is no fit memory,please waitn); else adjust(); printf(after allocation,the free memory is this:n); print();/*打印空闲区表*/ printf(jobs memory start address is:%dn,start); printf(job size is:%dn,applyarea); printf(job is running.n); printf(job is terminated.n); for(j=1;j100000;j+);/*延迟时间*/ setfree();/*主存回收函数*/ adjust();/*调整空闲区说明表*/ print();/*打印空闲区表函数*/ printf(is there any job that is waiting? y/n:); end=getchar();/*是否有作业等待？有(Y)无(N)*/ /最佳void best() int applyarea,start,i,j; char end; getchar(); printf(n is there any job request memory? y or n:); while(end=getchar()=y) printf(at first the free memory is this:n); adjust();/*对空闲区表中的空闲区调整的函数*/ print();/*打印空闲区表的初始状态*/ printf(input request memory size:); scanf(%d,&applyarea);/*输入作业的申请量*/ start=alloc3(applyarea);/*调用alloc()函数为作业分配空间，start为返回的始地址*/ if(start=-1)/*alloc()分配不成功时，返回-1*/ printf(there is no fit memory,please waitn); else adjust(); printf(after allocation,the free memory is this:n); print();/*打印空闲区表*/ printf(jobs memory start address is:%dn,start); printf(job size is:%dn,applyarea); printf(job is running.n); printf(job is terminated.n); for(j=1;j100000;j+);/*延迟时间*/ s