计算机学院网络工程专业操作系统课程设计题目：内存的申请和释放班级：网工11102班姓名：郭阳学号：201117030216 同组人姓名：起迄日期: 第一周，第二周课程设计地点: E3——A513指导教师：贺玉才评阅意见：成绩评定：评阅人：日期：完成日期：2014年3月目录一、概述 (3)1、设计目的 (3)2、开发环境 (3)二、设计要求 (3)三、实验基本原理 (3)四、程序流程图 (4)1、整体程序流程图 (4)2、内存分配ALLOCATE()流程图 (5)五、源程序 (6)1、数据结构 (6)2、主要功能函数 (6)3、源程序代码 (7)六、运行结果 (17)1、测试用例与程序运行结果截图 (17)2、内存分配正确测试.................................................................... 错误!未定义书签。

3、内存回收错误测试.................................................................... 错误!未定义书签。

4、内存回收正确测试用例............................................................ 错误!未定义书签。

七、总结 (18)八、参考文献 (18)一、概述1、设计目的了解操作系统的内存分配的方法2、开发环境WINDOWS环境Visual C++6.0二、设计要求定义一个自由存储块链表，按块地址排序，表中记录块的大小。

当请求分配内存时，扫描自由存储块链表，知道找到一个足够大的可供分配的内存块，若找到的块的大小正好等于所请求的大小时，就把这一块从自由链表中取下来，返回给申请者。

若找到的块太大，即对其分割，并从该块的高地址不分往低地址部分分割，取出大小合适的块返还给申请者，愈小的低地址部分留在链表中。

若找不到足够大的块，就从操作系统中请求另外一个足够大的内存区域，并把它连接到自由块链表中，然后再继续搜索。

释放存储块也要搜索自由链表，目的是找到适当的位置将要释放的块插进去，如果被释放的块的任何一边与链表中的某一块临接，即对其进行合并操作，直到没有合并的临接块为止，这样可以防止存储空间变得零碎。

三、实验基本原理分区存储管理是给内存中的进程划分适当大小的存储区，以连续存储各进程的程序和数据，使各进程能并发地执行。

最优适应分配算法扫描整个未分配区表或链表，从空闲区中挑选一个能满足用户进程要求的最小分区进行分配。

在可变分区模式下，在系统初启且用户作业尚未装入主存储器之前，整个用户区是一个大空闲分区，随着作业的装入和撤离，主存空间被分成许多分区，有的分区被占用，而有的分区时空闲的。

为了方便主存空间的分配和去配，用于管理的数据结构可由两张表组成：“已分配区表”和“未分配区表”。

在“未分配表中”将空闲区按长度递增顺序排列，当装入新作业时，从未分配区表中挑选一个能满足用户进程要求的最小分区进行分配。

这时从已分配表中找出一个空栏目登记新作业的起始地址和占用长度，同时修改未分配区表中空闲区的长度和起始地址。

当作业撤离时已分配区表中的相应状态变为“空”，而将收回的分区登记到未分配区表中，若有相邻空闲区再将其连接后登记。

可变分区的回收算法较为复杂，当一个作业撤离时，可分为4种情况：其临近都有作业（A和B）,其一边有作业（A或B），其两边均为空闲区。

尤其重要的是，在程序中利用“new 类型T(初值列表)”申请分配用于存放T类型数据的内存空间，利用“delete 指针名”释放指针所指向的内存空间。

四、程序流程图1、整体程序流程图2、内存分配allocate()流程图五、源程序1、数据结构（1）内存块struct space //定义内存空间结构体{long startaddress;long length;struct space *next;};space *pbc;（2）、作业块struct work //定义进程结构体{char name[20];long startaddress;long length;struct work *next;};work *S;2、主要功能函数allocate() ：实现内存分配，并在当中调用display(pbc)，以及display(S) 两个函数显示内存分配完后的空闲块链表和进程链表情况。

requireback()：实现内存回收，在满足情况的条件下调用allocate()对用户申请的内存块进行回收并在当中调用display(pbc)，以及display(S)显示内存回收完后的空闲块链表和进程链表情况。

callback()：按内存回收时的四种情况对内存进行回收。

display(pbc)：对空闲块链表中的空闲块进行从小到大排序并显示空闲链情况。

display(S)：对进程链表中的进程进行从小到大排序并显示进程链情况。

main()：创建并初始化空闲块链表和进程链链表，用户选择操作功能3、源程序代码#include <iostream.h>#include<string.h>#include <stdio.h>struct space //定义内存空间结构体{long startaddress;long length;struct space *next;};space *pbc; //申明结构体指针struct work //定义进程结构体{char name[20];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 work; //申请分配用于存放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->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==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->next->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); //显示进程链情况}void requireback(){ //用户申请进程回收函数char name[20];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<<"此进程不存在!"<<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; //将所要回收的进程大小赋给该空间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=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==NULL)&&(w->startaddress+n!=p->startaddress)) //q为空，且该空间的结束地址不是下临的结束地址{space *sp=new space; //申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针sp sp->startaddress=w->startaddress; //将该空间的起始地址赋给spsp->length=n; //将该空间的大小赋给spsp->next=pbc->next; //将sp插入空闲链中pbc->next=sp;t->next=w->next; //修改进程链，删除所回收的进程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->length=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->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; //将缩回收的进程大小赋给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=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;while(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==NULL){ 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){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<<"内存中无进程."<<endl; return;}while(t!=NULL){cout<<"进程名:"<<t->name<<"起始地址:"<<t->startaddress<<"长度:"<<t->length<<endl;t=t->next;}cout<<endl;}void main(){pbc=new space; //申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针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<<" "<<" "<<" "<<" "<<" "<<" "<<" "<<" "<<" "<<" "<<" "<<" "<<" "<<" "<<" "<<"·"<<"最佳适应算法模拟内存分配与回收"<<"·"<<endl;cout<<endl;cout<<"·····························"<<endl;cout<<"功能选项:"<<" "<<" "<<" "<<" "<<" "<<" "<<"0:分配内存"<<" "<<" "<<" "<<" "<<" "<<"1:回收内存"<<" "<<" "<<" "<<" "<<" "<<"2:退出"<<endl;cout<<"·····························"<<endl;while(1){ //循环选择功能cout<<endl<<"请按键选择：";cin>>b;switch(b){case 0: allocate(); break; //功能0：进行内存分配case 1: requireback(); break; //功能1: 进行内存回收case 2: ;break; //功能2: 退出}}六、运行结果1、测试用例与程序运行结果截图程序运行结果：分配成功程序运行结果：回收成功七、总结在做课程设计的过程中我遇到了不少问题，比如链表指针部分就很容易搞混，而且很多地方不容易考虑全面，比如内存回收时空闲区的合并部分，要考虑释放的内存空间前后是否为空闲区，若是，如何来合并，如果释放的内存块是链表的最后一个，或是链表的倒数第二个，则这两种情况要单独讨论，因为当内存空间释放后存在一个后向指针的定义问题，若是在链表中间，则可以直接指定,但若是在链表的末尾，则要指定为NULL，另外若用的是最佳适应算法，进行内存回收时还有考虑前后空闲块地址是否相接，因为它是按照块的大小排序的，若不相接，即使两个块在链表中的位置相邻，也不能合并，而且要注意每次分配或释放空间后都要对链表进行排序，这是由算法思想决定的，这些条件都是在做的过程中逐步完善的，所遇到的这些问题通过问老师、查阅资料得以解决。