In SJF scheduling, the process with the lowest burst time, among the list of available processes in the ready queue, is going to be scheduled next.
However, it is very difficult to predict the burst time needed for a process hence this algorithm is very difficult to implement in the system.
- This is the best approach to minimize waiting time.
- This is used in Batch Systems.
- It is of two types:
- Non Pre-emptive
Advantages of SJF
- Maximum throughput
- Minimum average waiting and turnaround time
Disadvantages of SJF
- May suffer with the problem of starvation
- It is not implementable because the exact Burst time for a process can’t be known in advance.
Non Pre-emptive Shortest Job First
Consider the below processes available in the ready queue for execution, with arrival time as
0 for all and given burst times.
As you can see in the GANTT chart above, the process P4 will be picked up first as it has the shortest burst time, then P2,followed by P3 and at last P1.
We scheduled the same set of processes using the First come first serve algorithm in the previous tutorial, and got average waiting time to be
14.5 ms, whereas with SJF, the average waiting time comes out
Problem with Non Pre-emptive SJF
If the arrival time for processes are different, which means all the processes are not available in the ready queue at time
0, and some jobs arrive after some time, in such situation, sometimes process with short burst time have to wait for the current process’s execution to finish, because in Non Pre-emptive SJF, on arrival of a process with short duration, the existing job/process’s execution is not halted/stopped to execute the short job first.
This leads to the problem of Starvation, where a shorter process has to wait for a long time until the current longer process gets executed. This happens if shorter jobs keep coming, but this can be solved using the concept of aging.
Pre-emptive Shortest Job First
In Preemptive Shortest Job First Scheduling, jobs are put into ready queue as they arrive, but as a process with short burst time arrives, the existing process is preempted or removed from execution, and the shorter job is executed first.
The average waiting time for preemptive Shortest Job First Scheduling is less than both, Non-preemptive SJF Scheduling and FCFS Scheduling.
As you can see in the GANTT chart above, as P1 arrives first, hence it’s execution starts immediately, but just after
1 ms, process P2 arrives with a burst time of
4 ms which is less than the burst time of P1, hence the process P1(1 ms done, 14 ms left) is preemptied and process P2 is executed.
As P2 is getting executed, after
1 ms, P3 arrives, but it has a burst time greater than that of P2, hence execution of P2 continues. But after another millisecond, P4 arrives with a burst time of
1 ms, as a result P2(2 ms done, 2 ms left) is preemptied and P4 is executed.
After the completion of P4, process P2 is picked up and finishes, then P2 will get executed and after that P3 is executed and at last P1.
The Pre-emptive SJF is also known as Shortest Remaining Time First, because at any given point of time, the job with the shortest remaining time is executed first.