ldm.cpp

动态内存分派．． ．． ．． ．

#include "iostream.h"
#include "iomanip.h"

#define ERR_NOFREEAREA 1
#define ERR_NOADEQUACYAREA 2
#define ERR_ALLOCATED 4

#define ERR_NOJOBS 1
#define ERR_NOSUCHJOB 2
#define ERR_RECLAIMED 4


typedef struct tagUsedNode
{
 long address;
 long length;
 int flag;                 
 struct tagUsedNode *next;
} USED_AREA , *USED_TABLE;

typedef struct tagFreeNode
{
 long address;
 long length;
 struct tagFreeNode *next;
} FREE_AREA , *FREE_TABLE;

//空闲区、作业区链表
USED_TABLE usedTable = NULL;
FREE_TABLE freeTable = NULL;


//给作业分配空间
//jobname: 作业名
//jobsize: 作业所需空间大小
//--------------------------------------------------------------------------
int Allocate( int jobname , long jobsize )
{
 //如果没有空闲区
 if( freeTable == NULL )
  return ERR_NOFREEAREA;
 FREE_TABLE p = freeTable;
 FREE_TABLE q = p;
 //找首次适应空闲区
 while( p != NULL && p->length < jobsize )
 {
  q = p;
  p = p->next;
 }
 //如果找不到有足够空间的分区
 if( p == NULL )
  return ERR_NOADEQUACYAREA;

 USED_TABLE x = new USED_AREA;
 x->address = p->address;
 x->length = jobsize;
 x->flag = jobname;
 x->next = NULL;

 //如果该分区大于作业需求，空间大小减去作业大小
 if( p->length > jobsize )
 {
  p->length -= jobsize;
  p->address += jobsize;
 }
 //如果该分区等于作业大小，删除该分区
 else
 {
  if( p == freeTable )
   freeTable = NULL;
  else
   q->next = p->next;
  delete p;
 }
 //作业加入“作业表”中
 USED_TABLE r = usedTable;
 USED_TABLE t = r;

 while( r != NULL && r->address < x->address )
 {
  t = r;
  r = r->next;
 }
 
 if( usedTable == NULL )
  usedTable = x;
 else
 {
  x->next = r;
  t->next = x;
 }

 return ERR_ALLOCATED;
}
//---------------------------------------------------------------------------------

//回收作业空间
//jobname: 作业名
//---------------------------------------------------------------------------------
int Reclaim( int jobname )
{
 if( usedTable == NULL )
  return ERR_NOJOBS;
 USED_TABLE p = usedTable;
 USED_TABLE q = p;
 while( p != NULL && p->flag != jobname )
 {
  q = p;
  p = p->next;
 }
 //如果没有该作业
 if( p == NULL )
  return ERR_NOSUCHJOB;
 //回收后的空间加入到空闲区
 FREE_TABLE r = freeTable;
 FREE_TABLE t = r;
 FREE_TABLE x;
 while( r != NULL && r->address < p->address )
 {
  t = r;
  r = r->next;
 }

 x = new FREE_AREA;
 x->address = p->address;
 x->length = p->length;
 x->next = NULL;

 if( r == freeTable )
 {
  x->next = r;
  freeTable = x;
  t = freeTable;
   if( t->next != NULL && t->address + t->length == t->next->address)
 {
  t->length += t->next->length;
  r = t->next;
  t->next = t->next->next;
  delete r;
  }
 }
 else
 {
  x->next = r;
  t->next = x;
  if( t->next != NULL && t->address + t->length == t->next->address)
 {
  t->length += t->next->length;
  r = t->next;
  t->next = t->next->next;
  delete r;
  }
  t = t->next;
 if( t->next != NULL && t->address + t->length == t->next->address)
 {
  t->length += t->next->length;
  r = t->next;
  t->next = t->next->next;
  delete r;
  t = t->next;
  }
 }
 //合并分区

 //删除该作业
 if( p == usedTable )
 {
  usedTable = usedTable->next;
 }
 else
  q->next = p->next;
 delete p;

 return ERR_RECLAIMED;
}
//-------------------------------------------------------------------------------
int Init()
{
 freeTable = new FREE_AREA;
 freeTable->address = 0;
 freeTable->length = 64;
 freeTable->next = NULL;
 return 1;
}
//-------------------------------------------------------------------------------
void jobrequest()
{
 int jobname;
 int jobsize;

 cout<<"作业名: ";
 cin >> jobname;
 cout<<"作业长度: ";
 cin >> jobsize;

 if( Allocate( jobname , jobsize ) == ERR_ALLOCATED )
  cout<<"该作业已成功获得所需空间"<<endl;
 else
  cout<<"该作业没有获得所需空间"<<endl;
}
//---------------------------------------------------------------------------------
void jobreclaim()
{
 int jobname;
 cout<<"需要回收的作业名: ";
 cin >>jobname;
 int result = Reclaim( jobname );
 if(  result == ERR_RECLAIMED )
  cout<<"作业"<<jobname<<"已成功回收"<<endl;
 else if( result == ERR_NOSUCHJOB || result == ERR_NOJOBS )
  cout<<"系统没有作业"<<jobname<<"或该作业"<<jobname<<"不存在"<<endl;
}
//---------------------------------------------------------------------------------
void freeTablePrint()
{
 cout<<"..............................................................."<<endl;
 cout<<setw(10)<<"address"<<setw(15)<<"length"<<setw(15)<<"state"<<setw(15)<<"jobname"<<endl<<endl;
 FREE_TABLE p = freeTable;
 USED_TABLE q = usedTable;
 int x , y;
 while( p || q )
 {
  if( p )
   x = p->address;
  else
   x = 0x7fffffff;
  if( q )
   y = q->address;
  else
   y = 0x7fffffff;

  if( x < y )
  {
   cout<<setw(10)<<p->address<<setw(15)<<p->length<<setw(15)<<"空闲"<<endl;
   p = p->next;
  }
  if( x > y )
  {
   cout<<setw(10)<<q->address<<setw(15)<<q->length<<setw(15)<<"已分配"<<setw(15)<<"jobname="<<q->flag<<endl;
   q = q->next;
  }
 }
 cout<<".............................................................."<<endl;
 cout<<endl;
}

void main()
{
	cout<<"--------------------------------------------------------------------"<<endl;
	cout<<"             操作系统课程设计实验：连续动态内存管理模拟实现         "<<endl;
	cout<<"                             计算机科学与技术学院                   "<<endl;
	cout<<"--------------------------------------------------------------------"<<endl;
 Init();

 int choose;
 bool exitFlag = false;
 cout<<"输入功能项: 0 -　退出   1 - 分配主存  2 - 回收主存  3 - 显示主存 "<<endl;
 while( !exitFlag )
 {
  cout<<"输入:";
  cin>>choose;
  switch( choose )
  {
  case 0:
   exitFlag = true;
   break;
  case 1:
   jobrequest();
   break;
  case 2:
   jobreclaim();
   break;
  case 3:
   freeTablePrint();
   break;
  }
 }
}