内存管理实验报告.doc

操作系统课程设计报告

题 目：
动态分区内存管理
班 级：
计算机1303班
学 号：
2120131138
姓 名：
徐叶
指导教师：
代仕芳
日 期：
2015.11.5

一、 实验目的及要求
本实验要求用高级语言编写模拟内存的动态分区分配和回收算法（不考虑紧凑），以
便加深理解并实现首次适应算法（FF）、循环首次适应算法(NF)、最佳适应算法（BF），
最坏适应算法(WF)的具体实现。

二、 实验内容
本实验主要针对操作系统中内存管理相关理论进行实验，要求实验者编写一个程序，该程序管理一块虚拟内存，实现内存分配和回收功能。
1） 设计内存分配的数据结构（空闲分区表/空闲分区链），模拟管理 64M 的内存块；
2） 设计内存分配函数；
3） 设计内存回收函数；
4） 实现动态分配和回收操作；
5） 可动态显示每个内存块信息

动态分区分配是要根据进程的实际需求，动态地分配内存空间，涉及到分区分配所用的数据结构、分区分配算法和分区的分配回收。

程序主要分为四个模块：
（1）首次适应算法（FF）
在首次适应算法中，是从已建立好的数组中顺序查找，直至找到第一个大小能满足要求的空闲分区为止，然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空间令开辟一块新的地址，大小为原来的大小减去作业大小，若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。
（2）循环首次适应算法(NF)
该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N==0时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。
（3）最佳适应算法(BF)
最坏适应分配算法是每次为作业分配内存时，扫描整个数组，总是把能满足条件的，又是最小的空闲分区分配给作业。
（4）最坏适应算法(WF)
最坏适应分配算法是每次为作业分配内存时，扫描整个数组，总是把能满足条件的，又是最大的空闲分区分配给作业。

系统从空闲分区链表中找到所需大小的分区，如果空闲分区大小大于分区大小，则从分区中根据请求的大小划分出一块内存分配出去，余下的部分则留在空闲链表中。然后，将分配区的首址返回给调用者。
当进程运行完回收内存时，系统根据回收区的首址，从空闲区中找到相应的插入点，此时可能出现四种情况：
1、 当空闲区的上下两相邻分区都是空闲区：将三个空闲区合并为一个空闲区。新空闲区的起始地址为上空闲区的始址，大小为三个空闲区之和。空闲区合并后，取消可用表中下空闲区的表目项，修改上空闲区的对应项。
2、 当空闲区的上相邻区是空闲区：将释放区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地址，大小为上空闲区与释放区之和。合并后修改上空闲区对应的可用表的表目项。
3、 当空闲区的下相邻区是空闲区：将释放区与下空闲区合并，并将释放区的始址作为合并区的始址。合并区的长度为释放区与下空闲区之和。合并后修改可用表中相应的表目项。
4、 两相邻区都不是空闲区：释放区作为一个新空闲可用区插入可用表。

三、调试及运行
测试案例：
假定主存中按地址顺序依次有五个空闲区。始址地址分别为：3K, 40K, 60K, 100K, 500K,空闲区大小依次为：32k,10k,15k,228k,100k。现有五个作业J1,J2,J3,J4,J5。他们各需要主存1k,10k,128k,28k,25k。作业的完成顺序为：J5, J1,J3,J2,J4，每完成一个作业系统回收为其分配的内存空间，使用回收算法，回收内存。

初始界面（输入）

主存分配情况
(1)首次适应算法

(2)循环首次适应算法

(3)最佳适应算法

(4)最坏适应算法

(首次适应算法下)分配内存

(首次适应算法下)回收内存

四、总结
老师布置这次的实验题目的一开始，自己根本不知道要干什么，因为在上课时对动态分区分配这节内容学得没有很深刻，对许多东西一知半解，所以在上机时根本不知道如何下手，后来，将本章内容反复的看了几遍之后，终于有了自己的思路。
通过此次的学习，理解了内存管理的相关理论，掌握了连续动态分区管理的理论，通过对实际问题的编程实现，获得实际应用和编程能力；充分了解了内存管理的机制实现，从而对计算机的内部有了更深的认识，对于以后对操作系统的深入有很大的作用。
在做课程设计的过程中我遇到了不少问题，比如链表指针部分就很容易搞混，而且很多地方不容易考虑全面，比如内存回收时空闲区的合并部分，要考虑释放的内存空间前后是否为空闲区，若是，如何来合并，另外若用的是最佳适应算法，进行内存回收时还有考虑前后空闲块地址是否相接，因为它是按照块的大小排序的，若不相接，即使两个块在链表中的位置相邻，也不能合并，而且要注意每次分配或释放空间后都要对链表进行排序，这是由算法思想决定的，这些条件都是在做的过程中逐步完善的，所遇到的这些问题通过询问同学和查阅资料得以解决。
整个实验做完后，我对内存动态分区内存管理有了更加深刻的理解，我个人的编程能力也得到了一定程度的提高。

附录（附录源代码）
#include<iostream>
#include<stdlib.h>
using namespace std;
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define Notfree 2
#define OK 1 //完成
#define ERROR 0 //出错
#define MAX_length 65536 //最大内存空间为64M
typedef int Status;
int flag;
typedef struct freearea//定义一个空闲区说明表结构
{
long size; //分区大小
long address; //分区地址
int state; //状态
}ElemType;
// 线性表的双向链表存储结构
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior; //前趋指针
struct DuLNode *next; //后继指针
}
DuLNode,*DuLinkList;
DuLinkList block_first; //头结点
DuLinkList block_last; //尾结点
Status alloc(int);//内存分配
Status free(int); //内存回收
Status FF(int);//首次适应算法
Status NF(int);//循环首次适应算法
Status BF(int); //最佳适应算法
Status WF(int); //最差适应算法
void show();//查看分配
Status Initblock();//开创空间表
Status Initblock()//开创带头结点的内存空间链表
{
block_first=(DuLinkList)malloc(sizeof(DuLNode));
block_last=(DuLinkList)malloc(sizeof(DuLNode));
block_first->prior=NULL;
block_first->next=block_last;
block_last->prior=block_first;
block_last->next=NULL;
block_last->data.address=0;
block_last->data.size=MAX_length;
block_last->data.state=Notfree;
return OK;
}
Status NotFree(int i,int j){
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));

static DuLNode *p=block_first->next;
temp->data.size=i;
temp->data.state=Free;
temp->prior=p->prior;
temp->next=p;
temp->data.address=j;
p->prior->next=temp;
p->prior=temp;
p->data.address=temp->data.address+temp->data.size;
p->data.size-=i;

temp->next=block_last;
block_last->prior=temp;
return OK;
}
//分配主存
Status alloc(int ch)
{
int request = 0;
cout<<"请输入需要分配的主存大小(单位:KB)：";
cin>>request;
if(request<0 ||request==0)
{
cout<<"分配大小不合适，请重试！"<<endl;
return ERROR;
}
if(ch==2) //选择首次循环适应算法
{
if(NF(request)==OK) cout<<"分配成功！"<<endl;
else cout<<"内存不足，分配失败！"<<endl;
return OK;
}
if(ch==3) //选择最佳适应算法
{
if(BF(request)==OK) cout<<"分配成功！"<<endl;
else cout<<"内存不足，分配失败！"<<endl;
return OK;
}
if(ch==4) //选择最差适应算法
{
if(WF(request)==OK) cout<<"分配成功！"<<endl;
else cout<<"内存不足，分配失败！"<<endl;
return OK;
}

else //默认首次适应算法
{
if(FF(request)==OK) cout<<"分配成功！"<<endl;
else cout<<"内存不足，分配失败！"<<endl;
return OK;
}
}

//首次适应算法
Status FF(int request)
{
//为申请作业开辟新空间且初始化
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.size=request;
temp->data.state=Busy;
DuLNode *p=block_first->next;
while(p)
{
if(p->data.state==Free && p->data.size==request)
{//有大小恰好合适的空闲块
p->data.state=Busy;
return OK;
break;
}
if(p->data.state==Free && p->data.size>request)
{//有空闲块能满足需求且有剩余
temp->prior=p->prior;
temp->next=p;
temp->data.address=p->data.address;
p->prior->next=temp;
p->prior=temp;
p->data.address=temp->data.address+temp->data.size;
p->data.size-=request;
return OK;
break;
}
p=p->next;
}
return ERROR;
}
//循环首次适应算法
Status NF(int request)
{
//为申请作业开辟新空间且初始化
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.size=request;
temp->data.state=Busy;
static DuLNode *p=block_first->next;//static 其值在下次调用时仍维持上次的值
if(p->data.size<request)
p=block_first->next;
while(p)
{
if(p->data.state==Free&&p->data.size==request)
{
//有大小恰好合适的空闲块
p->data.state=Busy;
return OK;
break;
}
if(p->data.state==Free&&p->data.size>request)
{//有空闲块能满足需求且有剩余
temp->prior=p->prior;
temp->next=p;
temp->data.address=p->data.address;
p->prior->next=temp;
p->prior=temp;
p->data.address=temp->data.address+temp->data.size;
p->data.size-=request;
return OK;
break;
}
p=p->next;
}
return ERROR;
}
//最佳适应算法
Status BF(int request)
{
int ch; //记录最小剩余空间
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.size=request;
temp->data.state=Busy;
DuLNode *p=block_first->next;
DuLNode *q=NULL; //记录最佳插入位置
while(p) //初始化最小空间和最佳位置
{
if(p->data.state==Free && (p->data.size>=request) )
{
if(q==NULL)
{
q=p;
ch=p->data.size-request;
}
else if(q->data.size > p->data.size)
{
q=p;
ch=p->data.size-request;
}
}
p=p->next;
}
if(q==NULL) return ERROR;//没有找到空闲块
else if(q->data.size==request)
{
q->data.state=Busy;
return OK;
}
else
{
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.size=ch;
return OK;
}
return OK;
}
//最坏适应算法
Status WF(int request)
{
int ch; //记录最大剩余空间
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.size=request;
temp->data.state=Busy;
DuLNode *p=block_first->next;
DuLNode *q=NULL; //记录最佳插入位置
while(p) //初始化最大空间和最佳位置
{
if(p->data.state==Free && (p->data.size>=request) )
{
if(q==NULL)
{
q=p;
ch=p->data.size-request;
}
else if(q->data.size < p->data.size)
{
q=p;
ch=p->data.size-request;
}
}
p=p->next;
}
if(q==NULL) return ERROR;//没有找到空闲块
else if(q->data.size==request)
{
q->data.state=Busy;
return OK;
}
else
{
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.size=ch;
return OK;
}
return OK;
}

//主存回收
Status free(int flag)
{
DuLNode *p=block_first;
for(int i= 0; i <= flag; i++)
if(p!=NULL)
p=p->next;
else
return ERROR;
p->data.state=Free;
if(p->prior!=block_first && p->prior->data.state==Free&&p->data.address==p->prior->data.address+p->prior->data.size)//与前面的空闲块相连
{
p->prior->data.size+=p->data.size;
p->prior->next=p->next;
p->next->prior=p->prior;
p=p->prior;
}
if(p->next!=block_last && p->next->data.state==Free&&p->next->data.address==p->data.address+p->data.size)//与后面的空闲块相连
{
p->data.size+=p->next->data.size;
p->next->next->prior=p;
p->next=p->next->next;
}
if(p->next==block_last && p->next->data.state==Free)//与最后的空闲块相连
{
p->data.size+=p->next->data.size;
p->next=NULL;
}
return OK;
}
//显示主存分配情况
void show()
{
int flag = 0;
cout<<"\n主存分配情况:\n";
cout<<"**********************************************\n\n";
DuLNode *p=block_first->next;
cout<<"分区号\t起始地址\t分区大小\t状态\n\n";
while(p)
{
if(p->data.state==Notfree) p=p->next;
else{
if(p->data.state==Busy) cout<<" "<<flag++<<"\t";
else
{
cout<<"\t";
flag++;
}
cout<<" "<<p->data.address<<"\t\t";
cout<<" "<<p->data.size<<"KB\t\t";
if(p->data.state==Free) cout<<"空闲\n\n";
else cout<<"已分配\n\n";
p=p->next;
}
}
cout<<"*********************************************\n\n";
}
//主函数
void main()
{
int ch;//算法选择标记
int i,j,n;
Initblock(); //开创空间表
cout<<"请输入空闲区的个数:" <<endl ;
cin >> n;
cout<<"请依次输入空闲区大小和始址（空格键分开）:" <<endl ;
for (int k=0;k<n;k++)
{
cin >> i >> j; // 键盘输入i,j 值
NotFree(i,j);
}
cout<<"请选择内存分配算法：(选择1~4输入)\n";
cout<<"1.首次适应算法\n2.循环首次适应算法\n3.最佳适应算法\n4.最坏适应算法\n";
cin>>ch;

while(ch<1||ch>4)
{
cout<<"输入错误，请重新选择内存分配算法：\n";
cin>>ch;
}

int choice; //操作选择标记
while(1)
{
show();
cout<<"请输入要进行的操作：(选择0~2输入)";
cout<<"\n1: 分配内存\n2: 回收内存\n0: 退出\n";
cin>>choice;
if(choice==1)
{
cout<<"请输入要分配的内存个数:" <<endl ;
cin >> n;
cout<<"请依次输入其大小," <<endl ;
for (int k=0;k<n;k++)
{
alloc(ch); // 分配内存
}

}
else if(choice==2) // 内存回收
{
int flag;
cout<<"请输入要回收的分区号：";
cin>>flag;
free(flag);
}
else if(choice==0) break; //退出
else //输入操作有误
{
cout<<"输入有误，请重试！"<<endl;
continue;
}
}
}

17