allocate.cpp

操做系统动态内存分配

//#include "stdafx.h"
#include <iostream>
#include <cstddef>
using namespace std;
int const MEMO=256;
struct FreeMemory
{
 int ID;int StartAdd;int Size;bool State;
 FreeMemory* Next;
};

FreeMemory* AllocTable=new FreeMemory;//建立全局管理表
FreeMemory* PtrforCycleFit=AllocTable;//为循环首次适应定义的指针，此指针用于指向当前查找的起始地址;
void MemoryInit(FreeMemory* &tempAdd)
{
 tempAdd->ID=0;
 tempAdd->Size=MEMO;
 tempAdd->StartAdd=0;
 tempAdd->State=false;
 tempAdd->Next=NULL;
}

//反馈内存现态
void DispMemory()
{
 FreeMemory* temp=AllocTable;
 cout<<"系统总内存:  "<<MEMO<<endl;
 for(;temp;temp=temp->Next)
 cout<<"进程ID："<<temp->ID<<" "<<"大小："<<temp->Size<<"   "<<"起始地址:"<<temp->StartAdd<<" "<<"是否已分配:"<<temp->State<<endl;
}

//分区排序
void SortPartition(bool order)//在此我使用的是快速排序算法
{
FreeMemory* temp1=AllocTable;
FreeMemory* temp2=AllocTable;
FreeMemory* Last1=temp1;
FreeMemory* Last2=temp2;
if(temp2->Next)
temp2=temp2->Next;

 switch(order)
 {
 case 1://升序部分
  {
for(;temp1;temp1=temp1->Next)
{
 for(;temp2;temp2=temp2->Next)
 {
  if((temp1->Size> temp2->Size)&&!temp1->State&&!temp2->State)//找到符合条件的，则交换
  {
   Last1->Next=temp2;
   Last2->Next=temp1;
   FreeMemory* temp=temp2->Next;
   temp2->Next=temp1->Next;
   temp1->Next=temp->Next;
  }
   Last2=temp2;
 }
  Last1=temp1;
}
  }
  break;
 case 0://降序部分
  {
for(;temp1;temp1=temp1->Next)
{
 for(;temp2;temp2=temp2->Next)
 {
  if((temp1->Size < temp2->Size)&&!temp1->State&&!temp2->State)//找到符合条件的，则交换
  {
   Last1->Next=temp2;
   Last2->Next=temp1;
   FreeMemory* temp=temp2->Next;
   temp2->Next=temp1->Next;
   temp1->Next=temp->Next;
  }
  Last2=temp2;
 }
 Last1=temp1;
}

  }
 }
}
/*内存分配MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM*/
bool Alloc_FirstFit(int id, int TrySize)
{
//查找一个可用第一个满足分配请求的分区，如果满足将其写入内存分配表
//否则分配失败，返回
 FreeMemory* temp=AllocTable;
for(;temp;temp=temp->Next)
{
 if(TrySize<=temp->Size && !temp->State)//第一个满足条件的分区已找到
 {
  if(TrySize==temp->Size)//刚好和申请的大小一致
  {
   temp->ID=id;
   //保持不变temp->Next,Size,StartAdd都不用变
   temp->State=true; //值为真表示已分配
  }
  else//比所找到的要小，则需要将其拆分
  {
   FreeMemory* NewItem=new FreeMemory;
   NewItem->Next=temp->Next;
   NewItem->ID=0;
   NewItem->Size=temp->Size-TrySize;
   NewItem->StartAdd=temp->StartAdd+TrySize;
   NewItem->State=false;
   temp->ID=id;
   temp->Size=TrySize;
   temp->State=true;
   temp->Next=NewItem;
  }
  return true;
 }
}//end for
return false;
}

bool Alloc_FirstFitCycle(int id,int TrySize)
{
 FreeMemory* temp=PtrforCycleFit;
 for(;PtrforCycleFit;PtrforCycleFit=PtrforCycleFit->Next)
{
 if(TrySize<=PtrforCycleFit->Size && !PtrforCycleFit->State)//第一个满足条件的分区已找到
 {
  if(TrySize==PtrforCycleFit->Size)//刚好和申请的大小一致
  {
   PtrforCycleFit->ID=id;
   //保持不变temp->Next,Size,StartAdd都不用变
   PtrforCycleFit->State=true; //值为真表示已分配
  }
  else//比所找到的要小，则需要将其拆分
  {
   FreeMemory* NewItem=new FreeMemory;
   NewItem->Next=PtrforCycleFit->Next;
   NewItem->ID=0;
   NewItem->Size=PtrforCycleFit->Size-TrySize;
   NewItem->StartAdd=PtrforCycleFit->StartAdd+TrySize;
   NewItem->State=false;
   PtrforCycleFit->ID=id;
   PtrforCycleFit->Size=TrySize;
   PtrforCycleFit->State=true;
   PtrforCycleFit->Next=NewItem;
  }
  return true;
 }
}//end for
 PtrforCycleFit=AllocTable;//走到了末尾，再返回到上面去
 for(;PtrforCycleFit!=temp;PtrforCycleFit=PtrforCycleFit->Next)
{
 if(TrySize<=PtrforCycleFit->Size && !PtrforCycleFit->State)//第一个满足条件的分区已找到
 {
  if(TrySize==PtrforCycleFit->Size)//刚好和申请的大小一致
  {
   PtrforCycleFit->ID=id;
   //保持不变temp->Next,Size,StartAdd都不用变
   PtrforCycleFit->State=true; //值为真表示已分配
  }
  else//比所找到的要小，则需要将其拆分
  {
   FreeMemory* NewItem=new FreeMemory;
   NewItem->Next=PtrforCycleFit->Next;
   NewItem->ID=0;
   NewItem->Size=PtrforCycleFit->Size-TrySize;
   NewItem->StartAdd=PtrforCycleFit->StartAdd+TrySize;
   NewItem->State=false;
   PtrforCycleFit->ID=id;
   PtrforCycleFit->Size=TrySize;
   PtrforCycleFit->State=true;
   PtrforCycleFit->Next=NewItem;
  }
  return true;
 }
}//end for
return false;
}

 

bool Alloc_BestFit(int id,int TrySize)
{//查找满足此条件的 x1<=TrySize<=x2 的分区,然后将其放置在x2中，并将x2拆分成两个分区
 SortPartition(true);
FreeMemory* temp=AllocTable;
if(temp->Next)
temp=temp->Next;
for(;temp;temp=temp->Next)
{
 if(TrySize<=temp->Size && !temp->State)//第一个满足条件的分区已找到
 {
  if(TrySize==temp->Size)//刚好和申请的大小一致
  {
   temp->ID=id;
   //保持不变temp->Next,Size,StartAdd都不用变
   temp->State=true; //值为真表示已分配
  }
  else//比所找到的要小，则需要将其拆分
  {
   FreeMemory* NewItem=new FreeMemory;
   NewItem->Next=temp->Next;
   NewItem->ID=0;
   NewItem->Size=temp->Size-TrySize;
   NewItem->StartAdd=temp->StartAdd+TrySize;
   NewItem->State=false;
   temp->ID=id;
   temp->Size=TrySize;
   temp->State=true;
   temp->Next=NewItem;
  }
  return true;
 }
}//end for
 return false;
}

bool Alloc_BadFit(int id,int TrySize)
{//查找满足此条件的TrySize<=x2 的分区,然后将其放置在x2中，并将x2拆分成两个分区
 SortPartition(false);//按降序排序
FreeMemory* temp=AllocTable;
for(;temp;temp=temp->Next)
{
 if(TrySize<=temp->Size && !temp->State)//第一个满足条件的分区已找到
 {
  if(TrySize==temp->Size)//刚好和申请的大小一致
  {
   temp->ID=id;
   //保持不变temp->Next,Size,StartAdd都不用变
   temp->State=true; //值为真表示已分配
  }
  else//比所找到的要小，则需要将其拆分
  {
   FreeMemory* NewItem=new FreeMemory;
   NewItem->Next=temp->Next;
   NewItem->ID=0;
   NewItem->Size=temp->Size-TrySize;
   NewItem->StartAdd=temp->StartAdd+TrySize;
   NewItem->State=false;
   temp->ID=id;
   temp->Size=TrySize;
   temp->State=true;
   temp->Next=NewItem;
  }
  return true;
 }
}//end for
 return false;
}
bool Alloc_Memory(int id, int Algorithm,int TrySize)
{
 switch(Algorithm)
 {
  case 1 :
   return Alloc_FirstFit(id,TrySize);
   break;
  case 2:
   return Alloc_FirstFitCycle(id,TrySize);
   break;
  case 3:
   return Alloc_BadFit(id,TrySize);
   break;
  case 4:
   return Alloc_BestFit(id,TrySize);
   break;
  default:
   cout<<"你没有指定算法,系统将默认为首次适应算法!!!"<<endl;
   return Alloc_FirstFit(id,TrySize);
 }
}
/*End Memory Alloc 内存分配区操作定义完成EndMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM*/


/*Recycle Memory 回收内存 MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM*/

bool Free_Memory(int id)//一个进程在这里可以是多个块吗？
{

 FreeMemory* temp=AllocTable;
 FreeMemory* Last=temp;
 if(temp->ID==id)
 {
  //考虑第一条记录的特殊情况
  if(temp->Next && !temp->Next->State)//下一分区没有被占用，将与本条合并
  {
   temp->ID=0;
   temp->Size=temp->Size+temp->Next->Size;
   temp->State=0;//回收
   Last=temp->Next;
   temp->Next=temp->Next->Next;
   delete Last;
  }
  else//只有第一分区为空，则清除相关表项的数据
  {
   temp->ID=0;
   temp->State=false;//改为没有使用状态
  }
  return true;
 }//////////特殊情况第一条
 if(temp->Next)
 temp=temp->Next;

 for(;temp;temp=temp->Next)
 {
  /*回收操作,回收过程中，要用到三个指针，上一个Last,当前temp,下一个temp->next
  其中有四种情况( 后面的数据为处理的优先级
  回收区与插入点的前、后两个分区邻接 优先级 1
  回收区与插入点的前一个分区相邻接   2
  回收区与插入点的后一个分区相邻接   3
  回收区为独立单位.       4
  当temp指向表头或表尾时需要特殊考虑*/
  if(temp->ID==id)//begin 找到该ID表项
  {
  if(temp->Next)//没有到最后一条
  {
   if(!Last->State&&!temp->Next->State)//1
   {
    Last->Next=temp->Next->Next;
    Last->Size=Last->Size+temp->Size+temp->Next->Size;
    delete temp->Next;
    delete temp;
   }else if(!Last->State)//2
   {
    Last->Next=temp->Next;
    Last->Size=Last->Size+temp->Size;
    delete temp;
   }else if(!(temp->Next->State))
   {
    //if(temp->Next->Next)
     Last=temp->Next->Next;
    //else
    // Last=NULL;
    temp->Size=temp->Size+temp->Next->Size;
    temp->State=false;
    temp->ID=0;
    FreeMemory* tempfor=temp->Next;
    temp->Next=Last;
    delete tempfor;
   }
   else//4
   {
    temp->ID=0;
    temp->State=false;
   }
  }//最后一条
  else
  {
   if(!Last->State)//最后一条的前一条为空
   {
    Last->Size=Last->Size+temp->Size;
    Last->Next=NULL;
    delete temp;
   }
   else//最后一条的前一条不为空
   {
    temp->ID=0;
    temp->State=0;
   }
  }
  return true;
  }//end 找到该ID表项  此类情况处理完毕
  Last=temp;

 }//endfor
return false;
}
/*Memory Recycled 内存分配完毕 All done ,the job refered will leave system MMMMMMMMMMMMMMMMMMMM*/
//当进程开始时,就应该为之分配内存
void BeginJob(int id,int Algorithm,int TrySize)
{
 Alloc_Memory(id,Algorithm,TrySize);

}
//当要退出工作时,就要回收//此退出的工作由执行函数调用
void EndJob(int id)
{
 Free_Memory(id);
}
int main()
{
 MemoryInit(AllocTable);//初始化
 int Way;
 while(true)
 {
  cout<<"请输入你所选择的算法:\r\n\
    1 首次适应\r\n\
    2 首次循环适应\r\n\
    3 最坏分配\r\n\
    4 最佳适应"<<endl;
 
 cout<<"请输入:";
 cin >> Way;
 if(Way>0&&Way<=4)
  break;
 cout<<"你的输入不正确，请重新输入！"<<endl;
 }
 while(true)
 {
  int choice;
  cout<<"操作选择：\r\n\
     0 Exit\r\n\
     1 分配内存\r\n\
     2 回收内存\r\n\
     3 显示内存现状\r\n"<<endl;
  cout<<"请输入:";
  cin>>choice;

  if(choice<0&&choice>2)
  {cout<< "操作选择有误重新输入"<<endl;
  continue;
  }

  if(choice==1)
  {
  int id;
  int size;
  cout<<"请输入进程ID："<<endl;
  cin >>id;
  cout<<"请输入进程所需大小："<<endl;
  cin>>size;
  BeginJob(id,Way,size);
  }
  else if(choice==2)
  {
   int id;
   cout<<"请输入进程ID:"<<endl;
   cin>>id;
   EndJob(id);
  }else if(choice==0)//Exit;
  {
   break;
  }else //显示内存现状
  {
   DispMemory();
  }
 }

 return 1;
}