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

可变分区首次适应算法

--操作系统实验报告

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

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

初始化

输出内存分配情况

输入申请内存空间大小

是否可以进行分配

否

是

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

是

否

结束

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

//*******************输出可视结果*****************//
void Output()
{
int j;
cout<<" 输出内存分配情况： "<<endl;
cout<<endl;
cout<<" | 分区号 | 分区大小 | 起始地址 | 状态 |"<<endl;
for(j=1;j<=count;j++)
{
cout<<" | "<<j<<" ";
cout<<" | "<<part[j]<<" ";
cout<<" | "<<address[j]<<" ";
if(flag[j]==1)
cout<<" | "<<"已分配";
if(flag[j]==0)
cout<<" | "<<"未分配";
cout<<" |";
cout<<endl;
}
}
//******************创建原始环境******************//
void Create()//指明内存空间并初步地为作业分配内存
{
int i=1,m=0,s=0,start=0;
char contin='Y';
cout<<"请输入待分配的内存大小：";
cin>>size;
cout<<endl;
cout<<"开始为作业分配内存空间"<<endl;
cout<<endl;
cout<<"请输入第一次分区的首地址：";
cin>>start;
cout<<endl;
cout<<"输入每个分区的大小，以‘Y’继续操作，以‘N’结束分区操作:"<<endl;
cout<<endl;
while(contin!='N')
{
count=i;
cout<<"请输入第"<<i<<"个作业的大小：";
cin>>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<<endl;
cout<<"已分配完所有内存空间，请结束操作！"<<endl;
cout<<endl;
contin='N';
}
if(m<size)
{
cout<<endl;
cout<<"是否继续? Y/N:";
cin>>contin;
cout<<endl;
while(contin!='Y'&&contin!='N')
{
cout<<endl;
cout<<"输入‘N’或‘Y’继续操作：";
cin>>contin;
cout<<endl;
}
if(contin=='Y')
i++;
if(contin=='N')//如果不继续分配内存，将剩余的空间定义为一个分区，但标记为未分配
{
part[++i]=size-m;
count=i;//分区总数
address[i]=start;//起始地址
}
}//if(m<size)
if(m>size)
{
cout<<endl;
cout<<"申请空间超出未分配的空间大小，是否重新分配？ Y/N:";
cin>>contin;
cout<<endl;
if(contin=='N')
{ flag[i]=0;
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<<endl;
cout<<"输入作业所需的内存空间：";
cin>>space;
cout<<endl;
for(i=1;i<=count;i++)
{
if(part[i]==space&&flag[i]==0)
{
flag[i]=1;
Output();
situation=1;
break;
}
if(part[i]>space&&flag[i]==0)
{
flag[i]=1;
cout<<"分配成功！"<<endl;
cout<<endl;
for(j=count+1;j>=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<count;j++)
{
address[j+1]=address[j]+part[j];
}
Output();
situation=1;
break;
}
}
if(situation==0)
{
cout<<"分配失败！"<<endl;
cout<<endl;
for(j=1;j<=count;j++)//判断是什么原因造成分配失败
{
if(flag[j]==0)
{
tag=1;
break;
}
}
if(tag==1)
cout<<"所有的空间大小都不足以分配！"<<endl<<endl;
if(tag==0)
cout<<"所有的空间均已分配！"<<endl<<endl;;
Output();
}
}
//********************回收分配出去的内存**********************//
void Restore()
{
int tag=0,i,j,m=0,k;
for(i=1;i<=count;i++)
{
if(flag[i]==1)
{
tag=1;
break;
}
}
if(tag==0)//回收前进行判断内存是否已经被分配
{
cout<<endl;
cout<<"所有分区均未分配，不需要回收操作！"<<endl;
}
if(tag==1)
{
cout<<endl;
cout<<"请输入要回收的分区号：";
cin>>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<k;j++)
{
part[j]=part[j+1];
address[j]=address[j+1];
flag[j]=flag[j+1];
}
--count;//撤销一个区分，总数减一
}
}
Output();
}
}
//********************主函数*********************//
void main()
{
int i;char ch='y',s;
cout<<endl<<endl<<"\t\t\t可变分区首次适应算法"<<endl<<endl;
cout<<endl;
for(i=0;i<1000;i++)
{
part[i]=0;
address[i]=0;//初始化数组的值
flag[i]=0;
}
Create();
Output();
while(ch=='y'||ch=='Y')
{
cout<<endl;
cout<<"选择操作，回收内存(R)或继续分配(D):";
cin>>s;
while(s!='R'&&s!='D')
{
cout<<endl;
cout<<"请选择正确地操作，回收内存请输入R，继续分配请输入D:";
cin>>s;
}
if(s=='R')
{ Restore(); cout<<endl;}
if(s=='D')
{ Distribute(); cout<<endl;}
cout<<"是否继续操作！是请输入'y'或'Y'，否请输入任意字符以结束程序：";
cin>>ch;
}
cout<<endl;
cout<<"本程序结束执行！"<<endl;
}

五、实验结果
建立内存分配环境：

剩余空间不足以分配：

所有的空间均已分配：

回收分区1：

回收分区2，由于两个空闲分区连续，将合并区分1和分区2：

六、实验小结
本算法从链首开始查找可以满足请求申请的空间大小的第一个结点，然后按照请求的大小，从该结点空间中划分一块适当的空间分配，剩下的空间作为一个新的结点接到后面。如果所有的结点都已分配了，或者请求分配的空间大小大于所有结点的大小，则分配失败。该算法优先利用内存中低地址部分的空闲块，这为后面来的需要空间较大的请求创造了条件，但是也会留下许多难以利用的、较小的内存空间，从而造成内存浪费。
通过本次实验，我对链表的链接、删除等都有了比以前更进一步的理解，更重要的是，对内存的结构、内存空间的分配等的认识也更加深入。