Online Tutorials & Training Materials | STechies.com
Register Login

Round Robin Scheduling

|| 0

Round Robin Scheduling
Stechies

What is Round Robin Scheduling

Round Robin Scheduling is a pre-emptive scheduling algorithm that is used to schedule CPU utilization tasks, where each task is assigned a fixed time slot to execute known as quantum value. Once a task is executed for his assigned quantum value, it gets interrupted, and then the next task is executed until its quantum value. If a particular task is not completed in their assigned quantum value/time slot, then the algorithm moves to the next task, which arrives in the quantum, this makes Round Robin Scheduling a preemptive scheduling algorithm.

Note:

  • It is also known as Time slicing Scheduling
  • Round Robin Scheduling works on First Come First Serve approach.
  • A time slot (quantum value) is assigned to each sheduled task
  • It is a fair process scheduling algorithm because no priority is given to any process or task

Pro and Cons of Round Robin Scheduling

Pros.

  • Round Robin Scheduling is cyclic in nature; therefore, starvation does not occur
  • The CPU executes every task for a fixed time; therefore, every task has the same priority.

Cons.

  • Cannot assign priority for any task

How Round Robin Scheduling Works

  • First, the tasks are queued in first come first serve order.
  • A quantum value (time slot) is assigned to each task need to be executed.
  • The first task executes until quantum value ends. After this, the task becomes pre-emptive
  • Then the CPU moves to the next task for execution.
  • The same process repeats until all the task is complete.

Round Robin Scheduling Program in C

#include<stdio.h>
#include<stdlib.h>
int processes[100][3], NP, quantum, ProcessScheduler[1000],WaitingTime[100];
unsigned int time = 0;
typedef struct el
{
	unsigned int p;
	struct el * next;
}Q;
Q * queue = NULL;

//Function to get input from user (e.g. number of process, Quantum Time etc )

void getSystem()
{
	int i;
	printf("\nNumber of processes: ");
	scanf("%d", &NP);
	
	printf("\nThe Quantum: ");
	scanf("%d", &quantum);
	
	for(i=0; i<NP; i++ )
	{
		printf("\n Arrival Time of process%d: ", i);
		scanf("%d", &processes[i][0]);
		printf("\n Burst time for process%d: ", i);
		scanf("%d", &processes[i][1]);
		processes[i][2] = processes[i][1];
		printf("\n-----------");
	}
}

//Printing the output for which process is running and how much remaining for the process
void printSystem()
{
	int i;
	printf("\n\n******************************************************************");
	printf("\nQuantum Time: %d",quantum);
	printf("\nProcess:  Arrival-Time  Burst-Time Remaining-Time");
	for(i=0; i<NP; i++)
	{
		printf("\nProcess%d:  \t%d  \t\t%d  \t\t%d", i, processes[i][0], processes[i][1], processes[i][2]);
		printf("\n______________________________________________________");
	}
	printf("\nProcess in the Queue: ");
	Q *n;
	for(n=queue; n!=NULL; n=n->next)
	{
		printf("Process%d ",n->p);
	}
}

//Function to get remaining time for the process

unsigned int executionRemained()
{
	int i;
	unsigned int x = 0;
	for(i=0; i<NP; i++)
	{
		if(processes[i][2] > 0)
		{
			x = 1;
		}
	}
	return x;
}

//Function to add process in the Queue
void addToQueue(int i)
{
	Q *n, *n1;
	n = (Q *)malloc(sizeof(Q));
	n->next = NULL;
	n->p = i;
	if(queue == NULL)
	{
		
		queue = n;
	}
	else
	{
		for(n1 = queue ; n1->next!=NULL; n1=n1->next);
		n1 -> next = n;
	}
}

//Function Adding the arrived process into the queue
void addArrivedProcessesToQueue()
{
	int i;
	for(i=0; i<NP; i++)
	{
		if(processes[i][0] == time)
		{
			addToQueue(i);
		}
	}
}

//Function returns the next process in the queue
unsigned int getNextProcess()
{
	Q *n;
	int x;
	if(queue == NULL)
	{
		return -1;
	}
	else
	{
		x = queue -> p;
		n = queue;
		queue = queue -> next;
		free(n);
		return x;
	}
}

//function to get the schedule of the process

void schedule()
{
	unsigned int np, toRun, q, i;
	q = 0;
	addArrivedProcessesToQueue();
	while(executionRemained())
	{
		np = getNextProcess();
		if(np == -1)
		{
			/*
			here if there is no process in waiting queue
			which mean the process get IDLe state.
			here in this program we put -1 in ProcessScheduler[time]
			which mean that the processor get IDLE in this time.
			
			*/
			ProcessScheduler[time] = -1;
			time++;
			addArrivedProcessesToQueue();
		}
		else
		{
			q = quantum;
			if(processes[np][2] < q)
			{
				q = processes[np][2];
			}
			for(i = q; i>0; i--)
			{
				ProcessScheduler[time]=np;
				time++;
				processes[np][2]--;
				addArrivedProcessesToQueue();
			}
			if(processes[np][2] > 0)
			{
				addToQueue(np);
			}
		}
		
		
		printSystem();
		int x;
		
	}
}

//Function to print the scheduling of the process during the life time
//This function also give the average waiting time for all the process
void printScheduling()
{
	int i;
	printf("\n\nScheduling Progress Throughout the program : \n");
	for(i=0; i<time; i++)
	{
		printf("\n[%d-%d] (Process%d) \n",i,i+1 ,ProcessScheduler[i]);
		printf("\n______________________________");
	}
	printf("\n\nWaiting Time Per Process : \n");
	for(i=0; i<NP; i++)
	{
		printf("\nP%d: %d", i, WaitingTime[i]);
	}
	//counting Average Waiting Time...
	float AverageWaitingTime = 0.0;
	for(i=0; i<NP; i++)
	{
		AverageWaitingTime = AverageWaitingTime+WaitingTime[i];
	}
	AverageWaitingTime = AverageWaitingTime/NP;
	printf("\n\nAverage Waiting Time: %f", AverageWaitingTime);
	
}

//Function to get the waiting time for all the process individually

void WatingTime()
{
	int i;
	unsigned int releaseTime, t;
	for(i=0; i<NP; i++)
	{
		
		for(t=time-1; ProcessScheduler[t]!= i; t--);
		releaseTime = t+1;
		WaitingTime[i] = releaseTime - processes[i][0] - processes[i][1];
	}
}

//Main function of the program
main()
{
	getSystem();
	printSystem();
	schedule();
	WatingTime();
	printScheduling();
}