内存分配与回收.doc

学校代码： 学 号： 课程设计题 目：主存空间的分配与回收学生姓名：学 院：信息工程学院系 别：计算机系 专 业：计算机科学与技术 班 级：计算机指导教师：副教授 副教授 2011年月日内蒙古工业大学课程设计任务书（三）学院（系）：信息学院计算机系 课程名称：操作系统课程设计 指导教师（签名）： 专业班级：计算机09-2 学生姓名： 学号： 一、课程设计题目主存空间的分配与回收二、课程设计的目的通过该课程设计使学生理解在不同的存储管理方式下，如何实现主存空间的分配与回收。使学生初步具有研究、设计、编制和调试操作系统模块的能力。 三、课程设计的主要内容和要求（包括原始数据、技术参数、设计要求、工作量要求等） 原始数据：空闲区说明表结构体。 技术参数：Windows XP系统，VC+6.0开发工具。设计要求： 1 设计基于空闲区说明表的可变分区分配与回收算法；2 或设计基于空闲区链表的可变分区分配与回收算法；3 画出以上算法流程图；4 编程实现算法功能；5编写课程设计说明书。 工作量要求：完成以上设计要求中的所有算法功能。四、工作进度安排 周四：布置、讲解题目，收集资料；周五：系统分析，算法设计；周一：编制、调试程序；周二：测试系统，形成设计结论，编写课设报告；周三：系统及材料验收，课设答辩。五、主要参考文献1 张尧学编计算机操作系统教程（第三版）习题解答与实验指导北京:清华大学出版社，20062 汤子瀛主编计算机操作系统（第三版）西安:西安电子科技大学出版社，2001 3 张坤等编操作系统实验教程北京:清华大学出版社，2008审核批准意见系（教研室）主任（签字） 内蒙古工业大学操作系统课程设计目 录第一章 背景研究11.1课题简介11.2 设计要求11.3概念原理11.4 环境说明和使用工具2第二章 详细设计32.1功能介绍32.1.1分配函数发fenpei()的执行过程（最佳适应算法）32.1.2回收进程空间所占的函数free()的执行过程32.2函数的规格说明32.2.1打印分配表空闲表函数 print()32.2.2为进程分配空间函数 fenpei(char *c, struct node *p,struct node *f)42.2.3回收进程所占空间函数struct node * free(char *c, struct node *p,struct node *f)42.3 主要数据结构42.4 流程图5第三章 核心算法的实现63.1 分配函数63.2回收函数8第四章 测试124.1 预测试124.2 实际运行结果（截图）13第五章 总结17参考文献18第一章 背景研究1.1课题简介操作系统是当代计算机软件系统的核心，是计算机系统的基础和支撑，它管理和控制着计算机系统中的所有软、硬件资源，可以说操作系统是计算机系统的灵魂。操作系统课程是计算机专业学生必须学习和掌握的基础课程, 是计算机应用人员深入了解和使用计算机的必备知识, 是进行系统软件开发的理论基础，也是计算机科学与技术专业的一门理论性和实践性并重的核心主干课程。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。通过本次课程设计熟悉主存空间的分配与回收，所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时，将作业或进程所占用的主存空间归还给系统。采用可变式分区管理，使用最佳适应算法实现主存的分配与回收。深入研究此算法有助于我们全面的理解内存的分配原理，培养我们逻辑思维能力。1.2 设计要求设计多个作业或进程动态请求内存资源的模拟系统，使用最佳适应算法实现内存的分配与回收，实现可变式分区管理；设计相应的内存分配算法，定义相关数据结构，以及输出显示每次请求分配内存的结果和内存的已分配和未分配的状况。1.3概念原理 可变式分区管理的原理：区域的大小及起始地址是可变的，根据程序装入时的大小动态地分配一个区域。保证每个区域之中刚好放一个程序。这样可以充分地利用存储空间，提高内存的使用效率。如果一个程序运行完毕，就要释放出它所占有的分区，使之变成空闲区。这样就会出现空闲区与占用区相互交错的情况。这样就需要P表，F表来分别表示内存的占用区状态与空闲区的状态。最佳适应性算法，所谓“最佳”是指每次为作业分配内存时，总能把满足要求、有是最小的空闲分区分配给作业，避免“大材小用”。该算法要求从小到大的次序组成空闲区可用表或自由链。当用户作业或进程申请一个空闲区时，先检查空闲区可用表或自由链的第一个空闲区大小是否大于或等于所要求的内存长度，若可用表或自由链的第一个项长度小于所要求的，则分配失败，否则从空闲区可用表或自由链中分配相应的存储空间给用户，然后修改和调整可用表或自由链。1.4 环境说明和使用工具工具：C+语言在windows Xp环境下使用vc+6.0 ， visio进行开发。第二章 详细设计2.1功能介绍2.1.1分配函数发fenpei()的执行过程（最佳适应算法）A:查找空闲表F，在其中找到一个满足要求的空闲块。如果没有找到则提示用户。B:申请一个新的P结点，进行填写相关的数据，将其挂接在P表的尾部。C:修改原空闲区结点，并将其从F表中提出来。D:将修改后的结点插入到合适的位置，保证F表中的结点是按地址空间的大小由小到大的进行排序。E:返回新生成的P结点的首地址。2.1.2回收进程空间所占的函数free()的执行过程 A:查找P表，找到需要回收的程序的占用区的结点。将它提出P表。B:生成一个空的结点，填写。表示新生成了一个空闲区。C:观察F表，看其中是否有旧的空闲区和新的空闲区相邻。如果有，就将他与新的空闲区结点合并成一个大的空闲区。D:将新生成的空闲区结点插入到F表中合适的位子。2.2函数的规格说明2.2.1打印分配表空闲表函数 print()A 形参个数和类型：无形参B 函数的返回类型：int型C 函数的前提条件是什么：D 函数的功能：打印分配表空闲表函数2.2.2为进程分配空间函数 fenpei(char *c, struct node *p,struct node *f)A 形参个数和类型：字符串类型的C， 结构体指针指向P,FB 函数的返回类型：int型C 函数的前提条件是什么：之前要建立结构体并声明需要的全局变量D 函数的功能：按最佳适应算法分配内存空间2.2.3回收进程所占空间函数struct node * free(char *c, struct node *p,struct node *f)A 形参个数和类型：结构体定义的结点指针B 函数的返回类型：struct node *型C 函数的前提条件是什么：按之前写的fenpei算法已经分配了内存空间D 函数的功能：回收内存2.3 主要数据结构 A 用一个数组unsigned char memory1024 模拟1K内存B 用单链表建立结点模拟分配表与空闲表 Struct node Char name10;Int start ,length;Struct node *next;Struct node *p,*f;C 确定头结点 P=(struct node *)malloc(sizeof(struct node); p-next=NULL;f=(struct node *)malloc(sizeof(struct node); f-next=(struct node *)malloc(sizeof(struct node); f-next-start=0; f-next-length=1024; f-next-next=NULL;2.4 流程图 图 2-1 使用Microsoft Visio制图 main（）流程图第三章 核心算法的实现3.1 分配函数 void apply(block *task,string job1,int job22,string wait1,int wait2) /*作业申请*/string name;int datasize,i,flag=0;block *p;cout 请输入作业名称和大小： name datasize; /*作业名称和大小*/p=task;if(datasize100)cout作业大小超过分区最大空间100KBnext!=NULL;p=p-next)if(p-next-size=datasize & p-next-state=0)flag=1; cout 作业name使用了地址nextaddressK中的datasizeKB。next-size=p-next-size-datasize; /*使用分区空间*/if(p-next-size=0)p-next-state=1; /*分区空间完全被占用*/addjob(job1,job2,name,p-nextaddress,datasize);break;if(flag=0) /*分区无足够空闲资源，作业进入等待状态*/cout 分区无足够空闲资源，作业进入等待状态endl;for(i=0;i10;i+)if(wait2i=0) /*等待作业列表登记*/wait1i=name;wait2i=datasize;break;void adjust(block *task,string job1,int job22,string wait1,int wait2) /*等待作业执行函数*/block *p;int i;for(i=0;inext!=NULL;p=p-next)if(p-next-size=wait2i)p-next-size-=wait2i; /*等待作业使用空闲分区*/if(p-next-size=0)p-next-state=1;addjob(job1,job2,wait1i,p-nextaddress,wait2i); /*作业由等待作业列表转入执行作业列表*/cout 等待作业wait1i使用了地址nextaddressK中的wait2iKB。next ; p2 = p; /p2是p1是跟随指针 while(p1!= NULL) /按外界提供的程序名在P表中查找其结点，若没找到，则返回NULL if (!(strcmp(p1-name,c) break; p1 = p1-next; p2 = p2-next; /end while if (p1=NULL) printf(没找到该进程!n); return (NULL); /end if p2-next = p1-next ; /将找到的结点取出 f1 = (struct node *)malloc(sizeof(struct node);/据此生成一个新的空闲结点 f1-start = p1-start ; f1-length = p1-length; /在F表中依次观察各个结点，看是否能与此新的空闲结点合并 f2 = f-next; f3 = f; while (f2!= NULL) if (f1-start + f1 -length = f2-start) f1-length += f2-length; f3-next = f2-next; f2 = f2-next; /end if else if (f2-start + f2-length = f1-start ) f1-start = f2 -start; f1 -length += f2-length; f3 -next = f2 -next ; f2 = f2-next; /end else if else f2=f2-next ; f3 = f3-next; /end else /end while f2 = f; /再寻找一个合适的地方插入此空闲结点 while (f2-next!=NULL)&(f2-next-lengthlength) f2 = f2-next; f1-next = f2-next; f2-next = f1; return (f1); /返回值 /end free 图3-2 回收函数第四章 测试4.1 预测试这是预先假设运行结果的。例 (1)分四步 分配内存分配表P name start length aa 1 12 bb 13 25 cc 38 90 dd 128 22空闲区F start length150 875（2）回收输入要回收的进程名 ： CC分配表P name start length aa 1 12 bb 13 25 dd 128 22空闲区F start length 38 90150 875输入要回收的进程名：AA分配表P name start length bb 13 25 dd 128 22空闲区F start length 1 12 38 90150 875 4.2 实际运行结果（截图）注：这里是针对代码本身的测试，可以看做是白盒测试。（1）程序主界面 图 4-1 程序主界面 （2）依次创建进程注：本例创建四个进程，但此程序可以在开辟的内存范围内申请任意多个进程 图 4-2 创建进程AA 图 4-3 创建进程BB 图 4-4 创建进程 CC 图 4-5 创建进程 DD（3）作业显示 图 4-6 作业显示 图 4-7 回收进程AA (4)退出 图 4-8 没有找到要回收的进程8 通过测试，此程序满足模拟内存的分配与回收要求。第五章 总结通过本次OS课设，让我对内存的分配与回收有了更为深刻的认识，尤其是对可变式分区管理的认识，区域的大小及起始地址是可变的，根据程序装入时的大小动态地分配一个区域。保证每个区域之中刚好放一个程序。这样可以充分地利用存储空间，提高内存的使用效率。如果一个程序运行完毕，就要释放出它所占有的分区，使之变成空闲区。提高了内存的使用效率，进而提高计算机的整体工作效率。在设计过程中，查询了不少相关资料，不断的发现问题、提出问题、解决问题。在对自己所编写的源程序段的纠错的过程中，使我更好的理解了操作系统中文件系统的理论知识，同时在编程时用到了模块化的设计思想，这种编程方法可以使我们的编程变的更简单，可以使我们的查错与纠错变的更方便。与面向对象编程方法学各有所长。更为重要的是，以前往往忽略了软件程序的需求分析的重要性，认为程序开发就是盲目的写代码，而忽略了之前的需求分析，只有正确的进行了需求分析才能准确的理解课题，设计出用户满意的程序。最后，操作系统是计算机系统的核心，他负责控制和管理整个计算机系统的软硬件资源，使之协调工作。这里深刻理解内存的分配与回收显得尤为重要，这是计算机系统的核心的核心，因为不论计算机怎样发展，都遵循这冯诺依曼计算机。第六章 附录源代码：#include #include using namespace std;typedef struct block /*分区结构*/int size; /*分区大小*/int state; /*分区状态：0为空闲，1为被占用*/int prioraddress; /*指向上一个分区地址*/int nextaddress; /*指向下一个分区地址*/struct block * prior;struct block * next;block;void addjob(string job1,int job22,string name,int nextaddress,int datasize) /*作业添加到执行作业列表*/for(int i=0;job2i1!=0;i+)job1i=name; job2i0=nextaddress;job2i1=datasize;void init(block *task) /*初始化函数*/block *p,*q;p=task;p-prior=NULL;p-prioraddress=0;p-size=0;p-state=0;p-nextaddress=20; /*第一个分区地址20K*/q=(block*)malloc(sizeof(block); /*创建第一个分区*/q-prior=NULL;q-prioraddress=0;q-size=20; /*第一个分区长度20KB*/q-state=0;q-nextaddress=80; /*第二个分区地址80K*/p-next=q;p=p-next;q=(block*)malloc(sizeof(block); /*创建第二个分区*/q-prior=p;q-prioraddress=20; /*第一个分区地址20K*/q-size=50; /*第二个分区长度50KB*/q-state=0;q-nextaddress=150; /*第三个分区地址150K*/p-next=q;p=p-next;q=(block*)malloc(sizeof(block); /*创建第三个分区*/q-prior=p;q-prioraddress=80; /*第二个分区地址80K*/q-size=100; /*第三个分区长度100KB*/q-state=0;q-nextaddress=300; /*第四个分区地址300K*/p-next=q;p=p-next;q=(block*)malloc(sizeof(block); /*创建第四个分区*/q-prior=p;q-prioraddress=150; /*第三个分区地址150K*/q-size=30; /*第四个分区长度30KB*/q-state=0;q-nextaddress=600; /*第五个分区地址600K*/p-next=q;p=p-next;q=(block*)malloc(sizeof(block); /*创建第五个分区*/q-prior=p;q-prioraddress=300; /*第四个分区地址300K*/q-size=100; /*第二个分区长度100KB*/q-state=0;q-next=NULL;q-nextaddress=0;p-next=q;p=p-next;void apply(block *task,string job1,int job22,string wait1,int wait2) /*作业申请*/string name;int datasize,i,flag=0;block *p;cout 请输入作业名称和大小： name datasize; /*作业名称和大小*/p=task;if(datasize100)cout作业大小超过分区最大空间100KBnext!=NULL;p=p-next)if(p-next-size=datasize & p-next-state=0)flag=1; cout 作业name使用了地址nextaddressK中的datasizeKB。next-size=p-next-size-datasize; /*使用分区空间*/if(p-next-size=0)p-next-state=1; /*分区空间完全被占用*/addjob(job1,job2,name,p-nextaddress,datasize);break;if(flag=0) /*分区无足够空闲资源，作业进入等待状态*/cout 分区无足够空闲资源，作业进入等待状态endl;for(i=0;i10;i+)if(wait2i=0) /*等待作业列表登记*/wait1i=name;wait2i=datasize;break;void adjust(block *task,string job1,int job22,string wait1,int wait2) /*等待作业执行函数*/block *p;int i;for(i=0;inext!=NULL;p=p-next)if(p-next-size=wait2i)p-next-size-=wait2i; /*等待作业使用空闲分区*/if(p-next-size=0)p-next-state=1;addjob(job1,job2,wait1i,p-nextaddress,wait2i); /*作业由等待作业列表转入执行作业列表*/cout 等待作业wait1i使用了地址nextaddressK中的wait2iKB。endl;wait1i=0;wait2i=0;break;void setfree(block *task,string job1,int job22,string wait1,int wait2) /*作业结束*/int i,flag;string name;block *p;p=task;cout 请输入需要结束的作业名称：name; /*输入完成的作业名称*/for(i=0,flag=0;inext!=NULL;p=p-next)if(p-nextaddress=job2i0) /*/p-next-size+=job2i1; /*释放作业占用的空间*/p-next-state=0; /*恢复分区空闲状态*/cout 已经释放job2i1KB到地址nextaddressK中。endl;job1i=0; /*从执行作业列表中删除已完成的作业*/job2i0=job2i1=0;break;break;if(flag=0) /*执行作业列表查找失败*/cout未找到作业！endl;adjust(task,job1,job2,wait1,wait2); /*添加到执行作业列表*/void print(block *p) /*打印函数*/cout | - | endl;cout | 地址 内存 | endl;cout | - | next!=NULL;p=p-next)if(p-next-state=0)printf( | %3dK %3dKB |n,p-nextaddress,p-next-size);cout