CPU scheduling

In the last lecture, processes waited in the ready state for a CPU. With a few cores and hundreds of runnable threads, the kernel faces a question thousands of times a second: who runs next, and for how long? The part of the kernel that answers it is the scheduler.

What “good” means

There is no single best schedule, because the goals conflict:

Turnaround time

From arrival to completion. Matters for batch jobs such as reports and builds.

Waiting time

Time spent ready but not running. The part scheduling can actually improve.

Response time

From arrival until the task first runs. What users feel in interactive systems.

Throughput

Jobs completed per unit of time. Reduced by switching overhead.

Fairness

Every task gets a reasonable share; nothing starves forever.

Three classic policies

• First-come, first-served (FCFS) runs jobs to completion in arrival order. Simple, predictable — and prone to the convoy effect, where short jobs wait behind a long one.
• Shortest job first (SJF) always picks the ready job with the smallest remaining work. It provably minimizes average waiting time, but requires knowing job lengths in advance and can starve long jobs.
• Round robin (RR) gives each ready job a fixed time slice (quantum) in turn, then pre-empts it and moves it to the back of the queue. Everyone makes progress quickly, which suits interactive systems.

Simulate them

Four processes arrive at different times with different amounts of work. Switch policies and watch the Gantt chart and the metrics. For round robin, change the time slice.

Notice the pattern. SJF gives the lowest average waiting time. Round robin gives the best response times — every process starts soon after it arrives — but finishes some jobs later and needs more context switches. A large time slice makes round robin behave like FCFS; a tiny one drowns in overhead.

What real kernels do

Production schedulers blend these ideas with extra goals such as multiple cores, priorities and power saving:

• Priorities and fairness. Linux’s general-purpose scheduler aims to give each runnable task a fair share of CPU time, weighted by its priority (its nice value). Tasks that have run less recently get to run sooner.
• Interactive boosts. Tasks that often sleep waiting for input tend to get the CPU quickly when they wake, keeping desktops and terminals snappy.
• Multiple cores. Each core has its own run queue, and the kernel balances load between them — while trying to keep tasks on the same core so their data stays in that core’s caches.
• Real-time classes. Some tasks, such as audio processing, need strict deadlines and can be given scheduling classes that always run before normal tasks.

Fair sharing by weight is easy to see. Give three busy tasks different nice values — lower means more important — and watch both their shares and the order in which a fair scheduler runs them:

See it happen. A service gets a burst of work and spreads it over several threads, inside a container with a CPU limit:

So far, one task runs at a time per core. The next lecture looks at what goes wrong when several threads run at the same time and share data.