A new deadline scheduler patch
Recently, version 2 of the SCHED_DEADLINE patch was posted. The changes reflect a number of comments which were made the first time around; among other things, there is a new implementation of the group scheduling mechanism. Perhaps most significant in this patch, though, is an early attempt at addressing priority inversion problems, where a low-priority process can, by holding shared resources, prevent a higher-priority process from running. Priority inversion is a hard problem, and, in the deadline scheduling area, it remains without a definitive solution.
In classic realtime scheduling, priority inversion is usually addressed by raising the priority of a process which is holding a resource required by a higher-priority process. But there are no priorities in deadline scheduling, so a variant of this approach is required. The new patch works by "deadline inheritance" - if a process holds a resource required by another process which has a tighter deadline, the holding process has its deadline shortened until the resource is released. It is also necessary to exempt the process from bandwidth throttling (exclusion from the CPU when the stated execution time is exceeded) during this time. That, in turn, could lead to the CPU being oversubscribed - something deadline schedulers are supposed to prevent - but the size of the problem is expected to be small.
The "to do" list for this patch still has a number of entries, including
less disruptive bandwidth throttling, a port to the realtime preemption
tree, truly global deadline scheduling on multiprocessor systems (another hard
problem), and more. The code is progressing, though, and Linux can be
expected to have a proper deadline scheduler at some point in the
not-too-distant future - though no deadline can be given as the worst case
development time is still unknown.
| Index entries for this article | |
|---|---|
| Kernel | Realtime/Deadline scheduling |
| Kernel | Scheduler/Deadline scheduling |