Shortest-Job-First (SJF) Scheduling
The Shortest-Job-First (SJF) scheduling algorithm associates each process with the length of its next CPU burst. When the CPU becomes available, it is assigned to the process that has the smallest next CPU burst. If two processes have the same length next CPU burst, First-Come, First-Served (FCFS) scheduling is used to break the tie.
A more appropriate term for this scheduling method would be Shortest-Next-CPU-Burst First, because scheduling depends on the length of the next CPU burst of a process, rather than its total overall length.
Real-Life Example
Think of a print shop where people submit jobs to be printed. If a person walks in wanting to print a massive 500-page book, and another person walks in wanting to print a single 1-page document, it makes sense to let the 1-page document go first. The person with the 1-page document gets to leave almost immediately, and the person with the 500-page book hardly notices the extra few seconds of wait time. This drastically reduces the overall average time customers spend in the shop.
Example 1: Processes Arriving at the Same Time
Let's look at a mathematical example. Consider the following set of processes, assuming they all arrive at time 0:
| Process | Burst Time (ms) |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
By treating these as SJF, the algorithm will sort them from shortest to longest burst. The execution order will be: P4 (3ms), P1 (6ms), P3 (7ms), P2 (8ms).
Here is the execution timeline (Gantt chart):
+------+------------+--------------+----------------+
| P4 | P1 | P3 | P2 |
+------+------------+--------------+----------------+
0 3 9 16 24Let's calculate the Waiting Time and Turnaround Time for each process.
Waiting Time = Start Time - Arrival Time:
- P4 waits for 0 - 0 = 0 ms.
- P1 waits for 3 - 0 = 3 ms.
- P3 waits for 9 - 0 = 9 ms.
- P2 waits for 16 - 0 = 16 ms.
The Average Waiting Time is therefore: (0 + 3 + 9 + 16) / 4 = 7 ms.
Turnaround Time = Completion Time - Arrival Time:
- P4 turnaround is 3 - 0 = 3 ms.
- P1 turnaround is 9 - 0 = 9 ms.
- P3 turnaround is 16 - 0 = 16 ms.
- P2 turnaround is 24 - 0 = 24 ms.
The Average Turnaround Time is therefore: (3 + 9 + 16 + 24) / 4 = 13 ms.
Example 2: Processes Arriving at Different Times
Now let's look at a more complex example where processes arrive at different times. Remember, we are using the non-preemptive version of SJF, so once a process starts running, it cannot be interrupted even if a shorter job arrives.
| Process | Arrival Time (ms) | Burst Time (ms) |
|---|---|---|
| P1 | 0 | 7 |
| P2 | 2 | 4 |
| P3 | 4 | 1 |
| P4 | 5 | 4 |
Here is how the scheduling decisions are made:
1. At time 0, only P1 has arrived. It starts executing and will run until time 7 (non-preemptive).
2. By the time P1 finishes at time 7, P2, P3, and P4 have all arrived and are waiting in the ready queue.
3. The OS selects the shortest job available at time 7, which is P3 (burst of 1). P3 runs until time 8.
4. At time 8, P2 and P4 are left in the queue. They both have a burst time of 4. FCFS is used to break the tie, so P2 (which arrived earlier at time 2) goes next and runs until time 12.
5. Finally, P4 runs from time 12 to 16.
Here is the Gantt chart:
+--------------+--+--------+--------+
| P1 |P3| P2 | P4 |
+--------------+--+--------+--------+
0 7 8 12 16Let's calculate the Waiting Time (Start Time - Arrival Time):
- P1: 0 - 0 = 0 ms.
- P2: 8 - 2 = 6 ms.
- P3: 7 - 4 = 3 ms.
- P4: 12 - 5 = 7 ms.
Average Waiting Time = (0 + 6 + 3 + 7) / 4 = 4 ms.
Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1: 7 - 0 = 7 ms.
- P2: 12 - 2 = 10 ms.
- P3: 8 - 4 = 4 ms.
- P4: 16 - 5 = 11 ms.
Average Turnaround Time = (7 + 10 + 4 + 11) / 4 = 8 ms.
The Catch: Predicting the Future
While SJF is mathematically optimal, it has a massive practical flaw: it is impossible to implement perfectly at the level of short-term CPU scheduling. There is simply no way to know the exact length of the next CPU burst for a process before it actually runs!
To get around this, operating systems try to predict the length of the next burst by looking at the history of previous bursts. They use a technique called exponential averaging, which assumes that the next burst will be similar in length to the recent ones.
Advantages of SJF
- Provably optimal for minimizing average waiting time.
- Significantly increases system throughput since shorter jobs clear out of the system quickly.
- Excellent for batch processing systems where job runtimes are often known in advance.
Disadvantages of SJF
- Impossible to implement perfectly because the exact length of future CPU bursts cannot be known.
- Computing predictions for future bursts adds computational overhead to the operating system.
- Highly susceptible to Starvation. If a constant stream of short processes keeps arriving, a long process will be continually pushed back and may never get to run.
SJF Knowledge Check
Question 1 of 2Test your understanding of the strengths and weaknesses of SJF.