存储管理---动态分区分配算法的模拟　　　.doc

齐齐哈尔大学操作系统课程综合实践题目：存储管理-动态分区分配算法的模拟班级：计本062姓名：wolfboy学号：1111111111指导教师：TEACHER2008年12月班级姓名指导教师题目：存储管理-动态分区分配算法的模拟评分标准评分标准分数权重评分的依据得分AC选题10选题符合大纲要求，题目较新颖，工作量大选题基本符合大纲要求，工作量适中工作态度10态度端正，能主动认真完成各个环节的工作，不迟到早退，出勤好。能够完成各环节基本工作，出勤较好。存储结构、算法描述20能正确选择存储结构，定义准确，算法流程图或类C语言描述的算法准确无误能正确选择存储结构，算法流程图或类C语言描述的算法基本准确独立解决问题的能力10具有独立分析、解决问题能力，有一定的创造性，能够独立完成软件的设计与调试工作，程序结构清晰，逻辑严谨，功能完善。有一定的分析、解决问题能力。能够在老师指导下完成软件的设计与调试工作，程序功能较完善。答辨问题回答20能准确回答老师提出的问题能基本准确回答老师提出的问题程序运行情况10程序运行正确、界面清晰，测试数据设计合理。程序运行正确、界面较清晰，能给出合适的测试数据。综合实践报告20格式规范，层次清晰，设计思想明确，解决问题方法合理，体会深刻。格式较规范，设计思想基本明确，解决问题方法较合理。总分指导教师（签字）：17存储管理-动态分区分配算法的模拟摘要:分区分配算法就是系统在寻找空闲的分区分配给某一用户作业,具体可采用首次适应算法,循环首次适应算法和最佳适应算法。下面将针对每个算法的数据结构及算法实现进行分析，在分析算法前，先对此次课题进行了分析，再对一些基础相关知识进行了整理。关键字:分区分配算法；首次适应；循环首次适应；最佳适应 概 述动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。1、设计目的及开发环境(1)设计目的分区管理是满足多道程序运行的最简单的存储管理方式，为了实现对内存空间的有效管理，需要采取一些方法和策略，用以实现对内存空间的分配或回收。(2)开发环境操作系统：windows xp开发环境：Dev-C+ 52数据结构设计(1) 空闲区说明表结构：把空闲区定义为结构体变量，包括空闲区始址，空闲区大小和空闲区状态，用0表示空表目，1为可用空闲块。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; (2) 为作业分配主存空间的函数alloc()，三个算法分别对应三个分配主存空间的算法。applyarea为作业申请量，tag为检查是否有满足作业需要的空闲区的标志。首次适应算法:检查空闲区说明表是否有满足作业要求的空闲区时,如果大于作业要求,则分配给作业,修改地址和空闲区大小,并将tag置“1”,表示有满足作业要求的空闲区,返回为作业分配主存的地址.程序如下所示：if(freeblocki.state=1&freeblocki.sizeapplyarea)freeblocki.startaddress=freeblocki.startaddress+applyarea;freeblocki.size=freeblocki.size-applyarea;tag=1;return freeblocki.startaddress-applyarea;如果空闲区等于作业要求，则分配给作业,修改地址和空闲区大小,并将tag置“1”,表示有满足作业要求的空闲区,返回为作业分配主存的地址.if(freeblocki.state=1&freeblocki.size=applyarea) freeblocki.state=0; tag=1; return freeblocki.startaddress;如果没有满足条件的空闲区，分配不成功，返回-1if(tag=0)return -1;循环首次适应算法的alloc()函数与首次适应算法的alloc()函数区别在于从哪里开始找是否有满足作业要求的空闲区，它是从上次找到的空闲区的下一个空闲分区开始找，只需要改变for循环的条件即可。for(i=s;iN;i+)最佳适应算法：该算法总是把满足要求、又是最小的空闲区分配给作业。检查空闲区说明表是否有满足作业要求的空闲区，也分为三种情况：大于，等于，小于。若检查到有“等于”的情况，就可以直接分配，若没有，则继续检查是否有“大于”的情况：if(freeblocki.state=1&freeblocki.size=applyarea) freeblocki.state=0; tag=1; return freeblocki.startaddress;检查“大于”的情况：先把所有大于所要求的空闲区放入数组,for(i=0;iapplyarea)aj+=i;再从数组中挑出最小的那个：如果数组中的元素大于一个，则需要一个个比较过去，然后取出最小的那个分配给作业：if(j1) h=a0; min=freeblockh; 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; return min.startaddress-applyarea; 如果数组中只有一个元素，则直接分配给作业：if(j=1) h=a0; min=freeblockh; min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea; tag=1; return min.startaddress-applyarea; 如果没有满足条件的空闲区，分配不成功，返回-1if(tag=0)return -1; (3) 主存回收函数setfree()：tag1代表释放区的高地址是否邻接一个空闲区，tag2代表释放区的高低地址是否都邻接一个空闲区，tag3代表释放区的低地址是否邻接一个空闲区。分为四种情况：回收分区的上邻和下邻分区都不是空闲的，则直接将回收区的相关信息记录在空闲区表中。if(tag3=0)for(j=0;jN;j+)if(freeblockj.state=0)freeblockj.startaddress=s;freeblockj.size=l;freeblockj.state=1;break; 回收分区的上邻分区是空闲的，需要将这两个相邻的空闲区合并成一个较大的空闲区，然后修改空闲区表。if(freeblocki.startaddress=s+l&freeblocki.state=1) l=l+freeblocki.size; tag1=1; 回收分区的下邻分区是空闲区，需要将这两个相邻的空闲区合并成一个空闲区，并修改空闲区表。if(freeblocki.startaddress+freeblocki.size=s&freeblocki.state=1)freeblocki.size=freeblocki.size+l;tag3=1;break; 回收分区的上邻和下邻都是空闲区，则需要将这三个空闲区合并成一个更大的空闲区，然后修改空闲区表。先判断有上邻空闲区（如所示），再判断有下邻空闲区（如所示），若都有，则将tag2置1。(4) 对空闲区表中的空闲区调整的函数adjust()：使空闲区按始地址从小到大排列，空表目放在最后面。(5) 打印空闲区说明表函数：print()(6) 首次适应算法函数shouci():若有作业需要分配内存，则对空闲区表中的空闲区进行调整，调用调整函数adjust()，再将其打印出来；输入作业申请量，调用alloc()函数为作业分配空间，分配结束后，要进行主存回收，再次调整空闲区表后，打印出来。循环执行直到没有作业为止。(7) 循环首次适应算法xunhuan():与首次适应算法不同的是，循环首次适应算法要记录上次找到的空闲区地址，并在下次分配时从这个地址开始。(8) 最佳时应算法best():该算法在分配内存时，把所有满足要求的空闲区中最小的那个空闲区分配给请求进程。3算法的实现（1）首次适应算法 首次适应算法要求空闲区按其起始地址由小到大排列，当某一用户作业要求装入内存时，存储分配程序从起始地址最小的空间区开始扫描，直到找到满足该作业要求的空闲区为止。（2）循环首次适应算法 在查找空闲区时，不再每次从链首开始查找，而是从上一次找到的空闲区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区为止，并从中划出一块与请求大小相等的内存空间分给该作业。（3）最佳适应算法 该算法总是把满足要求，又是最小的空闲区分配给请求进程，即在空闲区表中，按空闲区的大小由小到大排序，建立索引，当用户进程请求分配内存时，从索引表中找到第一个满足该进程大小要求的空闲区分配给它。（4）整体实现过程： 系统利用某种分配算法，从空闲分区链（表）中找到所需大小的分区，设请求分区的大小为r.size，其中空闲分区的大小可表示为f.size，若 f.size-r.sizesize（size为事先规定的不再切割的剩余分区的大小）成立，则说明多余部分太小，不能满足其它请求进程，故将整个分区分配给该请求者；否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分留在空闲区表中，然后将分区首部返回给调用者。4结束语采用首次适应算法，会使空闲链（表）低地址部分得到充分利用，但随作业增多，会在低地址部分留下很多的难以利用的空闲分区，还有每次查找都是从低址部分开始，必然会增加查找的时间。循环首次适应算法使得内存中剩余空闲区的大小更加均匀地分布，减少平均查找的时间，但实验表明，在内存利用率方面它比首次适应算法略差一点。 实验中发现，最佳算法在内存的利用率并不是最佳的，甚至比首次适应算法和循环首次适应算法更差。因为所选用的空闲区刚好或略大于请求进程，那么剩余的碎片通常太小而无法使用，因此最佳适应算法会产生数量很多的碎片，此外算法的查找时间也相对较长。三个分配算法，其主要区别就在于如何为作业分配主存空间。5参考文献1、汤子嬴 等 计算机操作系统.西安电子科技大学出版社.2001年8月2、滕艳平 主编 计算机操作系统.哈尔滨工业大学出版社.2008年9月3、谭浩强 编C程序设计.清华大学出版社.2005年7月4、Anany Levitin(美) 著 潘彦 译算法设计与分析.清华大学出版社.2004年6月5、王红梅 等数据结构（C+版）.清华大学出版社.2005年7月附录：程序清单/*动态分区的分配与回收演示程序*/#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 runni