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

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