Debian Codegraph @

Documentation/core-api/real-time/theory.rst

raw
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.