Round Robin

Easy
0/40
Average time to solve is 20m
profile
Contributed by
60 upvotes
Asked in company
Intuit

Problem statement

Round Robin is a CPU Scheduling algorithm where each process is assigned a fixed time slice / quantum in a cyclic manner.

You should be aware of the following terms before proceeding:

Arrival time: Time at which the process arrives.

Burst time: The time the process takes for its execution. 

Completion time: Time at which the process completes its execution.

Turn Around time: Time difference between the Completion time and the Arrival time.

Waiting time: Time difference between the Turn Around time and the Burst time.

You are given time slice / quantum and a list of processes where 'PROCESS[ i ]' denotes the Burst time of the process 'i'. Your task is to perform Round Robin scheduling and print a list of Waiting time where (i)th index of your list denotes the waiting time for 'PROCESS[ i ]'.

Note:

You can consider Arrival time for every process to be 0.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer 'T' representing the number of test cases.     
The 'T' test cases are as follows:

The first line contains two integers 'N' and 'S' denoting the number of processes and time slice / quantum for performing round-robin scheduling respectively. 

The second line contains 'N' space-separated integers, where the ith element denotes the Burst time for process 'i'.
Output Format : 
For each test case, return the list that contains 'N' integers where ith element denotes the Waiting time for process 'i'.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^2
1 <= Time slice <= 10^2
1 <= Burst time <= 10^3

Time Limit: 1 sec
Sample Input 1:
1
4 2
5 3 4 2
Sample output 1:
9 8 9 6
Explanation of Sample output 1:
The pictorial representation for the scheduling will be as follows:

alt

Waiting time for P1: 14 - 5 i.e. 9.
Waiting time for P2: 11 - 3 i.e. 8.
Waiting time for P3: 13 - 4 i.e. 9.
Waiting time for P4: 8 - 2 i.e. 6.

Thus, the output will be [ 9, 8, 9, 6 ].
Sample Input2:
1 
3 2
5 4 3
Sample Output2:
7 6 8
Hint

Can you do this iteratively? Try to solve the problem by minimising the time required for the execution of the whole process.

Approaches (1)
Iterative Approach

The problem can be solved by storing the remaining burst times in a separate array say rem and iterate over all the processes again and again until all the processes are completely executed (all the elements of rem become 0).

Algorithm:

  • Create array rem where ‘REM[ i ]’ denotes the remaining time for execution of 'PROCESS[ i ]'.
    • Initially, for all the processes:
      • 'REM[i]' =  'PROCESS[ i ]'
  • Create an extra array 'WAITING' which stores the 'WAITING' time for every process. Initialise all elements of 'WAITING' as 0.
  • Initialise a variable 'Time' as 0.
  • Loop until all the processes are executed completely:
    • If 'REM[i]' > 'TIME-SLICE':
      • Now, the process will execute for 'TIME-SLICE' seconds. Thus, update 'Time' as 'Time' + quantum.
      • Update the remaining time i.e. 'REM[i]' = 'REM[i]' - quantum.
    • Otherwise, this means that this is the last cycle of this process:
      • Now, the process will execute for its remaining time. Thus, update 'Time' as 'Time' + 'REM[i]'.
      • As this being the last cycle, update 'WAITING[ i ]’ as 'Time' - 'PROCESS[ i ]'.
      • Update 'REM[i]' = 0 as this process is completely executed.
  • Return array 'WAITING'.

Let us understand it by an example:

For a time slice of 2 seconds and process array of size 3 as [ 5, 4, 3 ] 

Initially,  'Time' = 0, rem array and 'WAITING' array are as follows:

For the first iteration of all the processes:

For the second iteration of all the processes:

 

For the third iteration of all the processes:

As all the processes are completed, we end our function. 

Time Complexity

O(S), where ‘S’ is the sum of burst time of all the processes. 

 

We will iterate all the processes until all the processes are fully completed. The processes will definitely be fully completed in O(sum of burst time of all the processes). 

Space Complexity

O(N), where ‘N’ is the number of processes.

 

We are using an extra array to store the remaining execution time for each process. 

Code Solution
(100% EXP penalty)
Round Robin
Full screen
Console