#include<iostream>
#include<cstdlib>
#include<ctime>
#include<windows.h>
using namespace std;
#define N 5
enum STATUS{
RUN,
READY,
FINISH,
WAIT
};
typedef struct _tagPCB
{
int pid;
char name[20];
int priority;
int cputime;
int timeneed;
int arrivetime;
char *protection;
STATUS status;
struct _tagPCB* next;
}PCB,*PPCB;
PPCB run=0,
ready=0,
tail=0,
finish=0,
arrive=0;
char algo='J';
int EscapeTime=0;
int RandRange(int min=50,int max=100)
{
return(int)(((double)rand()/(double)RAND_MAX)*(max-min)+min);
}
void Insert1(PPCB p)
{
PPCB tmp,q;
if(ready==NULL)
{
ready=p;
tail=p;
}
{
if(p->priority>ready->priority)
{
p->next=ready;
ready=p;
}
else
{
tmp=ready;
while(tmp!=NULL&&tmp->priority>=p->priority)
{
q=tmp;
tmp=tmp->next;
}
q->next=p;
p->next=tmp;
if(tmp==NULL)
tail=p;
}
}
}
void Insert2(PPCB p)
{
if(ready==NULL)
{
ready=tail=p;
}
else
{
tail->next=p;
p->next=NULL;
tail=p;
}
}
void Insert3(PPCB p)
{
PPCB tmp,q;
if(ready==NULL)
{
ready=p;
tail=p;
}
else
{
if(p->timeneed<ready->timeneed)
{
p->next=ready;
ready=p;
}
else
{
tmp=ready;
while(tmp!=NULL&&tmp->timeneed<=p->timeneed)
{
q=tmp;
tmp=tmp->next;
}
q->next=p;
p->next=tmp;
if(tmp==NULL)
tail=p;
}
}
}
void InsertArrive(PPCB p)
{
PPCB tmp,q;
if(arrive==NULL)
arrive=p;
else
{
if(p->arrivetime<arrive->arrivetime)
{
p->next=arrive;
arrive=p;
}
else
{
tmp=arrive;
while(tmp!=NULL&&tmp->arrivetime<=p->arrivetime)
{
q=tmp;
tmp=tmp->next;
}
q->next=p;
p->next=tmp;
}
}
}
void Insert(PPCB p)
{
if(algo=='P')
{
Insert1(p);
}
else if(algo=='R')
{
Insert2(p);
}
else if(algo=='S')
{
Insert3(p);
}
else if(algo=='J')
{
Insert3(p);
}
}
void CreateProcesses()
{
PPCB p;
for(int i=0;i<N;i++)
{
p=new PCB;
p->cputime=0;
p->timeneed=RandRange(1,20);
p->pid=i;
p->arrivetime=RandRange(0,N*2);
p->priority=RandRange(64,128);
p->status=READY;
p->name[0]=0;
p->next=0;
p->protection=0;
if(p->arrivetime==0)
Insert(p);
else
InsertArrive(p);
}
}
void DistroyProcesses(PPCB head)
{
PPCB p;
while(head)
{
p=head;
head=head->next;
delete p;
}
}
void PrintList(PPCB head)
{
if(!head)
return;
cout<<"进程id"<<'\t'<<"优先级"<<'\t'<<"用时"<<'\t'<<"需要时间"<<'\t'<<"到达时间"<<endl;
while(head)
{
cout<<head->pid<<'\t'<<head->priority<<'\t'<<head->cputime<<'\t'<<head->timeneed<<'\t'<<head->arrivetime<<endl;
head=head->next;
}
}
void PrioritySchedular()
{
while(ready||arrive)
{
if(ready==0)
{
EscapeTime++;
while(arrive->arrivetime==EscapeTime)
{
PPCB tmp;
tmp=arrive;
arrive=arrive->next;
tmp->next=0;
Insert(tmp);
}
continue;
}
run=ready;
ready=ready->next;
run->status=RUN;
if(algo=='P')
run->priority-=3;
run->timeneed--;
run->cputime++;
Sleep(100);
cout<<"运行进程的信息"<<endl;
cout<<"进程id"<<'\t'<<"优先级"<<'\t'<<"用时"<<'\t'<<"需要时间"<<endl;
cout<<run->pid<<'\t'<<run->priority<<'\t'<<run->cputime<<'\t'<<run->timeneed<<endl;
if(run->timeneed>0)
Insert(run);
else
{
run->next=finish;
finish=run;
}
EscapeTime++;
while(arrive&&arrive->arrivetime==EscapeTime)
{
PPCB tmp;
tmp=arrive;
arrive=arrive->next;
tmp->next=0;
Insert(tmp);
}
cout<<"就绪进程队列的信息"<<endl;
PrintList(ready);
cout<<"完成进程队列的信息"<<endl;
PrintList(finish);
cout<<"============================================"<<endl;
}
}
void Round_Robin()
{
PrioritySchedular();
}
void SRTF()
{
PrioritySchedular();
}
void SJF()
{
while(ready||arrive)
{
if(ready==0)
{
EscapeTime++;
while(arrive->arrivetime<=EscapeTime)
{
PPCB tmp;
tmp=arrive;
arrive=arrive->next;
tmp->next=0;
Insert(tmp);
}
continue;
}
run=ready;
ready=ready->next;
run->status=RUN;
run->cputime=run->timeneed;
run->timeneed=0;
cout<<"运行进程的信息"<<endl;
cout<<"进程id"<<'\t'<<"优先级"<<'\t'<<"用时"<<'\t'<<"需要时间"<<endl;
cout<<run->pid<<'\t'<<run->priority<<'\t'<<run->cputime<<'\t'<<run->timeneed<<endl;
run->status=FINISH;
run->next=finish;
finish=run;
EscapeTime+=run->cputime;
while(arrive&&arrive->arrivetime<=EscapeTime)
{
PPCB tmp;
tmp=arrive;
arrive=arrive->next;
tmp->next=0;
Insert(tmp);
}
cout<<"就绪进程队列的信息"<<endl;
PrintList(ready);
cout<<"完成进程队列的信息"<<endl;
PrintList(finish);
cout<<"============================================"<<endl;
}
}
void main()
{
srand((unsigned int)(time(NULL)));
CreateProcesses();
PrintList(arrive);
cout<<"请输入调度类型"<<endl;
cout<<"P__优先级调度"<<endl;
cout<<"R__时间片调度"<<endl;
cout<<"S__最短剩余时间调度"<<endl;
cout<<"J__最短作业优先"<<endl;
cout<<"F__先来先服务"<<endl;
cin>>algo;
switch(algo)
{
case'P':
PrioritySchedular();
break;
case'R':
Round_Robin();
break;
case'S':
SRTF();
break;
case'J':
SJF();
break;
case'F':
break;
default:
break;
}
DistroyProcesses(finish);
}