Last Updated: 7 Apr, 2021

Round Robin Scheduling with different arrival times

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

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

Sort the processes in increasing order of arrival time.
Create an array/list “remTime” to store the remaining time for each process and initialize it with the burst time of each process.
Create an array/list “completionTime” to store the completion time for each process.
Create a queue “readyQueue,” which stores the processes which are currently in the ready queue. Push the first process (which arrived earliest).
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.
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.
Return the completionTime for all the processes.

Solve now