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

1、精选优质文档-倾情为你奉上存储管理-动态分区分配算法的模拟齐齐哈尔大学 操作系统课程综合实践 题目：存储管理-动态分区分配算法的模拟 班级：计本062 姓名：wolfboy 学号： 指导教师：TEACHER 2008年12月 班级 姓名 指导教师 题目：存储管理-动态分区分配算法的模拟 评分标准 评分的依据 评分标准 分数权重 得分 A C 选题符合大纲要求，选题基本符合大纲要 10 选题 题目较新颖，工作量求，工作量适中 大 态度端正，能主动认真完成各个环节的工能够完成各环节基本 10 工作态度 作，不迟到早退，出工作，出勤较好。 勤好。 能正确选择存储结能正确选择存储结存储结构、算构，定义

2、准确，算法构，算法流程图或类 20 法描述 流程图或类C语言描C语言描述的算法基述的算法准确无误 本准确 具有独立分析、解决有一定的分析、解决问题能力，有一定的问题能力。能够在老独立解决问创造性，能够独立完 10 师指导下完成软件的题的能力 成软件的设计与调试设计与调试工作，程工作，程序结构清晰，序功能较完善。 逻辑严谨，功能完善。 答辨问题回能准确回答老师提出能基本准确回答老师 20 答 的问题 提出的问题 程序运行正确、界面程序运行正确、界面程序运行情 10 清晰，测试数据设计较清晰，能给出合适况 合理。 的测试数据。 格式规范，层次清晰，格式较规范，设计思综合实践报设计思想明确，解决 2

3、0 想基本明确，解决问告 问题方法合理，体会题方法较合理。 深刻。 总分 指导教师（签字）： 1 存储管理 -动态分区分配算法的模拟 :分区分配算法就是系统在寻找空闲的分区分配给某一用户作业,具体可采用首次适应算法,循环首次适应算法和最佳适应算法。下面将针对每个算法的数据结构及算法实现进行分析，在分析算法前，先对此次课题进行了分析，再对一些基础相关知识进行了整理。 :分区分配算法；首次适应；循环首次适应；最佳适应 概 述 动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。 1、设计目

4、的及开发环境 分区管理是满足多道程序运行的最简单的存储管理方式，为了实现对内存空间的有效管理，需要采取一些方法和策略，用以实现对内存空间的分配或回收。 操作系统：windows xp 开发环境：Dev-C+ 5 2数据结构设计 (1) 空闲区说明表结构：把空闲区定义为结构体变量，包括空闲区始址，空闲区大小和空闲区状态，用0表示空表目，1为可用空闲块。 struct freearea int startaddress;/*空闲区始址*/ int size;/*空闲区大小*/ int state;/*空闲区状态:0为空表目，1为可用空闲块*/ freeblockN=20,20,1,80,50,1,

5、150,30,1,300,30,0,600,10,1; (2) 为作业分配主存空间的函数alloc()，三个算法分别对应三个分配主存空间的算法。applyarea为作业申请量，tag为检查是否有满足作业需要的空闲区的标志。 2 1?首次适应算法: 检查空闲区说明表是否有满足作业要求的空闲区时,如果大于作业要求,则分配给作业,修改地址和空闲区大小,并将tag置“1”,表示有满足作业要求的空闲区,返回为作业分配主存的地址.程序如下所示： if(freeblocki.state=1&&freeblocki.size>applyarea) freeblocki.startaddr

6、ess=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 freeblock

7、i.startaddress; 如果没有满足条件的空闲区，分配不成功，返回-1 if(tag=0)return -1; 2?循环首次适应算法的alloc()函数与首次适应算法的alloc()函数区别在于从哪里开始找是否有满足作业要求的空闲区，它是从上次找到的空闲区的下一个空闲分区开始找，只需要改变for循环的条件即可。 for(i=s;i<N;i+) 3?最佳适应算法：该算法总是把满足要求、又是最小的空闲区分配给作业。检查空闲区说明表是否有满足作业要求的空闲区，也分为三种情况：大于，等于，小于。若检查到有“等于”的情况，就可以直接分配，若没有，则继续检查是否有“大于”的情况： if(fr

8、eeblocki.state=1&&freeblocki.size=applyarea) freeblocki.state=0; tag=1; return freeblocki.startaddress; 3 检查“大于”的情况：先把所有大于所要求的空闲区放入数组, for(i=0;i<N;i+) if(freeblocki.state=1&&freeblocki.size>applyarea)aj+=i; 再从数组中挑出最小的那个： 如果数组中的元素大于一个，则需要一个个比较过去，然后取出最小的那个分配给作业： if(j>1) h=a0;

9、min=freeblockh; for(k=1;k<j;k+) h=ak; if(freeblockh.size<min.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.st

10、ate; min.startaddress=mid.startaddress; min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea; tag=1; return min.startaddress-applyarea; 如果数组中只有一个元素，则直接分配给作业： if(j=1) 4 h=a0; min=freeblockh; min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea; tag=1; return mi

11、n.startaddress-applyarea; 如果没有满足条件的空闲区，分配不成功，返回-1 if(tag=0)return -1; (3) 主存回收函数setfree()：tag1代表释放区的高地址是否邻接一个空闲区，tag2代表释放区的高低地址是否都邻接一个空闲区，tag3代表释放区的低地址是否邻接一个空闲区。分为四种情况： 1?回收分区的上邻和下邻分区都不是空闲的，则直接将回收区的相关信息记录在空闲区表中。 if(tag3=0) for(j=0;j<N;j+) if(freeblockj.state=0) freeblockj.startaddress=s; freebloc

12、kj.size=l; freeblockj.state=1; break; 2 ?回收分区的上邻分区是空闲的，需要将这两个相邻的空闲区合并成一个较大的空闲区，然后修改空闲区表。 if(freeblocki.startaddress=s+l&&freeblocki.state=1) l=l+freeblocki.size; tag1=1; 5 3 ?回收分区的下邻分区是空闲区，需要将这两个相邻的空闲区合并成一个空闲区，并修改空闲区表。 if(freeblocki.startaddress+freeblocki.size=s&&freeblocki.state=1)

13、 freeblocki.size=freeblocki.size+l; tag3=1; break; 4 ?回收分区的上邻和下邻都是空闲区，则需要将这三个空闲区合并成一个更大2的空闲区，然后修改空闲区表。先判断有上邻空闲区（如?所示），再判断有下3邻空闲区（如?所示），若都有，则将tag2置1。 (4) 对空闲区表中的空闲区调整的函数adjust()：使空闲区按始地址从小到大排列，空表目放在最后面。 (5) 打印空闲区说明表函数：print() (6) 首次适应算法函数shouci():若有作业需要分配内存，则对空闲区表中的空闲区进行调整，调用调整函数adjust()，再将其打印出来；输入作业

14、申请量，调用alloc()函数为作业分配空间，分配结束后，要进行主存回收，再次调整空闲区表后，打印出来。循环执行直到没有作业为止。 (7) 循环首次适应算法xunhuan():与首次适应算法不同的是，循环首次适应算法要记录上次找到的空闲区地址，并在下次分配时从这个地址开始。 (8) 最佳时应算法best():该算法在分配内存时，把所有满足要求的空闲区中最小的那个空闲区分配给请求进程。 3算法的实现 首次适应算法要求空闲区按其起始地址由小到大排列，当某一用户作业要求装入内存时，存储分配程序从起始地址最小的空间区开始扫描，直到找到满足该作业要求的空闲区为止。 在查找空闲区时，不再每次从链首开始查找

15、，而是从上一次找到的空闲区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区为止，并从中划出一块与请求大小相等的内存空间分给该作业。 该算法总是把满足要求，又是最小的空闲区分配给请求进程，即在空闲区表6 中，按空闲区的大小由小到大排序，建立索引，当用户进程请求分配内存时，从索引表中找到第一个满足该进程大小要求的空闲区分配给它。 系统利用某种分配算法，从空闲分区链（表）中找到所需大小的分区，设请求分区的大小为r.size，其中空闲分区的大小可表示为f.size，若 f.size-r.size?size（size为事先规定的不再切割的剩余分区的大小）成立，则说明多余部分太小，不能满足其它请求

16、进程，故将整个分区分配给该请求者；否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分留在空闲区表中，然后将分区首部返回给调用者。 4结束语 采用首次适应算法，会使空闲链（表）低地址部分得到充分利用，但随作业增多，会在低地址部分留下很多的难以利用的空闲分区，还有每次查找都是从低址部分开始，必然会增加查找的时间。 循环首次适应算法使得内存中剩余空闲区的大小更加均匀地分布，减少平均查找的时间，但实验表明，在内存利用率方面它比首次适应算法略差一点。 实验中发现，最佳算法在内存的利用率并不是最佳的，甚至比首次适应算法和循环首次适应算法更差。因为所选用的空闲区刚好或略大于请求进程，那么剩余

17、的碎片通常太小而无法使用，因此最佳适应算法会产生数量很多的碎片，此外算法的查找时间也相对较长。三个分配算法，其主要区别就在于如何为作业分配主存空间。 5参考文献 1、汤子嬴 等 计算机操作系统.西安电子科技大学出版社.2001年8月 2、滕艳平 主编 计算机操作系统.哈尔滨工业大学出版社.2008年9月 3、谭浩强 编C程序设计.清华大学出版社.2005年7月 4、Anany Levitin(美) 著 潘彦 译算法设计与分析.清华大学出版社.2004年6月 5、王红梅 等数据结构（C+版）.清华大学出版社.2005年7月 7 附录：程序清单 /*动态分区的分配与回收演示程序*/ #includ

18、e "stdio.h" #define N 5 int 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为作业

19、申请量*/ int i,tag=0; /*tag为检查是否有满足作业需要的空闲区的标志*/ for(i=0;i<N;i+) /*检查空闲区说明表是否有满足作业要求的空闲区*/ if(freeblocki.state=1&&freeblocki.size>applyarea) freeblocki.startaddress=freeblocki.startaddress+applyarea; freeblocki.size=freeblocki.size-applyarea; tag=1; /*有满足条件的空闲区时，tag置1*/ return freeblocki.

20、startaddress-applyarea; else if(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

21、) /*applyarea为作业申请量*/ int i,tag=0; /*tag为检查是否有满足作业需要的空闲区的标志*/ for(i=s;i<N;i+)/*检查空闲区说明表是否有满足作业要求的空闲区,从上次找到的空闲去的下一个空闲分区开始找*/ if(freeblocki.state=1&&freeblocki.size>applyarea) 8 freeblocki.startaddress=freeblocki.startaddress+applyarea; freeblocki.size=freeblocki.size-applyarea; tag=1; /

22、*有满足条件的空闲区时，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*/ /*定义为作业分配主存空间

23、的函数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;i<N;i+) /*检查空闲区说明表是否有满足作业要求的空闲区*/ if(freeblocki.state=1&&freeblocki.size=applyarea)/大小刚好相等 freeblocki.state=

24、0; tag=1; /*有满足条件的空闲区时，tag置1*/ return freeblocki.startaddress; /*返回为作业分配的主存地址*/ for(i=0;i<N;i+)/把所有大于所要求的空闲区放入数组,挑出最小的那个 if(freeblocki.state=1&&freeblocki.size>applyarea)aj+=i; if(j>1) h=a0; min=freeblockh; /min.startaddress=freeblockh.startaddress; /min.size=freeblockh.size; 9 /min

25、.state=freeblockh.state; for(k=1;k<j;k+) h=ak; if(freeblockh.size<min.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.sta

26、te=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

27、; /*有满足条件的空闲区时，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")

28、; scanf("%d",&s); /*输入释放区的开始地址*/ 10 printf("input free area size:n"); scanf("%d",&l); /*输入释放区的大小*/ for(i=0;i<N;i+) if(freeblocki.startaddress=s+l&&freeblocki.state=1) l=l+freeblocki.size; tag1=1; /*有与释放区高地址邻接的空闲区，tag1置1*/ for(j=0;j<N;j+) if(freeblo

29、ckj.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;i<

30、;N;i+) if(freeblocki.startaddress+freeblocki.size=s&&freeblocki.state=1) freeblocki.size=freeblocki.size+l; tag3=1; /*有与释放区低地址邻接的空闲区*/ break; if(tag3=0) /*无与释放区低地址邻接的空闲区*/ for(j=0;j<N;j+) if(freeblockj.state=0)/*找一个空表目，将释放区放入表中*/ freeblockj.startaddress=s; freeblockj.size=l; freeblockj.st

31、ate=1; break; 11 /*定义对空闲区表中的空闲区调整的函数adjust(), 使空闲区按始地址从小到大排列，空表目放在最后面*/ void adjust() int i,j; struct freearea middata; for(i=0;i<N;i+) /*将空闲区按始地址顺序在表中排列*/ for(j=0;j<N;j+) if(freeblockj.startaddress>freeblockj+1.startaddress) middata.startaddress=freeblockj.startaddress; middata.size=freebl

32、ockj.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;i<N;i+) /

33、*将空表目放在表后面*/ for(j=0;j<N;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=free

34、blockj+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"); 12 for(i=0;i<N;i+) print

35、f(" | %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 firs

36、t 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("the

37、re is no fit memory,please waitn"); else adjust(); printf("after allocation,the free memory is this:n"); print(); /*打印空闲区表*/ printf("job's memory start address is:%dn",start); printf("job size is:%dn",applyarea); printf("job is running.n"); printf(&qu

38、ot;job is terminated.n"); for(j=1;j<j+);/*延迟时间*/ setfree(); /*主存回收函数*/ adjust(); /*调整空闲区说明表*/ print(); /*打印空闲区表函数*/ printf("is there any job that is waiting? y/n:"); end=getchar();/*是否有作业等待？有(Y)无(N)*/ 13 /循环首次 void xunhuan() int applyarea,i=0,j; char end; getchar(); printf("n

39、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)

40、 i=alloc2(applyarea,i); if(i=-1)i=0; else if(i<N-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("job's 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;j<j+);/*延迟时间*/ setfree(); /*主存回收函数*/ adjust(); /*