Scheduling goals and metrics

Why it matters

Whenever there are more runnable threads than cores, something decides who runs next. That decision shapes how responsive a laptop feels, how much batch work a server finishes per hour, and whether a background job can starve the request handlers. The same choices appear one level up in every queue you design: a job scheduler, a thread pool, a load balancer, a message consumer. Learning the vocabulary here pays off in all of them.

The idea

The scheduler is the part of the kernel that picks which runnable thread gets a core next and for how long. It keeps runnable threads in one or more run queues, and it runs whenever a thread blocks, a time slice ends, or a new thread becomes runnable. Its policy is a set of trade-offs between goals that conflict.

The goals

Metric	Definition	Who cares
CPU utilisation	Fraction of time cores do useful work	Anyone paying for hardware
Throughput	Jobs completed per unit time	Batch processing, analytics, CI runners
Turnaround time	From a job's arrival to its completion	Someone waiting for a batch job to finish
Waiting time	Time spent ready but not running	A proxy for how much the queue hurts each job
Response time	From arrival to the first time it runs (or first output)	Interactive users, request handlers, UIs
Fairness	Each thread or user gets its share over time	Multi-tenant systems; avoiding starvation
Predictability	Low variance; deadlines met	Real-time systems, audio, control loops

Why you cannot win them all

Finishing the shortest jobs first minimises average waiting time and can starve long jobs forever. Switching often keeps response time low and wastes CPU on context switches. Giving each tenant an equal share is fair and can lower total throughput when one tenant's work would run more efficiently in a long uninterrupted batch. Every scheduler, in the kernel or in your application, chooses a point in this space, and the right point depends on the workload: interactive, batch, latency-sensitive services, or a mix.

Workload shapes

Threads alternate between CPU bursts (computing) and I/O waits. Interactive and request-handling threads have short bursts and wait a lot; they want to run quickly when they wake, and they barely use their slices. Batch threads have long bursts; they want long uninterrupted slices for cache locality. A good general-purpose scheduler favours threads that have been waiting (they are probably interactive) without letting compute-heavy threads starve.

Measuring it on a real machine

The load average on Linux is the average number of threads that are runnable or in uninterruptible wait over 1, 5 and 15 minutes; a load persistently above the core count means work is queuing. Run queue length (vmstat's r column) shows how many threads are waiting for a core right now. Per-thread scheduling latency, the time from becoming runnable to running, is the direct measure of queueing and can be traced with tools like perf sched or eBPF-based run-queue latency histograms. CPU steal time on virtual machines shows the hypervisor running other guests on your cores.

The same trade-offs, one level up

A thread pool with a FIFO queue, a job scheduler deciding which build runs next, a consumer choosing which partition to poll, and a load balancer choosing which server gets a request all face the same choice between throughput, response time and fairness. Recognising the scheduling problem in them lets you borrow the solutions: separate queues for interactive and batch work, aging to prevent starvation, and weighted fair sharing per tenant.

Trade-offs

Optimising average metrics (mean waiting time) can hide terrible tail latency for some jobs; optimising worst-case fairness can lower average throughput. Short time slices buy responsiveness with overhead; long ones buy efficiency with latency. Measurement matters because intuition about which metric a system needs is often wrong.

In an interview

Name the metric before the policy: "This queue serves interactive API calls and nightly exports, so response time matters for one and throughput for the other. Put them in separate queues with weighted shares so exports cannot starve requests, and age long-waiting jobs so nothing waits forever." That is a scheduler design in one breath, applied to an application.