Introduction
Shortest Job First (SJF) is a CPU scheduling algorithm that selects the process with the shortest burst time for execution first. It is also known as Shortest Next CPU Burst (SNCB) Scheduling.
Types of SJF Scheduling
SJF can be implemented in two ways:
- Non-Preemptive SJF – Once a process starts execution, it runs until completion.
- Preemptive SJF (Shortest Remaining Time First – SRTF) – If a new process arrives with a smaller burst time than the current process, the CPU switches to the new process.
How SJF Works
- The scheduler selects the process with the shortest burst time.
- If two processes have the same burst time, FCFS is used.
- If preemptive, the scheduler interrupts the current process if a shorter one arrives.
Example of Non-Preemptive SJF Scheduling
Given Processes:
| Process | Arrival Time (AT) | Burst Time (BT) |
|---|---|---|
| P1 | 0 ms | 7 ms |
| P2 | 2 ms | 4 ms |
| P3 | 4 ms | 1 ms |
| P4 | 5 ms | 2 ms |
Step-by-Step Execution:
- P1 arrives first (0 ms) and starts execution.
- P3 arrives at 4 ms but P1 is still running.
- P1 completes at 7 ms, then P3 (1 ms burst) executes.
- P3 completes at 8 ms, then P4 (2 ms burst) executes.
- P4 completes at 10 ms, then P2 (4 ms burst) executes.
- P2 completes at 14 ms.
Gantt Chart for Non-Preemptive SJF Execution
CopyEdit| P1 | P1 | P1 | P1 | P1 | P1 | P1 | P3 | P4 | P4 | P2 | P2 | P2 | P2 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Calculation of Turnaround Time (TAT) & Waiting Time (WT):
| Process | Arrival Time (AT) | Burst Time (BT) | Completion Time (CT) | Turnaround Time (TAT) = CT – AT | Waiting Time (WT) = TAT – BT |
|---|---|---|---|---|---|
| P1 | 0 ms | 7 ms | 7 ms | 7 ms | 0 ms |
| P2 | 2 ms | 4 ms | 14 ms | 12 ms | 8 ms |
| P3 | 4 ms | 1 ms | 8 ms | 4 ms | 3 ms |
| P4 | 5 ms | 2 ms | 10 ms | 5 ms | 3 ms |
Example of Preemptive SJF (SRTF) Scheduling
Given Processes:
| Process | Arrival Time (AT) | Burst Time (BT) |
|---|---|---|
| P1 | 0 ms | 7 ms |
| P2 | 2 ms | 4 ms |
| P3 | 4 ms | 1 ms |
| P4 | 5 ms | 2 ms |
Step-by-Step Execution (Preemptive SJF)
- P1 starts execution at 0 ms.
- At 2 ms, P2 arrives (shorter than P1), so CPU switches to P2.
- At 4 ms, P3 arrives (shorter than P2), so CPU switches to P3.
- P3 completes at 5 ms, CPU resumes P2.
- At 5 ms, P4 arrives (shorter than P2), so CPU switches to P4.
- P4 completes at 7 ms, CPU resumes P2.
- P2 completes at 9 ms, CPU resumes P1.
- P1 completes at 16 ms.
Gantt Chart for Preemptive SJF Execution
CopyEdit| P1 | P1 | P2 | P2 | P3 | P4 | P4 | P2 | P2 | P1 | P1 | P1 | P1 | P1 | P1 | P1 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Turnaround & Waiting Time Calculation (SRTF)
| Process | Arrival Time (AT) | Burst Time (BT) | Completion Time (CT) | Turnaround Time (TAT) = CT – AT | Waiting Time (WT) = TAT – BT |
|---|---|---|---|---|---|
| P1 | 0 ms | 7 ms | 16 ms | 16 ms | 9 ms |
| P2 | 2 ms | 4 ms | 9 ms | 7 ms | 3 ms |
| P3 | 4 ms | 1 ms | 5 ms | 1 ms | 0 ms |
| P4 | 5 ms | 2 ms | 7 ms | 2 ms | 0 ms |
Advantages of SJF Scheduling
Minimizes waiting time → Shortest jobs finish quickly. Minimizes turnaround time → More efficient than FCFS. Preemptive SJF (SRTF) is optimal → Always executes the shortest job first.
Disadvantages of SJF Scheduling
Starvation of longer processes → Long processes may never execute. Requires knowledge of burst time in advance → Difficult to predict. More complex than FCFS → Preemptive version requires frequent context switching.
When to Use SJF Scheduling?
- Best for batch processing systems where burst times are predictable.
- Works well when most jobs are short and few long processes exist.
- Not suitable for real-time systems that require immediate response.
Conclusion
SJF is an efficient CPU scheduling algorithm that minimizes waiting and turnaround time. However, it has issues like process starvation and requires precise burst time estimation. Preemptive SJF (SRTF) is even more efficient but increases context switching overhead.