Last Updated: 7 Apr, 2021

Round Robin Scheduling

Easy

Asked in companies

Solve now

Problem statement

In an operating system, processes are scheduled to execute using many algorithms, of which one is the Round Robin Algorithm. This algorithm ensures democracy in utilizing the CPU time for each of the processes currently in execution.

Assuming that all the processes start executing at the same time, each process gets a fixed time slot (say t seconds) for execution, after which it has to let the next process take the CPU. Let there be 5 processes (p1, p2, p3, p4 and p5) ready for execution. If p1 accesses the CPU at time t0, it should give access to p2 after t0+t seconds and wait. p2 executes from t0+t to t0+2t and so on. Once p5 completes its share of CPU usage, p1 gets its next chance.

Each process can leave this execution loop when its own execution time is over. Therefore, the process with the largest execution time will be the one that would be the last process waiting. Simulate the Round Robin algorithm execution using the set of process burst times and process ids are given.

The processes (runtime) are to be inserted into the queue first and then decremented (by CPU execution time) for each iteration through the queue until their runtime is over.

For Example

Input: 
# Process id's 
proc = [1, 2, 3]
n = 3

# Burst time of all processes 
burst_time = [10, 5, 8] 

# Time quantum 
quantum = 2;

Output:

Processes  Burst time  Waiting time  Turnaround time
1          10          13            23
2          5           10            15
3          8           13            21

Average waiting time = 12
Average turnaround time = 19.6667

Input Format:

The first line of input is the number of  test cases ‘T’ which are going to be there 

The first line of each test case would be two space-separated integers majorly representing the  ‘numberOfProcesses’ and ‘timeQuanta’.

The second line of each test case contains 'numberOfProcesses' space-separated integers denoting the elements of the array processes.

The third line of each test case contains 'numberOfProcesses' space-separated integers denoting the burst-times of the processes given.

Output Format:

For every test case, print the average wait time and turn around time for the calculated set of processes given the round-robin strategy which is to be used. Print the closest integer less than or equal to a given number.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraint :

1 <= T <= 5
1 <= process.length <= 10^5
1 <= processId <= process.length
1 <= burstTimes.length <= process.length
1 <= burstTimes <= 10^5
1 <= timeQuantum <= burst times

Where ‘process.length’ would denote the number of process id which would be given the schedule using the round-robin algorithm, where ‘burstTimes’ are the running times of the given processes (CPU execution times) while the “timeQuantum” is the time duration (slot).

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach: The tricky part is to compute waiting times. Once waiting times are computed, turn around times can be quickly calculated.

The required terms used here are as follows:

Completion Time: Time at which process completes its execution.

Turn Around Time: Time Difference between completion time and arrival time.

Turn Around Time = Completion Time – Arrival Time

Waiting Time(W.T.): Time Difference between turn around time and burst time.

Waiting Time = Turnaround Time – Burst Time

The algorithm to calculate waiting time and turnaround times will be-

Create a list (array) ‘REM_BT’ to keep track of remaining burst time of processes. This list is initially a copy of the ‘BT’ (burst times list)
Create another list (array) ‘WT’ to store waiting times of processes. Initialize this list (array) as 0.
Initialize time 'T' as 0.
Keep traversing all processes while all processes are not done. Do the following for ‘i’ th process if it is not done yet.
- If ‘REM_BT[i]’ > ‘QUANTUM’:
  - Then increment ‘T’ by ‘QUANTUM’.
  - Decrement ‘REM_BT[i]’ by ‘QUANTUM’.
- Else it is last cycle for this process.
  - Then increment ‘T’ by ‘QUANTUM’.
  - Assign the value of ‘T’ - ‘BT[i]’ to ‘WT[i]’.
  - Assign the value 0 to ‘REM_WT[i]’.

5. Once we have waiting times, we can compute turn around time ‘TAT[i]’ of a process as sum of waiting and burst times, i.e., ‘WT[i] + BT[i]’.

6. We finally return the average waiting time and average turnaround time.

Solve now