Last Updated: 15 Jan, 2021

Round Robin

Easy

Asked in company

Solve now

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.

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

Solve now

Approaches

01 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: