Round Robin Scheduling with different arrival times

Moderate
0/80
Average time to solve is 30m
6 upvotes
Asked in companies
OlaAmazonGoogle inc

Problem statement

You have been given the ‘N’ process with process id’s from 1 to ‘N’. For each process, you are given the arrival time and burst time. You are also provided with the time quantum. Now you are supposed to execute a round-robin scheduling algorithm and find the completion time for each given process.

Please refer to Round-robin_scheduling for more detailed information .

Note: 
A time quantum is associated with the algorithm. Each process gets CPU for some units of time, which are decided by time quantum value, and then again enter the ready queue if they have burst time remaining.

Arrival Time - The time when the process enters the system and is ready for execution.

Burst Time - The total time taken by the process for execution.

Completion Time - The time when the process completes its execution and leaves the system.
Note: 
If two processes are having the same arrival time, then a process with a lower ID will be executed first.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two integers ‘N’ and ‘M’, denoting the number of processes and the quantum time, respectively.

Each of the next ‘N’ lines contains two space integers denoting the arrival time and burst time of the ith process.
Output Format : 
For each test case, print a single line containing ‘N’ space-separated integers denoting the complete time of each process.

The output of each test case will be printed in a separate line.
Note : 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
1 <= N <= 1000
1 <= M <= 1000
1 <= ARRIVALTIME[i], BURSTTIME[i] <= 1000

Where ‘N’ and ‘M’ denotes the number of processes and the quantum time, respectively.

Time limit: 1 sec
Sample Input 1 :
2
4 2
0 5
1 4
2 2
3 1
1 4
3 5
Sample output 1 :
12 11 6 9 
8
Explanation of Sample output 1 :
For the first test case,
Assume {a, (l : r)} denotes a pair of integers where ‘a’ denotes the process index and (l : r) denotes the start time ( l ) and end time ( r ) of a particular instance of execution. Basically it means process ‘a’ got executed from lth to rth unit of time. Following round robin scheduling the execution order will be  {0, (0 : 2)} -> {1, (2 : 4)} -> {2, (4 : 6)} -> {0, (6 : 8)} -> {4, (8 : 9)} -> {1, (9: 11)} -> {0, (11: 12)}. 

For the second test case, there is only one process. Its completion time will be 8.
Sample Input 2 :
2
2 10
0 3
0 5
2 1
1 1
2 1
Sample output 2 :
3 8
2 3
Explanation of Sample output 2 :
For the first test case, the completion time of processes will be [3, 8].

For the second test case, the completion time of processes will be [2, 3].
Hint

Can you think of using a queue?

Approaches (1)
Queue based approach.

The basic idea of this approach is to use a queue to solve the problem. We’ll keep the process in the queue which needs to be executed. And when a process is executed for the time quantum time, then we’ll push it to the end of the queue.


 

Consider the following steps:

  1. Sort the processes in increasing order of arrival time.
  2. Create an array/list “remTime” to store the remaining time for each process and initialize it with the burst time of each process.
  3. Create an array/list “completionTime” to store the completion time for each process.
  4. Create a queue “readyQueue,” which stores the processes which are currently in the ready queue. Push the first process (which arrived earliest).
  5. Also, create two variables “currentTime” and “completed,” to store the current time and to store the total completed processes. We’ll initialize the “currentTime” with the arrival time of the first process.
  6. Iterate until each process is not complete.
    • Extract the front element from the “readyQueue” and check if its remaining burst time is less than the time quantum. If it is, then complete executing the process and store the completion time for this process. Increment the “completed” variable. Also, update the currentTime accordingly.
    • Now, push all the processes in the readyTueue, for which the arrival time is less than the current time.
    • Push the current process at the end of the queue if the remaining burst time is greater than zero.
    • If the readQueue is empty, but all the processes are not executed, then push the next process in the queue and update the currentTime with its arrival time.
  7. Return the completionTime for all the processes.
Time Complexity

O(N * log(N) + W / M), where ‘N’ is the total number of processes, and ‘W’ is the sum of burst times of the given process, and ‘M’ is the time quantum.

 

Since we are sorting the array/list of processes which will take O(N * log(N)) time and then at each iteration, we are executing a process for at max one quantum time, so the overall time complexity will be O(N * log(N) + W / M).

Space Complexity

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

 

Since we are using an array/list to store the remaining burst time and completion time for each process and also using a queue that stores at max ‘N’ elements so the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Round Robin Scheduling with different arrival times
Full screen
Console