实验五__动态分区分配方式内存管理模拟
2014——2015学年 第一学期
专 业 计算机科学与技术 班 级 专升本 学 号 姓 名 日 期 2014-12-5
实
实验五 动态分区分配方式内存管理模拟 验
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目
实1、 掌握连续分配方式内存管理理论;
验
2、 掌握动态分区分配方式内存管理理论;
目
的
实动态分区分配:根据进程的实际需要，动态地创建分区为之分配验内存空间，在实现动态分区分配时，将涉及分区分配中所使用的数据理结构，分区分配算法和分区的分配与回收操作等问题。 论
1) 分区分配中的数据结构
基
, 空闲分区表:一个数据表，用于记录每个空闲块的情况，如起础
始地址、大小、使用情况等;
, 空闲分区链表:把所有的空闲分区链接成一个链表，便于内存
空间查看与分配回收。
2) 分配算法
, 首次适应法:空闲分区按首地址递增次序组织，每次查找时从
链首出发，寻找满足要求的内存块。
, 循环首次适应算法:空闲分区按首地址递增次序组织，每次从
上次查找的下一个空闲块开始查找，直到找到满足要求的内存
块。
, 最佳适应法:空闲分区按空闲分区大小址递增次序组织，每次
查找时从链首出发，寻找满足要求的最小内存块进行分配。
, 最坏适应法:空闲分区按空闲分区大小递减次序组织，每次查
找时直接判断最大空闲分区是否满足要求。
3) 内存分配过程
利用分配算法找到满足要求的内存块，设请求的内存大小为size:
, 若找到的空闲分区的大小等于size，完全分配;
, 若找到的空闲分区大小大于size，且一分为二后，剩余大小小于
1K，则不再分割，作为整体进行分配;否则一分为二，剩余部
分仍然作为空闲分区存在;
, 若无满足要求空闲分区，则分配失败
4) 内存回收
根据释放区首址和大小，查找空闲分区表/链表，判断是否有相邻的空闲分区存在:
, 释放区与前空闲区相邻:将释放区与前空闲区合并为一个空闲
区。其首址仍为前空闲区首址，大小为释放区大小与空闲区大
小之和。
, 释放区与前后两个空闲区相邻:将这三个区合为一个空闲区，
其首址为前空闲区首址，大小为这三个区大小之和，并取消原
后空闲区表目。
, 释放区与后空闲区相邻:则把释放区合并到后空闲，首地址为
释放区首地址，大小为二者大小之和。
, 释放区不与任何空闲区相邻:将释放区作为一个空闲区，将其
大小和首址插入到空闲区表的适当位置。
实1、要求编写一个动态分区分配管理程序实现一块模拟内存空间验的管理，包括内存分配与回收功能。具体要求完成功能: 内
1) 模拟实现640K内存空间的管理
容
2) 设计内存分配结构，记录内存使用情况 和
3) 设计内存分配算法(首次适应法、最佳适应法两种算法) 步
骤 4) 设计内存回收算法(考虑相邻空间的合并)
5) 可动态显示内存分区状况
以下提供了该实例的部分源代码，要求同学们根据理论基础部分
内容分析该源代码，并将缺失的程序代码补充完整，然后调试这段程
序，最终按要求给出相应的结论。
//***************************************************************
//******** 动态内存分区方式的模拟 *********
//***************************************************************
#include
#include
#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_first->data.state=3;
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<<"分配大小不合适，请重试～"<next;
//请在此处添加为作业申请新空间且初始化的代码
//请在此处完成首次适应算法的代码，分两种情况:有大小恰好合适的空闲
块和有空闲块能满足需求且有剩余。
注意函数返回值。
}
//-------------------- 最佳适应算法 ------------------------ Status Best_fit(int ID,int request)
{
//请在此处添加为作业申请新空间且初始化的代码
DuLNode *p=block_first->next;
DuLNode *q=NULL; //记录最佳插入位置
//请在此处完成最佳适应算法的代码，重点:要查找到最小剩余空间的分区，
即最佳插入位置
if(q==NULL) return ERROR;//没有找到空闲块
else
{
//请插入找到了最佳位置并实现内存分配的代码～
}
}
//----------------------- 主 存 回 收 -------------------- Status free(int ID)
{
DuLNode *p=block_first;
while(p)
{
if(p->data.ID==ID)
{
p->data.state=Free;
p->data.ID=Free;
cout<<"内存块找到，准备回收～"<next;
}
cout<<"回收成功～"<next;
while(p)
{
cout<<"分 区 号:";
if(p->data.ID==Free) cout<<"Free"<data.ID<data.address<data.size<<" KB"<data.state==Free) cout<<"空 闲"<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<<"输入有误，请重试～"<
#include
#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_first->data.state=3;
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<<"分配大小不合适，请重试～"<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-requestdata.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;
cout<<"内存块找到，准备回收～"<prior->data.state==Free)//与前面的空闲块相连
{
DuLNode *q=p->prior;
p->prior->data.size+=p->data.size;
p->prior->next=p->next;
p->next->prior=p->prior;
p=q;
}
if(p->next->data.state==Free&&p->next!=block_last)//与后面的空
闲块相连
{
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)
{
DuLNode *q=block_last;
p->data.size=p->data.size+block_last->data.size;
p->prior->next=p;
p->next=NULL;
block_last=p;
free(q);
}
break;
}
p=p->next;
}
cout<<"回收成功～"<next;
while(p)
{
cout<<"分 区 号:";
if(p->data.ID==Free) cout<<"Free"<data.ID<data.address<data.size<<" KB"<data.state==Free) cout<<"空 闲"<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<<"输入有误，请重试～"<
本文档为【实验五__动态分区分配方式内存管理模拟】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483