Skip to content
Linux Systems Field Manual

linux/kernel/sched/deadline.c

Imported from _research/manual-study-linux/file-notes/linux__kernel__sched__deadline.c.md.

File Notes: kernel/sched/deadline.c

Status: reviewed.

Purpose

Implements SCHED_DEADLINE: Earliest Deadline First selection combined with Constant Bandwidth Server reservation, bandwidth accounting, replenishment, throttling, parameter validation, and deadline class callbacks.

Key Types And Functions

  • init_dl_rq(): initializes deadline runqueue tree and bandwidth counters.
  • __add_running_bw() / __sub_running_bw() and rq bandwidth helpers.
  • setup_new_dl_entity() / replenish_dl_entity(): CBS replenishment.
  • dl_runtime_exceeded() / update_curr_dl(): budget accounting.
  • enqueue_dl_entity() / dequeue_dl_entity(): RB-tree membership.
  • pick_next_dl_entity() / pick_task_dl(): EDF selection.
  • __checkparam_dl(): user parameter validation.
  • DEFINE_SCHED_CLASS(dl): deadline class callback table.

Data Flow

Deadline entities carry runtime, deadline, period, remaining runtime, and bandwidth. Each CPU’s dl_rq stores runnable entities in a cached RB tree, where the leftmost node has the earliest deadline. The class also tracks running_bw and this_bw so active and reserved bandwidth can be accounted separately.

On wakeup or new instance, CBS logic may set a fresh absolute deadline and runtime budget. When a task overruns, it is throttled until replenishment. update_curr_dl() charges elapsed runtime and updates the deadline entity. When a throttled or deferred entity becomes eligible again, enqueue_dl_entity() can replenish, cancel obsolete timers, clear throttling, and insert the entity in the RB tree.

pick_next_dl_entity() returns the leftmost RB-tree entity. pick_task_dl() then resolves either a server entity or a normal deadline task. Parameter validation rejects invalid deadline settings before admission.

Invariants And Safety Contracts

  • CBS prevents an overrunning entity from interfering with other reservations.
  • Bandwidth counters must not underflow/overflow and are updated under the runqueue lock.
  • Deadline parameters must satisfy runtime <= deadline <= period and internal resolution/limit constraints.
  • Throttled entities are not runnable until replenishment rules permit it.

Rust Translation Guidance

Use a reservation type with validated construction; invalid deadline/runtime triples should be impossible after admission. Keep runnable ordering in a deadline tree and bandwidth accounting in the runqueue. Timers and throttling state should be attached to the reservation entity, not scattered across the task.

AI-Native Systems Guidance

Deadline scheduling maps cleanly to AI jobs with explicit service-level objectives: runtime budget, deadline, period, and admission control. Overrun jobs should be throttled or degraded rather than allowed to consume unrelated job budgets.

Evidence

  • The file describes EDF plus CBS and isolation guarantees at kernel/sched/deadline.c:3-11.
  • Bandwidth helpers update running_bw and this_bw under runqueue lock and guard overflow/underflow at kernel/sched/deadline.c:213-289.
  • init_dl_rq() initializes the RB tree, earliest deadline state, pushable tree, and bandwidth counters at kernel/sched/deadline.c:519-532.
  • New-period setup and CBS replenishment are documented and implemented at kernel/sched/deadline.c:724-799.
  • Runtime-exceeded and GRUB accounting logic starts at kernel/sched/deadline.c:1345-1368; update_curr_dl() charges current deadline execution at kernel/sched/deadline.c:2124-2147.
  • RB-tree enqueue/dequeue and throttling/replenishment checks are at kernel/sched/deadline.c:2356-2488.
  • Deadline task selection uses the leftmost cached RB node at kernel/sched/deadline.c:2769-2844; switch hooks follow at kernel/sched/deadline.c:2846-2865.
  • The deadline callback table is at kernel/sched/deadline.c:3644-3676.
  • User parameter validation appears at kernel/sched/deadline.c:3879-3930.