Round Robin with weights Algorithm
Round Robin with weights
In Round Robin Algorithm we have various disadvantages , one being frequent context switching. When we use this algorithm in practice for process scheduling overhead of context switching is very large to reduce this overhead we use Round Robin Algorithm with different weights on it according to the importance of the process where weights are directly dependent to importance of the process. In this blog post we will discuss about Round Robin with weights algorithm and how we can implement it in practice using circular linked list.
What is the significance of weights ?
We use weights in Round Robin with weights for reducing the context switch time, the weights in this algorithm determines how long will a particular process use the processor time. In other words , we determine pre-emptive time based on weights using different weight to pre-emptive time assigning technique.
How will the weights decrease the context switches?
When we increase the pre-emptive time to a particular process then it actually means that we are giving more processor time for the important processes and finishing it faster , meaning that we are doing context switches less while not losing the essence of multitasking.
Example:
Assume, We have two processes P1 and P2 , process P1 is of greater importance than process P2 in all the following cases.
For Weights of important process we give weight as 2 and for weights of normal process we give weights as 1.
We are assuming a linear model for assigning pre-emptive time,
i.e. new pre-emptive time = weight * pre-emptive time
We are Defining Cold Context switch as a processor switching the processor time to itself.
CASE 1 (P1 = P2) :-
Suppose the processes P1 and P2 both requires 10 time quantum. In Normal Round Robin Algorithm with pre-emptive time 1, we require 10 cycles to complete P1 and 10 cycles to complete P2 while we require 20 context switches for it. In Round Robin Algorithm with weights, Since we will now give 2 time quantum for processing process P1 while 1 time quantum for process P2 , we require 5 cycles for P1 and 10 cycles for P2 and we now require 10 context switches and 5 cold context switches.
CASE 2 (P1 > P2) :-
Suppose now the process P1 requires 20 time quantum and P2 requires 10 time quantum in normal Round Robin Algorithm with pre-emptive time 1 , we require 20 cycles for process P1 and 10 cycles for process P2 we require 20 context switches and 10 cold context switches. In Round Robin Algorithm with weights we require 10 cycles for completing process P1 and P2. But then we only require 20 context switches and 0 cold context switches thereby reducing the total context switches from 30 to 20.
CASE 3 (P1 < P2) :-
Suppose now the process P1 requires 10 units of time quantum and P2 requires 20 unit of time quantum , In normal Round Robin Algorithm with pre-emptive time 1, we require 10 cycles for P1 and 20 cycles for P2. We require 20 context switches and 10 cold context switches. In Round Robin Algorithm with weights, we require 5 cycles for completing P1 and 20 cycles for P2. But then we only require 10 context switches and 15 cold context switches reducing context switch from 30 to 25.
Hence, by increasing the pre-emptive time , we are reducing the context switch overhead thereby improving efficiency of the algorithm.
You might also like: Flow Shop Scheduling Algorithm
CPP Code for Round Robin with weights Algorithm :-
Written By, Sarvesh Bhatnagar
You might also like: Flow Shop Scheduling Algorithm
