可变分区首次适应算法.docx

可变分区首次适应算法

--操作系统实验报告

题 目 ：可变分区首次适应算法
指导老师 ：
班 级 ：
姓 名 ：
学 号 ：
时 间 ：

实验三 可变分区首次适应算法
一、实验目的
模拟内存分配, 了解并掌握动态分区分配中所用的数据结构、分区分配算法。回顾链表的创建，插入，删除等基本操作； 深刻理解首次适应内存分配算法。
二、实验内容
编程实现首次适应内存分配算法，并上机验证。
实验环境：Microsoft Visual Studio 2010
三、算法描述
该程序用一个链表来模拟内存的空间分布。从键盘输入链表长度和第一个结点的首地址、以及其他各个结点所占空间大小。然后进行申请空间，并判断所申请的大小是否符合要求，能不能进行分配。本程序主要包括两大模块，一是建立链表模块，二是申请并分配空间模块。
开始
程序流程图如下：

初始化

输出内存分配情况

输入申请内存空间大小

是否可以进行分配

否

是

是否继续
内存分配并输出分配结果

是

否

结束

四、程序清单及简单注释
// 内存分配算法：
#include
#include
#include
using namespace std;
int size=0,count=0,part[1000],address[1000],flag[1000];//设定全局变量

//*******************输出可视结果*****************//
void Output()
{
int j;
cout<<" 输出内存分配情况： "< 分区大小 | 起始地址 | 状态 |"<环境******************//
void Create()//指明内存空间并初步地为作业分配内存
{
int i=1,m=0,s=0,start=0;
char contin='Y';
cout<<"请输入待分配的内存大小：";
cin>>size;
cout<>start;
cout<
cout<>part[i];
address[i]=start;
start=start+part[i];
s=m;//m用来标记已分配内存的总的大小，s用来标记m之前的值
m=m+part[i];
flag[i]=1;//标识内存已分配

if(m==size)
{
cout< cout<>contin;
cout<>contin;
cout<'N')//如果不继续分配内存，将剩余的空间定义为一个分区，但标记为未分配
{
part[++i]=size-m;
count=i;//分区总数
address[i]=start;//起始地址
}
}//if(msize)
{
cout<>contin;
cout< part[i]=size-s;
}
else
{
start=start-part[i];//如果重新分配，恢复原来的起始地址
m=s;
flag[i]=0;
}
}//if(m>size)
}//while
}
//**************************分配内存********************//
void Distribute()
{
int tag=0,space=0,i,j,situation=0;//situation用来表示分配是否成功
cout<cout<<"输入作业所需的内存空间：";
cin>>space;
cout<space&&flag[i]==0)
{
flag[i]=1;
cout<<"分配成功！"<=i+2;j-)
{
part[j]=part[j-1];
flag[j]=flag[j-1];
}
flag[i+1]=0;//多余的内存部分状态为未分配
part[i+1]=part[i]-space;
part[i]=space;//划出一部分内存空间分配给作业
flag[count+1]=0;
++count;
//重新定义分区的首地址
for(j=1;j Output();
situation=1;
break;
}
}
if(situation==0)
{
cout<<"分配失败！"<已分配！"<收操作！"<>j;
flag[j]=0;//回收分区
//如果有几段连续的空闲分区，则将他们合并
for(i=count;i>1;i--)
{
if(flag[i]==0&&flag[i-1]==0)
{
m++;//用以标记将被撤销的分区块数
part[i-1]=part[i-1]+part[i];
part[i]=0; //先将后一个分区的大小和地址置空
address[i]=0;
}
}
for(i=count;i>=1;i--)
{
if(address[i]!=0)
{ k=i; break;}
else
count--;
}//处理末位连续的空闲分区

for(i=k;i>1;i--)//处理中间的连续的空闲分区
{
if(address[i]==0)
{
for(j=i;j flag[j]=flag[j+1];
}
--count;//撤销一个区分，总数减一
}
}
Output();
}
}
//********************主函数*********************//
void main()
{
int i;char ch='y',s;
cout<//初始化数组的值
flag[i]=0;
}
Create();
Output();
while(ch=='y'||ch=='Y')
{
cout<>s;
while(s!='R'&&s!='D')
{
cout<>s;
}
if(s=='R')
{ Restore(); cout<'D')
{ Distribute(); cout<>ch;
}
cout<