动态内存分配
动态内存分配
一、实验目的
动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了四种分配算法，分别是1.首次适应算法，2.循环首次适应算法，3.最坏适应算法4.最佳适应算法。
二、实验要求及功能介绍
1．实验要求
1.在实现关于内存管理的内存首选适应算法和最佳适用算法。
2.实现关于内存管理的内存动态分区分配布局初始化。
3.实现关于内存管理的内存动态分区分配申请分配。
4.实现关于内存管理的内存回收等基本功能操作函数。
2．功能介绍
（1）首次适应算法
在首次适应算法中，是从已建立好的数组中顺序查找，直至找到第一个大小能满足要求的空闲分区为止，然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空间令开辟一块新的地址，大小为原来的大小减去作业大小，若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。
（2）循环首次适应算法
该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N==0时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。
（3）最坏适应算法
最坏适应分配算法是每次为作业分配内存时，扫描整个数组，总是把能满足条件的，又是最大的空闲分区分配给作业。
（4）最佳适应算法
最坏适应分配算法是每次为作业分配内存时，扫描整个数组，总是把能满足条件的，又是最小的空闲分区分配给作业。
三、实验流程图
四、实验主要代码
typedef struct freeNode //空闲区链表结点{
int address; //开始地址
int size; //分区大小
freeNode *next; //指向下一个分区}*freetable;
typedef struct workNode //作业区链表结点
{
char proname[20]; //作业名
int address; //开始地址
int size; //作业大小
struct workNode *next; //指向下一个作业
}*worktable;
void workdiaodu(freetable freehead,worktable workhead,freetable p,freetable q,char proname[20],int size) //进行作业内存的分配
{
worktable newwork = new workNode;
strcpy(newwork->proname,proname); //作业名
newwork->size = size; //作业大小
newwork->address = p->address; //起始地址
newwork->next = NULL;
//情况3：当作业大小<分区大小时
if(p->size > newwork->size)
{
p->address = p->address + newwork->size; //作业大小作为此分区的起始地址
p->size = p->size - newwork->size; //分区大小为原分区大小-作业大小
}
//情况2：当作业大小=分区大小时
else if(p->size == newwork->size)
{
q->next = p->next;
delete p; //删除此分区
}
//以下把新作业加入到作业区链表中
worktable r = workhead->next;
worktable w = workhead;
while(r != NULL && r->address < newwork->address) //在作业区中进行查找新作业的内存位置
{
w = r;
r = r->next;
}
if(r == NULL) //在作业区链尾
{
w->next = newwork; //添加到链尾
}
else //添加到链中任意位置
{
newwork->next = r;
w->next = newwork;
}
cout<<"\n\n\t\t\t\t分配成功"<<"\n";
}
/*首次适应算法的原理*/
void FFRequestMemory(freetable freehead,worktable workhead,char proname[20],int size)
{
if(freehead->next == NULL)
{
cout<<"\n\n\t\t\t分配失败，当前已无空闲区"<<"\n";
return;
}
freetable p = freehead->next;
freetable q = freehead;
while(p != NULL && p->size < size) //进行从低地址分区开始搜索符合作业大小的内存分区
{
q = p;
p = p->next;
}
if(p == NULL)
{
cout<<"\n\n\t\t\t分配失败，当前已无足够内存分配"<<"\n";
return;
}
workdiaodu(freehead,workhead,p,q,proname,size);
}
void deletebackup(freetable &backuphead) //删除临时链表，释放内存{
freetable p = backuphead->next;
freetable q;
while(p != NULL)
{
q = p;
p = p->next;
delete q;
}
backuphead->next = NULL;
}
/*循环首次适应算法的原理：*/
freetable currenthead; //定义一个全局变量指针，指向每次分配完分区的下一个分区地址
void NFRequestMemory(freetable freehead,worktable workhead,char proname[20],int size)
{
if(freehead->next == NULL) //空闲区为空
{
cout<<"\n\n\t\t\t分配失败，当前已无空闲区"<<"\n";
return;
}
freetable p = freehead->next;
if(p->next == NULL) //当空闲区链表中只有一个分区时
{
if(p->size < size) //分区容量小于作业大小
{
cout<<"\n\n\t\t\t分配失败，当前已无足够内存分配"<<"\n";
return;
}
workdiaodu(freehead,workhead,p,freehead,proname,size);
return;
}
//当有2个或2个以上分区时,应该会出现以下2种情况：
//情况1、上一次分配的分区刚好是空闲区链表中最后一个分区结点
//情况2、上一次分配的分区刚好是空闲区链表中第一个分区结点至倒数第二个分区结点的任意一个
p = currenthead;
freetable q;
q = freehead;
while(q->next != currenthead )
{
q = q->next;
}
//从currenthead指向的下一个分区开始查找至链尾
while(p != NULL && p->size < size )
{
q = p;
p = p->next;
}
if(p == NULL && currenthead == freehead->next) //当currenthead指向第一个分区时，就不需要进行循环了
{
cout<<"\n\n\t\t\t分配失败，当前已无足够内存分配"<<"\n";
return;
}
if(p != NULL) //在未循环之前查找到了符合作业大小的分区{
workdiaodu(freehead,workhead,p,q,proname,size); //进行内存分配if(p->next == NULL) //如果是空闲区中最后一个分区
{
currenthead = freehead->next;
}
else
{
currenthead = p->next;
}
return;
}
//以下说明currenthead指向的不是第一个分区，因此需要进行循环查找操作p = freehead->next;
q = freehead;
while(p != currenthead && p->size < size) //从链首开始查找到currenthead
{
q = p;
p = p->next;
}
if(p == currenthead) //查找失败，没有符合条件的分区
{
cout<<"\n\n\t\t\t分配失败，当前已无足够内存分配"<<"\n";
return;
}
//查找成功了
workdiaodu(freehead,workhead,p,q,proname,size);
if(p->next == NULL)
{
currenthead = freehead->next;
return;
}
currenthead = p->next;
}
/*最佳适应算法的原理：*/
void BFRequestMemory(freetable freehead,worktable workhead,freetable backuphead,char proname[20],int size)
{
//无空闲区时
if(freehead->next == NULL)
{
cout<<"\n\n\t\t\t分配失败，当前已无空闲区"<<"\n";
return;
}
freetable p = freehead->next;
if(p->next == NULL) //当空闲区中只有一个分区时，无需对分区进行排序
{
if(p->size < size) //当当前的分区内存不足分配作业时
{
cout<<"\n\n\t\t\t分配失败，当前已无足够内存分配"<<"\n";
return;
}
else //当这个分区的内存大小大于或等于作业大小时
{
workdiaodu(freehead,workhead,p,freehead,proname,size);
return;
}
}
//当空闲区中有2个或2个以上分区时，应根据各分区的容量大小，进行从小至大的排序
else
{
freetable newfree = new freeNode;
newfree->address = p->address; //起始地址
newfree->size = p->size; //分区大小
newfree->next = NULL;
//开始建立按容量大小排序的临时链表
backuphead->next = newfree;
p = p->next;
freetable current;
freetable prevnode;
while(p != NULL)
{
newfree = new freeNode;
newfree->address = p->address; //起始地址
newfree->size = p->size; //分区大小
newfree->next = NULL;
current = backuphead->next;
prevnode = backuphead;
while(current != NULL && current->size < newfree->size) //当作业大小大于或等于分区时，向后移
{
prevnode = current;
current = current->next;
}
if(current == NULL) //链尾时，则将此分区排在最后
{
prevnode->next = newfree;
}
else
{
newfree->next = current;
prevnode->next = newfree;
}
p = p->next;
}
//按从小到大排序完成后，则进行查找最优分区
current = backuphead->next;
while(current != NULL && current->size < size) //从链表第一个分区进行查找，当分区大小小于作业大小时，向后移动
{
current = current->next;
}
if(current == NULL) //移动到链尾，说明分配失败，没有适合作业大小的分区
{
cout<<"\n\n\t\t\t分配失败，当前无足够内存"<<"\n";
deletebackup(backuphead);
return;
}
else //查找到符合作业大小的分区，则应根据该分区记录的起始地址，在空闲区链表中查找此分区的具体位置
{
p = freehead->next;
freetable q = freehead;
while(p != NULL && p->address != current->address)
{
q = p;
p = p->next;
}
workdiaodu(freehead,workhead,p,q,proname,size); //开始进行内存分配
deletebackup(backuphead);
}
}
}
/*内存的回收原理：*/
void ReturnMemory(freetable freehead,worktable workhead,char proname[20]) {
//作业区为空时
if(workhead->next == NULL)
{
cout<<"\n\n\t\t\t回收内存失败，作业区为空"<<"\n";
return;
}
worktable p = workhead->next;
worktable q = workhead;
while(p != NULL && strcmp(p->proname,proname) != 0) //从作业区中进行查找作业名
{
q = p;
p = p->next;
}
if(p == NULL)
{
cout<<"\n\n\t\t\t回收内存失败，作业区中无此作业名"<<"\n";
return;
}
//以下是查找作业名成功后进行的操作
freetable newfree = new freeNode;
newfree->address = p->address; //作业的起始地址
newfree->size = p->size; //作业的大小
newfree->next = NULL;
q->next = p->next;
delete p; //从作业区中删除此作业
//从空闲区中查找回收内存的起始地址
freetable r = freehead->next;
freetable w = freehead;
while(r != NULL && r->address < newfree->address)
{
w = r;
r = r->next;
}
if(r == NULL) //查找在链尾
{
w->next = newfree;
//判断能否进行合并
if(w->address + w->size == newfree->address) //如果前一个分区的起始地址+分区大小=回收内存分区的起始地址，则进行分区合并{
w->size = w->size + newfree->size;
w->next = NULL;
delete newfree;
}
}
else //查找到空闲区的其他位置时
{
newfree->next = r; //将分区插入到空闲区中
w->next = newfree;
//进行判断能否进行内存合并
if(w->address + w->size == newfree->address && newfree->address + newfree->size != r->address)
{
w->size = w->size + newfree->size;
w->next = r;
delete newfree;
}
else if(w->address + w->size != newfree->address && newfree->address + newfree->size == r->address)
{
newfree->size = newfree->size + r->size;
newfree->next = r->next;
delete r;
}
else if(w->address + w->size == newfree->address && newfree->address + newfree->size == r->address)
{
w->size = w->size + newfree->size + r->size;
w->next = r->next;
delete newfree;
delete r;
}
}
cout<<"\n\n\t\t\t\t回收内存成功"<<"\n";
}
void deleteall(freetable freehead,worktable workhead) //释放空闲区链表、作业区链表的所有内存
{
freetable p = freehead->next;
freetable q;
while(p != NULL) //释放空闲区链表
{
q = p;
p = p->next;
delete q;
}
freehead->next = NULL;
delete freehead; //删除空闲区链表的头结点
worktable r = workhead->next;
worktable w = workhead;
while(r != NULL) //释放作业区链表
{
w = r;
r =r->next;
delete w;
}
workhead->next = NULL;
delete workhead; //删除作业区链表的头结点
}
五、实验结果
六、实验总结
通过本次实验，我对内存分配有了更深的了解。动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。而且动态内存分配是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。做了这个实验无疑更明白了靠理论和仅有的一点想象能力是不够的，必须自己动手操作才会有所进步。无疑，要学好操作系统，学好编程，在以后的学习中必须更多的动手完成实验编程。
七、参考文献
[1] 《计算机操作系统》汤小丹、梁红兵等编著,西安电子科技大学出版社，2007
[2]《C++程序设计》谭浩强著，清华大学出版社，2004