Scheduler Subsystem Details

Scheduler Subsystem Details

Runqueue Locking

• Runqueue locks are raw_spinlock_t (never sleeps, even on PREEMPT_RT)
• Multi-runqueue operations must lock in consistent order to prevent deadlock
• double_rq_lock() / double_rq_unlock() handle ordering automatically (swaps to ascending order internally via rq_order_less())
• lockdep_assert_rq_held() validates rq lock is held in accessors
• task_rq(p) expands to cpu_rq(task_cpu(p)). Without pinning or holding pi_lock / rq lock, the task can migrate after task_cpu(p) is read, so the caller gets CPU A's runqueue while the task is now on CPU B.
• Never release rq lock with a task in inconsistent state — on_rq, the RB-tree, and p->__state must all agree before the lock is dropped. Other CPUs observe these fields immediately after unlock:
  • Task in tree but on_rq == 0: try_to_wake_up() sees on_rq == 0 and calls activate_task() → double enqueue corrupts the RB-tree
  • on_rq == 1 but not in tree: try_to_wake_up() sees on_rq == 1 and skips enqueue, but pick_next_task never finds the task — permanently lost
  • TASK_RUNNING with on_rq == 0: try_to_wake_up() sees TASK_RUNNING and returns early (no wakeup needed) — task hangs forever with no way to recover

Task State Transitions

• set_current_state() includes a barrier so the state write is ordered relative to subsequent memory accesses (the condition check)
• Voluntary sleep pattern: set state BEFORE checking the condition, otherwise a wakeup between the check and the state change is lost

// CORRECT — state set before condition check
set_current_state(TASK_UNINTERRUPTIBLE);
if (!condition)
    schedule();
set_current_state(TASK_RUNNING);

// WRONG — lost wakeup if condition changes between check and set_current_state
if (!condition) {
    set_current_state(TASK_UNINTERRUPTIBLE);  // wakeup already happened
    schedule();                                // sleeps forever
}

• TASK_RUNNING is the only state where a task can be on a runqueue
• TASK_DEAD requires special handling — task cannot be rescheduled
• wake_up_process() handles state races internally (safe for any task state)

CPU Affinity and Migration

• set_cpus_allowed_ptr() changes a task's allowed CPU mask
• kthread_bind() restricts a kthread to a specific CPU
• Migration must respect cpumask_subset() against allowed CPUs
• Check is_migration_disabled() before migrating a task
• stop_one_cpu() may be needed for forced migration
• CPU hotplug requires special care — tasks must not be migrated to a CPU being taken offline
• Migration-disabled sections cannot block or sleep

CFS (SCHED_NORMAL / SCHED_BATCH / SCHED_IDLE)

EEVDF Algorithm

• Selects the eligible task (positive lag = owed service) with the earliest virtual deadline
• Virtual deadline: vd = vruntime + vslice where vslice = calc_delta_fair(slice, se) computes slice * NICE_0_LOAD / weight (source comment: vd_i = ve_i + r_i/w_i)
• Base slice: sysctl_sched_base_slice (default 700μs); deadline updated when vruntime >= deadline

Key Fields

• vruntime: per-entity monotonic counter of weighted CPU time; must be normalized when migrating between CPUs
• min_vruntime: per-cfs_rq monotonic clock tracking progress; must never decrease
• vlag: tracks service deficit/surplus; vlag = V - vruntime where V is the weighted average vruntime (avg_vruntime); preserved across enqueue/dequeue by place_entity()
• on_rq: must be 1 iff entity is in the RB-tree; double enqueue or mismatch corrupts the runqueue
• Load weight: derived from nice value via prio_to_weight[]; ~10% change per nice level

RB-Tree Structure

The RB-tree is sorted by deadline and augmented with min_vruntime per node, enabling O(log n) eligibility pruning in __pick_eevdf(). A subtree can be skipped entirely if its min_vruntime shows no eligible entities.

PELT (Per-Entity Load Tracking)

• update_load_avg() must be called BEFORE any entity state change (enqueue/dequeue/migration) to maintain hierarchy consistency
• Tracks a decaying average of utilization per entity and per cfs_rq
• On migration: DO_ATTACH attaches load to new CPU, DO_DETACH detaches from old CPU

CFS Bandwidth

• Group throttling uses cfs_rq->runtime_remaining
• Must properly dequeue on throttle, enqueue on unthrottle
• Hierarchical: parent throttle affects all children

Real-Time (SCHED_FIFO / SCHED_RR)

• Priority range: 1–99 (userspace); higher number = higher priority. Kernel internal priority is inverted (MAX_RT_PRIO - 1 - rt_priority)
• RT bandwidth: sched_rt_runtime_us / sched_rt_period_us prevent CPU monopolization (default 95% limit — 950ms per 1000ms period)
• Tasks throttled when bandwidth exhausted; check sched_rt_runtime()

Deadline (SCHED_DEADLINE)

• Invariant: runtime ≤ deadline ≤ period
• Admission control: tasks can be created while Σ(runtime_i / period_i) ≤ M × (rt_runtime / rt_period) where M is CPU count in the root domain
• CBS (Constant Bandwidth Server) enforces bandwidth isolation
• Global Earliest Deadline First (GEDF): on an M-CPU system, the M tasks with earliest deadlines should be running
• Throttling: task blocked when runtime exhausted, unblocked at next period (replenishment)
• DL tasks tracked per root domain for migration decisions

sched_ext (SCHED_EXT — BPF Extensible Scheduler)

• Scheduler behavior defined by BPF programs via ops callbacks (select_cpu, enqueue, dispatch, etc.)
• Dispatch queues (DSQ): tasks queued in local (per-CPU), global, or custom DSQs; can use FIFO or PRIQ (vtime) ordering but not mixed
• ops_state tracking: atomic p->scx.ops_state prevents concurrent BPF operations on the same task; transitions: NONE → QUEUEING → QUEUED → DISPATCHING
• Direct dispatch: optimization allowing enqueue path to dispatch directly to local DSQ via per-CPU direct_dispatch_task marker
• Failsafe: watchdog timeout, scx_error(), and SysRq-S all trigger automatic revert to CFS

Priority Inheritance

• When a high-priority task blocks on a lock held by a low-priority task, the lock holder temporarily inherits the blocked task's priority
• PI chain must be updated atomically; checked for cycles to detect deadlock
• RT mutex is the primary use case
• pi_lock protects PI state; must be held when traversing the chain

Quick Checks

• preempt_disable() / preempt_enable() must always be balanced
• set_task_cpu() only safe during migration with proper locks held
• Never call schedule() with preemption disabled or non-rq locks held
• Never enqueue a task that is already on a runqueue