课程设计题目：主存空间的分配与回收学生姓名：学院：信息工程学院系别：计算机系专业：计算机科学与技术班级：计算机指导教师：副教授副教授2011年月日内蒙古工业大学课程设计任务书（三）学院（系）：信息学院计算机系课程名称：操作系统课程设计指导教师（签名）：专业班级：计算机09-2 学生姓名：学号：目录第一章背景研究 (1)1.1课题简介 (1)1.2 设计要求 (1)1.3概念原理 (1)1.4 环境说明和使用工具 (2)第二章详细设计 (2)2.1功能介绍 (2)2.1.1分配函数发fenpei()的执行过程（最佳适应算法） (2)2.1.2回收进程空间所占的函数free()的执行过程 (2)2.2函数的规格说明 (3)2.2.1打印分配表空闲表函数 print() (3)2.2.2为进程分配空间函数 fenpei(char *c, struct node *p,struct node*f) (3)2.2.3回收进程所占空间函数struct node * free(char *c, struct node*p,struct node *f) (3)2.3 主要数据结构 (3)2.4 流程图 (5)第三章核心算法的实现 (6)3.1 分配函数 (6)3.2回收函数 (11)第四章测试 (15)4.1 预测试 (15)4.2 实际运行结果（截图） (16)第五章总结 (18)参考文献 (25)第一章背景研究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 memory[1024] 模拟1K内存B 用单链表建立结点模拟分配表与空闲表Struct node{Char name[10];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 job2[][2],string wait1[],int wait2[]) /*作业申请*/{string name;int datasize,i,flag=0;block *p;cout << "请输入作业名称和大小："<< endl;cin >> name >> datasize; /*作业名称和大小*/p=task;if(datasize>100){cout<<"作业大小超过分区最大空间100KB"<<endl; /**/}else{for(;p->next!=NULL;p=p->next){if(p->next->size>=datasize && p->next->state==0){flag=1;cout <<"作业"<<name<<"使用了地址"<<p->nextaddress<<"K中的"<<datasize<<"KB。
"<<endl;p->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;i<10;i++){if(wait2[i]==0) /*等待作业列表登记*/{wait1[i]=name;wait2[i]=datasize;break;}}}}}void adjust(block *task,string job1[],int job2[][2],string wait1[],int wait2[]) /*等待作业执行函数*/{block *p;int i;for(i=0;i<10;i++){if(wait2[i]!=0){for(p=task;p->next!=NULL;p=p->next){if(p->next->size>=wait2[i]){p->next->size-=wait2[i]; /*等待作业使用空闲分区*/if(p->next->size==0){p->next->state=1;}addjob(job1,job2,wait1[i],p->nextaddress,wait2[i]); /*作业由等待作业列表转入执行作业列表*/cout <<"等待作业"<<wait1[i]<<"使用了地址"<<p->nextaddress<<"K中的"<<wait2[i]<<"KB。
"<<endl;wait1[i]='\0';wait2[i]=0;break;}}}}}图3-1 分配函数3.2回收函数struct node *free(char *c, struct node *p,struct node *f) {struct node *p1, *p2, *f1, *f2, *f3;p1 = p->next ;p2 = p; //p2是p1是跟随指针while(p1!= NULL)//按外界提供的程序名在P表中查找其结点，若没找到，则返回NULL {if (!(strcmp(p1->name,c))) break;p1 = p1->next;p2 = p2->next;}//end whileif (p1==NULL){printf("没找到该进程!!!\n");return (NULL);}//end ifp2->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 ifelse if (f2->start + f2->length == f1->start ){f1->start = f2 ->start;f1 ->length += f2->length;f3 ->next = f2 ->next ;f2 = f2->next;}//end else ifelse{f2=f2->next ; f3 = f3->next;}//end else}//end whilef2 = f; //再寻找一个合适的地方插入此空闲结点while ((f2->next!=NULL)&&(f2->next->length<=f1->length)) f2 = f2->next;f1->next = f2->next;f2->next = f1;return (f1); //返回值}//end free图3-2 回收函数第四章测试4.1 预测试这是预先假设运行结果的。