Round Robin Algorithm

Brief:

Round Robin algorithm is a pre-emptive process scheduling algorithm. Round Robin algorithm gives a user a feel that the processor is running for that user only and gives a feel of multi tasking to the user. It can be easily implemented by using circular queue.

Working:

In Round Robin Algorithm , A Circular Linked List Data structure is used. We start by processing the first process in this case , Process A. for the defined time quantum. after we emptied the time quantum , we stop the processing and move to the next process i.e. process B. We continue this process of processing for the pre-emptive time and keep moving ahead if we complete any of the process, then we remove the process from the queue and move ahead processing the next process.

e.g. :

Suppose there are 6 processes , A,B,C,D,E,F . Time Quantum :- 3
PROCESS   CPU TIME REQUIRED
A                           5
B                           2
C                           3
D                           4
E                           6
F                           7

First process :- A
Last Process :- F

first cycle:
A -> 2
B -> 0 (Remove B)
C -> 0 (Remove C)
D -> 1
E -> 3
F -> 4

second cycle:
A -> 0 (Remove A)
D -> 0 (Remove D)
E -> 0 (Remove E)
F -> 1

third cycle:
F -> 0 (Remove F)

How to proceed for developing code for Round Robin Algorithm

We know that we will require a circular linked list, we will implement circular linked list with two parameters :
1. Process Time
2. Process Name

After that we want to make a function which deletes the process, we will do that by using 3 parameters:
1. Currently processed(the one to be deleted , b)
2. Next Process (a)
3. Previous Process(c)
We will delete b , and do c->next  = a so as not to disrupt the linked list.

After we made a function to delete we will require a function to process the current node (b) with the given pre-emptive time.

We have some of the problems in this ,
1. from which process we should start from? (what will  a, b , c be initially)
2. how will we delete the node if process time is satisfied?
3. what if first process is satisfied and we want to delete it, where will the first pointer point?
4. what if last process is satisfied and we want to delete it, where will the last pointer point?
5. what is the halting condition?

• We are initialising the first process to be the first node in the circular linked list, i.e. b = first; and we are setting a = b->next , c = last;   i.e. b will point towards first, a will point towards second and c will point at last node.
• We will delete a node if the time required by the process is satisfied. we will use an additional pointer d, which we will initialise as d = b; when deleting process we will delete d by using deleteProcess(a,d,c); now after we deleted the d, we have b pointing at nothing so we will have to initialise b as the next node ie a and move a ahead while not changing b. Similarly if the node to be deleted is the last node then we will do last = c; ...
• we will halt the program if a == b == c and we will then process the remaining time required for b.

CPP Program for Round Robin Algorithm

Written By, Sarvesh Bhatnagar