Part 4 of 7 · 2 min read
Prediction
In plain words: SJF needs the length of the next CPU burst, and nobody knows that in advance. A kernel cannot read a program's mind. It can only guess from the past, on the assumption that the next burst resembles the recent ones.
The usual guess is an exponential average. Let t(n) be the length of the nth measured burst, and τ(n) the prediction made for it. The next prediction is
τ(n+1) = α × t(n) + (1 − α) × τ(n)
where α is a number between 0 and 1. With α = 0 the guess never changes. With α = 1 it uses only the last burst. A common choice is 0.5, which weights the newest burst and the older history equally. The history counts less as it gets older, since each step multiplies the old terms by (1 − α).
A worked example, made up to show the idea. The first guess is τ(0) = 8, α = 0.5, and the measured bursts are 4, 4, 12, 12 and 12:
| n | Measured burst t(n) | Prediction τ(n) | Next prediction τ(n+1) |
|---|---|---|---|
| 0 | 4 | 8 | 0.5 × 4 + 0.5 × 8 = 6 |
| 1 | 4 | 6 | 0.5 × 4 + 0.5 × 6 = 5 |
| 2 | 12 | 5 | 0.5 × 12 + 0.5 × 5 = 8.5 |
| 3 | 12 | 8.5 | 0.5 × 12 + 0.5 × 8.5 = 10.25 |
| 4 | 12 | 10.25 | 0.5 × 12 + 0.5 × 10.25 = 11.125 |
The prediction follows the change from short to long bursts, and it moves toward 12 without leaping to it, which smooths out single odd bursts.
Real systems use this idea in disguise. They do not run exact SJF. They favour processes that used little CPU recently, which are likely to have short bursts (page 4, and Linux in page 5).
Exponential average
An exponential average is a prediction rule that computes the next estimate as α times the latest measurement plus (1 − α) times the previous estimate, so that older measurements count less each step.
Example: with α = 0.5, a previous estimate of 5 and a new burst of 12, the next estimate is 0.5 × 12 + 0.5 × 5 = 8.5.
Check yourself:
1. What does α = 1 do to the prediction?
2. Compute τ(n+1) for α = 0.5, τ(n) = 10 and t(n) = 2.
3. Why does the kernel need a prediction at all?