Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Shortest Job First(Non - preemptive)

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
8 upvotes
Asked in company
OYO

Problem statement

You are given ‘N’ processes with their respective process id, arrival time, and burst time. Your task is to schedule the given ‘N’ processes using the shortest job first scheduling algorithm and find their respective waiting time and turnaround time.

Shortest Job First is a scheduling algorithm in which the process having the shortest execution time is chosen for the subsequent execution. Here, you will implement a non - preemptive version (Non-preemptive Scheduling is a CPU scheduling technique in which the process takes the resource (CPU time) and holds it till the process gets terminated or is pushed to the waiting state. No process is interrupted until it is completed, and after that processor switches to another process). It significantly reduces the average waiting time for other processes awaiting execution.

For example:

1

We have four processes in our ready queue. As we discussed, SJF will select the waiting process with the shortest execution time to execute next. So for the above example, the SJF scheduling of the processes along with their completion time, waiting time, and turnaround time will be,

1

Note:

1) Completion Time: Time at which process completes its execution.
2) Turn Around Time: Time difference between completion time and arrival time. Turn Around Time = Completion Time – Arrival Time.
3) Waiting Time(W.T.): Time difference between turn around time and the burst time. Waiting Time = Turn Around Time – Burst Time.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single integer, ‘N’, where ‘N’ represents the number of processes.

The next ‘N’ lines of each test case containing three space-separated integers, ‘processId’, ‘arrivalTime’ and ‘burstTime’, where ‘processId’, ‘arrivalTime’ and ‘burstTime’ represents the process id, arrival time, and burst time for the processes, respectively.

Note: It is guaranteed that each process has a unique process id.

Output Format:

For each test case, print ‘N’ lines, each having five space-separated integers, process id, arrival time, burst time, waiting time, and turnaround time.

Print the processes according to SJF scheduling. If multiple processes have the same execution time, schedule the process with a lower process id first.

The output of each test case will be printed in a separate line.

Note:

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

Constraints:

1 <= T <= 5
1 <= N <= 100
1 <= processId <= N
0 <= arrivalTime <= 10 ^ 7
1 <= burstTime <= 10 ^ 7

Where ‘T’ is the total number of test cases, ‘N’ denotes the number of processes,  ‘processId’, ‘arrivalTime’, and ‘burstTime’ represents the process id, arrival time, and burst time of any process, respectively.

Time Limit: 1 sec

Sample Input 1:

2
3
1 3 2
3 1 5
2 4 1
4
1 2 7
3 2 3
2 0 4
4 0 1

Sample Output 1:

3 1 5 0 5
2 4 1 2 3
1 3 2 4 6
4 0 1 0 1
2 0 4 1 5
3 2 3 3 6
1 2 7 6 13

Explanation Of Sample Input 1:

Test Case 1 :  
The process given is,

1

We have three processes in our ready queue. SJF will select the waiting process with the shortest execution time to execute next. The SJF scheduling of the processes along with their completion time, waiting time, and turnaround time will be,

1

Test Case 2 : 
The process given is,

1

We have four processes in our ready queue. SJF will select the waiting process with the shortest execution time to execute next. The SJF scheduling of the processes along with their completion time, waiting time, and turnaround time will be,

1

Sample Input 2:

1
4
1 4 1
4 3 2
2 2 3
3 1 4

Sample Output 2:

3 1 4 0 4
1 4 1 1 2
4 3 2 3 5
2 2 3 6 9

Explanation of Sample Input 2:

Test Case 1 :  
The process given is,

1

We have four processes in our ready queue. SJF will select the waiting process with the shortest execution time to execute next. The SJF scheduling of the processes along with their completion time, waiting time, and turnaround time will be,

1

Full screen
Console