Shortest Job First Scheduling or SJF allocates the CPU to the process which has the smallest CPU-bursts time.
SJF is also called Shortest Job Next scheduling shortly referred to as SJN. Since Job can be called as a process, SJF is also referred to as Shortest Process Next or SPN scheduling
Suppose, if the CPU bursts of two processes are the same, then we use FCFS scheduling to break the tie.
SJF is used frequently in long term scheduling but it cannot be implemented in short-term scheduling.
SJF can either be a preemptive or nonpreemptive.
Advantages of SJF
Pros of using SJF:
Limitations of SJF
Disadvantages/drawbacks/cons of using SJF:
Preemptive SJF scheduling
Preemptive SJF scheduling is sometime called Shortest remaining time first Scheduling.
How does it work?
Preemptive means a Job can be stopped midway to give CPU time to another Job. In Preemptive SJF, the job which has minimum remaining time will be executed next
SJF Example 1 - For Processes That Arrive At The Same Time
For example, consider the set of processes that arrive at time 0 and CPU burst time given in millisecond:
SJF Example 1 - Gantt Chart
In the above diagram: 3,7 and 27 are finish times
SJF Example 1 - Waiting Time and Turnaround time
Average Waiting Time = (7+3+0)/3 = 3.333 ms Average Turnaround Time = (27+7+3)/3 = 12.333 ms
|P1||Job executed Third||0||20||7||27|
|P2||Job executed Second||0||4||3||7|
|P3||Job executed First because it takes less time||0||3||0||3|
SJF Example 2 - For Processes That Arrive At Different Times
Let us say, the processes arrive in the different arrival time, and say, the process is served by using Preemptive SJF Scheduling.
|Process||Arrival Time||CPU-Burst Time|
Now, based on the processes which are in queue at the start:
- Process which takes the least time will be executed first.
- Once first process is progressing, other processes are checked.
- Algorithm will calculate the remaining time for all the processes.
- Either the current process or any other process that arrived, which has the least remaining time will execute next.
- In a similar way, as more processes arrive, current process is paused and process with the least remaining time will be executed.
SJF Example 2 - Gantt Chart:
SJF Example 2 -Waiting Time and Turnaround time
|Waiting Time =|
Start Time -
Finish Time -
Average Waiting Time = (7+0+2)/3 = 3 ms Average Turnaround Time = (27+4+5)/3 = 12 ms
Average Waiting Time
= 3 ms Average Turnaround Time
= 12 ms
Wait and Turnaround time example- For Processes That Arrive At Different Times