^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) ========================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) Deadline Task Scheduling
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) ========================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) .. CONTENTS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) 0. WARNING
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) 1. Overview
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) 2. Scheduling algorithm
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) 2.1 Main algorithm
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) 2.2 Bandwidth reclaiming
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) 3. Scheduling Real-Time Tasks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) 3.1 Definitions
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) 3.2 Schedulability Analysis for Uniprocessor Systems
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) 3.3 Schedulability Analysis for Multiprocessor Systems
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) 3.4 Relationship with SCHED_DEADLINE Parameters
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) 4. Bandwidth management
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) 4.1 System-wide settings
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) 4.2 Task interface
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) 4.3 Default behavior
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) 4.4 Behavior of sched_yield()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) 5. Tasks CPU affinity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) 5.1 SCHED_DEADLINE and cpusets HOWTO
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) 6. Future plans
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) A. Test suite
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) B. Minimal main()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) 0. WARNING
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) ==========
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) Fiddling with these settings can result in an unpredictable or even unstable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) system behavior. As for -rt (group) scheduling, it is assumed that root users
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) know what they're doing.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) 1. Overview
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) ===========
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) basically an implementation of the Earliest Deadline First (EDF) scheduling
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) that makes it possible to isolate the behavior of tasks between each other.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) 2. Scheduling algorithm
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) =======================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) 2.1 Main algorithm
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) ------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) SCHED_DEADLINE [18] uses three parameters, named "runtime", "period", and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) "deadline", to schedule tasks. A SCHED_DEADLINE task should receive
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) "runtime" microseconds of execution time every "period" microseconds, and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) these "runtime" microseconds are available within "deadline" microseconds
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) from the beginning of the period. In order to implement this behavior,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) every time the task wakes up, the scheduler computes a "scheduling deadline"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) consistent with the guarantee (using the CBS[2,3] algorithm). Tasks are then
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) scheduled using EDF[1] on these scheduling deadlines (the task with the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) earliest scheduling deadline is selected for execution). Notice that the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) task actually receives "runtime" time units within "deadline" if a proper
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) "admission control" strategy (see Section "4. Bandwidth management") is used
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) (clearly, if the system is overloaded this guarantee cannot be respected).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) Summing up, the CBS[2,3] algorithm assigns scheduling deadlines to tasks so
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) that each task runs for at most its runtime every period, avoiding any
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) interference between different tasks (bandwidth isolation), while the EDF[1]
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) algorithm selects the task with the earliest scheduling deadline as the one
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) to be executed next. Thanks to this feature, tasks that do not strictly comply
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) with the "traditional" real-time task model (see Section 3) can effectively
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) use the new policy.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) In more details, the CBS algorithm assigns scheduling deadlines to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) tasks in the following way:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) - Each SCHED_DEADLINE task is characterized by the "runtime",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) "deadline", and "period" parameters;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) - The state of the task is described by a "scheduling deadline", and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) a "remaining runtime". These two parameters are initially set to 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) - When a SCHED_DEADLINE task wakes up (becomes ready for execution),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) the scheduler checks if::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) remaining runtime runtime
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) ---------------------------------- > ---------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) scheduling deadline - current time period
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) then, if the scheduling deadline is smaller than the current time, or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) this condition is verified, the scheduling deadline and the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) remaining runtime are re-initialized as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) scheduling deadline = current time + deadline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) remaining runtime = runtime
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) otherwise, the scheduling deadline and the remaining runtime are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) left unchanged;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) - When a SCHED_DEADLINE task executes for an amount of time t, its
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) remaining runtime is decreased as::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) remaining runtime = remaining runtime - t
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) (technically, the runtime is decreased at every tick, or when the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) task is descheduled / preempted);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) - When the remaining runtime becomes less or equal than 0, the task is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) said to be "throttled" (also known as "depleted" in real-time literature)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) and cannot be scheduled until its scheduling deadline. The "replenishment
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) time" for this task (see next item) is set to be equal to the current
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) value of the scheduling deadline;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) - When the current time is equal to the replenishment time of a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) throttled task, the scheduling deadline and the remaining runtime are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) updated as::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) scheduling deadline = scheduling deadline + period
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) remaining runtime = remaining runtime + runtime
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) The SCHED_FLAG_DL_OVERRUN flag in sched_attr's sched_flags field allows a task
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) to get informed about runtime overruns through the delivery of SIGXCPU
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) signals.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) 2.2 Bandwidth reclaiming
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) ------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) Bandwidth reclaiming for deadline tasks is based on the GRUB (Greedy
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) Reclamation of Unused Bandwidth) algorithm [15, 16, 17] and it is enabled
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) when flag SCHED_FLAG_RECLAIM is set.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) The following diagram illustrates the state names for tasks handled by GRUB::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) ------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) (d) | Active |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) ------------->| |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) | | Contending |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) | ------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) | A |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) ---------- | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) | | | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) | Inactive | |(b) | (a)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) | | | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) ---------- | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) A | V
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) | ------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) | | Active |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) --------------| Non |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) (c) | Contending |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) ------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) A task can be in one of the following states:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) - ActiveContending: if it is ready for execution (or executing);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) - ActiveNonContending: if it just blocked and has not yet surpassed the 0-lag
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) time;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) - Inactive: if it is blocked and has surpassed the 0-lag time.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) State transitions:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) (a) When a task blocks, it does not become immediately inactive since its
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) bandwidth cannot be immediately reclaimed without breaking the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) real-time guarantees. It therefore enters a transitional state called
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) ActiveNonContending. The scheduler arms the "inactive timer" to fire at
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) the 0-lag time, when the task's bandwidth can be reclaimed without
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) breaking the real-time guarantees.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) The 0-lag time for a task entering the ActiveNonContending state is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) computed as::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) (runtime * dl_period)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) deadline - ---------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) dl_runtime
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) where runtime is the remaining runtime, while dl_runtime and dl_period
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) are the reservation parameters.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) (b) If the task wakes up before the inactive timer fires, the task re-enters
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) the ActiveContending state and the "inactive timer" is canceled.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) In addition, if the task wakes up on a different runqueue, then
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) the task's utilization must be removed from the previous runqueue's active
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) utilization and must be added to the new runqueue's active utilization.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) In order to avoid races between a task waking up on a runqueue while the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) "inactive timer" is running on a different CPU, the "dl_non_contending"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) flag is used to indicate that a task is not on a runqueue but is active
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) (so, the flag is set when the task blocks and is cleared when the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) "inactive timer" fires or when the task wakes up).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) (c) When the "inactive timer" fires, the task enters the Inactive state and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) its utilization is removed from the runqueue's active utilization.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) (d) When an inactive task wakes up, it enters the ActiveContending state and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) its utilization is added to the active utilization of the runqueue where
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) it has been enqueued.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) For each runqueue, the algorithm GRUB keeps track of two different bandwidths:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) - Active bandwidth (running_bw): this is the sum of the bandwidths of all
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) tasks in active state (i.e., ActiveContending or ActiveNonContending);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) - Total bandwidth (this_bw): this is the sum of all tasks "belonging" to the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) runqueue, including the tasks in Inactive state.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) The algorithm reclaims the bandwidth of the tasks in Inactive state.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) It does so by decrementing the runtime of the executing task Ti at a pace equal
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) dq = -max{ Ui / Umax, (1 - Uinact - Uextra) } dt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) where:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) - Ui is the bandwidth of task Ti;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) - Umax is the maximum reclaimable utilization (subjected to RT throttling
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) limits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) - Uinact is the (per runqueue) inactive utilization, computed as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) (this_bq - running_bw);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) - Uextra is the (per runqueue) extra reclaimable utilization
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) (subjected to RT throttling limits).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) Let's now see a trivial example of two deadline tasks with runtime equal
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) to 4 and period equal to 8 (i.e., bandwidth equal to 0.5)::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) A Task T1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) |-------- |----
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) | | V
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) |---|---|---|---|---|---|---|---|--------->t
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) 0 1 2 3 4 5 6 7 8
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) A Task T2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) | ------------------------|
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) | | V
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) |---|---|---|---|---|---|---|---|--------->t
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) 0 1 2 3 4 5 6 7 8
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) A running_bw
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) 1 ----------------- ------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) | | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) 0.5- -----------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) | |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) |---|---|---|---|---|---|---|---|--------->t
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) 0 1 2 3 4 5 6 7 8
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) - Time t = 0:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) Both tasks are ready for execution and therefore in ActiveContending state.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) Suppose Task T1 is the first task to start execution.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) Since there are no inactive tasks, its runtime is decreased as dq = -1 dt.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) - Time t = 2:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) Suppose that task T1 blocks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) Task T1 therefore enters the ActiveNonContending state. Since its remaining
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) runtime is equal to 2, its 0-lag time is equal to t = 4.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) Task T2 start execution, with runtime still decreased as dq = -1 dt since
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) there are no inactive tasks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) - Time t = 4:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) This is the 0-lag time for Task T1. Since it didn't woken up in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) meantime, it enters the Inactive state. Its bandwidth is removed from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) running_bw.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) Task T2 continues its execution. However, its runtime is now decreased as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) dq = - 0.5 dt because Uinact = 0.5.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) Task T2 therefore reclaims the bandwidth unused by Task T1.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) - Time t = 8:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) Task T1 wakes up. It enters the ActiveContending state again, and the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) running_bw is incremented.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) 2.3 Energy-aware scheduling
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) ---------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) When cpufreq's schedutil governor is selected, SCHED_DEADLINE implements the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) GRUB-PA [19] algorithm, reducing the CPU operating frequency to the minimum
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) value that still allows to meet the deadlines. This behavior is currently
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) implemented only for ARM architectures.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) A particular care must be taken in case the time needed for changing frequency
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) is of the same order of magnitude of the reservation period. In such cases,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) setting a fixed CPU frequency results in a lower amount of deadline misses.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) 3. Scheduling Real-Time Tasks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) =============================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) .. BIG FAT WARNING ******************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) .. warning::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) This section contains a (not-thorough) summary on classical deadline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) scheduling theory, and how it applies to SCHED_DEADLINE.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) The reader can "safely" skip to Section 4 if only interested in seeing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) how the scheduling policy can be used. Anyway, we strongly recommend
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) to come back here and continue reading (once the urge for testing is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) satisfied :P) to be sure of fully understanding all technical details.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) .. ************************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) There are no limitations on what kind of task can exploit this new
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) scheduling discipline, even if it must be said that it is particularly
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) suited for periodic or sporadic real-time tasks that need guarantees on their
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) timing behavior, e.g., multimedia, streaming, control applications, etc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) 3.1 Definitions
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) ------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) A typical real-time task is composed of a repetition of computation phases
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) (task instances, or jobs) which are activated on a periodic or sporadic
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) fashion.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) Each job J_j (where J_j is the j^th job of the task) is characterized by an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) arrival time r_j (the time when the job starts), an amount of computation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) time c_j needed to finish the job, and a job absolute deadline d_j, which
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) is the time within which the job should be finished. The maximum execution
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) time max{c_j} is called "Worst Case Execution Time" (WCET) for the task.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) A real-time task can be periodic with period P if r_{j+1} = r_j + P, or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) d_j = r_j + D, where D is the task's relative deadline.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) Summing up, a real-time task can be described as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) Task = (WCET, D, P)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) The utilization of a real-time task is defined as the ratio between its
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) WCET and its period (or minimum inter-arrival time), and represents
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) the fraction of CPU time needed to execute the task.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) If the total utilization U=sum(WCET_i/P_i) is larger than M (with M equal
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) to the number of CPUs), then the scheduler is unable to respect all the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) deadlines.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) Note that total utilization is defined as the sum of the utilizations
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) WCET_i/P_i over all the real-time tasks in the system. When considering
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) multiple real-time tasks, the parameters of the i-th task are indicated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) with the "_i" suffix.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) Moreover, if the total utilization is larger than M, then we risk starving
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) non- real-time tasks by real-time tasks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) If, instead, the total utilization is smaller than M, then non real-time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) tasks will not be starved and the system might be able to respect all the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) deadlines.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) As a matter of fact, in this case it is possible to provide an upper bound
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) for tardiness (defined as the maximum between 0 and the difference
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) between the finishing time of a job and its absolute deadline).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) More precisely, it can be proven that using a global EDF scheduler the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) maximum tardiness of each task is smaller or equal than
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) ((M − 1) · WCET_max − WCET_min)/(M − (M − 2) · U_max) + WCET_max
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) where WCET_max = max{WCET_i} is the maximum WCET, WCET_min=min{WCET_i}
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) is the minimum WCET, and U_max = max{WCET_i/P_i} is the maximum
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) utilization[12].
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) 3.2 Schedulability Analysis for Uniprocessor Systems
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) ----------------------------------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) If M=1 (uniprocessor system), or in case of partitioned scheduling (each
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) real-time task is statically assigned to one and only one CPU), it is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) possible to formally check if all the deadlines are respected.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) If D_i = P_i for all tasks, then EDF is able to respect all the deadlines
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) of all the tasks executing on a CPU if and only if the total utilization
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) of the tasks running on such a CPU is smaller or equal than 1.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) If D_i != P_i for some task, then it is possible to define the density of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) a task as WCET_i/min{D_i,P_i}, and EDF is able to respect all the deadlines
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) of all the tasks running on a CPU if the sum of the densities of the tasks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) running on such a CPU is smaller or equal than 1:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) sum(WCET_i / min{D_i, P_i}) <= 1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) It is important to notice that this condition is only sufficient, and not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) necessary: there are task sets that are schedulable, but do not respect the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) condition. For example, consider the task set {Task_1,Task_2} composed by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) Task_1=(50ms,50ms,100ms) and Task_2=(10ms,100ms,100ms).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) EDF is clearly able to schedule the two tasks without missing any deadline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) (Task_1 is scheduled as soon as it is released, and finishes just in time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) to respect its deadline; Task_2 is scheduled immediately after Task_1, hence
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) its response time cannot be larger than 50ms + 10ms = 60ms) even if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) 50 / min{50,100} + 10 / min{100, 100} = 50 / 50 + 10 / 100 = 1.1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) Of course it is possible to test the exact schedulability of tasks with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) D_i != P_i (checking a condition that is both sufficient and necessary),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) but this cannot be done by comparing the total utilization or density with
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) a constant. Instead, the so called "processor demand" approach can be used,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) computing the total amount of CPU time h(t) needed by all the tasks to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) respect all of their deadlines in a time interval of size t, and comparing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) such a time with the interval size t. If h(t) is smaller than t (that is,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) the amount of time needed by the tasks in a time interval of size t is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) smaller than the size of the interval) for all the possible values of t, then
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) EDF is able to schedule the tasks respecting all of their deadlines. Since
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) performing this check for all possible values of t is impossible, it has been
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) proven[4,5,6] that it is sufficient to perform the test for values of t
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) between 0 and a maximum value L. The cited papers contain all of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) mathematical details and explain how to compute h(t) and L.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) In any case, this kind of analysis is too complex as well as too
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) time-consuming to be performed on-line. Hence, as explained in Section
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) 4 Linux uses an admission test based on the tasks' utilizations.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) 3.3 Schedulability Analysis for Multiprocessor Systems
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) ------------------------------------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) On multiprocessor systems with global EDF scheduling (non partitioned
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) systems), a sufficient test for schedulability can not be based on the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) utilizations or densities: it can be shown that even if D_i = P_i task
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) sets with utilizations slightly larger than 1 can miss deadlines regardless
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) of the number of CPUs.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) Consider a set {Task_1,...Task_{M+1}} of M+1 tasks on a system with M
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) CPUs, with the first task Task_1=(P,P,P) having period, relative deadline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) and WCET equal to P. The remaining M tasks Task_i=(e,P-1,P-1) have an
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) arbitrarily small worst case execution time (indicated as "e" here) and a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) period smaller than the one of the first task. Hence, if all the tasks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) activate at the same time t, global EDF schedules these M tasks first
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) (because their absolute deadlines are equal to t + P - 1, hence they are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) smaller than the absolute deadline of Task_1, which is t + P). As a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) result, Task_1 can be scheduled only at time t + e, and will finish at
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) time t + e + P, after its absolute deadline. The total utilization of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) task set is U = M · e / (P - 1) + P / P = M · e / (P - 1) + 1, and for small
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) values of e this can become very close to 1. This is known as "Dhall's
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) effect"[7]. Note: the example in the original paper by Dhall has been
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) slightly simplified here (for example, Dhall more correctly computed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) lim_{e->0}U).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) More complex schedulability tests for global EDF have been developed in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) real-time literature[8,9], but they are not based on a simple comparison
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) between total utilization (or density) and a fixed constant. If all tasks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) have D_i = P_i, a sufficient schedulability condition can be expressed in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) a simple way:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) sum(WCET_i / P_i) <= M - (M - 1) · U_max
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) where U_max = max{WCET_i / P_i}[10]. Notice that for U_max = 1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) M - (M - 1) · U_max becomes M - M + 1 = 1 and this schedulability condition
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) just confirms the Dhall's effect. A more complete survey of the literature
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) about schedulability tests for multi-processor real-time scheduling can be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) found in [11].
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) As seen, enforcing that the total utilization is smaller than M does not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) guarantee that global EDF schedules the tasks without missing any deadline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) (in other words, global EDF is not an optimal scheduling algorithm). However,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) a total utilization smaller than M is enough to guarantee that non real-time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) tasks are not starved and that the tardiness of real-time tasks has an upper
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) bound[12] (as previously noted). Different bounds on the maximum tardiness
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) experienced by real-time tasks have been developed in various papers[13,14],
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) but the theoretical result that is important for SCHED_DEADLINE is that if
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) the total utilization is smaller or equal than M then the response times of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) the tasks are limited.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) 3.4 Relationship with SCHED_DEADLINE Parameters
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) -----------------------------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) Finally, it is important to understand the relationship between the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) SCHED_DEADLINE scheduling parameters described in Section 2 (runtime,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) deadline and period) and the real-time task parameters (WCET, D, P)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) described in this section. Note that the tasks' temporal constraints are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) represented by its absolute deadlines d_j = r_j + D described above, while
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) SCHED_DEADLINE schedules the tasks according to scheduling deadlines (see
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) Section 2).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) If an admission test is used to guarantee that the scheduling deadlines
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) are respected, then SCHED_DEADLINE can be used to schedule real-time tasks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) guaranteeing that all the jobs' deadlines of a task are respected.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) In order to do this, a task must be scheduled by setting:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) - runtime >= WCET
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) - deadline = D
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) - period <= P
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) IOW, if runtime >= WCET and if period is <= P, then the scheduling deadlines
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) and the absolute deadlines (d_j) coincide, so a proper admission control
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) allows to respect the jobs' absolute deadlines for this task (this is what is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) called "hard schedulability property" and is an extension of Lemma 1 of [2]).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) Notice that if runtime > deadline the admission control will surely reject
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) this task, as it is not possible to respect its temporal constraints.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) References:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) 1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram-
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) ming in a hard-real-time environment. Journal of the Association for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) Computing Machinery, 20(1), 1973.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) 2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) 3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) Technical Report. http://disi.unitn.it/~abeni/tr-98-01.pdf
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) 4 - J. Y. Leung and M.L. Merril. A Note on Preemptive Scheduling of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) Periodic, Real-Time Tasks. Information Processing Letters, vol. 11,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) no. 3, pp. 115-118, 1980.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) 5 - S. K. Baruah, A. K. Mok and L. E. Rosier. Preemptively Scheduling
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) Hard-Real-Time Sporadic Tasks on One Processor. Proceedings of the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) 11th IEEE Real-time Systems Symposium, 1990.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) 6 - S. K. Baruah, L. E. Rosier and R. R. Howell. Algorithms and Complexity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) Concerning the Preemptive Scheduling of Periodic Real-Time tasks on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) One Processor. Real-Time Systems Journal, vol. 4, no. 2, pp 301-324,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) 1990.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) 7 - S. J. Dhall and C. L. Liu. On a real-time scheduling problem. Operations
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) research, vol. 26, no. 1, pp 127-140, 1978.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) 8 - T. Baker. Multiprocessor EDF and Deadline Monotonic Schedulability
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) Analysis. Proceedings of the 24th IEEE Real-Time Systems Symposium, 2003.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) 9 - T. Baker. An Analysis of EDF Schedulability on a Multiprocessor.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 8,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) pp 760-768, 2005.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) 10 - J. Goossens, S. Funk and S. Baruah, Priority-Driven Scheduling of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) Periodic Task Systems on Multiprocessors. Real-Time Systems Journal,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) vol. 25, no. 2–3, pp. 187–205, 2003.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) 11 - R. Davis and A. Burns. A Survey of Hard Real-Time Scheduling for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) Multiprocessor Systems. ACM Computing Surveys, vol. 43, no. 4, 2011.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) http://www-users.cs.york.ac.uk/~robdavis/papers/MPSurveyv5.0.pdf
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) 12 - U. C. Devi and J. H. Anderson. Tardiness Bounds under Global EDF
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) Scheduling on a Multiprocessor. Real-Time Systems Journal, vol. 32,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) no. 2, pp 133-189, 2008.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) 13 - P. Valente and G. Lipari. An Upper Bound to the Lateness of Soft
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) Real-Time Tasks Scheduled by EDF on Multiprocessors. Proceedings of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) the 26th IEEE Real-Time Systems Symposium, 2005.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) 14 - J. Erickson, U. Devi and S. Baruah. Improved tardiness bounds for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) Global EDF. Proceedings of the 22nd Euromicro Conference on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) Real-Time Systems, 2010.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) 15 - G. Lipari, S. Baruah, Greedy reclamation of unused bandwidth in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) constant-bandwidth servers, 12th IEEE Euromicro Conference on Real-Time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) Systems, 2000.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) 16 - L. Abeni, J. Lelli, C. Scordino, L. Palopoli, Greedy CPU reclaiming for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) SCHED DEADLINE. In Proceedings of the Real-Time Linux Workshop (RTLWS),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) Dusseldorf, Germany, 2014.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) 17 - L. Abeni, G. Lipari, A. Parri, Y. Sun, Multicore CPU reclaiming: parallel
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) or sequential?. In Proceedings of the 31st Annual ACM Symposium on Applied
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) Computing, 2016.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) 18 - J. Lelli, C. Scordino, L. Abeni, D. Faggioli, Deadline scheduling in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) Linux kernel, Software: Practice and Experience, 46(6): 821-839, June
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) 2016.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) 19 - C. Scordino, L. Abeni, J. Lelli, Energy-Aware Real-Time Scheduling in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) the Linux Kernel, 33rd ACM/SIGAPP Symposium On Applied Computing (SAC
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) 2018), Pau, France, April 2018.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) 4. Bandwidth management
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) =======================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) As previously mentioned, in order for -deadline scheduling to be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) effective and useful (that is, to be able to provide "runtime" time units
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) within "deadline"), it is important to have some method to keep the allocation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) of the available fractions of CPU time to the various tasks under control.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) This is usually called "admission control" and if it is not performed, then
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) no guarantee can be given on the actual scheduling of the -deadline tasks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) As already stated in Section 3, a necessary condition to be respected to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) correctly schedule a set of real-time tasks is that the total utilization
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) is smaller than M. When talking about -deadline tasks, this requires that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) the sum of the ratio between runtime and period for all tasks is smaller
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) than M. Notice that the ratio runtime/period is equivalent to the utilization
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) of a "traditional" real-time task, and is also often referred to as
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) "bandwidth".
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) The interface used to control the CPU bandwidth that can be allocated
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) to -deadline tasks is similar to the one already used for -rt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) tasks with real-time group scheduling (a.k.a. RT-throttling - see
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) Documentation/scheduler/sched-rt-group.rst), and is based on readable/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) writable control files located in procfs (for system wide settings).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) Notice that per-group settings (controlled through cgroupfs) are still not
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) defined for -deadline tasks, because more discussion is needed in order to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) figure out how we want to manage SCHED_DEADLINE bandwidth at the task group
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) level.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) A main difference between deadline bandwidth management and RT-throttling
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) is that -deadline tasks have bandwidth on their own (while -rt ones don't!),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) and thus we don't need a higher level throttling mechanism to enforce the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) desired bandwidth. In other words, this means that interface parameters are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) only used at admission control time (i.e., when the user calls
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) sched_setattr()). Scheduling is then performed considering actual tasks'
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) parameters, so that CPU bandwidth is allocated to SCHED_DEADLINE tasks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) respecting their needs in terms of granularity. Therefore, using this simple
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) interface we can put a cap on total utilization of -deadline tasks (i.e.,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) \Sum (runtime_i / period_i) < global_dl_utilization_cap).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) 4.1 System wide settings
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) ------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) The system wide settings are configured under the /proc virtual file system.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) For now the -rt knobs are used for -deadline admission control and the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) -deadline runtime is accounted against the -rt runtime. We realize that this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) isn't entirely desirable; however, it is better to have a small interface for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) now, and be able to change it easily later. The ideal situation (see 5.) is to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) run -rt tasks from a -deadline server; in which case the -rt bandwidth is a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) direct subset of dl_bw.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) This means that, for a root_domain comprising M CPUs, -deadline tasks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) can be created while the sum of their bandwidths stays below:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) M * (sched_rt_runtime_us / sched_rt_period_us)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) It is also possible to disable this bandwidth management logic, and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604) be thus free of oversubscribing the system up to any arbitrary level.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605) This is done by writing -1 in /proc/sys/kernel/sched_rt_runtime_us.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) 4.2 Task interface
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) ------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) Specifying a periodic/sporadic task that executes for a given amount of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) runtime at each instance, and that is scheduled according to the urgency of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) its own timing constraints needs, in general, a way of declaring:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) - a (maximum/typical) instance execution time,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) - a minimum interval between consecutive instances,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) - a time constraint by which each instance must be completed.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) Therefore:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) * a new struct sched_attr, containing all the necessary fields is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) provided;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) * the new scheduling related syscalls that manipulate it, i.e.,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) sched_setattr() and sched_getattr() are implemented.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) For debugging purposes, the leftover runtime and absolute deadline of a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) SCHED_DEADLINE task can be retrieved through /proc/<pid>/sched (entries
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) dl.runtime and dl.deadline, both values in ns). A programmatic way to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) retrieve these values from production code is under discussion.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) 4.3 Default behavior
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) ---------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) The default value for SCHED_DEADLINE bandwidth is to have rt_runtime equal to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) 950000. With rt_period equal to 1000000, by default, it means that -deadline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) tasks can use at most 95%, multiplied by the number of CPUs that compose the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) root_domain, for each root_domain.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) This means that non -deadline tasks will receive at least 5% of the CPU time,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) and that -deadline tasks will receive their runtime with a guaranteed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) worst-case delay respect to the "deadline" parameter. If "deadline" = "period"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) and the cpuset mechanism is used to implement partitioned scheduling (see
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) Section 5), then this simple setting of the bandwidth management is able to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) deterministically guarantee that -deadline tasks will receive their runtime
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) in a period.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) Finally, notice that in order not to jeopardize the admission control a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) -deadline task cannot fork.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) 4.4 Behavior of sched_yield()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) -----------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) When a SCHED_DEADLINE task calls sched_yield(), it gives up its
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) remaining runtime and is immediately throttled, until the next
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) period, when its runtime will be replenished (a special flag
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) dl_yielded is set and used to handle correctly throttling and runtime
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) replenishment after a call to sched_yield()).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) This behavior of sched_yield() allows the task to wake-up exactly at
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) the beginning of the next period. Also, this may be useful in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) future with bandwidth reclaiming mechanisms, where sched_yield() will
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) make the leftoever runtime available for reclamation by other
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) SCHED_DEADLINE tasks.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) 5. Tasks CPU affinity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) =====================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) -deadline tasks cannot have an affinity mask smaller that the entire
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) root_domain they are created on. However, affinities can be specified
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) through the cpuset facility (Documentation/admin-guide/cgroup-v1/cpusets.rst).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) 5.1 SCHED_DEADLINE and cpusets HOWTO
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675) ------------------------------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677) An example of a simple configuration (pin a -deadline task to CPU0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) follows (rt-app is used to create a -deadline task)::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) mkdir /dev/cpuset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) mount -t cgroup -o cpuset cpuset /dev/cpuset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) cd /dev/cpuset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) mkdir cpu0
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) echo 0 > cpu0/cpuset.cpus
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) echo 0 > cpu0/cpuset.mems
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) echo 1 > cpuset.cpu_exclusive
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) echo 0 > cpuset.sched_load_balance
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) echo 1 > cpu0/cpuset.cpu_exclusive
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) echo 1 > cpu0/cpuset.mem_exclusive
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690) echo $$ > cpu0/tasks
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) rt-app -t 100000:10000:d:0 -D5 # it is now actually superfluous to specify
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) # task affinity
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694) 6. Future plans
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695) ===============
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) Still missing:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699) - programmatic way to retrieve current runtime and absolute deadline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) - refinements to deadline inheritance, especially regarding the possibility
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) of retaining bandwidth isolation among non-interacting tasks. This is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) being studied from both theoretical and practical points of view, and
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) hopefully we should be able to produce some demonstrative code soon;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) - (c)group based bandwidth management, and maybe scheduling;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) - access control for non-root users (and related security concerns to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706) address), which is the best way to allow unprivileged use of the mechanisms
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) and how to prevent non-root users "cheat" the system?
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) As already discussed, we are planning also to merge this work with the EDF
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) the preliminary phases of the merge and we really seek feedback that would
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712) help us decide on the direction it should take.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) Appendix A. Test suite
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) ======================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) The SCHED_DEADLINE policy can be easily tested using two applications that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718) are part of a wider Linux Scheduler validation suite. The suite is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) available as a GitHub repository: https://github.com/scheduler-tools.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) The first testing application is called rt-app and can be used to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) start multiple threads with specific parameters. rt-app supports
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723) SCHED_{OTHER,FIFO,RR,DEADLINE} scheduling policies and their related
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) parameters (e.g., niceness, priority, runtime/deadline/period). rt-app
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) is a valuable tool, as it can be used to synthetically recreate certain
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) workloads (maybe mimicking real use-cases) and evaluate how the scheduler
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) behaves under such workloads. In this way, results are easily reproducible.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) rt-app is available at: https://github.com/scheduler-tools/rt-app.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) Thread parameters can be specified from the command line, with something like
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) this::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) # rt-app -t 100000:10000:d -t 150000:20000:f:10 -D5
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) The above creates 2 threads. The first one, scheduled by SCHED_DEADLINE,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) executes for 10ms every 100ms. The second one, scheduled at SCHED_FIFO
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) priority 10, executes for 20ms every 150ms. The test will run for a total
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) of 5 seconds.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) More interestingly, configurations can be described with a json file that
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741) can be passed as input to rt-app with something like this::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) # rt-app my_config.json
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) The parameters that can be specified with the second method are a superset
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) of the command line options. Please refer to rt-app documentation for more
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) details (`<rt-app-sources>/doc/*.json`).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) The second testing application is a modification of schedtool, called
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) schedtool-dl, which can be used to setup SCHED_DEADLINE parameters for a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) certain pid/application. schedtool-dl is available at:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) https://github.com/scheduler-tools/schedtool-dl.git.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754) The usage is straightforward::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) # schedtool -E -t 10000000:100000000 -e ./my_cpuhog_app
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) With this, my_cpuhog_app is put to run inside a SCHED_DEADLINE reservation
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) of 10ms every 100ms (note that parameters are expressed in microseconds).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760) You can also use schedtool to create a reservation for an already running
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) application, given that you know its pid::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763) # schedtool -E -t 10000000:100000000 my_app_pid
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) Appendix B. Minimal main()
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766) ==========================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) We provide in what follows a simple (ugly) self-contained code snippet
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769) showing how SCHED_DEADLINE reservations can be created by a real-time
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770) application developer::
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) #define _GNU_SOURCE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773) #include <unistd.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) #include <stdio.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) #include <stdlib.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776) #include <string.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) #include <time.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) #include <linux/unistd.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) #include <linux/types.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781) #include <sys/syscall.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782) #include <pthread.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784) #define gettid() syscall(__NR_gettid)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786) #define SCHED_DEADLINE 6
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788) /* XXX use the proper syscall numbers */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789) #ifdef __x86_64__
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) #define __NR_sched_setattr 314
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) #define __NR_sched_getattr 315
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794) #ifdef __i386__
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) #define __NR_sched_setattr 351
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 796) #define __NR_sched_getattr 352
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 797) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 798)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 799) #ifdef __arm__
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 800) #define __NR_sched_setattr 380
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 801) #define __NR_sched_getattr 381
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 802) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 803)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 804) static volatile int done;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 805)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 806) struct sched_attr {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 807) __u32 size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 808)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 809) __u32 sched_policy;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 810) __u64 sched_flags;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 811)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 812) /* SCHED_NORMAL, SCHED_BATCH */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 813) __s32 sched_nice;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 814)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 815) /* SCHED_FIFO, SCHED_RR */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 816) __u32 sched_priority;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 817)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 818) /* SCHED_DEADLINE (nsec) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 819) __u64 sched_runtime;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 820) __u64 sched_deadline;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 821) __u64 sched_period;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 822) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 823)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 824) int sched_setattr(pid_t pid,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 825) const struct sched_attr *attr,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 826) unsigned int flags)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 827) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 828) return syscall(__NR_sched_setattr, pid, attr, flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 829) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 830)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 831) int sched_getattr(pid_t pid,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 832) struct sched_attr *attr,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 833) unsigned int size,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 834) unsigned int flags)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 835) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 836) return syscall(__NR_sched_getattr, pid, attr, size, flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 837) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 838)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 839) void *run_deadline(void *data)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 840) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 841) struct sched_attr attr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 842) int x = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 843) int ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 844) unsigned int flags = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 845)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 846) printf("deadline thread started [%ld]\n", gettid());
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 847)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 848) attr.size = sizeof(attr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 849) attr.sched_flags = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 850) attr.sched_nice = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 851) attr.sched_priority = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 852)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 853) /* This creates a 10ms/30ms reservation */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 854) attr.sched_policy = SCHED_DEADLINE;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 855) attr.sched_runtime = 10 * 1000 * 1000;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 856) attr.sched_period = attr.sched_deadline = 30 * 1000 * 1000;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 857)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 858) ret = sched_setattr(0, &attr, flags);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 859) if (ret < 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 860) done = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 861) perror("sched_setattr");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 862) exit(-1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 863) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 864)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 865) while (!done) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 866) x++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 867) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 868)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 869) printf("deadline thread dies [%ld]\n", gettid());
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 870) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 871) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 872)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 873) int main (int argc, char **argv)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 874) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 875) pthread_t thread;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 876)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 877) printf("main thread [%ld]\n", gettid());
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 878)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 879) pthread_create(&thread, NULL, run_deadline, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 880)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 881) sleep(10);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 882)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 883) done = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 884) pthread_join(thread, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 885)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 886) printf("main dies [%ld]\n", gettid());
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 887) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 888) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags