Real-time, deadline, and priority inversion

Before you start#

Read scheduler core and fair scheduling and EEVDF. This chapter introduces the lock concepts it needs; later chapters develop them further. The source baseline is upstream v6.12. The host exercise never installs a real-time policy on the host and uses only one short-lived child with deliberately invalid parameters.

Learning goals#

Differentiate FIFO, round-robin and deadline scheduling; follow real-time selection and deadline runtime exhaustion in actual source; explain admission, throttling and priority inheritance as separate mechanisms; and reason about a bounded illustrative timeline without promising a hardware deadline.

Priority and policy are different coordinates#

SCHED_FIFO and SCHED_RR are fixed-priority real-time scheduling policies. Their user-visible priority range is queried using sched_get_priority_min and sched_get_priority_max; on Linux the real-time range is normally 1 through 99, with larger public numbers representing higher priority. The kernel's internal priority numbering uses the opposite numerical direction in relevant comparisons: smaller internal values can represent higher priority. Do not compare a public RT priority directly to an internal p->prio without understanding the conversion. Nice values control a different fair-scheduling weight mechanism and do not rank FIFO tasks.

Among runnable FIFO tasks at the highest applicable priority, a task continues until it blocks, yields, is preempted by higher-priority work, or another applicable scheduler condition intervenes. FIFO does not provide a periodic time slice to rotate equal-priority tasks. SCHED_RR adds round-robin time-slice behavior among equal-priority peers. A quantum expiry can move an entity to the tail when there is an eligible peer; it is not an unconditional guarantee that another process runs at a particular microsecond. The applicable scheduler, CPU affinity, configuration and bandwidth constraints matter.

A continuously runnable high-priority FIFO task can starve lower-priority real-time and fair work on a CPU, subject to throttling and other constraints. This is why examples that create busy real-time loops on a shared host are unsafe and unnecessary here. Real-time scheduling changes CPU selection policy; it does not speed up a blocked device, remove interrupt latency, or give a general guarantee that all deadlines are met. Linux RT throttling can reserve time for non-RT work under applicable configuration, but do not treat it as a substitute for a bounded workload and recovery plan.

Source walkthrough#

The real-time runqueue rt_rq and sched_rt_entity represent class-specific queued state and can be hierarchical when configured. In v6.12 kernel/sched/rt.c, pick_task_rt includes this excerpt (SPDX GPL-2.0; local declarations omitted):

if (!sched_rt_runnable(rq))
	return NULL;

p = _pick_next_task_rt(rq);

The function first checks whether the RT class has runnable work on that runqueue. If not, it returns no RT candidate. Otherwise it delegates selection; _pick_next_task_rt follows RT entities and any configured group runqueues until it reaches a task or has no entity. The runqueue's lock and scheduler context protect this operation. A returned pointer's validity depends on those rules, not on the text of this snippet alone. Selection of a candidate is one stage in the overall class and CPU decision, not a claim that the task has already executed.

The same file's task_tick_rt updates current runtime and checks policy. Its comments and branch distinguish FIFO from RR: FIFO has no RR time slice, while an RR entity's remaining slice is decremented and reset as appropriate. RT bandwidth accounting and throttling can be compiled or configured differently, including group scheduling. The sched_rt_runtime_us and sched_rt_period_us controls and their exact effect depend on the kernel and configured groups; do not modify them on the host as a learning shortcut. Consult RT group scheduling for the relevant configuration.

The RR branch of that function reads (SPDX GPL-2.0; the group requeue loop that follows it is not shown):

	/*
	 * RR tasks need a special form of time-slice management.
	 * FIFO tasks have no timeslices.
	 */
	if (p->policy != SCHED_RR)
		return;

	if (--p->rt.time_slice)
		return;

	p->rt.time_slice = sched_rr_timeslice;

FIFO returns before any slice arithmetic. For RR the counter is decremented on each tick and, when it reaches zero, reset to sched_rr_timeslice. Whether the task is then requeued behind a peer and whether a reschedule is requested depends on the loop after this block, which checks the entity's run list; the excerpt alone does not show that decision.

Deadline scheduling is distinct. A sched_dl_entity carries parameters and evolving state associated with a deadline reservation, and a dl_rq organizes deadline-class entities. SCHED_DEADLINE uses an earliest-deadline-first ordering combined with Constant Bandwidth Server-style runtime control. Userspace supplies runtime, deadline and period values under the API's constraints; they are not the same fields as EEVDF's virtual deadline. The kernel performs admission control and can reject a request that cannot be admitted under its policy and scheduling domain. A successful admission is not proof that hardware, interrupts, blocking and application assumptions satisfy an end-to-end deadline.

In v6.12 kernel/sched/deadline.c, dl_runtime_exceeded is this short function (SPDX GPL-2.0; surrounding code omitted):

return (dl_se->runtime <= 0);

The entity's remaining runtime is tested against zero; it is not a test that the application completed its work. In the later accounting path, exhausted or yielded runtime can mark the entity throttled and dequeue it until the applicable replenishment behavior. The timer and enqueue paths coordinate replenishment, runqueue locks, task state and references; a task can change policy or exit while a timer is relevant, so lifetime and state checks matter. update_curr_dl accounts execution using scheduler-observed task time, while the source comments distinguish deadline wall time. Reclaiming and server-specific branches change details. Read the deadline scheduling documentation before applying a simplified formula to a real system.

A budget is not a completion guarantee#

For a simple illustrative reservation, runtime Q is the execution budget, D is the relative deadline, and T is the period. Together they describe a requested budget and timing relationship, subject to kernel validation and admission. The ratio Q/T is a useful utilization measure in a simplified periodic model, not a complete admission algorithm for every multiprocessor root domain or a proof of schedulability under arbitrary blocking. Linux's actual admission decision depends on its configured policy and eligible CPUs. Invalid parameter relationships can return EINVAL; insufficient admitted bandwidth can result in EBUSY; insufficient authority can result in EPERM. The exact first error depends on the request and validation order. CAP_SYS_NICE, resource limits, namespaces and security policy affect authority; possessing a capability does not bypass parameter validation or guarantee admission.

Consider one CPU with two synthetic periodic jobs, no overhead, no blocking and no other work. A has runtime budget 2 ms, relative deadline 5 ms and period 10 ms; B has runtime budget 3 ms, relative deadline 10 ms and period 10 ms. Both release at time 0, so their absolute deadlines are 5 and 10. Assume the CPU is continuously available, with no other runnable work, overhead or blocking. If both are runnable and admitted under the model, EDF selects A first. A consumes 2 ms and completes at time 2; B then consumes 3 ms and completes at time 5. This timeline uses exactly 5 ms of CPU within the 10 ms period. The arithmetic illustrates ordering and budget, not an actual v6.12 measurement or a universal multicore admission test.

Now suppose A needs 3 ms of work despite a 2 ms reservation. After it consumes its available budget, the deadline scheduler's applicable CBS path can throttle it until replenishment; it cannot simply continue to consume unlimited CPU under that reservation. Its job may miss a deadline. If a higher-class event, interrupt, lock contention or different release pattern is introduced, the simple timeline changes. The deadline source has special server and reclaiming behavior; this teaching example assumes ordinary non-reclaiming reservations and does not reproduce every branch.

Contrast a FIFO scenario: high-priority task H becomes runnable on the same CPU and loops without blocking, while lower-priority task L is ready. Under the simple model with no throttling or higher-class intervention, L cannot run until H stops, blocks or yields. If RT bandwidth throttling applies, the actual system may impose an additional limit. This is a thought experiment only; it is not an instruction to create H on the host.

Placement, push and pull#

On SMP, RT and deadline tasks still have allowed CPU masks and runqueue state. Their implementations include push and pull mechanisms for overloaded runqueues and migration under appropriate locks and affinity constraints. The selected candidate can differ from a single-CPU queue ordering if migration or a higher-priority task on another CPU is involved. rt_rq and dl_rq protect class-specific state through scheduler runqueue synchronization; a timer callback or migration path must coordinate with task policy changes and object lifetime. A task can block, exit or change policy while a timer or wakeup is in flight, so a source trace must include the relevant locks and references rather than simply follow a pointer after unlock.

A CPU mask restriction can also make an otherwise plausible admission or placement impossible. User-visible errors are not exhaustive explanations: EINVAL can indicate invalid policy parameters, EPERM can indicate insufficient authority, and EBUSY can indicate an admission conflict on a relevant path. Other kernel versions and security mechanisms can return different errors for particular conditions. Always retain the requested parameters and the exact call and environment.

Priority inheritance and its limits#

Priority inversion occurs when high-priority task H waits for a lock held by lower-priority task L, while medium-priority work can prevent L from running to release it. An RT mutex can implement priority inheritance: the owner temporarily inherits an effective priority associated with a higher-priority waiter, including propagation through a chain when the relevant locks and rules support it. The boost helps L run and release the lock; it does not transfer ownership to H or make the critical section instantaneous.

In v6.12 kernel/locking/rtmutex.c, rt_mutex_adjust_prio contains (SPDX GPL-2.0-only; lock assertions and declarations omitted):

if (task_has_pi_waiters(p))
	pi_task = task_top_pi_waiter(p)->task;

rt_mutex_setprio(p, pi_task);

The conditional identifies the highest-priority relevant waiter when one exists, and the final call adjusts the owner's effective scheduling priority using that information. The surrounding function asserts that the lock's wait lock and the owner's pi_lock are held; those assertions are not incidental. When contention changes or the owner releases the lock, deboost and further adjustments follow the applicable paths. PI does not solve deadlocks, unbounded I/O while holding a lock, all device delays, incorrect lock ordering or arbitrary non-PI locks. PREEMPT_RT changes the implementation of some lock classes, but raw spinlocks and interrupt-context restrictions remain distinct.

Distinguishing a deadline from a timer event#

A deadline entity's absolute deadline identifies an ordering target in the deadline scheduler's time domain; the runtime budget records how much service the reservation can still consume under its accounting rules. Those values change for different reasons. Merely reaching an absolute deadline does not prove that a particular userspace computation was completed, nor does the exhaustion of budget tell the kernel what the application considers a completed job. A replenishment timer can make a throttled entity eligible for scheduling again, but the timer callback must recheck task state, policy and the relevant runqueue under the correct locks. A pending timer also has a lifetime: policy changes and task exit must coordinate with it so that its callback cannot access freed state. Those details are why a runtime-exhaustion source trace must include its timer and cleanup paths before it is used to justify a teardown change.

Practice#

Source-only route: draw the A/B deadline timeline with releases at 0, deadlines at 5 and 10 ms, and execution intervals 0–2 and 2–5 ms. Add the budget-overrun alternative and identify which assumption changes if an interrupt consumes time. Draw H, L and a lock owner/waiter relation for priority inversion; label temporary donation, lock release and deboost. These are explicit models, not measured response times.

Safe own-child host route: the following synthetic C program reads its own scheduler policy and priority ranges. Its only attempted change is in one child, with SCHED_FIFO priority zero, outside Linux's RT priority range. It waits for the child and does not attempt to establish a real-time task. Run as an ordinary user; do not add capabilities or modify limits.

lab_dir=$(mktemp -d) || exit 1
cd "$lab_dir" || exit 1
cat > policy.c <<'C'
#define _POSIX_C_SOURCE 200809L
#include <errno.h>
#include <sched.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
int main(void) {
    int policy = sched_getscheduler(0);
    int lo = sched_get_priority_min(SCHED_FIFO);
    int hi = sched_get_priority_max(SCHED_FIFO);
    if (policy < 0 || lo < 0 || hi < 0) { perror("query"); return 1; }
    printf("own policy=%d FIFO range=%d..%d\n", policy, lo, hi);
    fflush(stdout);
    pid_t p = fork();
    if (p < 0) { perror("fork"); return 1; }
    if (p == 0) {
        struct sched_param param = { .sched_priority = 0 };
        errno = 0;
        int r = sched_setscheduler(0, SCHED_FIFO, &param);
        dprintf(STDOUT_FILENO, "invalid FIFO request: return=%d errno=%d\n", r, errno);
        _exit(r == -1 ? 0 : 1);
    }
    int status;
    pid_t r;
    do { r = waitpid(p, &status, 0); } while (r < 0 && errno == EINTR);
    if (r < 0) { perror("waitpid"); return 1; }
    if (!WIFEXITED(status) || WEXITSTATUS(status) != 0) return 1;
    return 0;
}
C
cc -std=c11 -Wall -Wextra -Werror -o policy policy.c || exit 1
./policy

On a typical Linux host the invalid request returns -1 with EINVAL; validation, permissions and security policy can produce a different first error, which must be recorded. If the program reports success or the priority range does not make zero invalid, stop and do not repeat with another priority. No positive RT priority is requested. The output is a host observation, not evidence that this machine runs upstream v6.12. Keep the output and the source-only timelines, then remove only your files:

rm policy policy.c
cd /tmp
rmdir "$lab_dir"

A bounded guest experiment with valid RT scheduling would require a disposable guest, suitable permissions and limits, a watchdog, an explicit timeout and a recovery route. This chapter does not supply or require such an experiment; no host scheduler policy or global RT control should be changed.

Knowledge check#

1. How do FIFO and RR differ at equal real-time priority, and why does neither guarantee a deadline?
2. What does the dl_se->runtime <= 0 test establish, and what does it not establish about job completion?
3. Why can a valid-looking deadline request still be rejected with EBUSY or EPERM?
4. How does priority inheritance help a low-priority lock owner, and what does it not solve?
5. Why is a user-visible RT priority not directly comparable to the kernel's internal priority number?

Answers#

1. FIFO has no RR time slice; RR rotates equal-priority peers according to its slice rules. Blocking, interrupts, affinity, throttling and execution time still affect completion.
2. It says remaining runtime is exhausted under the relevant accounting path. It does not say the application finished its job or met an absolute deadline.
3. Admission can reject insufficient available bandwidth, and authority or security policy can reject the operation. Correct parameter relations are necessary but not sufficient.
4. The owner can inherit an effective priority associated with its top waiter so it can make progress toward releasing the lock. PI does not eliminate deadlocks, unbounded critical sections or unrelated blocking.
5. Public RT priorities use larger numbers for higher priority; relevant kernel internal ordering uses smaller numbers for higher priority. The policy conversion must be considered.

Checkpoint#

Deliver the deadline and inversion timelines and the child program's result or the equivalent source-only error analysis. Pass when you distinguish FIFO/RR from deadline budgets, explain a real exhaustion branch, and identify both an admission and a lifetime or locking limit. If uncertain, reread task_tick_rt, dl_runtime_exceeded and rt_mutex_adjust_prio, then revise the model. This is not certification.

Sources#

• v6.12 RT scheduler: selection and RR tick behavior.
• v6.12 deadline scheduler: runtime, throttling and timers.
• v6.12 RT mutex implementation: PI adjustment.
• Deadline scheduler documentation.
• RT group scheduling.