Round Robin Algorithm
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 :
- Process Time
- Process Name
After that we want to make a function which deletes the process, we will do that by using 3 parameters:
- Currently processed(the one to be deleted , b)
- Next Process (a)
- 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 ,
- from which process we should start from? (what will a, b , c be initially)
- how will we delete the node if process time is satisfied?
- what if first process is satisfied and we want to delete it, where will the first pointer point?
- what if last process is satisfied and we want to delete it, where will the last pointer point?
- 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.
