动态分区分配算法
【实验目的】
1、 熟悉内存自由空闲队列的分配策略 2、 熟悉内存分区的回收原则及实现过程 3、 通过实验深刻理解主存管理的内容
【实验内容】
模拟内存的动态分配和回收，并编程实现。
【实验报告】
1、 列出调试通过程序的清单，并附上文档说明。 2、 总结上机调试过程中所遇到的问题和解决方法及感想。
【实验说明】
实验原理
内存的分配可采用操作系统中的首次适应算法、最佳适应算法或最坏适应算法。 内存的回收回收区与空闲区相邻的各种情况分别处理。
(1) 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。
(2) 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：
•作业1申请130KB。
•作业2申请60KB。
•作业3申请100KB。
•作业2释放60KB。
•作业4申请200KB。
•作业3释放100KB。
•作业1释放130KB。
•作业5申请140KB。
•作业6申请60KB。
•作业7申请50KB。
•作业6释放60KB。
请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。
程序代码——C语言实现
#include<stdio.h>
#include<stdlib.h>
struct node //空闲分区链结点的定义
{
node *before;
node *after;
int size;
int address;
int state;
};
node L;
struct usenode
{
usenode *next;
int num;
int add;
int size;
}U,*n;
void Init() //空闲分区链的初始化
{
node *p;
p=(node *)malloc(sizeof(node));
p->before=&L;
p->after=NULL;
p->size=640;
p->address=0;
p->state=0;
L.after=p;
L.before=NULL;
L.size=0;
U.next=NULL;
n=&U;
}
node *search(int a)
{
node *p=L.after;
if(p==NULL)
{
printf("没有空闲的区域!");
p=NULL;
return p;
}
else
{
while(p!=NULL && a>p->size)
p=p->after;
if(p==NULL)
{
printf("没有找到合适的空闲空间!");
p=NULL;
return p;
}
else
return p;
}
}
void recovery(int a,int b) //内存回收算法
{
node *c,*s,*r=L.after;
node *d=L.after,*e;
usenode *k=U.next,*h=&U;
while(k!=NULL && a!=k->num)
{
h=k;
k=k->next;
}
if(k==NULL)
printf("没有找到这样的作业!");
else
{
h->next=k->next;
if(h->next==NULL)
n=h;
}
while(r!=NULL) //若回收得到的空闲块的前方有空闲块合并此空闲块
{
if(k->add==r->address+r->size)
{
r->size=r->size+k->size;
break;
}
else
r=r->after;
}
if(r==NULL) //若回收得到的空闲块的后面有空闲块合并此空闲块
{
r=L.after;
while(r!=NULL)
{
if(k->add+k->size==r->address)
{
r->address=k->add;
r->size=r->size+k->size;
break;
}
else
r=r->after;
}
}
while(d!=NULL) //保证空闲链表中没有相邻的空闲空间
{
if(d->after!=NULL)
e=d->after;
else
break;
if(d->address+d->size==e->address)
{
d->after=e->after;
while(e->after!=NULL)
e->after->before=d;
d->size=d->size+e->size;
free(e);
break;
}
else
d=d->after;
}
if(r==NULL)
{
r=L.after;
c=(node *)malloc(sizeof(node));
c->size=b;
c->address=k->add;
if(L.after==NULL)
{
c->after=L.after;
c->before=&L;
L.after=c;
}
else
{
r=L.after;
while(r!=NULL)
{
if(r->address>c->address)
{
c->after=r;
c->before=r->before;
r->before->after=c;
r->before=c;
free(k);
return;
}
else
r=r->after;
}
}
}
free(k);
}
void alloc(int a ,int b) //分配内存算法
{
node *p,*q=L.after;
usenode *m;
p=search(b);
if(p==NULL)
return;
m=(usenode *)malloc(sizeof(usenode));//生成一个被占用链表的结点,并插入到该链表的尾部
m->add=p->address;
m->size=b;
m->num=a;
m->next=n->next;
n->next=m;
n=m; //保证n始终指向被占用链表的尾部，方便以后新生成结点的插入
if(p->size>b) //如果申请空间的大小小于找到空闲空间的大小的处理
{
p->size=p->size-b;
p->address=p->address+b;
}
else //如果申请空间的大小等于找到空闲空间的大小的处理
{
p->before->after=p->after;
if(p->after!=NULL)
p->after->before=p->before;
free(p);
}
}
void sort() //对空闲链表进行排序
{
int max;
node *p,*q,*r,*s;
node a;
p=L.after;
while(p!=NULL) //让指针q指向链表的最后一个结点
{
q=p;
p=p->after;
}
if(L.after->after==NULL)
return;
else
{
while(p!=q)
{
s=r=p=L.after;
max=r->size;
while(s!=q->after)
{
if(s->size>max)
{
max=s->size;
r=s;
s=s->after;
}
else
s=s->after;
}
a.size=q->size;
a.address=q->address;
q->size=r->size;
q->address=r->address;
r->size=a.size;
r->address=a.address;
if(q->before->before==&L)
return;
else
q=q->before;
}
}
}
void Print()
{
node *p=L.after;
usenode *q=U.next;
int i=1;
printf("\n空闲区域列表:\n");
printf("FREEID address size\n");
while(p!=NULL)
{
printf("%-10d",i);
printf("%-10d",p->address);
printf("%d\n",p->size);
p=p->after;
i++;
}
if(q==NULL)
return;
else
{
printf("\n已分配区域列表:\n");
printf("WORKID address size\n");
while(q!=NULL)
{
printf("%-10d",q->num);
printf("%-10d",q->add);
printf("%d\n",q->size);
q=q->next;
}
}
}
void firstfit() //首次适应算法
{
int a,b,i;
Init();
Print();
while(1)
{printf("\n1、申请空间\n");
printf("2、释放空间\n");
printf("3、退出首次适应算法\n");
printf("请输入你的选择:");
scanf("%d",&i);
switch(i)
{
case 1:
{
printf("请输入申请空间的作业号:");
scanf("%d",&a);
printf("请输入申请空间的大小:");
scanf("%d",&b);
alloc(a,b);
Print();
break;
}
case 2:
{
printf("请输入释放空间的作业号:");
scanf("%d",&a);
printf("请输入释放空间的大小:");
scanf("%d",&b);
recovery(a,b);
Print();
break;
}
case 3:printf("\n");return;
}
}
}
void bestfit()
{
int a,b,i;
Init();
Print();
while(1)
{printf("\n1、申请空间\n");
printf("2、释放空间\n");
printf("3、退出最佳适应算法\n");
printf("请输入你的选择:");
scanf("%d",&i);
switch(i)
{
case 1:
{
printf("请输入申请空间的作业号:");
scanf("%d",&a);
printf("请输入申请空间的大小:");
scanf("%d",&b);
alloc(a,b);
sort();
Print();
break;
}
case 2:
{
printf("请输入释放空间的作业号:");
scanf("%d",&a);
printf("请输入释放空间的大小:");
scanf("%d",&b);
recovery(a,b);
sort();
Print();
break;
}
case 3:printf("\n");return;
}
}
}
void main()
{
int i;
while(1)
{
printf("1、首次适应算法\n");
printf("2、最佳适应算法\n");
printf("3、退出\n");
printf("请输入你的选择:");
scanf("%d",&i);
switch(i)
{
case 1:firstfit();break;
case 2:bestfit();break;
case 3:return;
}
}
}
运行结果
① 开始界面
② 首次适应算法
③ 最佳适应算法
程序代码——C++语言实现
//***************************************************************
//******** 动态分区分配方式的模拟 *********
//***************************************************************
#include<iostream.h>
#include<stdlib.h>
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1 //完成
#define ERROR 0 //出错
#define MAX_length 640 //最大内存空间为640KB
typedef int Status;
typedef struct freearea//定义一个空闲区说明表结构
{
int ID; //分区号
long size; //分区大小
long address; //分区地址
int state; //状态
}ElemType;
//---------- 线性表的双向链表存储结构 ------------
typedef struct DuLNode //double linked list
{
ElemType data;
struct DuLNode *prior; //前趋指针
struct DuLNode *next; //后继指针
}DuLNode,*DuLinkList;
DuLinkList block_first; //头结点
DuLinkList block_last; //尾结点
Status alloc(int);//内存分配
Status free(int); //内存回收
Status First_fit(int,int);//首次适应算法
Status Best_fit(int,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.ID=0;
block_last->data.state=Free;
return OK;
}
//----------------------- 分 配 主 存 -------------------------
Status alloc(int ch)
{
int ID,request;
cout<<"请输入作业(分区号)：";
cin>>ID;
cout<<"请输入需要分配的主存大小(单位:KB)：";
cin>>request;
if(request<0 ||request==0)
{
cout<<"分配大小不合适，请重试！"<<endl;
return ERROR;
}
if(ch==2) //选择最佳适应算法
{
if(Best_fit(ID,request)==OK) cout<<"分配成功！"<<endl;
else cout<<"内存不足，分配失败！"<<endl;
return OK;
}
else //默认首次适应算法
{
if(First_fit(ID,request)==OK) cout<<"分配成功！"<<endl;
else cout<<"内存不足，分配失败！"<<endl;
return OK;
}
}
//------------------ 首次适应算法 -----------------------
Status First_fit(int ID,int request)//传入作业名及申请量
{
//为申请作业开辟新空间且初始化
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.ID=ID;
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;
p->data.ID=ID;
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 Best_fit(int ID,int request)
{
int ch; //记录最小剩余空间
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp->data.ID=ID;
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 || p->data.size==request) )
{
q=p;
ch=p->data.size-request;
break;
}
p=p->next;
}
while(p)
{
if(p->data.state==Free && p->data.size==request)
{//空闲块大小恰好合适
p->data.ID=ID;
p->data.state=Busy;
return OK;
break;
}
if(p->data.state==Free && p->data.size>request)
{//空闲块大于分配需求
if(p->data.size-request<ch)//剩余空间比初值还小
{
ch=p->data.size-request;//更新剩余最小值
q=p;//更新最佳位置指向
}
}
p=p->next;
}
if(q==NULL) return ERROR;//没有找到空闲块
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;
}
}
//----------------------- 主 存 回 收 --------------------
Status free(int ID)
{
DuLNode *p=block_first;
while(p)
{
if(p->data.ID==ID)
{
p->data.state=Free;
p->data.ID=Free;
if(p->prior->data.state==Free)//与前面的空闲块相连
{
p->prior->data.size+=p->data.size;
p->prior->next=p->next;
p->next->prior=p->prior;
}
if(p->next->data.state==Free)//与后面的空闲块相连
{
p->data.size+=p->next->data.size;
p->next->next->prior=p;
p->next=p->next->next;
}
break;
}
p=p->next;
}
return OK;
}
//--------------- 显示主存分配情况 ------------------
void show()
{
cout<<"+++++++++++++++++++++++++++++++++++++++\n";
cout<<"+++ 主 存 分 配 情 况 +++\n";
cout<<"+++++++++++++++++++++++++++++++++++++++\n";
DuLNode *p=block_first->next;
while(p)
{
cout<<"分 区 号：";
if(p->data.ID==Free) cout<<"Free"<<endl;
else cout<<p->data.ID<<endl;
cout<<"起始地址："<<p->data.address<<endl;
cout<<"分区大小："<<p->data.size<<" KB"<<endl;
cout<<"状 态：";
if(p->data.state==Free) cout<<"空 闲"<<endl;
else cout<<"已分配"<<endl;
cout<<"——————————————"<<endl;
p=p->next;
}
}
//----------------------- 主 函 数---------------------------
void main()
{
int ch;//算法选择标记
cout<<" 动态分区分配方式的模拟 \n";
cout<<"************************************\n";
cout<<"** 1)首次适应算法 2)最佳适应算法 **\n";
cout<<"************************************\n";
cout<<"请选择分配算法：";
cin>>ch;
Initblock(); //开创空间表
int choice; //操作选择标记
while(1)
{
cout<<"********************************************\n";
cout<<"** 1: 分配内存 2: 回收内存 **\n";
cout<<"** 3: 查看分配 0: 退 出 **\n";
cout<<"********************************************\n";
cout<<"请输入您的操作 ：";
cin>>choice;
if(choice==1) alloc(ch); // 分配内存
else if(choice==2) // 内存回收
{
int ID;
cout<<"请输入您要释放的分区号：";
cin>>ID;
free(ID);
}
else if(choice==3) show();//显示主存
else if(choice==0) break; //退出
else //输入操作有误
{
cout<<"输入有误，请重试！"<<endl;
continue;
}
}
}