Predicting the Future in SJF
We know that Shortest Job First (SJF) is the mathematically optimal scheduling algorithm for minimizing average waiting time. However, it has a massive real-world flaw: the operating system cannot see the future. It has no way of knowing exactly how long the next CPU burst of a process will be before it actually runs.
So how does SJF work in the real world? It guesses! Operating systems use a mathematical technique called Exponential Averaging to predict the length of the next CPU burst based on the history of previous bursts.
Real-Life Example
Imagine predicting your commute time to work. If your historical average is 30 minutes, but yesterday there was an accident and it took 50 minutes, what is your guess for today?
You probably won't guess 50 minutes, because accidents are rare. But you might bump your guess up to 35 minutes just in case there is lingering traffic. The Alpha value (α) represents how much weight you give to "yesterday's accident" versus your "historical average".
Example 1: Calculating the Prediction
Let's see the math in action. Assume the OS weighs the recent past and historical past equally by setting Alpha to 0.5 (α = 0.5).
Let's assume our initial prediction for the very first burst (τ0) is 10 ms.
If the actual first burst (t0) turns out to be 8 ms, the prediction for the next burst is: 0.5 * 8 + (1 - 0.5) * 10 = 4 + 5 = 9 ms.
| Burst Number (n) | Actual Burst Length t(n) | Past Prediction τ(n) | New Prediction τ(n+1) |
|---|---|---|---|
| 0 | 8 | 10 | 9.0 |
| 1 | 6 | 9.0 | 7.5 |
| 2 | 6 | 7.5 | 6.75 |
| 3 | 5 | 6.75 | 5.87 |
| 4 | 9 | 5.87 | 7.43 |
Notice how the prediction smoothly adjusts to the actual burst times without aggressively jumping every time there is a sudden spike (like the 9 ms spike at Burst 4).
Example 2: The Cost of a Bad Prediction
Why does predicting burst time matter so much? Because if the OS guesses wrong, it schedules the wrong processes, completely destroying SJF's optimality!
Let's look at a scenario with two processes arriving at time 0.
| Process | Predicted Burst Time | Actual Burst Time |
|---|---|---|
| P1 | 4 ms | 10 ms |
| P2 | 6 ms | 2 ms |
Based entirely on the predictions, the OS thinks P1 is the shorter job (4 < 6). Therefore, it schedules P1 first, followed by P2. Let's draw the Gantt chart using the actual burst times that played out:
+----------------+----+
| P1 | P2 |
+----------------+----+
0 10 12Let's calculate the Turnaround Time and Waiting Time for this flawed schedule:
- P1: Turnaround = 10 - 0 = 10 ms. Wait = 10 - 10 = 0 ms.
- P2: Turnaround = 12 - 0 = 12 ms. Wait = 12 - 2 = 10 ms.
Average Turnaround Time = (10 + 12) / 2 = 11 ms.
Average Waiting Time = (0 + 10) / 2 = 5 ms.
Now, what if the OS had perfectly predicted the future? It would have known that P2 was actually shorter (2 < 10) and scheduled P2 first! Here is the Gantt chart for a perfect prediction:
+----+----------------+
| P2 | P1 |
+----+----------------+
0 2 12Let's recalculate the metrics for the perfect schedule:
- P2: Turnaround = 2 - 0 = 2 ms. Wait = 2 - 2 = 0 ms.
- P1: Turnaround = 12 - 0 = 12 ms. Wait = 12 - 10 = 2 ms.
Average Turnaround Time = (2 + 12) / 2 = 7 ms.
Average Waiting Time = (0 + 2) / 2 = 1 ms.
Because the OS guessed wrong, the average waiting time shot up from 1 ms to 5 ms! This proves that SJF is only optimal if its exponential averaging formula is highly accurate.
The Role of Alpha (α)
- If α = 0: The recent history has no effect. The formula becomes τ(n+1) = τ(n). The prediction is static and never changes.
- If α = 1: Only the most recent burst matters. The formula becomes τ(n+1) = t(n). The OS aggressively assumes the next burst will be exactly the same length as the very last one.
- If α = 0.5: The OS perfectly balances the weight of the most recent burst with the entire historical average.
Tuning the Formula
Question 1 of 1Test your understanding of the Alpha weight factor.