| 1 |
.. SPDX-License-Identifier: GPL-2.0 |
| 2 |
|
| 3 |
===================== |
| 4 |
Theory of operation |
| 5 |
===================== |
| 6 |
|
| 7 |
:Author: Sebastian Andrzej Siewior <[email protected]> |
| 8 |
|
| 9 |
Preface |
| 10 |
======= |
| 11 |
|
| 12 |
PREEMPT_RT transforms the Linux kernel into a real-time kernel. It achieves |
| 13 |
this by replacing locking primitives, such as spinlock_t, with a preemptible |
| 14 |
and priority-inheritance aware implementation known as rtmutex, and by enforcing |
| 15 |
the use of threaded interrupts. As a result, the kernel becomes fully |
| 16 |
preemptible, with the exception of a few critical code paths, including entry |
| 17 |
code, the scheduler, and low-level interrupt handling routines. |
| 18 |
|
| 19 |
This transformation places the majority of kernel execution contexts under the |
| 20 |
control of the scheduler and significantly increasing the number of preemption |
| 21 |
points. Consequently, it reduces the latency between a high-priority task |
| 22 |
becoming runnable and its actual execution on the CPU. |
| 23 |
|
| 24 |
Scheduling |
| 25 |
========== |
| 26 |
|
| 27 |
The core principles of Linux scheduling and the associated user-space API are |
| 28 |
documented in the man page sched(7) |
| 29 |
`sched(7) <https://man7.org/linux/man-pages/man7/sched.7.html>`_. |
| 30 |
By default, the Linux kernel uses the SCHED_OTHER scheduling policy. Under |
| 31 |
this policy, a task is preempted when the scheduler determines that it has |
| 32 |
consumed a fair share of CPU time relative to other runnable tasks. However, |
| 33 |
the policy does not guarantee immediate preemption when a new SCHED_OTHER task |
| 34 |
becomes runnable. The currently running task may continue executing. |
| 35 |
|
| 36 |
This behavior differs from that of real-time scheduling policies such as |
| 37 |
SCHED_FIFO. When a task with a real-time policy becomes runnable, the |
| 38 |
scheduler immediately selects it for execution if it has a higher priority than |
| 39 |
the currently running task. The task continues to run until it voluntarily |
| 40 |
yields the CPU, typically by blocking on an event. |
| 41 |
|
| 42 |
Sleeping spin locks |
| 43 |
=================== |
| 44 |
|
| 45 |
The various lock types and their behavior under real-time configurations are |
| 46 |
described in detail in Documentation/locking/locktypes.rst. |
| 47 |
In a non-PREEMPT_RT configuration, a spinlock_t is acquired by first disabling |
| 48 |
preemption and then actively spinning until the lock becomes available. Once |
| 49 |
the lock is released, preemption is enabled. From a real-time perspective, |
| 50 |
this approach is undesirable because disabling preemption prevents the |
| 51 |
scheduler from switching to a higher-priority task, potentially increasing |
| 52 |
latency. |
| 53 |
|
| 54 |
To address this, PREEMPT_RT replaces spinning locks with sleeping spin locks |
| 55 |
that do not disable preemption. On PREEMPT_RT, spinlock_t is implemented using |
| 56 |
rtmutex. Instead of spinning, a task attempting to acquire a contended lock |
| 57 |
disables CPU migration, donates its priority to the lock owner (priority |
| 58 |
inheritance), and voluntarily schedules out while waiting for the lock to |
| 59 |
become available. |
| 60 |
|
| 61 |
Disabling CPU migration provides the same effect as disabling preemption, while |
| 62 |
still allowing preemption and ensuring that the task continues to run on the |
| 63 |
same CPU while holding a sleeping lock. |
| 64 |
|
| 65 |
Priority inheritance |
| 66 |
==================== |
| 67 |
|
| 68 |
Lock types such as spinlock_t and mutex_t in a PREEMPT_RT enabled kernel are |
| 69 |
implemented on top of rtmutex, which provides support for priority inheritance |
| 70 |
(PI). When a task blocks on such a lock, the PI mechanism temporarily |
| 71 |
propagates the blocked task’s scheduling parameters to the lock owner. |
| 72 |
|
| 73 |
For example, if a SCHED_FIFO task A blocks on a lock currently held by a |
| 74 |
SCHED_OTHER task B, task A’s scheduling policy and priority are temporarily |
| 75 |
inherited by task B. After this inheritance, task A is put to sleep while |
| 76 |
waiting for the lock, and task B effectively becomes the highest-priority task |
| 77 |
in the system. This allows B to continue executing, make progress, and |
| 78 |
eventually release the lock. |
| 79 |
|
| 80 |
Once B releases the lock, it reverts to its original scheduling parameters, and |
| 81 |
task A can resume execution. |
| 82 |
|
| 83 |
Threaded interrupts |
| 84 |
=================== |
| 85 |
|
| 86 |
Interrupt handlers are another source of code that executes with preemption |
| 87 |
disabled and outside the control of the scheduler. To bring interrupt handling |
| 88 |
under scheduler control, PREEMPT_RT enforces threaded interrupt handlers. |
| 89 |
|
| 90 |
With forced threading, interrupt handling is split into two stages. The first |
| 91 |
stage, the primary handler, is executed in IRQ context with interrupts disabled. |
| 92 |
Its sole responsibility is to wake the associated threaded handler. The second |
| 93 |
stage, the threaded handler, is the function passed to request_irq() as the |
| 94 |
interrupt handler. It runs in process context, scheduled by the kernel. |
| 95 |
|
| 96 |
From waking the interrupt thread until threaded handling is completed, the |
| 97 |
interrupt source is masked in the interrupt controller. This ensures that the |
| 98 |
device interrupt remains pending but does not retrigger the CPU, allowing the |
| 99 |
system to exit IRQ context and handle the interrupt in a scheduled thread. |
| 100 |
|
| 101 |
By default, the threaded handler executes with the SCHED_FIFO scheduling policy |
| 102 |
and a priority of 50 (MAX_RT_PRIO / 2), which is midway between the minimum and |
| 103 |
maximum real-time priorities. |
| 104 |
|
| 105 |
If the threaded interrupt handler raises any soft interrupts during its |
| 106 |
execution, those soft interrupt routines are invoked after the threaded handler |
| 107 |
completes, within the same thread. Preemption remains enabled during the |
| 108 |
execution of the soft interrupt handler. |
| 109 |
|
| 110 |
Summary |
| 111 |
======= |
| 112 |
|
| 113 |
By using sleeping locks and forced-threaded interrupts, PREEMPT_RT |
| 114 |
significantly reduces sections of code where interrupts or preemption is |
| 115 |
disabled, allowing the scheduler to preempt the current execution context and |
| 116 |
switch to a higher-priority task. |