Runqueues, scheduling, and context switches

Before you start#

Read tasks, fork, exit, and wait, CPU, memory and I/O, and system-call entry. This chapter describes upstream Linux v6.12; runtime observations depend on architecture, configuration, scheduling policy and the running workload. The source-only timeline requires no guest or privileged access. The host exercise reads only its own shell's proc entries.

Learning goals#

Distinguish runnable, running, sleeping and exited tasks; follow a conditional wakeup and scheduling decision through a per-CPU runqueue; explain why a context switch requires synchronization and can resume a previous call much later; and interpret scheduler statistics as sampled evidence rather than a complete execution history.

States and separate questions#

A task is the kernel's schedulable execution context. Runnable means eligible to compete for CPU under its state and policy; running means currently executing on a CPU. A runnable task can wait on a runqueue while another task runs. A sleeping task has indicated that it cannot proceed until some event or condition changes. The scheduler does not decide whether a task's application-level condition is true: waitqueue users must establish a correct protocol between checking the condition, sleeping and waking so that a wakeup is not lost.

In v6.12 task_struct, __state represents scheduling-related state while exit_state represents a different part of task termination. on_rq and, under relevant SMP configurations, on_cpu describe scheduler bookkeeping with their own synchronization rules. None of these fields alone is a complete portable state diagram. A task can be involved in transitions such as wakeup or migration, and a reader must respect the locks, memory ordering and comments for the specific field. /proc reports an interpreted snapshot; its state letter is useful but does not expose every internal transition. See v6.12 include/linux/sched.h and scheduler internals.

A context switch changes which task executes on a CPU. It is not inherently a switch from userspace privilege to kernel privilege: the scheduler runs in kernel context, and the next task may later return to userspace or continue kernel work. A syscall entry and a task switch are different events. A syscall can complete without switching tasks, while an interrupt can lead to a scheduling decision depending on context and preemption state.

Source walkthrough#

The v6.12 scheduler keeps a runqueue, struct rq, associated with a CPU. It contains the current task, class-specific scheduling state, clocks and runnable accounting, among other fields. A runqueue's raw spinlock and interrupt-state rules protect scheduler invariants; the exact lock nesting differs for wakeup, migration and other paths. A raw spinlock is not permission to sleep. On PREEMPT_RT, many ordinary lock semantics change, but core scheduler raw locking and the specific source path must be studied rather than assumed identical to an ordinary mutex.

A wakeup can enter try_to_wake_up in v6.12 kernel/sched/core.c. It coordinates the target's state and pi_lock, checks whether the requested state matches, and may select a CPU and arrange enqueueing under the appropriate runqueue synchronization. A task already runnable can take a different path from a sleeping task; a wakeup that does not match the state does not necessarily enqueue anything. SMP wakeups and migration introduce ordering between on_rq, on_cpu, task state and the target runqueue. The source's memory-barrier commentary is part of the correctness argument; it is not safe to replace it with “write runnable, then add to a list.”

In kernel/sched/core.c, v6.12, SPDX GPL-2.0-only (earlier code and comments omitted):

	scoped_guard (raw_spinlock_irqsave, &p->pi_lock) {
		smp_mb__after_spinlock();
		if (!ttwu_state_match(p, state, &success))
			break;

		trace_sched_waking(p);

The check runs while holding p->pi_lock, and the comment above the guard describes its pairing with set_current_state on the waiting side. The excerpt does not show the enqueue path that follows, and it does not establish that a caller's condition is correct.

Later, a scheduling point reaches __schedule. This short excerpt is from that function in v6.12 kernel/sched/core.c (SPDX GPL-2.0-only; intervening bookkeeping omitted):

next = pick_next_task(rq, prev, &rf);

rq = context_switch(rq, prev, next, &rf);

The first call selects a next task using the current runqueue, previous task and lock-state flags. The second is reached only when prev != next on the relevant branch; the surrounding comment says that it also unlocks the runqueue. If the same task remains selected, the source instead follows the no-switch unlock path. Before selection, __schedule handles whether the previous task is blocking and updates scheduler state; after selection it clears reschedule requests and performs accounting. This is a conditional source map, not proof that every call to schedule switches to a different task.

In kernel/sched/core.c, v6.12, SPDX GPL-2.0-only (intervening bookkeeping omitted):

	if (likely(prev != next)) {
/* ... */
		/* Also unlocks the rq: */
		rq = context_switch(rq, prev, next, &rf);
	} else {
		rq_unpin_lock(rq, &rf);
		__balance_callbacks(rq);
		raw_spin_rq_unlock_irq(rq);
	}

The else branch is the no-switch path: it releases the runqueue lock itself, because context_switch releases it only on the switching branch. The excerpt does not show the state changes made before pick_next_task, or the counters and tracepoints on the switching branch.

context_switch coordinates the address-space transition and the architecture-specific register/stack switch. The applicable path can call switch_mm_irqs_off; kernel threads and lazy address-space handling introduce distinctions. Architecture switch_to code saves and restores execution context according to that architecture. The switched-out task's kernel stack and continuation remain associated with it: when it is selected again, it resumes after its earlier switch rather than starting the function from its first line. This is why code around a context switch cannot be read as a simple function call that returns immediately in the same task. Object lifetime, mm references, lock transfer and memory ordering must remain valid across the transition.

Scheduling classes in this release#

The scheduler uses class operations to enqueue, dequeue, select and account tasks. The ordering encoded in the v6.12 linker script is stop, deadline, real-time, fair, sched_ext, idle, from higher to lower class, subject to configuration and active-class behavior. The stopper class serves special kernel work; deadline and real-time classes have their own policies; fair handles ordinary policies when they are assigned there; idle supplies the fallback task. This list is not a statement that every class is enabled or runnable on every CPU. See v6.12 scheduler-class ordering.

Linux v6.12 also has sched_ext, a BPF-extensible scheduling class when configured and enabled. Its position is below fair in the class ordering, but an enabled sched_ext scheduler can schedule ordinary-policy tasks through the ext class depending on its operating mode. In partial mode, only SCHED_EXT tasks are scheduled by sched_ext; SCHED_NORMAL, SCHED_BATCH and SCHED_IDLE remain under CFS. Without the partial flag, those three policies plus SCHED_EXT are scheduled by sched_ext. A task explicitly set to SCHED_EXT is treated as SCHED_NORMAL under CFS until a BPF scheduler is loaded. The exact active state should be checked on the running system. The v6.12 sched_ext source and sched_ext documentation describe that facility.

A class ordering is not a complete application priority guarantee. Throttling, CPU affinity, bandwidth limits, class-specific rules, preemption points and available CPUs affect what runs. The next chapter examines fair-class EEVDF, while the following chapter treats real-time and deadline policies. A task's policy can change only under the relevant permissions and kernel rules; reading a policy value does not establish its history.

Wakeup, preemption and barriers#

A sleeping task usually sets an appropriate state, arranges to be awakened when a condition changes, and eventually calls a scheduling function. The condition and waitqueue protocol must be synchronized with the waker. The waker's try_to_wake_up path tests and transitions state under its documented locking and ordering rules, chooses or confirms a destination and makes the task runnable. Enqueueing does not mean the task executes immediately. If the awakened task should preempt the current one, the scheduler can set a need-reschedule indication; the actual switch occurs at an allowed scheduling or return-to-user point. Preemption-disabled regions, interrupt context and lock state constrain when that can happen.

A classic lost-wakeup bug arises if a waiter checks a condition without the required synchronization, the waker changes it and sends a wakeup, and only then the waiter goes to sleep without rechecking. No scheduler class can repair an incorrectly designed wait protocol. Memory barriers and locks ensure required ordering and visibility, but the correct operations depend on the waitqueue API and condition. Never replace the kernel's wakeup protocol with invented pseudocode when reviewing a real race. A task lifetime reference is also required if the waker retains a pointer beyond the lifetime guaranteed by its caller.

Sleeping while holding a raw spinlock, with interrupts disabled, or in other atomic contexts can deadlock or trigger diagnostics. A blocking allocation, normal user copy or mutex acquisition may sleep; whether a particular operation can block is part of its contract. A voluntary call to schedule is not a general way to release arbitrary locks. The scheduler internally has special lock and context rules; those do not authorize a driver to sleep while holding its own spinlock. Later locking chapters develop the distinctions.

Load and runtime are different measurements#

PELT, per-entity load tracking, maintains decaying estimates associated with runnable and running activity. It helps scheduling and placement code estimate demand, but it is not a literal trace of every instant, an exact future prediction or a synonym for /proc/loadavg. Utilization, runnable demand and weighted load answer related but different questions. Configuration, update timing, groups and CPU capacity affect interpretation. A task that recently blocked may retain a decaying contribution; a newly active task's estimate can rise over time. Read v6.12 kernel/sched/pelt.c with the relevant call sites before claiming a particular placement decision.

Scheduler statistics also have scope and permission limits. /proc/PID/sched, /proc/PID/schedstat and context-switch counters can be unavailable, disabled, restricted or sampled while the task changes state. Two counter reads establish a difference in a reported counter over an interval, not the precise sequence of all events between them. A context-switch count does not say by itself whether a particular lock, I/O operation or scheduler policy caused each switch. For a timeline, tracing requires additional instrumentation and its own measurement caveats.

A worked two-task timeline#

Assume two ordinary fair-class tasks A and B are allowed on CPUs 0 and 1, and no higher-priority work interferes. At time 0 A runs on CPU 0 while B sleeps waiting for a condition. A's state and B's sleep state are different from their process exit states. At time 1 another task completes the condition and wakes B using the correct wait protocol. try_to_wake_up can select an allowed CPU and enqueue B; suppose it chooses CPU 1. B is runnable after the successful enqueue, but it is not necessarily executing until CPU 1 selects it.

At time 2 CPU 1 picks B. The context-switch code saves the previous task's state and restores B's context; B resumes after the scheduling point where it had blocked. At time 3 B blocks again on another condition, and CPU 1 selects another runnable task or idle. If CPU availability or affinity changes, a later wakeup might place B on CPU 0 instead. Migration and wakeup paths coordinate runqueue and task state so that a task is not incorrectly executed simultaneously as two independent runnable copies. This is a simplified conditional timeline, not a prediction of which CPU a particular workload will use.

Change one assumption: B is already runnable when a redundant wakeup is attempted, or the requested wake state does not match. The source can take a different branch and the imagined new enqueue is not established. Another failure is a wait condition set without the required synchronization; a task can miss the event and remain asleep even though CPU 1 is idle. Distinguish the application's synchronization bug from the scheduler's choice among tasks already runnable.

Practice#

Source-only route: annotate the A/B timeline with four columns: task state, possible runqueue/CPU, synchronization or event, and what remains unknown. Include the redundant-wakeup counterexample and explain why the prev == next branch can perform no switch. This is a prediction from the cited source, not a captured scheduling trace.

Read-only host route: from an ordinary Linux shell, inspect only the shell process named by $$:

printf 'shell pid=%s\n' "$$"
cat "/proc/$$/stat"
sed -n '/^State:/p; /^Cpus_allowed_list:/p; /^voluntary_ctxt_switches:/p; /^nonvoluntary_ctxt_switches:/p' "/proc/$$/status"
head -25 "/proc/$$/sched" 2>/dev/null || printf 'sched details unavailable\n'
cat "/proc/$$/schedstat" 2>/dev/null || printf 'schedstat unavailable\n'

stat is a structured line whose second field is parenthesized and can contain spaces; do not split it blindly by whitespace to identify later fields. The state and counters are snapshots, and values may change between commands. Some files or fields can be unavailable because of kernel configuration, namespace or permissions. Do not use sudo or modify scheduler knobs to obtain them. The command may itself cause scheduling activity, so comparing successive reads is an intervention, not a zero-cost measurement. Process names, command lines and CPU topology can be sensitive; review notes before sharing.

Deliver a note with the four-column timeline, observed state and context-switch counters, and a statement of what those samples cannot prove. As a counterexample, a higher voluntary counter between two samples does not identify the exact blocking syscall or demonstrate that the task never migrated. No files or host settings were changed; no cleanup is required.

Knowledge check#

1. Why is a runnable task not necessarily running, and why is exit_state not interchangeable with __state?
2. What happens in the quoted __schedule path when prev and next are the same task?
3. How can ordinary-policy tasks be handled by sched_ext rather than fair in v6.12?
4. What must a wait/wakeup protocol protect against besides choosing the next CPU?
5. Why does a context-switch counter difference not reconstruct the complete task timeline?

Answers#

1. Runnable tasks compete for CPU and may wait while another runs. Scheduling state and termination state encode different relationships and transitions; neither alone provides a complete lifetime story.
2. The shown context_switch call is conditional on a different next task. The same-task branch performs its required runqueue unlock and bookkeeping without switching to another task.
3. When sched_ext is configured and a BPF scheduler is enabled, its mode determines which tasks enter the class. In the non-partial mode normal-policy tasks can be included; in partial mode the selection is narrower. Verify actual scheduler state.
4. It must prevent races such as checking a condition, missing a wakeup and then sleeping. Correct state, lock, barrier and object-lifetime protocols matter independently of CPU selection.
5. It is an aggregate sampled over an interval. It does not reveal every state, CPU, cause or ordering, and the measurement itself can perturb execution.

Checkpoint#

Deliver the A/B timeline and either source-only reasoning or the labeled /proc observations. Pass when you explain wakeup versus execution, the conditional prev != next switch, sched_ext's configuration-dependent role and one synchronization failure. If uncertain, retrace try_to_wake_up and __schedule and repeat the read-only observation. This checkpoint is not certification.

Sources#

• v6.12 scheduler core: wakeup, selection and context switch.
• v6.12 scheduler internals and task structure.
• v6.12 class ordering and sched_ext implementation.
• sched_ext documentation.
• v6.12 PELT implementation.