[C++]FCFS/RR/SJF/SRTF/RAND 调度算法模拟

Kotarou C/C++

一些进程调度算法的模拟.

输入参数:
./a.out 8 6 15 4

源代码:

#include 
#include 
#include 
#include 
#include 
using namespace std;
// some global value
int gMaxTimeInc, gMaxBurstTime;
int gNumProcesses, gTimeSlice;
struct Process
{
int ID;
int ArriveTime;
int WaitingTime;
int BurstTime;
int RunningTime;
int TurnAroundTime;
};
typedef deque dProcess;
void printResult(deque&, string*);
bool praseInput(int, const char**);
void getNextProcess(int&, int&);
bool isDigital(const char*);
char ganttChart(int);
dProcess generateJobQueue();
dProcess FCFS(dProcess, string&);
dProcess RR(dProcess, string&);
dProcess RAND(dProcess, string&);
dProcess SJF(dProcess, string&);
dProcess SRTF(dProcess, string&);
bool sortQueue (const Process &i,const Process &j) { return (i.ID list;
list.push_back(FCFS(Jobs,buffer[0]));
list.push_back(RR(Jobs,buffer[1]));
list.push_back(SJF(Jobs,buffer[2]));
list.push_back(SRTF(Jobs,buffer[3]));
list.push_back(RAND(Jobs,buffer[4]));
printResult(list, buffer);
}
else
{
cerr << "Invalid Argument, Try again.\n";
exit(EXIT_FAILURE);
}
return 0;
}
dProcess RAND(dProcess Jobs, string &chartBuffer)
{
unsigned long Time = 0;
bool done = false;
// get the job Queue.
dProcess ReadyQueue;
dProcess EndQueue;
Process* CPU = NULL;
//main loop for RAND.
for(; !done; ++Time)
{
//check the job queue, move job to the ready queue
for(dProcess::iterator it = Jobs.begin(); it != Jobs.end();)
{
if(Time >= it->ArriveTime)
{
ReadyQueue.push_back(*it);
it = Jobs.erase(it);
}
else
++it;
}
// move finished process to EndQueue
if(CPU && CPU->RunningTime == CPU->BurstTime)
{
CPU->TurnAroundTime += Time;
EndQueue.push_back(*CPU);
CPU = NULL;
}
//make the readyqueue randomly
random_shuffle(ReadyQueue.begin(), ReadyQueue.end());
// if all job finished, set done to true, skip all code.
if(EndQueue.size() == gNumProcesses)
{
done = true;
continue;
}
// check the ReadyQueue, move the first Process into CPU
if(CPU == NULL)
{
// if nothing in readyQueue, print -
if(!ReadyQueue.empty())
{
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
else
{
chartBuffer += "-";
continue;
}
}
else
{
for(dProcess::iterator it = ReadyQueue.begin(); it != ReadyQueue.end(); ++it)
{
if(it->ArriveTime != Time)
++it->WaitingTime;
}
}
if(CPU->RunningTime != CPU->BurstTime)
{
++CPU->RunningTime;
chartBuffer += ganttChart(CPU->ID);
}
}
return EndQueue;
}
dProcess SRTF(dProcess Jobs, string &chartBuffer)
{
unsigned long Time = 0;
bool done = false;
// get the job Queue.
dProcess ReadyQueue;
dProcess EndQueue;
Process* CPU = NULL;
//main loop for SRTF.
for(; !done; ++Time)
{
//check the job queue, move job to the ready queue
for(dProcess::iterator it = Jobs.begin(); it != Jobs.end();)
{
if(Time >= it->ArriveTime)
{
ReadyQueue.push_back(*it);
it = Jobs.erase(it);
}
else
++it;
}
// move finished process to EndQueue
if(CPU && CPU->RunningTime == CPU->BurstTime)
{
CPU->TurnAroundTime += Time;
EndQueue.push_back(*CPU);
CPU = NULL;
}
// if all job finished, set done to true, skip all code.
if(EndQueue.size() == gNumProcesses)
{
done = true;
continue;
}
//sort the ready queue
sort(ReadyQueue.begin(), ReadyQueue.end(), sortForSRTF);
// check the ReadyQueue, move the first Process into CPU
if(CPU == NULL)
{
// if nothing in readyQueue, print -
if(!ReadyQueue.empty())
{
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
else
{
chartBuffer += "-";
continue;
}
}
else
{
// check the ready queue.
if(!ReadyQueue.empty())
{
Process temp = ReadyQueue.front();
if(sortForSRTF(temp, *CPU))
{
ReadyQueue.push_back(*CPU);
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
}
for(dProcess::iterator it = ReadyQueue.begin(); it != ReadyQueue.end(); ++it)
{
if(it->ArriveTime != Time)
++it->WaitingTime;
}
}
if(CPU->RunningTime != CPU->BurstTime)
{
++CPU->RunningTime;
chartBuffer += ganttChart(CPU->ID);
}
}
sort(EndQueue.begin(), EndQueue.end(), sortQueue);
return EndQueue;
}
dProcess SJF(dProcess Jobs, string &chartBuffer)
{
unsigned long Time = 0;
bool done = false;
// get the job Queue.
dProcess ReadyQueue;
dProcess EndQueue;
Process* CPU = NULL;
//main loop for SJF.
for(; !done; ++Time)
{
//check the job queue, move job to the ready queue
for(dProcess::iterator it = Jobs.begin(); it != Jobs.end();)
{
if(Time >= it->ArriveTime)
{
ReadyQueue.push_back(*it);
it = Jobs.erase(it);
}
else
++it;
}
//sort the ready queue
sort(ReadyQueue.begin(), ReadyQueue.end(), sortForSJF);
// move finished process to EndQueue
if(CPU && CPU->RunningTime == CPU->BurstTime)
{
CPU->TurnAroundTime += Time;
EndQueue.push_back(*CPU);
CPU = NULL;
}
// if all job finished, set done to true, skip all code.
if(EndQueue.size() == gNumProcesses)
{
done = true;
continue;
}
// check the ReadyQueue, move the first Process into CPU
if(CPU == NULL)
{
// if nothing in readyQueue, print -
if(!ReadyQueue.empty())
{
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
else
{
chartBuffer += "-";
continue;
}
}
else
{
for(dProcess::iterator it = ReadyQueue.begin(); it != ReadyQueue.end(); ++it)
{
if(it->ArriveTime != Time)
++it->WaitingTime;
}
}
if(CPU->RunningTime != CPU->BurstTime)
{
++CPU->RunningTime;
chartBuffer += ganttChart(CPU->ID);
}
}
sort(EndQueue.begin(), EndQueue.end(), sortQueue);
return EndQueue;
}
dProcess RR(dProcess Jobs, string &chartBuffer)
{
unsigned long Time = 0;
bool done = false;
// get the job Queue.
dProcess ReadyQueue;
dProcess EndQueue;
Process* CPU = NULL;
//main loop for FCFS.
for(; !done; ++Time)
{
//check the job queue, move job to the ready queue
for(dProcess::iterator it = Jobs.begin(); it != Jobs.end();)
{
if(Time >= it->ArriveTime)
{
ReadyQueue.push_back(*it);
it = Jobs.erase(it);
}
else
++it;
}
// move finished process to EndQueue
if(CPU && CPU->RunningTime == CPU->BurstTime)
{
CPU->TurnAroundTime += Time;
EndQueue.push_back(*CPU);
CPU = NULL;
}
// push process back to the readyqueue
if(CPU && CPU->RunningTime != CPU->BurstTime && CPU->RunningTime % gTimeSlice == 0)
{
ReadyQueue.push_back(*CPU);
CPU = NULL;
}
// if all job finished, set done to true, skip all code.
if(EndQueue.size() == gNumProcesses)
{
done = true;
continue;
}
// check the ReadyQueue, move the first Process into CPU
if(CPU == NULL)
{
// if nothing in readyQueue, print -
if(!ReadyQueue.empty())
{
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
else
{
chartBuffer += "-";
continue;
}
}
else
{
for(dProcess::iterator it = ReadyQueue.begin(); it != ReadyQueue.end(); ++it)
{
if(it->ArriveTime != Time)
++it->WaitingTime;
}
}
if(CPU->RunningTime != CPU->BurstTime)
{
++CPU->RunningTime;
chartBuffer += ganttChart(CPU->ID);
}
}
sort(EndQueue.begin(),EndQueue.end(),sortQueue);
return EndQueue;
}
dProcess FCFS(dProcess Jobs, string &chartBuffer)
{
unsigned long Time = 0;
bool done = false;
// get the job Queue.
dProcess ReadyQueue;
dProcess EndQueue;
Process* CPU = NULL;
//main loop for FCFS.
for(; !done; ++Time)
{
//check the job queue, move job to the ready queue
for(dProcess::iterator it = Jobs.begin(); it != Jobs.end();)
{
if(Time >= it->ArriveTime)
{
ReadyQueue.push_back(*it);
it = Jobs.erase(it);
}
else
++it;
}
// move finished process to EndQueue
if(CPU && CPU->RunningTime == CPU->BurstTime)
{
CPU->TurnAroundTime += Time;
EndQueue.push_back(*CPU);
CPU = NULL;
}
// if all job finished, set done to true, skip all code.
if(EndQueue.size() == gNumProcesses)
{
done = true;
continue;
}
// check the ReadyQueue, move the first Process into CPU
if(CPU == NULL)
{
// if nothing in readyQueue, print -
if(!ReadyQueue.empty())
{
CPU = &ReadyQueue.front();
ReadyQueue.pop_front();
}
else
{
chartBuffer += "-";
continue;
}
}
else
{
for(dProcess::iterator it = ReadyQueue.begin(); it != ReadyQueue.end(); ++it)
{
if(it->ArriveTime != Time)
++it->WaitingTime;
}
}
if(CPU->RunningTime != CPU->BurstTime)
{
++CPU->RunningTime;
chartBuffer += ganttChart(CPU->ID);
}
}
return EndQueue;
}
void getNextProcess(int &ArrivalTime, int &BurstTime)
{
static int PrevTime=-1;
if(PrevTime == -1)
PrevTime = ArrivalTime = 0;
else
ArrivalTime = PrevTime + 1 + rand() % gMaxTimeInc;
BurstTime = 1 + rand() % gMaxBurstTime;
PrevTime = ArrivalTime;
}
dProcess generateJobQueue()
{
dProcess JobQueue;
for(int i = 0; i < gNumProcesses; ++i)
{
Process temp;
temp.ID = i;
temp.WaitingTime = 0;
temp.RunningTime = 0;
getNextProcess(temp.ArriveTime, temp.BurstTime);
temp.TurnAroundTime = 0 - temp.ArriveTime;
JobQueue.push_back(temp);
}
return JobQueue;
}
bool praseInput(int num, const char **input)
{
if(num < 5)
return false;
if(isDigital(input[1]) && isDigital(input[2]) && isDigital(input[3]) && isDigital(input[4]))
{
gNumProcesses = atoi(input[1]);
gMaxTimeInc = atoi(input[2]);
gMaxBurstTime = atoi(input[3]);
gTimeSlice = atoi(input[4]);
return true;
}
return false;
}
bool isDigital(const char *num)
{
size_t len = strlen(num);
for(size_t i = 0; i < len; ++i)
{
if(!isdigit(num[i]))
return false;
}
return true;
}
char ganttChart(int index)
{
while(index >= 62)
index -= 62;
if(index >= 0 && index <= 9)
return 48 + index;
else if(index >= 10 && index <= 35)
return 55 + index;
else if(index >= 36 && index <= 61)
return 61 + index;
return 0;
}
void printResult(deque &Queue, string *ChartArray)
{
printf("%16s%11s%13s%12s%12s\n","FCFS", "RR", "SJF", "SRTF", "RAND");
printf("%8s%5s%5s%7s%5s%7s%5s%7s%5s%7s%5s\n", "BT", "WT", "TT", "WT", "TT", "WT", "TT", "WT", "TT", "WT", "TT");
int waiting[5] = {}, turn[5] = {};
dProcess dp[5];
for(int i = 0; i < 5; ++i)
{
dp[i] = Queue.front();
Queue.pop_front();
}
for(int i = 0; i < gNumProcesses; ++i)
{
printf("P%-5d", i);
Process ps;
for(int j = 0; j < 5; ++j)
{
ps = dp[j].front();
dp[j].pop_front();
waiting[j] += ps.WaitingTime;
turn[j] += ps.TurnAroundTime;
if(j == 0)
printf("%-5d", ps.BurstTime);
printf("%-5d%-7d", ps.WaitingTime, ps.TurnAroundTime);
}
printf("\n");
}
printf("%-11s", "Average:");
for(int i = 0; i < 5; ++i)
{
printf("%-5d%-7d", waiting[i] / gNumProcesses, turn[i] / gNumProcesses);
}
printf("\n\n%-6s%s\n", "FCFS:", ChartArray[0].c_str());
printf("%-6s%s\n", "RR:", ChartArray[1].c_str());
printf("%-6s%s\n", "SJF:", ChartArray[2].c_str());
printf("%-6s%s\n", "SRTF:", ChartArray[3].c_str());
printf("%-6s%s\n", "RAND:", ChartArray[4].c_str());
}

运行结果:
QQ20151008-1@2x