操作系统课程设计报告--最佳适应算法模拟实现内存分配与回收

1、衡阳师范学院工科课程设计 -操作系统课程设计报告实验题目：最佳适应算法模拟实现内存分配与回收 学 号： 07190132 20 08 07 姓 名： 王果 刘芳麟 何超英 高超 班级： 0701 指导教师： 陈琼 日 期： 2009 年 12 月目 录 一、概述3 1设计目的3 2开发环境33任务分配3二、需求分析3三、实验基本原理41可变分区存储管理之最优适应分配算法的概念42关于最优适应分配算法的一些基本原理4四、数据结构设计4 1内存块与作业块4 2程序流程图5 2.1整体程序流程图5 2.2内存分配allocate()流程图6 2.3内存回收callback()流程图7五、算

2、法的实现7 1程序主要功能函数设计思想7 2源程序清单83测试用例与程序运行结果截图18六、总结21 1经验总结212心得与体会21七、参考文献2225一、概述1、设计目的（1）了解多道程序系统中，多个进程并发执行的内存资源分配。 （2）模拟可变分区存储管理算法实现分区管理的最佳适应分配算法（3）利用最佳适应算法动态实现内存分配与回收（3）通过实现最佳算法来进一步了解动态分区模式的优缺点。 （4）掌握最佳适应分配算法，深刻了解各进程在内存中的具体分配策略。 2、开发环境PC机DOS;WINDOWS环境Visual C+6.0 for Windows3、任务分配设计人员设计任务王果程序总体设计，

3、部分内存回收的实现，上机编码和调试，程序后期优化刘芳麟部分内存分配的实现，编写文档，设计测试用例何超英部分内存分配的实现，编写文档，数据结构设计高超部分内存回收的实现，资料收集，需求分析   二、需求分析克服固定分区中的主存资源的浪费，有利于多道程序设计，提高主存资源的利用率。 三、实验基本原理、可变分区存储管理之最优适应算法分配的概念：分区存储管理是给内存中的进程划分适当大小的存储区，以连续存储各进程的程序和数据，使各进程能并发地执行。最优适应分配算法扫描整个未分配区表或链表，从空闲区中挑选一个能满足用户进程要求的最小分区进行分配。2、关于最优适应的一

4、些基本原理： 在可变分区模式下，在系统初启且用户作业尚未装入主存储器之前，整个用户区是一个大空闲分区，随着作业的装入和撤离，主存空间被分成许多分区，有的分区被占用，而有的分区时空闲的。为了方便主存空间的分配和去配，用于管理的数据结构可由两张表组成：“已分配区表”和“未分配区表”。在“未分配表中”将空闲区按长度递增顺序排列，当装入新作业时，从未分配区表中挑选一个能满足用户进程要求的最小分区进行分配。这时从已分配表中找出一个空栏目登记新作业的起始地址和占用长度，同时修改未分配区表中空闲区的长度和起始地址。当作业撤离时已分配区表中的相应状态变为“空”，而将收回的分区登记到未分配区表中，若有相邻空闲区

5、再将其连接后登记。可变分区的回收算法较为复杂，当一个作业撤离时，可分为4种情况：其临近都有作业（A和B）,其一边有作业（A或B），其两边均为空闲区。尤其重要的是，在程序中利用“ new 类型T(初值列表)”申请分配用于存放T类型数据的内存空间，利用 “delete 指针名”释放指针所指向的内存空间。 四、数据结构设计1、（1）内存块struct space /定义内存空间结构体 long startaddress; long length; struct space *next;space *pbc; （2）作业块struct work /定义进程结构体 char name20; long s

6、tartaddress; long length; struct work *next;work *S; 2、程序流程图 2.1、整体程序流程图2.2、内存分配allocate()流程图2.3、内存回收callback()流程图五、算法的实现1、程序主要功能函数设计思想 allocate() ： 实现内存分配，并在当中调用display(pbc)，以及display(S) 两个函数显示内存分配完后的空闲块链表和进程链表情况。 requireback()： 实现内存回收，在满足情况的条件下调用allocate()对用户申请的内存块进行回收并在当中调用display(pbc)，以及display(

7、S)显示内存回收完后的空闲块链表和进程链表情况。 callback()： 按内存回收时的四种情况对内存进行回收。display(pbc)： 对空闲块链表中的空闲块进行从小到大排序并显示空闲链情况。display(S)： 对进程链表中的进程进行从小到大排序并显示进程链情况。main()： 创建并初始化空闲块链表和进程链链表，用户选择操作功能2、程序清单#include <iostream.h>#include<string.h>#include <stdio.h>struct space /定义内存空间结构体 long startaddress; long l

8、ength; struct space *next;space *pbc; /申明结构体指针struct work /定义进程结构体 char name20; long startaddress; long length; struct work *next;work *S; /申明结构体指针void callback(work *r); /申明callback()函数原型void display(space *pbc); /申明display()函数原型void display(work *S); void allocate() /内存分配函数实现 work *q,*w; q=new wor

9、k; /申请分配用于存放work类型的数据的内存空间 cout<<"请输入进程名和占用空间大小:"<<endl; cin>>q->name>>q->length; if(q->length<=0) /判断输入进程的合法性 cout<<"进程错误."<<endl; delete q; /进程错误，释放内存空间 return; w=S; while(w->next!=NULL) /进程链不为空 if(strcmp(w->next->name, q

10、->name)=0) /判断进程名是否已经存在 cout<<"此进程名已经存在!"<<endl; /进程名已经存在，返回 return; w=w->next; if(w->next=NULL) /进程名不存在，继续进行内存分配 space *p,*r; p=pbc; r=p; while(p->next!=NULL&&p->next->length<q->length) /在空间链中寻找第一个大于所输入的进程大小的空闲块 r=p; p=p->next; if(p->next=

11、NULL) /空闲链中无大于所输入进程空间大小的空闲块 cout<<"空间不足，分配失败！"<<endl; delete q; /空间不足，分配失败，释放空间 return; else /找到第一个满足要求的空闲块 q->startaddress=p->next->startaddress; /将该空闲块的起始地址赋给所输入的进程 q->next=S->next; S->next=q; /将所输入的进程插入work链首。 p->next->length-=q->length; if(p->n

12、ext->length!=0) /该空闲块空间有剩余，改变该空闲块的起始地址 p->next->startaddress+=q->length; else /该空闲块空间无剩余 if(p->next->next!=NULL) /该空闲块不处于空闲链链尾 p->next=p->next->next; /删除该空闲块，修改空闲链 else r->next=NULL; /该空闲块处于空闲链链尾，修改空闲链 delete p->next; /释放该空闲块的空间 display(pbc); /显示空闲链情况 display(S); /显示

13、进程链情况 void requireback() /用户申请进程回收函数 char name20; cout<<"输入要回收的进程名：" cin>>name; work *p; p=S; while(p->next!=NULL) /进程链不为空 if(strcmp(p->next->name, name)=0) /寻找与用户要求回收的进程名相同的进程 callback(p); /调用进程回收函数，回收进程 return; p=p->next; if(p->next=NULL) cout<<"此进程不

14、存在!"<<endl; /进程链中无与用户要求回收的进程名相同的进程 void callback(work *t) /利用最佳适应算法实现进程回收 work *w; w=t->next; space *p=NULL,*q=NULL; long n; n=w->length; if(pbc->next=NULL) /空闲链为空 space *f=new space; /申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针f f->startaddress=0; /初始该空间首地址 f->length=n; /将所要回收的进程大小赋

15、给该空间 f->next=NULL; pbc->next=f; /将该空间块插入空闲链中 t->next=w->next; delete w; /释放空间 cout<<"回收完毕!"<<endl; display(pbc); /显示回收完后的空闲链 display(S); /显示回收完后的进程链 return; p=pbc->next; while(p!=NULL&&p->startaddress<w->startaddress) /在空闲链表中寻找插入新的空闲区的合适位置 q=p; p

16、=p->next; if(q=NULL)&&(w->startaddress+n=p->startaddress) p->startaddress-=n; /修改下邻起始地址 p->length+=n; /将该空闲块与下邻合并 t->next=w->next; /修改进程链，删除进程链中所要回收的进程 delete w; /释放空间 cout<<"回收完毕!"<<endl; display(pbc); /显示回收后的空闲链 display(S); /显示回收后的进程链 return; if(q

17、=NULL)&&(w->startaddress+n!=p->startaddress) /q为空，且该空间的结束地址不是下临的结束地址 space *sp=new space; /申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针sp sp->startaddress=w->startaddress; /将该空间的起始地址赋给sp sp->length=n; /将该空间的大小赋给sp sp->next=pbc->next; /将sp插入空闲链中 pbc->next=sp; t->next=w->nex

18、t; /修改进程链，删除所回收的进程 delete w; cout<<"回收完毕!"<<endl; display(pbc); /显示回收后的空闲链 display(S); /显示回收后的进程链 return; if(q!=NULL)&&(q->startaddress+q->length=w->startaddress)&&(w->startaddress+n=p->start address) /上下均空 q->next=p->next; /修改空闲链 q->leng

19、th=q->length+p->length+n; /将该空闲块与上下邻合并 t->next=w->next; /修改进程链，删除所回收的进程 delete w; /释放空间 else if(q!=NULL)&&(w->startaddress+n=p->startaddress) /下邻空 p->startaddress-=n; /修改下邻起始地址 p->length+=n; /将该空闲快与下邻合并 t->next=w->next; delete w; else if(q!=NULL)&&(q->

20、;startaddress+q->length=w->startaddress) /上邻为空 q->length+=n; /改变上邻的大小，将两个空闲块合并 t->next=w->next; /修改进程链，删除所回收的进程 delete w; /释放空间 else /上下邻都不为空 space *sp=new space; /申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针sp sp->startaddress=w->startaddress; /将所回收的进程首地址赋给sp sp->length=n; /将缩回收的进程大小赋给

21、sp sp->next=pbc->next; pbc->next=sp; /将sp插入空闲链链首 t->next=w->next; /修改进程链，删除所回收的进程 delete w; /释放空间 cout<<"回收完毕!"<<endl; display(pbc); /显示回收后的空闲块 display(S); /显示回收后的进程链 space *sa,*sd,*sf,*sk; sa=pbc->next; /空闲块从小到大排序 pbc->next=NULL; while(sa!=NULL) sd=pbc;sf=

22、pbc->next; while(sf!=NULL)&&(sf->length<sa->length) sd=sf;sf=sf->next; sk=sa->next; if(sf=NULL) sd->next=sa;sa->next=NULL; else sa->next=sf;sd->next=sa; sa=sk; void display(space *pbc) /空闲链显示函数实现 space *p,*q,*r,*e; p=pbc->next; /空闲块从小到大排序 pbc->next=NULL; w

23、hile(p!=NULL) r=pbc;q=pbc->next; while(q!=NULL)&&(q->startaddress<p->startaddress) r=q;q=q->next; e=p->next; if(q=NULL) r->next=p;p->next=NULL; else p->next=q;r->next=p; p=e; space *t=pbc->next; cout<<endl<<"可用空闲区："<<endl; if(t=NUL

24、L) cout<<"无空闲区了."<<endl; return; while(t!=NULL) cout<<"起始地址:"<<t->startaddress<<"长度:"<<t->length<<endl; t=t->next; void display(work *S) /进程链显示函数实现 work *p,*q,*r,*f; p=S->next; /进程链表排序 S->next=NULL; while(p!=NULL)

25、 r=S;q=S->next; while(q!=NULL)&&(q->startaddress<p->startaddress) /按从小到大 r=q;q=q->next; f=p->next; if(q=NULL) r->next=p;p->next=NULL; else p->next=q;r->next=p; p=f; work *t=S->next; cout<<endl<<"已分配进程："<<endl; if(t=NULL) cout<&l

26、t;"内存中无进程."<<endl; return; while(t!=NULL) cout<<"进程名:"<<t->name<<"起始地址:"<<t->startaddress<<"长度:"<<t->length<<endl; t=t->next; cout<<endl; void main() pbc=new space; /申请分配用于存放space类型的数据的内存空间,并将首地

27、址赋给指针pbc space *p=new space; /申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针p p->startaddress=0; /初始化p的起始地址 p->length=130; /初始花p的大小 p->next=NULL; pbc->next=p; /将pbc作为p的头指针，创建空闲链 S=new work; /创建进程链头指针 S->next=NULL; int b; cout<<" "<<" "<<" "<<&q

28、uot; "<<" "<<" "<<" "<<" "<<" "<<" " <<" "<<" "<<" "<<" "<<" "<<"·"<<"最佳适应算法模拟内存分配与回收&q

29、uot;<<"·"<<endl; cout<<endl; cout<<"·····························"<<endl; cout<<"功能选项:&qu

30、ot;<<" "<<" "<<" "<<" "<<" "<<" "<<"0:分配内存"<<" "<<" " <<" "<<" "<<" "<<"1:回收内存"<<" "<<" "<<" "<<" "<<" "<<"2:退出"<<endl; cout<<"·