Per-CPU Run Queues and struct rq

Linux does not keep one global list of runnable tasks. It keeps one run queue per CPU, each an instance of struct rq, stored in the per-CPU variable runqueues. A run queue is the local universe of a single core: the set of tasks ready to run there, the bookkeeping the scheduler needs to pick among them, the lock that serializes all of it, and the per-CPU clock that times slices. The fair scheduler’s design doc puts the rationale plainly — “CFS uses a runqueue per CPU” — and this per-CPU structure is why the scheduler scales: most scheduling decisions touch only the local rq and never contend on a global lock (sched-design-CFS). Crucially, struct rq does not itself hold a flat list of tasks; it embeds one sub-runqueue per scheduling class (struct cfs_rq cfs, struct rt_rq rt, struct dl_rq dl, and struct scx_rq scx), so each policy keeps its tasks in its own optimal data structure while sharing the per-CPU envelope. The definitions below are verified against kernel/sched/sched.h at 6.12 LTS (released 2024-11-17) and cross-checked at 6.18 LTS (2025-11-30), where the layout is unchanged (v6.12 sched.h).

This note is about the container. The polymorphic methods that operate on it are Scheduling Classes and the sched_class Interface; the master routine that locks it and drives a context switch is The Core Scheduler and __schedule.

Mental Model — A Private Workspace Per Core

flowchart TB
  subgraph CPU0["CPU 0"]
    RQ0["struct rq (runqueues[0])<br/>__lock, nr_running, clock<br/>curr / idle / stop"]
    RQ0 --> C0["cfs (cfs_rq) — EEVDF rbtree"]
    RQ0 --> R0["rt (rt_rq) — prio array"]
    RQ0 --> D0["dl (dl_rq) — EDF rbtree"]
    RQ0 --> X0["scx (scx_rq) — sched_ext"]
  end
  subgraph CPU1["CPU 1"]
    RQ1["struct rq (runqueues[1])<br/>__lock, nr_running, clock<br/>curr / idle / stop"]
    RQ1 --> C1["cfs"]
    RQ1 --> R1["rt"]
    RQ1 --> D1["dl"]
    RQ1 --> X1["scx"]
  end
  BAL["load balancer<br/>(sched_domains)"] -.->|"migrate tasks,<br/>take both rq locks"| RQ0
  BAL -.-> RQ1

The per-CPU run queue layout. What it shows: each CPU owns one struct rq, accessed as runqueues[cpu]; inside it are the per-class sub-runqueues, each holding that class’s runnable tasks in its own structure (EEVDF’s augmented red-black tree for cfs, a priority-indexed array for rt, an EDF tree for dl). The insight to take: because every core has its own queue and its own lock, a scheduling decision on CPU 0 normally never contends with CPU 1 — contention happens only when the load balancer (dashed) deliberately reaches across to move a task, at which point it must lock both run queues in a defined order to avoid deadlock.

Walking struct rq Field by Field

The structure (sched.h line 1096 at v6.12) is large and config-heavy; the load-bearing fields are these.

The lock. The first field is raw_spinlock_t __lock. The leading underscores are deliberate: code must not touch rq->__lock directly but go through wrapper accessors (rq_lockp(rq), raw_spin_rq_lock(rq)), for a reason explained in the locking section below. It is a raw_spinlock_t — a spinlock that does not become a sleeping mutex even under PREEMPT_RT — because the scheduler core runs in atomic, IRQ-disabled context where sleeping is forbidden.

Counters. unsigned int nr_running is the number of runnable tasks across all classes on this CPU — the single number the scheduler checks to decide whether the CPU is idle and whether load balancing is warranted. nr_uninterruptible counts tasks in uninterruptible sleep (TASK_UNINTERRUPTIBLE) — its global sum feeds the classic load-average computation. nr_switches counts context switches for statistics. The comment on nr_uninterruptible is itself instructive: it is “part of a global counter where only the total sum over all CPUs matters” — a task can increment it on one CPU and decrement it on another after migration, “always updated under the runqueue lock.”

The per-class sub-runqueues. The heart of the structure:

struct cfs_rq		cfs;   // fair class (EEVDF) — runnable tasks in an rbtree keyed by virtual deadline
struct rt_rq		rt;    // real-time class — array of lists, one per RT priority
struct dl_rq		dl;    // deadline class — rbtree keyed by absolute deadline (EDF)
#ifdef CONFIG_SCHED_CLASS_EXT
struct scx_rq		scx;   // sched_ext (BPF) class
#endif

Each is the per-CPU portion of its class. cfs holds the EEVDF red-black tree and the per-CPU fair-scheduling state (see Virtual Runtime and the Fair Scheduling Invariant and The EEVDF Scheduler); rt holds the priority-indexed run lists for Real-Time Scheduling SCHED_FIFO and SCHED_RR; dl holds the earliest-deadline-first tree for SCHED_DEADLINE and Earliest Deadline First; scx holds the dispatch queues that sched_ext and BPF-Defined Schedulers manage. The class abstraction means the core scheduler reaches these only through the class methods — enqueue_task knows to add a fair task to rq->cfs, an RT task to rq->rt, and so on.

The distinguished task pointers.

struct task_struct __rcu *curr;   // the task currently running on this CPU
struct sched_dl_entity   *dl_server;
struct task_struct       *idle;   // this CPU's idle task (the per-CPU swapper/idle thread)
struct task_struct       *stop;   // this CPU's stop/migration kthread (stop_sched_class)

curr is what is running right now on this CPU; __schedule reads it as prev and writes the chosen task into it as the new current. It is annotated __rcu because other CPUs may read it lock-free under RCU (for example when deciding whether to send a reschedule IPI). idle is the special task that runs when nr_running reaches zero — idle_sched_class always has it ready, which is why __pick_next_task ends with BUG() if even idle has nothing (it never should). stop points at the per-CPU high-priority kthread that stop_sched_class schedules, used to execute migrations and other “stop the CPU and do this now” work — see Migration the Stop Class and the Migration Thread. The dl_server pointer is part of the deadline-server mechanism that lets fair tasks borrow deadline-class bandwidth so they cannot be starved by misconfigured real-time load.

The clocks. A run queue carries its own notion of time:

unsigned int clock_update_flags;
u64 clock;                              // rq's view of wall-ish time (ns)
u64 clock_task ____cacheline_aligned;   // clock minus time stolen by IRQ/steal
u64 clock_pelt;                         // clock used for PELT load tracking

rq->clock is the run queue’s timestamp in nanoseconds, refreshed once per scheduler activation by update_rq_clock(). rq->clock_task is clock with time consumed by hard/soft IRQ handling and (under virtualization) hypervisor-stolen time subtracted out, so that a task is only charged for time it actually got the CPU — this is the clock the fair class uses to accrue vruntime. The two are deliberately split across cache lines (____cacheline_aligned) so the hot clock_task reads don’t false-share. The accessors enforce discipline (sched.h lines 1643–1657):

static inline u64 rq_clock(struct rq *rq) {
	lockdep_assert_rq_held(rq);
	assert_clock_updated(rq);
	return rq->clock;
}

Both rq_clock and rq_clock_task assert that the rq lock is held and that the clock has been updated this activation, catching a whole class of bugs where code reads a stale timestamp.

SMP fields (under CONFIG_SMP). cpu is this run queue’s CPU id; online whether it is up; rd (root domain) and sd (the RCU-protected scheduling-domain pointer) link this CPU into the topology that Scheduling Domains and CPU Topology describes; cpu_capacity records the CPU’s compute capacity for Capacity-Aware and Energy-Aware Scheduling; nr_pinned, active_balance, push_cpu, and balance_callback drive Scheduler Load Balancing. cfs_tasks is a flat list of this CPU’s fair tasks used to pick migration candidates. There are also NUMA counters (nr_numa_running), tickless-idle fields (nohz_*, used by Housekeeping CPUs and Tickless Isolation), and, under CONFIG_SCHED_CORE, the core_* fields for SMT co-scheduling.

Accessing a Run Queue — cpu_rq, this_rq, task_rq

The run queues are one per-CPU array, declared and defined as:

DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);   // sched.h:1340
DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);    // core.c:120

SHARED_ALIGNED places each CPU’s rq on its own cache line(s) so cross-CPU accesses (the balancer touching a remote rq) don’t thrash the owning CPU’s cache. The standard accessors (sched.h lines 1342–1346):

#define cpu_rq(cpu)   (&per_cpu(runqueues, (cpu)))   // the rq for an arbitrary CPU
#define this_rq()     this_cpu_ptr(&runqueues)        // the rq for the CPU we're running on
#define task_rq(p)    cpu_rq(task_cpu(p))             // the rq a given task is queued on
#define cpu_curr(cpu) (cpu_rq(cpu)->curr)             // the task currently running on a CPU
#define raw_rq()      raw_cpu_ptr(&runqueues)

this_rq() is the workhorse on the local hot path (e.g. rq = cpu_rq(smp_processor_id()) at the top of __schedule). cpu_rq(cpu) is how the balancer reaches a remote CPU’s queue. task_rq(p) follows a task to its current queue via task_cpu(p) — which is why migrating a task is fundamentally “dequeue from task_rq(p), update task_cpu, enqueue on the destination rq.”

Locking — Why It Is __lock, Not lock

The brief calls this rq->lock; at 6.12 the field is actually named rq->__lock, and the rename encodes a real subtlety. Code never locks rq->__lock directly. It goes through raw_spin_rq_lock(rq), which resolves the effective lock via rq_lockp(rq). The reason is core scheduling (CONFIG_SCHED_CORE, the SMT-sibling co-scheduling feature). When core scheduling is enabled, two hyperthreads of the same physical core must coordinate their picks, so their run queues share a single lock (sched.h lines 1367–1381):

static inline raw_spinlock_t *rq_lockp(struct rq *rq) {
	if (sched_core_enabled(rq))
		return &rq->core->__lock;   // siblings share the core leader's lock
	return &rq->__lock;             // otherwise, the rq's own lock
}

When core scheduling is not configured (the common case), the alternate definition (lines 1466–1474) just returns &rq->__lock. So rq->__lock is the storage; rq_lockp() is the policy for which lock actually protects this rq. Calling it “rq->lock” is a useful shorthand but hides that two run queues can map to one lock.

Whatever it resolves to, it is a raw_spinlock_t taken with interrupts disabled (raw_spin_rq_lock_irqsave), because the scheduler runs from atomic context and from the timer interrupt. Every run-queue mutation — enqueue, dequeue, pick, clock update — happens under it, and lockdep_assert_rq_held(rq) peppers the code to enforce that. This dependence on the locking primitives connects directly to Linux Kernel Synchronization MOC. The double-locking dance the balancer needs (lock two rqs in address order to avoid ABBA deadlock) is double_rq_lock, used by Scheduler Load Balancing.

The Clock Update Path

rq->clock is not free-running; it is refreshed deliberately. update_rq_clock() (core.c line 789) reads the per-CPU sched clock and advances rq->clock and rq->clock_task:

void update_rq_clock(struct rq *rq) {
	s64 delta;
	lockdep_assert_rq_held(rq);
	if (rq->clock_update_flags & RQCF_ACT_SKIP)   // caller asked to skip this activation
		return;
	...
	delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
	if (delta < 0) return;
	rq->clock += delta;
	update_rq_clock_task(rq, delta);   // also advances clock_task, subtracting IRQ/steal time
}

The clock_update_flags field carries three states — RQCF_REQ_SKIP, RQCF_ACT_SKIP, RQCF_UPDATED (sched.h lines 1630–1632). A path that knows it will not consume time can call rq_clock_skip_update() to set RQCF_REQ_SKIP, promoted to RQCF_ACT_SKIP inside __schedule, so a redundant clock read is avoided; RQCF_UPDATED is a debug flag catching double updates. This is why rq_clock()/rq_clock_task() assert the clock was updated: reading a clock that a _skip_ path deliberately left stale is a bug, and the assertion finds it. The wall-clock-vs-task-clock split is what makes per-task time accounting fair under interrupt load — detailed alongside the tick in The need_resched Flag and Preemption Points and the time subsystem in Linux Time and Timers MOC.

Failure Modes and Diagnostics

• Stale-clock read. Reading rq->clock without having called update_rq_clock() this activation (or after a _skip_ request) trips assert_clock_updated. Symptom on a CONFIG_SCHED_DEBUG kernel: a SCHED_WARN_ON splat. Diagnosis: a code path took the rq lock but skipped the clock update before charging a task.
• Lock-ordering deadlock. Taking two run-queue locks in inconsistent order across CPUs is a classic ABBA deadlock; the kernel guards against it with double_rq_lock ordering by address and with lockdep. Out-of-tree code that locks rqs by hand is the usual culprit.
• nr_running drift. If a class’s enqueue/dequeue does not keep rq->nr_running consistent with the sum of its sub-runqueue counts, the CPU can appear busy when idle (no balancing, wasted core) or idle when busy (pick_next_task hits the BUG() because it expected idle to be the only runnable task and it wasn’t). This is why enqueue/dequeue are scrutinized in Runnable State Enqueue and Dequeue.
• Per-CPU access from the wrong CPU. this_rq() is only valid with preemption disabled; using it then migrating mid-function would read the wrong queue. Hot paths run with IRQs/preemption off precisely to pin the CPU.

Inspecting Run Queues in Production

The live state of every run queue is exposed under /proc/sched_debug (and, historically, /proc/<pid>/sched), which prints per-CPU nr_running, the cfs/rt/dl sub-runqueue contents, clock/clock_task, and load figures — invaluable for diagnosing why a CPU is idle while tasks wait elsewhere (a load-balancing or affinity problem) or why a task is not getting time. bpftrace/perf sched attach to the scheduler tracepoints (sched_switch, sched_wakeup, sched_migrate_task) that fire as curr changes and tasks move between run queues. A frequent real-world finding is severe imbalance — one CPU’s cfs.nr_running in the dozens while a sibling sits idle — caused by aggressive CPU pinning (CPU Affinity and sched_setaffinity) or isolcpus (CPU Isolation isolcpus and nohz_full) defeating the balancer.

See Also

• Scheduling Classes and the sched_class Interface — the methods that operate on the sub-runqueues inside rq
• The Core Scheduler and __schedule — locks the rq, reads curr, drives the context switch
• Scheduler Entry Points and pick_next_task — selects the next task to install as rq->curr
• Runnable State Enqueue and Dequeue — how tasks enter and leave the sub-runqueues and maintain nr_running
• The EEVDF Scheduler / Virtual Runtime and the Fair Scheduling Invariant — the cfs_rq sub-runqueue’s contents
• Scheduler Load Balancing / Scheduling Domains and CPU Topology — moving tasks between per-CPU run queues
• Migration the Stop Class and the Migration Thread — the rq->stop task
• Linux Kernel Synchronization MOC — the spinlock and RCU primitives rq->__lock and curr rely on
• Linux Process Scheduling MOC — the parent map