如果我告白的话内存的申请和释放

2020年12月13日发(作者：闵豫)

计算机学院网络工程专业
操作系统课程设计

题目：内存的申请和释放
班级：网工11102班
姓名：郭阳学号： 2
同组人姓名：
起迄日期: 第一周，第二周
课程设计地点: 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
二、设计要求
定义一个自 由存储块链表，按块地址排序，表中记录块的大小。当请求分配内存时，扫描
自由存储块链表，知道找到 一个足够大的可供分配的内存块，若找到的块的大小正好等于所
请求的大小时，就把这一块从自由链表中 取下来，返回给申请者。若找到的块太大，即对其
分割，并从该块的高地址不分往低地址部分分割，取出 大小合适的块返还给申请者，愈小的
低地址部分留在链表中。若找不到足够大的块，就从操作系统中请求 另外一个足够大的内存
区域，并把它连接到自由块链表中，然后再继续搜索。
释放存储 块也要搜索自由链表，目的是找到适当的位置将要释放的块插进去，如果被释
放的块的任何一边与链表中 的某一块临接，即对其进行合并操作，直到没有合并的临接块为
止，这样可以防止存储空间变得零碎。。
三、实验基本原理
分区存储管理是给内存中的进程划分适当大小的存储区，以连续存储各进程 的程序和数
据，使各进程能并发地执行。最优适应分配算法扫描整个未分配区表或链表，从空闲区中挑< br>选一个能满足用户进程要求的最小分区进行分配。
在可变分区模式下，在系统初启且 用户作业尚未装入主存储器之前，整个用户区是一
个大空闲分区，随着作业的装入和撤离，主存空间被分 成许多分区，有的分区被占用，而有
的分区时空闲的。为了方便主存空间的分配和去配，用于管理的数据 结构可由两张表组成：
“已分配区表”和“未分配区表”。在“未分配表中”将空闲区按长度递增顺序排 列，当装
入新作业时，从未分配区表中挑选一个能满足用户进程要求的最小分区进行分配。这时从已分配表中找出一个空栏目登记新作业的起始地址和占用长度，同时修改未分配区表中空闲区
的长度和 起始地址。当作业撤离时已分配区表中的相应状态变为“空”，而将收回的分区登
记到未分配区表中，若 有相邻空闲区再将其连接后登记。可变分区的回收算法较为复杂，当
一个作业撤离时，可分为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
#include
#include

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);
void display(space *pbc);
定义内存空间结构体
申明结构体指针
定义进程结构体
申明结构体指针
申明callback()函数原型
申明display()函数原型






void display(work *S);

void allocate() 内存分配函数实现
{
work *q,*w;
q=new work; 申请分配用于存放work类型的数据的内存空间
cout<<请输入进程名和占用空间大小:
cin>>q->name>>q->length;
if(q->length<=0) 判断输入进程的合法性
{
cout<<进程错误.
delete q; 进程错误，释放内存空间
return;
}
w=S;
while(w->next!=NULL) 进程链不为空
{
if(strcmp(w->next->name, q->name)==0) 判断进程名是否已经存在
{
cout<<此进程名已经存在! 进程名已经存在，返回
return;
}
w=w->next;
}
if(w->next==NULL) 进程名不存在，继续进行内存分配
{ space *p,*r;
p=pbc;
r=p;
while(p->next!=NULL&&p->next->lengthlength) 在空间链中寻找第一个大于
所输入的进程大小的空闲块
{
r=p;
p=p->next;
}
if(p->next==NULL) 空闲链中无大于所输入进程空间大小的空闲块
{
cout<<空间不足，分配失败！
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<<此进程不存在!进程链中无与用户要求回收的进程名相同的进程
}
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<<回收完毕!
display(pbc); 显示回收完后的空闲链
display(S); 显示回收完后的进程链
return;
}
p=pbc->next;
while(p!=NULL&&p->startaddressstartaddress) 在空闲链表中寻找插入新的
空闲区的合适位置
{
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<<回收完毕!
display(pbc); 显示回收后的空闲链
display(S); 显示回收后的进程链
return;
}
if( (q==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->next; 修改进程链，删除所回收的进程
delete w;
cout<<回收完毕!
display(pbc); 显示回收后的空闲链
display(S); 显示回收后的进程链
return;
}
if((q!=NULL)&&(q->startadd ress+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->st artaddress+n==p->startaddress)) 下邻空
{
p->startaddress-=n; 修改下邻起始地址
p->length+=n; 将该空闲快与下邻合并
t->next=w->next;
delete w;
}

else if((q!=NUL L)&&(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<<回收完毕!
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->lengthlength))
{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->s tartaddressstartaddress))
{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< if(t==NULL)
{ cout<<无空闲区了.
while(t!=NULL)
{
cout<<起始地址:长度:
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;
whi le((q!=NULL)&&(q->startaddressstartaddress)) 按从小到大
{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< if(t==NULL)
{ cout<<内存中无进程.
while(t!=NULL)
{
cout<<进程名:起始地址:长
度:
t=t->next;
}
cout<}

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<<



<<·最佳适应算法模拟内存分配与回收·
cout< cout<<····························
cout<<功能选项:分配内存



<<回收内存退出
cout<<····························
while(1){ 循环选择功能
cout< cin>>b;



{
switch(b)
case 0: allocate(); break; 功能0：进行内存分配
case 1: requireback(); break; 功能1: 进行内存回收
case 2: break; 功能2: 退出
}
}
}
六、运行结果
1、测试用例与程序运行结果截图


程序运行结果：分配成功


程序运行结果：回收成功

七、总结
在做 课程设计的过程中我遇到了不少问题，比如链表指针部分就很容易搞
混，而且很多地方不容易考虑全面， 比如内存回收时空闲区的合并部分，要考虑
释放的内存空间前后是否为空闲区，若是，如何来合并，如果 释放的内存块是链
表的最后一个，或是链表的倒数第二个，则这两种情况要单独讨论，因为当内存
空间释放后存在一个后向指针的定义问题，若是在链表中间，则可以直接指定,
但若是在链表的末尾， 则要指定为NULL，另外若用的是最佳适应算法，进行内
存回收时还有考虑前后空闲块地址是否相接， 因为它是按照块的大小排序的，若
不相接，即使两个块在链表中的位置相邻，也不能合并，而且要注意每 次分配或
释放空间后都要对链表进行排序，这是由算法思想决定的，这些条件都是在做的
过程中 逐步完善的，所遇到的这些问题通过问老师、查阅资料得以解决。
题目做完后，我对内存动态分区部分 又有了更加深刻的理解，我个人的编程
能力也得到了一定程度的提高，在课堂上我们只是听老师把理论知 识给讲了一
遍，课下很快就忘了，通过做课程设计，我们把它真正的实现出来，这样印象就
更深 了，而且不仅仅局限于理论层次，也提高了我们分析问题、解决问题的能力，
希望以后我们可以有更多的 机会来做这些东西。

八、参考文献

1、人民邮电出版社 宗大华《操作系统教程》
2、清华大学出版社出版的 严蔚敏《数据结构》（c语言版）
3.、清华大学出版社出版的 李爱华《c++语言程序设计》