#include <iostream>
#include <string>
#include <vector>
using namespace std;
#ifndef ROUND_ROBIN
#define ROUND_ROBIN 3/*时间片大小*/
#endif
#ifndef WAIT
#define WAIT -1/*等待状态*/
#endif
#ifndef READY
#define READY 0/*就绪状态*/
#endif
#ifndef RUN
#define RUN 1/*运行状态*/
#endif
#ifndef FLISH
#define FLISH 2/*完成状态*/
#endif
typedef unsigned int u16;
typedef unsigned long u32;
typedef string::size_type u16;
class PCB
{
public:
PCB(string name, u32 cometime, u32 needtime);/*创建进程*/
u16 InitPriority();/*初始化进程优先级*/
u16 calRunTime(u16 numberofprocess);/*计算经常周转时间、同时更新就绪进程的优先级*/
u16 show();/*显示就绪队列中各进程信息*/
u16 show(const PCB *pcb);/*显示当前正在运行进程的信息*/
u32 getEndTime();/*获得进程结束时间*/
double getRountTime();/*获得进程周转时间*/
double getRountWheitTime();/*获得带权周转时间*/
private:
string ProcessName;/*进程名*/
static u16 numberofprocess;/*进程计数*/
u16 PID;/*进程号*/
u16 Priority;/*进程优先级*/
u32 ComeTime;/*到达时间*/
u32 EndTime;/*结束时间*/
u32 NeedRunTime;/*估计运行时间*/
u32 RunTime;/*周转时间*/
u32 NextNeedTime;/*还需时间*/
int ProcessStatus;/*进程状态*/
};
u16 PCB::numberofprocess = 1;
typedef vector<PCB>::size_type u16;
vector<PCB> WaitQueue, ReadyQueue;/*等待队列、就绪队列*/
PCB::PCB(string name, u32 cometime, u32 needtime)
{
ProcessStatus = WAIT;
ProcessName = name;
Priority = 0;
ComeTime = cometime;
NeedRunTime = needtime;
NextNeedTime = NeedRunTime;
RunTime = 0;
PID = numberofprocess;
numberofprocess ++;
}
u16 PCB::InitPriority( )
{
u16 i, j, k, size, minpriority, starttime = 1000000;
size = WaitQueue.size();
for(i = 0; i != size; i ++)
{
if (WaitQueue[i].ComeTime < starttime)
starttime = WaitQueue[i].ComeTime;
}
for (i = 0; i != size; i ++)
{
minpriority = 100000;
loop:
for (j = 0; j != size; j ++)
{
if (WaitQueue[j].Priority == 0 && WaitQueue[j].ComeTime == starttime && WaitQueue[j].NeedRunTime < minpriority)
{
k = j;
minpriority = WaitQueue[j].NeedRunTime;
}
}
if (minpriority == 100000)
{
starttime ++;
goto loop;
}
WaitQueue[k].Priority = size - i;
ReadyQueue.push_back(WaitQueue[k]);
ReadyQueue[i].ProcessStatus = READY;
}
return 1;
}
u16 PCB::calRunTime(u16 numberofprocess)
{
u16 i, j, k, max = 0;
u16 size = ReadyQueue.size();
i = 1;
while(numberofprocess != 0)
{
cout << "第 " << i ++ << " 次调度"<< endl;
max = 0;
for (j = 0; j < size; j ++)
{
if (ReadyQueue[j].ProcessStatus != FLISH && ReadyQueue[j].Priority > max)
{
k = j;
max = ReadyQueue[j].Priority;
}
}
ReadyQueue[k].ProcessStatus = RUN;
for (j = 0; j < size; j ++)
{
if (j != k && ReadyQueue[j].ProcessStatus != FLISH && ReadyQueue[j].ComeTime <= ReadyQueue[k].ComeTime + ReadyQueue[k].RunTime)
{
ReadyQueue[j].RunTime += ROUND_ROBIN;
ReadyQueue[j].Priority ++;
}
}
ReadyQueue[k].show(&ReadyQueue[k]);
ReadyQueue[k].RunTime += ROUND_ROBIN;
if (ReadyQueue[k].NextNeedTime <= ROUND_ROBIN)
{
ReadyQueue[k].NextNeedTime = 0;
ReadyQueue[k].EndTime = ReadyQueue[k].ComeTime + ReadyQueue[k].RunTime;
ReadyQueue[k].ProcessStatus = FLISH;
numberofprocess --;
ReadyQueue[k].show();
}
else
{
ReadyQueue[k].show();
ReadyQueue[k].NextNeedTime -= ROUND_ROBIN;
ReadyQueue[k].ProcessStatus = READY;
ReadyQueue[k].Priority = 1;
}
system("pause");
cout << endl;
}
return 1;
}
u32 PCB::getEndTime()
{
return this->EndTime - this->ComeTime;
}
double PCB::getRountTime()
{
double aver;
aver = (double) this->EndTime - this->ComeTime;
return aver;
}
double PCB::getRountWheitTime()
{
double aver;
aver = getRountTime() / this->NeedRunTime;
return aver;
}
u16 PCB::show()
{
u16 i, size;
PCB *pcb;
cout << "*****Readying...*****" << endl;
cout << "PID " << "Name " << "ComeTime " << "RoundTime " << "Priority " << "NextNeedTime " << endl;
cout << "--------------------------------------------------------------" << endl;
size = ReadyQueue.size();
for(i = 0; i != size; i ++)
{
pcb = &ReadyQueue[i];
if (pcb->ProcessStatus == READY && pcb->RunTime != 0)
{
u16 len = pcb->ProcessName.length();
cout << pcb->PID << " " << pcb->ProcessName;
for(u16 j = 0; j != 14 - len; j ++)
cout << ' ';
cout << pcb->ComeTime << " "
<< pcb->RunTime << " "
<< pcb->Priority << " "
<< pcb->NextNeedTime << " "
<< endl;
}
}
cout << "--------------------------------------------------------------" << endl << endl;;
return 1;
}
u16 PCB::show(const PCB *pcb)
{
u16 len = pcb->ProcessName.length();
cout << "*****Runing...****" << endl;
cout << "PID " << "Name " << "ComeTime " << "RoundTime " << "Priority " << "NextNeedTime " << endl;
cout << "--------------------------------------------------------------" << endl;
cout << pcb->PID << " " << pcb->ProcessName;
for(u16 j = 0; j != 14 - len; j ++)
cout << ' ';
cout << pcb->ComeTime << " "
<< pcb->RunTime << " "
<< pcb->Priority << " "
<< pcb->NextNeedTime << " "
<< endl;
cout << "--------------------------------------------------------------" << endl << endl;
return 1;
}
int main()
{
double AverRountTime = 0;
double AverRountWheitTime = 0;
string name;
u16 i;
u16 NumberOfProcess;
u32 cometime, needtime;
cout << "Please input the number of process:" << endl;
cin >> NumberOfProcess;
PCB *pcb;
for(i = 0; i != NumberOfProcess; i ++)
{
cout << "Please input process " << i + 1 << "'s NAME, COMETIME and NEEDTIME" << endl;
cin >> name >> cometime >> needtime;
pcb = new PCB(name, cometime, needtime);
WaitQueue.push_back(*pcb);
}
cout << endl << "*******BEGIN*******" << endl << endl;
pcb->InitPriority();
pcb->calRunTime(NumberOfProcess);
cout << "*******调度完成...*******" << endl << endl;
for(i = 0; i != NumberOfProcess; i ++)
{
AverRountTime += ReadyQueue[i].getRountTime();
AverRountWheitTime += ReadyQueue[i].getRountWheitTime();
}
AverRountTime /= NumberOfProcess;
AverRountWheitTime /= NumberOfProcess;
cout << "\t**************REUSLT***************" << endl;
cout << "\t* \t\t\t\t *" << endl;
printf( "\t* The AverRountTime is: %.2lf *\n", AverRountTime);
cout << "\t* \t\t\t\t *" << endl;
printf( "\t* The AverRountWheitTime is: %.2lf *\n", AverRountWheitTime);
cout << "\t* \t\t\t\t *" << endl;
cout << "\t**************END******************" << endl;
system("pause");
return 1;
}
/*
4
du 1 1
dd 1 2
da 1 23
ds 2 2
4
du 1 2
zhao 1 1
zhaodu 2 2
duzhao 3 2
2
du 1 1
zhao 2 3
*/