操作系统实验报告
实验报告三：内存管理器
专业班级 jk0701
学生姓名 舒月
学号 07281011
实验题目： 内存管理器实验
一 实验目的
设计和实现关于内存管理的内存布局初始化及内存申请分配、内存回收等基本功能操作函数，尝试对用256MB的内存空间进行动态分区方式模拟管理。内存分配的基本单位为1KB，同时要求支持至少两种分配策略，并进行测试和对不同分配策略的性能展开比较评估。
二 实验分析过程
数据结构：
struct node
{
}; struct node* prev; struct node* next; int number; int addr; int size; int status;
设计和实现内存申请分配函数：内存分配的基本单位为1KB，同时要求支持至少两种分配策略（如首次适应、循环首次适应、最佳适应、最坏适应等），若分配失败则返回NULL。在本实验中，我采用了循环首次适应算法和最佳适应算法。
设计和实现内存回收函数：若回收分区与其它空闲分区相邻接，则采取合并措施
小基于不同的内存分配策略形成不同版本的内存管理器，并根据内存平均利用率和分配查找分区比较次数等指标展开测试和对不同分配策略的内存管理器性能进行评估间长短将其与基于Windows互斥信号量的线程同步机制的效率展开比较。
实验要求：假定内存空间的低址部分56MB（即0~56M-1）作为系统区和不参与分配过程
三 验结果及分析
(1)dos界面
（2）使用循环首次适应算法
（3）切换算法
（4）使用最佳适应算法
（5）实现随机的回收一块内存
实验分析：有实验结果可知，最佳适应算法对内存的利用率高于循环首次适应算法，最佳适应算法平均比较次数多余循环首次适应算法。
最佳适应算法（Best Fit）：
它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。因为它要不断地找出能满足作业要求的、且大小最小的空闲分区，所以比较比较频繁。但是，对内存的利用率高 循环首次适应算法(Next Fit)：
该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。比较次数少于最佳适应算法（Best Fit），内存利用率低于最佳适应算法（Best Fit）。
四 实验总结
内存管理器的实验，把双向链表的使用再次回顾，对内存的分配，使用和回收加深了解，程序上还存在许多需改进的地方，需要继续努力。
第二篇：实验四内存管理模拟
实验四 内存管理模拟
1.实验要求：
模拟动态分区管理方式来管理内存，实现内存的分配和回收，观察内存空闲链表和内存分配表在内存分配和回收过程中数据的变化。
2.实验内容
要求随机产生进程或者由用户输入进程相应信息，实现动态内存管理：设计主界面以灵活选择某算法，主要实现以下算法：首次适应算法、最佳适应算法、最坏适应算法。实现的主要功能：内存的分配、内存的回收，内存空闲链表的变化、内存分配表的变化、内存分配和回收过程的模拟。
3.实验预备内容
(1)阅读和学习教材关于存储器管理和虚拟存储器管理的内容（连续存储管理和离散存储管理），了解相关的内存分配算法、内存分配和回收相关机制，内存管理过程中需要的数据结构。
(2)熟悉Visual C++的简单使用。
4．实验环境
（1）一台运行Windows 2000 professional操作系统的计算机。
（2）选用turbo c、visual c++、Delphi、c++ builder或visual basic等任何一种语言。
5．实验时间
4个机时。
6．参考算法
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#define MIN 5 //碎片最小容量
#define MAX 1024 //存储区的最大容量
#define MATSIZE 100 //作业分配表的最大容量
#define NOT_EXIST -1 //不存在
#define SUCCESS 1 //成功
#define FAILED 0 //失败
#define EXIT 0 //退出
#define NO_OPERATE -1//无操作
//+*+*+*+*+ 程序主要变量 +*+*+*+*+
typedef struct Free_Area FREEAREA;//***** 定义"空闲块链表"结构 ***** typedef struct Free_Area{
int size; //空区大小(以字节计),包括区头所占空间
int address; //空闲块首地址
FREEAREA *next; //前向链指针,指向下一个空区
FREEAREA *back; //反向链指针,指向上一个空区
}FREEAREA; //********** **********
typedef struct MAT_Table //***** 定义"作业分配表"结构 ***** {
int name; //用户作业名
int length; //作业所占分区大小
int addr; //作业所占分区首地址
}MATS; //********** **********
MATS MAT[MATSIZE]; //定义"作业分配表"变量
FREEAREA *head; //定义"空闲块链表"变量
int FreeAreaLength;//空闲分区的数目
int MAT_Length;//作业分配表的数目
//+*+*+*+*+ end 变量 +*+*+*+*+
// !*!*!*!*! 程序主要函数 !*!*!*!*!
void init(); //初始化作业分配表
void InitFreeArea(); //初始化空闲块链表
void print_MAT_table(); // 打印MAT表
void print_FreeTable(); // 打印空闲链表
int COALESCEC(int worksize); // 紧凑模块 int FFALOCATION(int worksize,int workname);//分配模块 char instruct();//指令打印
void time(); //延迟
// !*!*!*!*! end 函数 !*!*!*!*!
// ***** ***** ***** 初始化 ***** ***** ***** void init() //初始化作业分配表
{
MAT_Length=0;//作业分配表的有效长度
for(int i=0;i<MATSIZE;i++)
{
MAT[i].name=NOT_EXIST;
MAT[i].length=NOT_EXIST;
MAT[i].addr=NOT_EXIST;
}
}
void InitFreeArea() //初始化空闲块链表
{
FreeAreaLength=0; //空闲分区的数目初始化为0
head=new FREEAREA;//创建一整块空闲分区
head->next=head->back=head; //让首、尾指针指向本身
head->size=MAX; //大小赋值为:整个物理空间的大小
head->address=0; //空闲区的首地址为0
++FreeAreaLength;//空闲分区的数目变为1
}
// ***** ***** end 初始化 ***** *****
void print_MAT_table() //***** ***** ***** 打印MAT表 ***** ***** ***** {
cout<<"=================================================================="<<endl;
cout<<"$********************** 作业分配表MAT ***************************$"<<endl;
cout<<"\n 表项\t 作业名name \t 作业大小length \t 作业首址addr "<<endl; for(int i=0;i<MAT_Length;i++)
printf("%3d\t%6d\t\t%7d\t\t\t%7d\n",i,MAT[i].name,MAT[i].length,MAT[i].addr);
cout<<"\n$************************** END *********************************$"<<endl;
cout<<"==================================================================\n\n"<<endl;
} //***** ***** end 打印MAT表 ***** *****
void print_FreeTable() //***** ***** ***** 打印空闲链表 ***** ***** ***** {
FREEAREA *freep=head;//将'空闲链表头指针'赋值给'空闲分区链查找指针'
cout<<"_________________________________________________________________"<<endl; cout<<"$********************** 空闲链表 *******************************$"<<endl;
cout<<"\n 表项 \t 空闲块大小size \t 空闲块首址address"<<endl;
for(int i=0;i<FreeAreaLength;i++)
{
printf("%3d \t %6d \t\t %5d \n",i,freep->size,freep->address);
freep=freep->next;
}
cout<<"\n$************************ END
**********************************$"<<endl;
cout<<"-----------------------------------------------------------------\n\n"<<endl;
}
//***** ***** ***** ***** 分配模块 ***** ***** ***** *****
int FFALOCATION(int worksize,int workname)//分配模块
{
FREEAREA *freep=head;//将'空闲链表头指针'赋值给'空闲分区链查找指针'
int i=0; //FreeArea监督长度值
while(freep && i<FreeAreaLength) //***** 首次适应法 *****
{
if((freep->size)>=worksize)//遇到头一块适合的空闲区
{
//$$$$$ 判断剩余空闲空间是否大于规定的碎片最小容量MIN $$$$$
if(freep->size-worksize>=MIN)//是，则分割分配 {
MAT[MAT_Length].name=workname;
MAT[MAT_Length].length=worksize;
MAT[MAT_Length].addr=freep->size-worksize+freep->address;
freep->size-=worksize;
}
else//否则,完全分配
{
--FreeAreaLength;
MAT[MAT_Length].name=workname;
MAT[MAT_Length].length= freep->size;
MAT[MAT_Length].addr=freep->address;
//***** 判断分配后是否还有空闲区 *****
if(FreeAreaLength==0)//无,则置空
freep->next=freep->back=NULL;
else//有,则去除此结点
{
freep->back->next=freep->next;
freep->next->back=freep->back;
}
delete freep;
}
++MAT_Length;//分配表长度加1
return(SUCCESS);
}
else//未遇到合适的空闲区,则向后查找
{ ++i;
freep=freep->next;
}
}
if((freep->size=COALESCEC(worksize))!=0)//如无合适区域,且可紧凑,则同上处理
{
//$$$$$ 判断剩余空闲空间是否大于规定的碎片最小容量MIN $$$$$
if((freep->size-worksize)>=MIN)//是，则分割分配 {
MAT[MAT_Length].name=workname;
MAT[MAT_Length].length=worksize;
MAT[MAT_Length].addr=freep->size-worksize+freep->address; freep->size-=worksize;
}
else//否则,完全分配
{
--FreeAreaLength;
MAT[MAT_Length].name=workname;
MAT[MAT_Length].length= freep->size;
MAT[MAT_Length].addr=freep->address;
freep->next=freep->back=NULL;
delete freep;
}
++MAT_Length;//分配表长度加1
return(SUCCESS);
}
else//无合适区域,且不可紧凑
{
cout<<"! ! !*************** 内存不足，不能分配 **************! ! !\n"<<endl;
return(FAILED);
}
}
//***** ***** ***** ***** end 分配模块 ***** ***** ***** *****
//***** ***** ***** ***** ***** 回收模块 ***** ***** ***** ***** ***** ***** void FFCOLLECTION(int workname)//回收模块
{
FREEAREA *freep=head;//将'空闲链表头指针'赋值给'空闲分区链查找指针' int i=0;//用于记录在欲回收模块之前的模块数
int location=-1;//用于记录欲回收模块在表中的位置,初始值为-1
for(int m=0;m<MAT_Length;m++)//***** 查找欲回收模块 *****
{
if(MAT[m].name==workname)
{
location=m;
break;
}
} //***** *****
if(location!=-1)//如找到了欲回收模块
{
--MAT_Length;//有效长度减1
//*** 计算在欲回收模块之前的模块数,并将与此模块最近的空闲区(地址在此模块之后)找到 ***
while(i<FreeAreaLength && MAT[location].addr>freep->address)
{
freep=freep->next;
++i;
} //*** ***
if(freep->back->size+freep->back->address==MAT[location].addr && freep->address==MAT[location].addr+MAT[location].length)//欲回收模块前后都有空闲区
{
freep->back->size=freep->back->size+freep->size+MAT[location].length; freep->back->next=freep->next;
freep->next->back=freep->back;
}
if(freep->back->size+freep->back->address==MAT[location].addr && freep->address!=MAT[location].addr+MAT[location].length)//欲回收模块前都有空闲区
{
freep->back->size+=MAT[location].length;
}
if(freep->back->size+freep->back->address!=MAT[location].addr && freep->address==MAT[location].addr+MAT[location].length)//欲回收模块后都有空闲区
{
freep->size+=MAT[location].length;
freep->address=MAT[location].addr;
}
if(freep->back->size+freep->back->address!=MAT[location].addr &&
freep->address!=MAT[location].addr+MAT[location].length)//欲回收模块前后都没有
空闲区
{
++FreeAreaLength;
FREEAREA *freep1=new FREEAREA;
freep1->size=MAT[location].length;
freep1->address=MAT[location].addr;
freep1->back=freep->next;
freep->back->next=freep1;
freep1->next=freep;
freep->back=freep1;
}
for(int j=location;j<MAT_Length;j++)//****** 分配表中的值向前移,
消除回收项 ******
{
MAT[j].addr=MAT[j+1].addr;
MAT[j].length=MAT[j+1].length;
MAT[j].name=MAT[j+1].name;
} //****** ******
}
else//如未找到了欲回收模块
printf("\n\n! ! !********不存在这样的作业*********! ! !\n\n");
}
//***** ***** ***** ***** ***** end 回收模块 ***** ***** ***** ***** *****
//***** ***** ***** ***** ***** 紧凑模块 ***** ***** ***** ***** *****
int COALESCEC(int worksize)//紧凑模块
{
FREEAREA *freep=head;//将'空闲链表头指针'赋值给'空闲分区链查找指针'
FREEAREA *colloctp=freep;//将'空闲分区链查找指针'赋值给'空闲分区紧凑指针'
for(int j=0;j<FreeAreaLength-1;j++)//将'空闲分区紧凑指针'的大小赋值为'整个空
闲区的大小和'
{
freep=freep->next;
colloctp->size+=freep->size;
}
if(colloctp->size>=worksize)//如果紧凑后能满足分配要求,则紧凑分配
{
int i;
FreeAreaLength=1;
cout<<"\n*********开始紧凑碎片************\n"<<endl;
cout<<"\n*********************************\n"<<endl;
freep->address=0;
freep->size=colloctp->size;
freep->next=freep->back=freep;
MAT[0].addr=freep->size;
for(i=1;i<MAT_Length;i++)
{
MAT[i].addr=MAT[i-1].addr+MAT[i-1].length;
}
return (freep->size);//返回空闲区的大小
}
else
return(FAILED);
}
//***** ***** ***** ***** ***** end 紧凑模块 ***** ***** ***** ***** *****
//***** ***** ***** ***** 模块处理 ***** ***** ***** *****
int MENU()//模块处理
{
int worksize;//欲分配模块大小
int workname;//欲分配模块名字
char answer;//回答
int reply;//响应
cout<<"选择要执行的操作: (H.指令提示;)\n\t\t ";
cin>>answer;
if(answer=='H'||answer=='h')
answer=instruct();
if(answer=='A'||answer=='a')
reply=1;
else if(answer=='B'||answer=='b')
reply=2;
else if(answer=='C'||answer=='c')
reply=3;
else if(answer=='D'||answer=='d')
reply=4;
else if(answer=='E'||answer=='e')
reply=5;
else
reply=-1;
switch(reply)
{
case 1:
{
int name;
cout<<"输入要回收的作业名 : ";
cin>>name;
FFCOLLECTION(name);
break;
}
case 2:
{
printf("作业请求分配内存:\n");
printf("************!!!注意：作业名字只可为整
数!!!**************");
cout<<"\r ";
time();
cout<<"\r ----------作业名字(name)=";
cin>>workname;
cout<<" ----------作业大小(size)=";//输入作业大
小worksize
cin>>worksize;
FFALOCATION(worksize,workname);
break;
}
case 3:
return(EXIT);
break;
case 4:
print_FreeTable();
break;
case 5:
print_MAT_table();
break;
default:
{
cout<<" !-!-!-!-! 警告提示:"<<endl;
cout<<"****************不存在这样的操作，请重试***************\n"<<endl;
}
}
return NO_OPERATE;//
}
//***** ***** ***** ***** end 模块处理 ***** ***** ***** *****
//***** ***** ***** 指令打印 ***** ***** *****
char instruct()//指令打印
{
char answer;
YUNWEI:
cout<<" \t\t\b @*******系统指令***********@"<<endl;
cout<<" \t\t作业回收： A \n\t\t作业分配： B \n\t\t退出程序： C \n\t\t打印空闲链表:D \n\t\t打印分配表： E"<<endl;
cout<<" \t\t\b @**************************@\n"<<endl;
cout<<"选择要执行的操作 : ";
cin>>answer;
if(answer=='h'||answer=='H')
goto YUNWEI;
return answer;
}
//***** ***** ***** end 指令打印 ***** ***** *****
//***** ***** ***** 延迟 ***** ***** *****
void time()//延迟
{
for(int x=0;x<3000;x++)
for(int y=0;y<3000;y++)
for(int z=0;z<50;z++);
}
//***** ***** ****** end 延迟 ***** ***** *****
//***** ***** ***** ***** ***** 主函数 ***** ***** ***** ***** ***** void main()
{ cout<<")-------------- 采用可变分区存储器管理方案的模拟系统 ---------------(\n"<<endl;
init();
InitFreeArea();
while(1)
{
if( MENU()==0)
break;
}
cout<<")---------------------- ALL THE WORK OVER --------------------------(\n"<<endl; }
//***** ***** ***** ***** ***** end of all ***** ***** ***** ***** *****