/*本程序实现操作系统实验 存储管理—动态分区管理
对内存为1024k的内存进行动态分区管理
程序在Dev-c++环境下调试通过
*/
#include<iostream>
#include<iomanip>
#include<string>
#define MAXINT 10000
using namespace std;
const int StoreVolum=1024;
struct RegionDisplayTable{//分区说明表
int reg_number;//区号
int reg_length;//分区长度
int start_add;//起始地址
string state;//状态
RegionDisplayTable* next;
RegionDisplayTable* pro;
};
struct AvailableTable{//可用分区表
int reg_number;
int reg_length;
int start_add;
bool mark;//更新标志(未更新mark=false，已更新mark=true)
AvailableTable* next;
};
struct JobApplicationTable{//作业申请表
int job_number;
int app_length;
int distr_number;
bool mark;//作业执行标志（已执行mark==false,未执行mark=true）
};
class DynamicDistrict{
public:
DynamicDistrict();
void DisplayDistrict();//显示分区说明表
void DisplayAvailableDistric();//显示可用分区表
void DisplayJob();//按作业长度由小到大显示作业
RegionDisplayTable* NewNodeRDT();
AvailableTable* NewNodeAT();
void ModifyRDT(JobApplicationTable*);//修改分区说明表
void ModifyAT();//修改可用表
void StartJobDeploy();//初始化作业调度（初始化内存分区）
void JobDeploy();//作业调度
void JobRun();//控制作业结束；
private:
RegionDisplayTable* headrdt;
RegionDisplayTable* prdt;
RegionDisplayTable* qrdt;
AvailableTable* headat;
AvailableTable* pat;
AvailableTable* qat;
JobApplicationTable* J;
int jobnumber;
};
DynamicDistrict::DynamicDistrict(){
headrdt=NewNodeRDT();//初始化分区说明表
headrdt->next=NewNodeRDT();
headrdt->next->pro=headrdt;
headrdt->next->reg_number=1;
headrdt->next->reg_length=1024;
headrdt->next->start_add=0;
prdt=qrdt=headrdt->next;
headat=NewNodeAT();//初始化可用分区表
headat->next=NewNodeAT();
headat->next->reg_number=1;
headat->next->reg_length=1024;
headat->next->start_add=0;
}
RegionDisplayTable* DynamicDistrict::NewNodeRDT(){//开创分区说明表节点
RegionDisplayTable* p=new RegionDisplayTable;
p->pro=p->next=NULL;
p->reg_number=p->reg_length=p->start_add=0;
p->state="未分配";
return p;
}
AvailableTable* DynamicDistrict::NewNodeAT(){//开创可用分区表节点
AvailableTable *p=new AvailableTable;
p->reg_number=p->reg_length=p->start_add=0;
p->mark=true;
p->next=NULL;
return p;
}
void DynamicDistrict::StartJobDeploy(){//初始化作业调度（初始化内存分区）
cout<<"输入要调入的作业数目"<<endl;
cin>>jobnumber;
J=new JobApplicationTable[jobnumber];
cout<<"输入各作业的作业号、请求长度"<<endl;
for(int i=0;i<jobnumber;i++)
{cin>>J[i].job_number>>J[i].app_length;
J[i].mark=true;
J[i].distr_number=MAXINT;
}
for(int i=0;i<jobnumber;i++)
ModifyRDT(&J[i]);
for(int i=0;i<jobnumber-1;i++)
for(int j=0;j<jobnumber-i-1;j++)
if(J[j].app_length>J[j+1].app_length)
{JobApplicationTable temp=J[j];
J[j]=J[j+1];
J[j+1]=temp;
}
}
void DynamicDistrict::JobDeploy(){//作业调度
JobApplicationTable j;
cout<<"输入作业的作业号、请求长度"<<endl;
cin>>j.job_number>>j.app_length;
j.distr_number=MAXINT;
j.mark=true;
for(int i=0;i<jobnumber;i++)
if(!J[i].mark) {J[i]=j;ModifyRDT(&J[i]);break;}
}
void DynamicDistrict::DisplayJob()//显示初始调入内存的作业
{cout<<"各作业信息如下："<<endl;
cout<<"作业号"<<" 请求长度"<<" 分配区"<<endl;
for(int i=0;i<jobnumber;i++)
{cout<<J[i].job_number<<setw(12)<<J[i].app_length;
if(J[i].distr_number==MAXINT) cout<<setw(10)<<"未知"<<endl;
else cout<<setw(8)<<J[i].distr_number<<endl;
}
}
void DynamicDistrict::ModifyRDT(JobApplicationTable* J){//修改分区说明表
prdt=headrdt->next;
if(J->mark)
{ while(prdt)
{if(prdt->state=="未分配"&&prdt->reg_length>J->app_length)
{qrdt=NewNodeRDT();
if(prdt->next){qrdt->next=prdt->next;
prdt->next->pro=qrdt;
prdt->next=qrdt;
qrdt->pro=prdt;
RegionDisplayTable* temp=qrdt;
while(temp){temp->reg_number=temp->pro->reg_number+1;
temp=temp->next;}
}
else{prdt->next=qrdt;
qrdt->pro=prdt;
qrdt->reg_number=prdt->reg_number+1;
}
qrdt->reg_length=prdt->reg_length-J->app_length;
prdt->reg_length=J->app_length;
prdt->state="已分配";
qrdt->start_add=prdt->start_add+prdt->reg_length;
qrdt->state="未分配";
J->distr_number=prdt->reg_number;
break;
}
else if(prdt->state=="未分配"&&prdt->reg_length==J->app_length)
{prdt->state="已分配";J->distr_number=prdt->reg_number;break;}
else prdt=prdt->next;}
if(J->distr_number==MAXINT) cout<<"无法运行该作业(作业太大)"<<endl;
}
else{ while(1)
if(prdt->reg_number==J->distr_number) break;
else prdt=prdt->next;
if(prdt->pro->state=="未分配"&&prdt->pro!=headrdt&&prdt->next->state=="未分配")//如果回收区前后都为空闲区
{prdt->reg_number=prdt->pro->reg_number;
prdt->start_add=prdt->pro->start_add;
prdt->reg_length+=prdt->pro->reg_length+prdt->next->reg_length;
prdt->state="未分配";
qrdt=prdt->pro->pro;
delete(qrdt->next);
qrdt->next=prdt;
prdt->pro=qrdt;
qrdt=prdt->next->next;
delete(prdt->next);
prdt->next=qrdt;
qrdt->pro=prdt;
while(qrdt)//修改区号
{qrdt->reg_number=qrdt->pro->reg_number+1;
qrdt=qrdt->next;}
}
else if(prdt->pro->state=="未分配"&&prdt->pro!=headrdt&&prdt->next->state=="已分配")//如果回收区前面的区空闲
{prdt->reg_number=prdt->pro->reg_number;
prdt->start_add=prdt->pro->start_add;
prdt->reg_length+=prdt->pro->reg_length;
prdt->state="未分配";
qrdt=prdt->pro->pro;
delete(qrdt->next);
qrdt->next=prdt;
prdt->pro=qrdt;
qrdt=prdt->next;
while(qrdt)//修改区号
{qrdt->reg_number=qrdt->pro->reg_number+1;
qrdt=qrdt->next;}
}
else if(prdt->pro->state=="已分配"&&prdt->next->state=="未分配")//如果回收区后面的区空闲
{prdt->reg_length+=prdt->next->reg_length;
prdt->state="未分配";
qrdt=prdt->next->next;
delete(prdt->next);
prdt->next=qrdt;
qrdt->pro=prdt;
while(qrdt)//修改区号
{qrdt->reg_number=qrdt->pro->reg_number+1;
qrdt=qrdt->next;}
}
else prdt->state="未分配";
}
ModifyAT();
}
void DynamicDistrict::ModifyAT(){//修改可用分区表
prdt=headrdt->next;
pat=headat->next;
qat=headat;
while(prdt)
{if(prdt->state=="未分配")
if(pat->reg_number==prdt->reg_number)
{ pat->reg_length=prdt->reg_length;
pat->start_add=prdt->start_add;
pat->mark=true;//更新标志
qat=pat;
pat=pat->next;
prdt=prdt->next;
}
else
{AvailableTable* p= NewNodeAT();
p->reg_number=prdt->reg_number;
p->reg_length=prdt->reg_length;
p->start_add=prdt->start_add;
qat->next=p;
p->next=pat;
qat=p;
prdt=prdt->next;
}
else prdt=prdt->next;
}
pat=headat->next;
qat=headat;
while(pat)
if(pat->mark) {qat=pat;pat=pat->next;}
else
{qat->next=pat->next;
delete pat;
pat=qat->next;
}
pat=headat->next;
while(pat)
{pat->mark=false;
pat=pat->next;}
}
void DynamicDistrict::DisplayDistrict(){//显示分区说明表
cout<<"分区情况如下："<<endl;
cout<<"区号"<<" 分区长度"<<" 起始地址"<<" 状态"<<endl;;
prdt=headrdt->next;
while(prdt)
{cout<<prdt->reg_number<<setw(10)<<prdt->reg_length<<"K"<<setw(8)<<prdt->start_add<<"K"<<setw(10)<<prdt->state<<endl;
prdt=prdt->next;
}
}
void DynamicDistrict::DisplayAvailableDistric() //显示可用分区表
{cout<<"可用分区如下:"<<endl;
cout<<"区号"<<" 分区长度"<<" 起始地址"<<endl;
pat=headat->next;
if(!pat) cout<<"可用分区为空"<<endl;
while(pat)
{cout<<pat->reg_number<<setw(10)<<pat->reg_length<<"k"<<setw(8)<<pat->start_add<<"k"<<endl;;
pat=pat->next;
}
