The idea: one queue for all CPUs, or one queue per CPU

A scheduler on one CPU only has to choose which task runs next; that is the subject of CPU Scheduling. With several CPUs it must also choose where each task runs. The tasks that are ready to run wait in a run queue. There are two basic designs. In the first, all CPUs share one global run queue. In the second, each CPU has its own run queue, and a load balancer sometimes moves tasks between the queues.

Left: one global run queue holding tasks A to F, with one lock, and arrows from it to CPU0, CPU1, CPU2 and CPU3. Right: four run queues, one above each CPU, each with its own lock, and a load balancer that moves tasks between them.
One shared queue needs one lock for every pick; per-CPU queues need no shared lock but must be balanced.

The canvas has 4 CPUs and 6 tasks, A to F. Each task needs 6 ticks of work and runs in slices of 3 ticks: after a slice it goes back to the tail of its queue, as in round robin. Picking the next task takes 1 tick. A task's data stays in the cache of the CPU it last ran on. If it runs on another CPU, or for the first time, its slice starts with 2 extra ticks of cache misses: a cold start. The 6 tasks have 36 ticks of real work in all.

The chart has one row per CPU and time going right. Grey is a pick, orange is a cold cache, red is a CPU spinning on a lock, and light grey is idle time. The coloured bars are the tasks doing real work.

One global run queue: the lock and the bouncing tasks

One queue is the simple design. It is also fair, because no CPU sits idle while a task is waiting. But the queue is shared data, so a CPU must hold its lock while it takes a task. When several CPUs become free at the same moment, only one gets the lock. The others spin and wait. At t = 0 all four CPUs want the lock: CPU1 waits 1 tick, CPU2 waits 2 and CPU3 waits 3, which is 6 ticks lost before any work starts (Demo 1). With 64 CPUs and a scheduler that runs thousands of times per second, the queue lock becomes a real bottleneck. Mutex vs Spinlock shows what spinning costs.

The second problem is cache affinity. With one queue, a task runs next on whichever CPU happens to be free. In Demo 1 every task runs its second slice on a different CPU than its first, so all 12 slices start cold: 6 first runs and 6 restarts on a new CPU, 12 extra ticks of cache misses. The run ends at t = 21.

Two time bars for the second slice of task A. On the same CPU: a 1-tick pick and 3 ticks of work, 4 ticks in all. On a new CPU: a 1-tick pick, 2 ticks of cache misses, then 3 ticks of work, 6 ticks in all.
The same slice costs 4 ticks on the CPU whose cache holds the task's data and 6 ticks on a new one.

On real hardware the cost of a cold start depends on how much data the task uses: its data must come again from the shared L3 cache or from memory into the new core's L1 and L2 caches. CPU Cache shows hits and misses.

Per-CPU run queues and load imbalance

With one queue per CPU, each CPU takes tasks only from its own queue, under its own lock, so CPUs never wait for each other. A task stays on its CPU, so after its first run it is always warm. Linux (one struct rq per CPU), FreeBSD's ULE scheduler and Windows all work this way.

The danger is load imbalance. In Demo 2 CPU0 has A and E, CPU1 has B and F, CPU2 has only C and CPU3 only D. There are no lock waits and only the 6 first runs are cold, but C and D are done at t = 10. From then on CPU2 and CPU3 are idle while E and F wait in other queues: 20 idle ticks, done at t = 20. Demo 5 shows the worst case: a parent on CPU0 forks all six tasks, so they all land in CPU0's queue. CPU0 does all the work alone and the run ends at t = 60, with 180 idle ticks on the other three CPUs.

Migration: pull and push

A load balancer fixes imbalance by migration: it moves a task from one CPU's queue to another's. There are two ways to trigger it.

  • Pull (work stealing): a CPU whose queue is empty looks at the other queues and steals a waiting task from the busiest one. In Demo 3, at t = 10 CPU2 steals A from CPU0 and CPU3 steals B from CPU1. Each stolen task starts cold once, but no CPU is idle and the run ends at t = 16. In Demo 6 CPU1, CPU2 and CPU3 steal F, E and D from CPU0 at t = 0, and the forked tasks finish at t = 20 instead of 60.
  • Push: a balancer runs every so often (every 6 ticks on the page), compares the loads and moves tasks from the most loaded CPU to the least loaded one. In Demo 4 it runs at t = 6, finds the loads even enough, and at t = 12 moves E to CPU2 and F to CPU3. The CPUs were idle from t = 10 to t = 12, so the run ends at t = 18, between no balancing and pull.
Two charts with 4 CPU rows. Without balancing, CPU2 and CPU3 are idle from t = 10 to t = 20 while CPU0 and CPU1 still run E and F; done at 20. With pull, at t = 10 CPU2 steals A and CPU3 steals B, each starting with a cold cache, and all four CPUs finish at 16.
Per-CPU queues without balancing leave CPUs idle; stealing costs one cold start per stolen task and finishes 4 ticks sooner.
DemoDone atLock waitsCold starts (first runs + on a new CPU)MigrationsIdle ticks
1: one global queue21612 (6 + 6)66
2: per-CPU, no balancing2006 (6 + 0)020
3: per-CPU, pull1608 (6 + 2)20
4: per-CPU, push1808 (6 + 2)28
5: forked on CPU0, no balancing6006 (6 + 0)0180
6: forked on CPU0, pull2007 (6 + 1)518

For the global queue, "migrations" counts slices that ran on a different CPU than the slice before. In Demo 6 four of the five stolen tasks had not run yet, so only A pays a cold restart.

Migration is a trade. Moving a task costs a cold start, so a balancer should move tasks only when the idle time it saves is bigger. That is why balancers do not move tasks on every tick, and why they prefer tasks that have not run for a while (their cache is cold anyway).

What real kernels do

  • Linux keeps one run queue per CPU and does both. A CPU that is about to go idle pulls work at once (newidle_balance), and a periodic balancer runs from the timer tick. The balancer works in scheduling domains: it balances often between hyperthreads of one core, less often between cores of one chip, and rarely across NUMA nodes, where a migration also leaves the task's memory far away (see NUMA).
  • Linux treats a task as cache-hot for sched_migration_cost_ns (0.5 ms by default) after it last ran, and avoids migrating it during that time.
  • A program can pin a task to some CPUs with taskset or sched_setaffinity(). The balancer never moves it outside that set.
  • Language runtimes repeat the same design in user space: the Go scheduler has a run queue per P and steals half of another P's queue, and Java's ForkJoinPool has a deque per worker thread.

Which task each CPU runs from its own queue is then a one-CPU question again: CFS or EEVDF in Linux, or the classic policies on CPU Scheduling, Multilevel Feedback Queue and Lottery and Stride Scheduling.

What the page leaves out

The page has 4 CPUs, 6 equal tasks that never block for I/O, whole ticks and a fixed 2-tick cold start. Real caches evict data, so a task can be cold even on its old CPU after other tasks have run there. The global queue's lock is held for the whole 1-tick pick; real locks are held much more briefly, but are contended much more often. Left out: affinity heuristics on a single queue, hyperthreads sharing one core's caches, scheduling domain levels, NUMA memory migration, real-time scheduling classes, gang scheduling of the threads of one program, and the cost of the balancer itself.

On the mind map

Open the Operating Systems mind mapOperatingSystemsBoot and program start: from power on to main()Boot and program startProcesses and the kernel: how user code talks to the kernelProcesses and the kernelInterrupts and devices: hardware interrupts the CPUInterrupts and devicesScheduling and deadlock: who runs next, who gets whatScheduling and deadlockVirtual memory: every address is translatedVirtual memoryPhysical memory: who gets which bytes of RAMPhysical memoryFiles and storage: from open() down to the diskFiles and storageDisks and RAID: blocks down to platter or flashDisks and RAIDIsolation and security: limit what a process can doIsolation and securityContext switchContext switchswitch_mm loads CR3, switch_to swaps stacksCPU scheduling algorithmsCPU scheduling algorithmsFCFS, SJF, RR, CFS: compare waiting timeMultiprocessor SchedulingPer-CPU queues + stealing beat one lockMulti-Level Feedback QueueMulti-Level Feedback QueueUse your quantum, drop a levelLottery & strideLottery & strideTickets set shares; stride runs lowest passPreemptive vs cooperativePreemptive vs cooperativetimer forces a switch, or wait for yieldReal-time schedulingReal-time schedulingpriority inversion, fixed by inheritanceLoad averageLoad averagedamped count of R and D tasksBanker's algorithmBanker's algorithmgrant only if a safe order still existsDeadlock detectionDeadlock detectionFind the cycle, then kill a victimOpen the Operating Systems mind mapOperating Systemswho runs next, who gets whatScheduling and deadlockContext switchContext switchswitch_mm loads CR3, switch_to swaps stacksCPU scheduling algorithmsCPU scheduling algorithmsFCFS, SJF, RR, CFS: compare waiting timeMultiprocessor SchedulingPer-CPU queues + stealing beat one lockMulti-Level Feedback QueueMulti-Level Feedback QueueUse your quantum, drop a levelLottery & strideLottery & strideTickets set shares; stride runs lowest passPreemptive vs cooperativePreemptive vs cooperativetimer forces a switch, or wait for yieldReal-time schedulingReal-time schedulingpriority inversion, fixed by inheritanceLoad averageLoad averagedamped count of R and D tasksBanker's algorithmBanker's algorithmgrant only if a safe order still existsDeadlock detectionDeadlock detectionFind the cycle, then kill a victim
This page on the Operating Systems mind map · 64 pages in 9 branches · open it to see the whole map and test yourself in recall mode.