Last Updated: 22 Feb, 2021
SJF
Easy
Asked in company
You have to implement the shortest job first scheduling algorithm.
Shortest Job First is an algorithm in which the process having the smallest execution(burst) time is chosen for the next execution. Here, you will implement a non - preemptive version (a process will wait till process(es) with shorter burst time executes). You have to return the average waiting for the given number of processes.
Completion Time: Time at which process completes its execution.
Example:
SJF will schedule the job which is having least burst time.
Hence, Average waiting time = (5 + 0 + 2) / 3 = 2.33
Input format :
The first line contains a single integer 'N' which represents the number of processes.
The next 'N' lines contains two space-separated integers ‘at’ and ‘bt’ which represent arrival time and burst time for the 'ith' process, respectively.
Output format :
Print a floating value of 2 decimal points that represent average waiting time.
Note:
You don’t have to print anything; it has already been taken care of. Just implement the given function.
You have to return the answers up to two decimal places.
Approaches
The idea is to use the definition of the SJF. That is, first keep track of the process with the minimum arrival time because it will come first and then keep track of the process with the minimum burst time among the arrived process.
- To keep track of the waiting times, completion times, turn around times and the process which has been executed, we will create arrays waitingTime, completionTime, turnAroundTime, and completed respectively.
- Run a loop for the total number of processes, that is until all processes are executed.
- In each iteration, check for the minimum arrival time process and with the minimum burst time .
- After finding the process, execute it. Means,update turnAroundTime[i] = completionTime[i] - arrivalTime[i] and completionTime[i] = turnAroundTime[i] - burstTime[i] as mentioned in the formulas above and put this process as completed in the completed array i.e. completed[i] = true.
- Consider the remaining processes and repeat the above steps for each of them.
- Finally, calculate the average turn around and average waiting time and return both of them in an array.