#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;
}
}
}
