操作系统课程设计报告--动态分区分配

青岛理工大学操作系统课程设计报告院（系）：计算机工程学院专业：计算机科学与技术专业学生姓名:＿＿牛利利班级：＿＿计算073＿学号:200707106题目：＿动态分区分配模拟＿＿＿＿起迄日期:＿2010年7月5日至7月16日＿设计地点:2号实验楼402室指导教师:李兰2009—2010年度第2学期完成日期:2010年7月16日一、课程设计目的操作系统是最重要的计算机系统软件，同时也是最活跃的学科之一。计算机系统由硬件和软件两部分组成。操作系统是配置在计算机硬件上的第一层软件，是对硬件的首次扩充。本次课程设计的主要目的是在学习操作系统理论知识的基础上，对操作系统整体的一个模拟。也是对本学期所学知识的一个总体的检测，使理论知识应用到实际的编程中，根据理论的算法来实现具体的编程操作。同时通过本次课程设计加深对操作系统理论知识各个部分管理功能的感性认识，进一步分析和理解各个部分之间的联系和功能，最后达到对完整系统的理解。同时，可以提高运用操作系统知识和解决实际问题的能力；并且锻炼自己的编程能力、创新能力以及开发软件的能力；还能提高自己的调查研究、查阅文献、资料以及编写软件设计文档的能力并提高分析问题的能力。操作系统课程设计的主要任务是研究计算机操作系统的基本原理和算法，掌握操作系统的存储器管理、设备管理、文件管理和进程管理的基本原理和算法。使学生掌握基本的原理和方法，最后达到对完整系统的理解。二、课程设计内容仿真实现动态可变分区存储管理模拟系统。内存调度策略可采用首次适应算法、循环首次适应算法和最佳适应法等，并对各种算法进行性能比较。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。三、系统分析与设计1、系统分析：动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。目前常用的分配算法有：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法和快速适应算法。在动态分区存储管理方式中，主要操作是分配内存和回收内存。2、系统设计：系统利用某种分配算法，从空闲分区表中找到所需大小的分区。设请求分区的大小为u.size，表中每个空闲分区的大小可表示为m.size，若m.size-u.size≤size（size为事先规定的不再切割的剩余分区的大小）成立，则说明多余部分太小，可不再切割，将整个分区分配给请求者；否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分留在空闲区表中，然后将分配区的首址返回给调用者。当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区表中找到相应的插入点，并且按照四种情况进行插入。3、模块设计：(1)空闲区说明表结构：把空闲区定义为结构体变量，包括空闲区始址，空闲区大小和空闲区状态，用0表示空表目，1为可用空闲块。structfreearea{intstartaddress;/*空闲区始址*/intsize;/*空闲区大小*/intstate;/*空闲区状态:0为空表目，1为可用空闲块*/}freeblock[N]={{1,20,20,1},{2,80,50,1},{3,150,30,1},{4,300,30,1},{5,500,10,1}};(2)为作业分配主存空间的函数alloc()，三个算法分别对应三个分配主存空间的算法。applyarea为作业申请量，tag为检查是否有满足作业需要的空闲区的标志。○1首次适应算法:检查空闲区说明表是否有满足作业要求的空闲区时,如果大于作业要求,则分配给作业,修改地址和空闲区大小,并将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;}检查“大于”的情况：先把所有大于所要求的空闲区放入数组,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){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;}○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)首次适应算法函数First_fit():若有作业需要分配内存，则对空闲区表中的空闲区进行调整，调用调整函数adjust()，再将其打印出来；输入作业申请量，调用alloc()函数为作业分配空间，分配结束后，要进行主存回收，再次调整空闲区表后，打印出来。循环执行直到没有作业为止。(7)循环首次适应算法Next_fit():与首次适应算法不同的是，循环首次适应算法要记录上次找到的空闲区地址，并在下次分配时从这个地址开始。(8)最佳时应算法Best_fit():该算法在分配内存时，把所有满足要求的空闲区中最小的那个空闲区分配给请求进程。（9）主函数main()：主要用于调用各个函数来实现各项功能和显示主界面。4、数据结构说明：(1)空闲区说明表结构structfreearea：把空闲区定义为结构体变量，包括空闲区始址，空闲区大小和空闲区状态，用0表示空表目，1为可用空闲块。(2)为作业分配主存空间的函数alloc()，三个算法分别对应三个分配主存空间的算法。applyarea为作业申请量，tag为检查是否有满足作业需要的空闲区的标志。(3)主存回收函数setfree()：tag1代表释放区的高地址是否邻接一个空闲区，tag2代表释放区的高低地址是否都邻接一个空闲区，tag3代表释放区的低地址是否邻接一个空闲区。分为四种情况。(4)对空闲区表中的空闲区调整的函数adjust()：使空闲区按始地址从小到大排列，空表目放在最后面。(5)打印空闲区说明表函数：print()(6)首次适应算法函数First_fit():若有作业需要分配内存，则对空闲区表中的空闲区进行调整，调用调整函数adjust()，再将其打印出来；输入作业申请量，调用alloc()函数为作业分配空间，分配结束后，要进行主存回收，再次调整空闲区表后，打印出来。循环执行直到没有作业为止。(7)循环首次适应算法Next_fit():与首次适应算法不同的是，循环首次适应算法要记录上次找到的空闲区地址，并在下次分配时从这个地址开始。(8)最佳时应算法Bes