最佳适应算法.cpp

关于操作系统存储分配的最佳适应法

 




#include <iostream.h>
#include <iomanip.h>
int k=4;

struct list             // 初始化数据的结构体    
{
 int num; //分区序号               
 int adr;//首地址               
 int end;//尾地址              
    int size;//大小
}s[]={{1,1000,2999,2000},{2,500,799,300},{3,3500,3699,200},{4,4000,4499,500}}; // 初始化空闲分区

/*void print(struct list *p,int n)      // print函数作用输出结果
{
 int flag1=1;
 int flag2=1;
 int i,j=0;
    cout<<"-------------------------------------\n";
 for(i=0;i<n;p++,i++ )
 {
  if(p->size==0)   // 控制不输出size=0的空闲块
  {
   flag2=0;
   j++;
   continue;
  }
  else
   flag2=1;
  if(p->size!=0&&flag2!=0)
  { 
   flag1=0;
            cout<<"序号:"<<setw(2)<<p->num-j/*输出的序号仍然是从1开始*//*<<"   起始位置:"<<setw(5)<<p->adr<<"   终止位置:"<<setw(5)<<p->end<<"   空闲块大小:"<<setw(5)<<p->size<<endl;
  }
 }
 if(flag1==1)    // 当所有的空闲块正好被分配完时
  cout<<"\n空闲内存已被分配完，请回收！\n";
 cout<<"-------------------------------------\n";
}*/
void print(struct list a[],int n)      // print函数作用输出结果
{
 int i;
    cout<<"-------------------------------------\n";
 if(a[0].size==0)
 {
  for(i=0;i<k;i++)
  {
   a[i].adr=a[i+1].adr;
   a[i].size=a[i+1].size;
   a[i].end=a[i+1].end;
  }
  k=k-1;
 }
 if(k==0)
  cout<<"\n空闲块已经分配完毕,需要再分配,请回收!\n";
 for(i=0;i<k;i++)
 cout<<"序号:"<<setw(2)<<a[i].num/*输出的序号仍然是从1开始*/<<"   起始位置:"<<setw(5)<<a[i].adr<<"   终止位置:"<<setw(5)<<a[i].end<<"   空闲块大小:"<<setw(5)<<a[i].size<<endl;
    cout<<"-------------------------------------\n";
}

void link(struct list a[])  /*当一块空闲内存的尾地址和下一块的首地址相连时，将它们合并成一块*/
{
 int i;
 for(i=0;i<k;i++)
 {
  if(a[i].end==a[i+1].adr-1)
  {
   a[i].size=a[i].size+a[i+1].size;
   a[i].end=a[i+1].end;
   for(i=i+1;i<k;i++)
   {
    a[i].adr=a[i+1].adr;
    a[i].size=a[i+1].size;
    a[i].end=a[i+1].end;
   }
   k=k-1;
  }
 }
}

void order(struct list a[],int n)     // order函数将空闲内存块按空间块起始地址大小排序
{ 
 int i,j,adr,end,size;
 for(i=1;i<n;i++)
 {
  for(adr=a[i].adr,size=a[i].size ,end=a[i].end,j=i-1;j>=0&&adr<a[j].adr;j--)
  {
   a[j+1].size=a[j].size;
   a[j+1].adr=a[j].adr; 
   a[j+1].end=a[j].end;
  }
  a[j+1].adr=adr;
        a[j+1].size=size; 
  a[j+1].end=end;  
 }
}

void sort(struct list a[],int n)    // sort函数将空闲块按空间大小排序
{ 
 int i,j,size,adr,end;
 for(i=1;i<n;i++)
 {
  for(size=a[i].size,adr=a[i].adr,end=a[i].end,j=i-1;j>=0&&size<a[j].size;j--)
  {
   a[j+1].size=a[j].size;
   a[j+1].adr=a[j].adr; 
            a[j+1].end=a[j].end;
  }
  a[j+1].size=size;
        a[j+1].adr=adr; 
  a[j+1].end=end;  
 }
}

void assign(struct list a[],int size)
{
 int i,flag=0;
    for(i=0;i<k;i++)
  if(size<=a[i].size)
  {
   flag=1;
   a[i].adr=a[i].adr+size-1;
   a[i].size=a[i].size-size;
   sort(s,k);
   print(s,k);
   break;
  }
  if(flag==0)
  {
   cout<<"\n没有合适的内存块可用！"<<endl;
  }
}

void accept(struct list a[],int fadd,int size)  // accept函数用于回收内存空间      
{
 int i,j,flag; 
    flag=0;       // 当回收的内存不与其他已存在的内存空闲块相连的时候，设置flag=1
    for(i=0;i<k;i++)
 {
  for(j=a[i].adr;j<=a[i].end;j++)  
  {   
   if(a[i].size==0)         // 发现空闲块大小为空时跳出
         break;
            if(j>=fadd&&j<=fadd+size-1)//当要回收的内存中有未用过的内存时，提示错误。
   {    
    cout<<"\n输入数据错误,回收内存块中有未使用的地址。\n\n";
       flag=1;
    break;
   }
  }
  if(flag==1)
   break;
 }
       /*     if(((a[i].end+1)!=fadd)&&((fadd+size)==a[i+1].adr))//回收区与插入点的后一个分区相连
  {
   a[i+1].size=a[i+1].size+size;
   a[i+1].adr=fadd;
   flag=0;
   break;
  }
  if(i==0&&((fadd+size)==a[i].adr))//回收区与起始地址最小的空闲块相连
  {
   a[i].adr=fadd;
   a[i].size=a[i].size+size;
   flag=0;
   break;
  }
  if(((a[i].end+1)==fadd)&&((fadd+size)==a[i+1].adr))//回收的内存夹在两个空闲块之间
  {
   a[i].size=a[i].size+size+a[i+1].size;
   a[i].end=a[i].adr+a[i].size-1;
   for(i=i+1;i<k;i++)
   {
    a[i].adr=a[i+1].adr;
    a[i].size=a[i+1].size;
    a[i].end=a[i+1].end;
   }
   k=k-1;
   flag=0;
   break;
  }
  
 }                  */
 if(flag==0)
  {
   a[k].num=k+1;
      a[k].size=size;
      a[k].adr=fadd;
      a[k].end=fadd+size-1;
      k=k+1; 
cout<<"\n分配成功，新的内存块排列如下：\n";
  }
  }

void main()                
{   
    int size;
 int fadd ;                   // 回收区首地址
 int i=1;                     // 选择操作的代码
 cout<<"初始空闲内存块情况：\n";
 print(s,k);
 cout<<endl;
 cout<<"初始空闲内存块排序（最佳适应算法）：\n";
 sort(s,k);
 print(s,k);
 while(i)
 {
       cout<<"\n-------------------------------------\n选择操作：\n";
    cout<<"1---分配,2---回收,3---退出\n";
    cout<<"-------------------------------------\n";
    cin>>i;
    if(i==1)
    {
     cout<<"\n分配内存块的操作，请输入需要分配的大小：";
           cin>>size;
     assign(s,size);
    }
    else if(i==2)
    {
     cout<<"\n回收内存块的操作，请输入首地址和大小：";
     cin>>fadd;
     cin>>size;
     order(s,k);
     accept(s,fadd,size); 
     order(s,k);
     for(i=0;i<k;i++)
     link(s);
     sort(s,k);
     print(s,k);
    
    }
    else if(i==3)
        break;
    else 
     cout<<"错误的输入，请重新输入!\n";
  }
}