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

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

输入参数:
./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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据