17/32 · 6 min
Deciding who runs next
More ready processes than processors means choosing. The scheduler chooses, and which rule it uses changes how the machine feels.
The measures
- Turnaround time: completion minus arrival. How long the whole thing took.
- Waiting time: turnaround minus burst. How long it sat doing nothing.
- Response time: first run minus arrival. How long before anything happened, which is what a person notices.
Worked example
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
FCFS, in arrival order: P1, P2, P3, P4.
| P | Start | Complete | Turnaround | Waiting |
|---|---|---|---|---|
| P1 | 0 | 8 | 8 | 0 |
| P2 | 8 | 12 | 11 | 7 |
| P3 | 12 | 21 | 19 | 10 |
| P4 | 21 | 26 | 23 | 18 |
Average waiting: (0 + 7 + 10 + 18) / 4 = 8.75.
SJF, shortest job among those that have arrived: P1, P2, P4, P3. Average waiting drops to 7.75.
Why SJF is not used as written
It needs the burst time before running the job, and the operating system cannot know that. Real schedulers estimate it from recent history. And a long job starves while short ones keep arriving, which ageing patches by raising priority with waiting time.
Round robin
Every process gets a fixed quantum, then goes to the back of the queue. Worse average waiting time, bounded response time, no starvation, no prediction needed.
The quantum is the whole design. Too long and it becomes FCFS. Too short and context switches eat the processor. Typical values are 10 to 100 milliseconds, chosen so a switch costs about one percent.