可变分区分配与回收——采用最坏算法-操作系统课程设计

哈尔滨理工大学课程设计（操作系统）题目：可变分区分配与回收—采用最坏算法班级：计算机科学与技术学院计算机系10-8班姓名：张兢1004010813指导教师：高雪瑶系主任：林克正2013年03月01日哈尔滨理工大学课程设计报告一、课程设计目的1、背景主存是CPU可直接访问的信息空间，合理而有效的使用贮存将在很大程度上影响整个计算机系统的性能。本课题要求模拟实现分区式主存管理机制。模拟实现各种分区管理方法以及相应的主存分配以及回收算法。2、目的通过该课题进一步加深对可变分区存储机制的理解。加深对存储器动态分区分配算法的认识。掌握“首次适应算法”、“下次适应算法”、“最佳适应算法发”、“最坏适应算法”的内存分配过程。掌握内存的回收策略。二、课题任务描述1、设计可用的内存空闲空间，并能动态输入用户作业所需的内存大小。2、编程模拟各种分配算法的实施过程，允许自行选择如“首次适应算法”、“下次适应算法”、“最佳适应算法发”、“最坏适应算法”等常用算法，要求实现不少于三种算法。3、实现内存的回收。要求考虑回收时的内存合并问题。三、课题研发相关知识（包含所用库函数的介绍）1、首次适应算法（firstfit）FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能男足要求的空闲分区位置；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都哈尔滨理工大学课程设计报告不能找到一个能满足要求的分区，则此次内存分配失败，返回。但是，低址部分不断被划分，会留下许多难以利用的很小的空闲分区。2、最佳适应算法（bestfit）所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。这样，在存储器中会留下许多难以利用的小空闲区。3、最坏适应算法（worstfit）要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中小作业有力，查找效率很高。但是它会使存储器中缺乏大的空闲分区。4、回收内存当进程运行完毕释放内存时，系统根据会收取的首址，从空闲区链中找到相应的插入点，并考虑回收区前后是否有空闲分区，如果有，则把两个分区合并成一个大的空闲分区。5、库函数的介绍1）stdio就是指“standardbufferedinput&output意思就是说带缓冲的标准输入输出！所以了，用到标准输入输出函数时，就要调用这个头文件！2）Stdlib.h即standardlibrary标准库文件。Stdlib头文件里包含了C,C++语言的最常用的系统函数。Stdlib.h里面定义了五中类型，一些宏和通用工具函数。类型例如：size_t,wchar_t,div_t,ldiv_t,lldiv_t;宏例如：EXIT_FALIRE,EXIT_SUCCESS,RAND_MAX和MB_CUR_MAX。以下是一些常用的函数：dec置基数为10相当于%d；hex置基数为16相当于%X；oct置基数为8相当于%o；setw(n)设域宽为n个字符哈尔滨理工大学课程设计报告四、课题设计：总体结构、所使用的数据结构、主要功能的流程图、程序的技术路线1、总体结构本系统采用了首次适应算法、最佳适应算法和最坏适应算法模拟存储器动态分区。系统利用其中某种分配算法，从空闲分区链中找到满足请求内存大小的分区并分配内存给作业。假设总的内存大小为size，作业请求的内存大小为request,内存碎片最小为f。当requestsize时，内存溢出，出现系统错误；当request=size时，在内存中根据上述算法寻找最佳的内存分区分配给作业。寻找到合适的内存分区之后，如果size-request=f,将此分区上的内存全部分配给作业；如果size-requestf，就在此分区上分割request大小的内存给作业，剩余内存继续留在当前的分区中。当进程运行完毕，系统找到该进程并释放其内存，根据所释放内存的位置对内存进行合并。系统流程图：如图1哈尔滨理工大学课程设计报告YNNYNY开始输入option选择分配算法option=3??根据option的值选择相应算法，输入opeope=0?ope=1?ope=2?ope=3?NN退出分配内存回收内存返回上一级输入错误YY图1哈尔滨理工大学课程设计报告系统框架图：如图22、数据结构（1）定义的全局变量：#defineSIZE1000//内存初始大小#defineMINSIZE5//碎片最小值enumSTATE{Free,Busy}//枚举类型，记录分区是否空闲的状态量（2）定义的结构体：structsubAreaNode。记录分区的主要数据。（3）函数1）voidintSubArea()：分配初始分区内存。2）intfirstFit(inttaskId,intsize)：首次适应算法实现函数，taskId为作业名，size为作业申请的内存大小。存储器动态分区分配模拟系统首次适应算法最佳适应算法最坏适应算法退出系统分配内存回收内存返回上一级菜单图2哈尔滨理工大学课程设计报告3）intbestFit(inttaskId,intsize)：最佳适应算法实现函数，taskId为作业名，size为作业申请的内存大小。4）intworstFit(inttaskId,intsize)：最坏适应算法实现函数，taskId为作业名，size为作业申请的内存大小。5）intfreeSubArea(inttaskId)：内存回收函数，该函数主要用于实现内存的回收，根据回收内存的位置对分区进行合并操作。其中taskId为所需回收内存的作业号。6）voidshowSubArea()：显示空闲分区链情况。包括起始地址，空间大小。工作状态。作业号。7）intmain()：主函数，主要用于显示操作界面，调用各个子函数等功能。3、主要功能的流程图（1）首次适应算法First_fit(int,int);流程图（图3）哈尔滨理工大学课程设计报告图3NYY开始p=subHead.nxt，从链表的第一个节点开始寻找p是否为空p是否空闲，p-size大小是否满足作业需求p-size与作业需求大小之差是否小于等于内存碎片p中内存大小全部分配给作业N执行完毕结束Y分割分区p，并把剩余内存存入新的结点N哈尔滨理工大学课程设计报告（2）最佳适应算法Best_fit(int,int);流程图（图4）哈尔滨理工大学课程设计报告YYN开始subAreaNode*p=subHead.nxtP是否空P是否满足最佳分配空间YNp=p-nxttar=ptar为空？Ntar-size-size是否小于等于内存碎片tar全部分配给作业结束Y切割tar，分配给作业，并把剩余内存重新链入链表N图4哈尔滨理工大学课程设计报告（3）最坏适应算法Worst_fit(int,int);流程图（图5）哈尔滨理工大学课程设计报告NYYN开始subAreaNode*p=subHead.nxtmm=1P是否空且mm==1P是否满足最佳分配空间YNp=p-nxttar=p,mm=0tar为空？tar-size-size是否小于等于内存碎片tar全部分配给作业结束Y切割tar，分配给作业，并把剩余内存重新链入链表N遍历空闲链表，p=subHead.nxt寻找最大的空闲分区，tar=p;图5YY哈尔滨理工大学课程设计报告4.程序的技术路线本程序采用C语言编写，在windows下的VisualC++中编译，模拟可变分区存储管理方式的内存分配与回收。假定系统的最大内存空间为1000kb，判断是否划分空闲区的最小限值为MINSIZE=5。初始化用户可占用内存区的首地址为0，大小为0B。定义一个结构体及其对象subHead实现内存的分配回收及分配表和空闲表的登记。用最佳分配算法实现动态分配时，调用intbestFit(inttaskId,intsize)内存分配函数，设定循环条件查找最佳空闲分区，根据找到的空闲区大小和作业大小判断是整个分配给作业还是切割空闲区后再分配给作业，并在“内存分配表”和“空闲分区表”中作登记。调用intfreeSubArea(inttaskId)函数实现内存的回收。顺序循环“内存分配表”找到要回收的作业，设置标志位flag，当flag=1时表示回收成功。回收内存时需考虑内存的4种合并方式，即合并上下分区、合并上分区、合并下分区、上下分区都不合并。五、带有详细注解的源程序#includestdio.h#includetime.h#includestdlib.h#defineSIZE1000//内存初始大小#defineMINSIZE5//碎片最小值enumSTATE{Free,Busy};staticintss=0,ee=0;structsubAreaNode{intaddr;//起始地址intsize;//分区大小inttaskId;//作业号哈尔滨理工大学课程设计报告STATEstate;//分区状态subAreaNode*pre;//分区前向指针subAreaNode*nxt;//分区后向指针}subHead;//初始化空闲分区链voidintSubArea(){//分配初始分区内存subAreaNode*fir=(subAreaNode*)malloc(sizeof(subAreaNode));//给首个分区赋值fir-addr=0;fir-size=SIZE;fir-state=Free;fir-taskId=-1;fir-pre=&subHead;fir-nxt=NULL;//初始化分区头部信息subHead.pre=NULL;subHead.nxt=fir;}//首次适应算法intfirstFit(inttaskId,intsize){subAreaNode*p=subHead.nxt;while(p!=NULL){if(p-state==Free&&p-size=size){//找到要分配的空闲分区if(p-size-size=MINSIZE){哈尔滨理工大学课程设计报告//整块分配p-state=Busy;p-taskId=taskId;}else{//分配大小为size的区间subAreaNode*node=(subAreaNode*)malloc(sizeof(subAreaNode));node-addr=p-addr+size;node-size=p-size-size;node-state=Free;node-taskId=-1;//修改分区链节点指针node-pre=p;node-nxt=p-nxt;if(p-nxt!=NULL){p-nxt-pre=node;}p-nxt=node;//分配空闲区间p-size=size;p-state=Busy;p-taskId=taskId;}printf(内存分配成功！\n);return1;}p=p-nxt;}哈尔滨理工大学课程设计报告printf(找不到合适的内存分区，分配失败...\n);return0;}//最佳适应算法intbestFit(inttaskId,intsize){subAreaNode*tar=NULL;inttarSize=SIZE+1;subAreaNode*p=subHead.nxt;while(p!=NULL){//寻找最佳空闲区间if(p-state==Free&&p-size=size&&p-sizetarSize){tar=p;tarSize=p-size;}p=p-nxt;}if(tar!=NULL){//找到要分配的空闲分区if(tar-size-size=MINSIZE){//