More programs than processors
Your computer is running hundreds of things: a browser with thirty tabs, music, a chat app, system services. It may have eight processor cores. One core can run only one thing at a time.
The illusion that everything runs at once is created by the operating system's scheduler. Many times a second it decides which program gets a core next, lets it run briefly, then switches to another.
The rule it uses is the scheduling algorithm, and different rules give very different results from exactly the same work.
Five jobs, one CPU
To keep things clear, this page uses one CPU and five jobs that all arrive at the same moment. Each needs a known amount of CPU time.
| Job | Needs | Priority (1 = most important) |
|---|---|---|
| A | 8 ticks | 3 |
| B | 4 ticks | 1 |
| C | 2 ticks | 4 |
| D | 1 tick | 5 |
| E | 3 ticks | 2 |
The total work is 18 ticks whatever the scheduler does. What changes is the waiting: the time each job spends ready to run and not running. Lower average waiting means the machine feels faster.
Solid colour: running. Pale red: ready, but waiting for the CPU.
Start. Run the jobs in the order they arrived, each one to the end. All five jobs are ready at time 0.
- Time
- 0 / 18
- Jobs finished
- 0 / 5
- Waiting so far, per job
- 0.0
First come, first served
Run the jobs in arrival order, each one to completion.
It is the simplest possible rule, and fair in the way a queue at a shop is fair.
Solid colour: running. Pale red: ready, but waiting for the CPU.
Start. Run the jobs in the order they arrived, each one to the end. All five jobs are ready at time 0.
- Time
- 0 / 18
- Jobs finished
- 0 / 5
- Waiting so far, per job
- 0.0
Its weakness is obvious in the animation. The long job A happened to be first, so everyone sits behind it. D needs a single tick and waits 14 to get it. One long job at the front makes every short job behind it wait. This is called the convoy effect.
Shortest job first
Always run the job that needs the least time.
Solid colour: running. Pale red: ready, but waiting for the CPU.
Start. Always run the job that needs the least time. All five jobs are ready at time 0.
- Time
- 0 / 18
- Jobs finished
- 0 / 5
- Waiting so far, per job
- 0.0
The average wait falls from 9.8 ticks to 4. This is not luck: among rules that run each job to completion, shortest-first gives the lowest possible average wait.
Example
Why short jobs should go first
Two jobs: one needs 1 tick, one needs 10.
Long one first: the short job waits 10. Total waiting: 10.
Short one first: the long job waits 1. Total waiting: 1.
Moving a short job ahead costs the long job a little and saves the short job a lot.
It has two problems. First, look at A: it waits until every other job has finished. If short jobs keep arriving, a long job may never run. That is starvation. Second, the scheduler has to know how long each job will take, and real programs do not announce that. Real systems guess from how the program has behaved so far.
Round robin
Give each job a short turn, then send it to the back of the line. The turn is called a time slice. Here it is 2 ticks.
Solid colour: running. Pale red: ready, but waiting for the CPU.
Start. Give each job 2 ticks, then move it to the back of the line. All five jobs are ready at time 0.
- Time
- 0 / 18
- Jobs finished
- 0 / 5
- Waiting so far, per job
- 0.0
The average wait is worse than shortest-first. But look at something the average hides: every job gets to run within a few ticks of arriving. Nobody is frozen for a long stretch.
That is what matters for anything interactive. You do not care that your text editor's total work finishes 3 ticks later. You care that it responds to a key press now. Every desktop and phone system is built around this idea.
The slice length is a trade-off. Too long, and it behaves like first come, first served. Too short, and the CPU spends more time switching between jobs than running them, because each switch has a cost.
Priority
Always run the most important job that is ready.
Solid colour: running. Pale red: ready, but waiting for the CPU.
Start. Always run the most important job that is ready. All five jobs are ready at time 0.
- Time
- 0 / 18
- Jobs finished
- 0 / 5
- Waiting so far, per job
- 0.0
Important work gets through quickly: B waits nothing. Low-priority work suffers: D, a one-tick job, waits 17.
The risk is starvation again. A steady supply of important jobs can lock out unimportant ones for ever. The usual cure is aging: the longer a job waits, the more its priority is raised, until it finally gets a turn.
Side by side
The same five jobs under each scheduler. Lower is better.
| Scheduler | Good at | Weakness |
|---|---|---|
| First come, first served | Simplicity | Short jobs stuck behind long ones |
| Shortest job first | Lowest average wait | Long jobs can starve, and lengths must be known |
| Round robin | Quick response for everyone | Higher average wait, and switching has a cost |
| Priority | Important work first | Unimportant work can starve |
What real systems do
No real operating system uses one of these in pure form. They combine them:
- Time slices, so nothing hogs a core.
- Priorities, so that what you are interacting with comes first.
- Learning from behaviour. A program that keeps pausing to wait for input is probably interactive and is favoured. One that uses every slice in full is probably a long computation and can wait a little.
- Aging, so nothing starves.
Key takeaways
- A scheduler decides which program gets the CPU next, and the rule changes how long jobs wait.
- First come, first served is simple, but one long job delays everything behind it.
- Shortest job first gives the lowest average wait and can starve long jobs.
- Round robin gives every job regular short turns, which keeps a system responsive.
- Priority scheduling favours important work and needs aging to prevent starvation.