Against priority inheritance
Victor Yodaiken · 2004
The limitations, dangers, and performance costs of the “priority inheritance” scheme for managing priority inversion are not widely appreciated. This note explains why priority inheritance is a poor choice of design for most real-time projects. 1 Inversion and inheritance There is a mismatch between the properties required from priority driven real-time systems and the property required for mutual exclusion. A priority scheduled real-time system must ensure that the highest priority runnable task can start to run in a bounded time — and the bound needs to be small. A mutual exclusion mechanism must ensure that every task requesting a certain resource wait as long as it takes for the task that owns the resource to release it, no matter what the priorities of the tasks. These two constraints can easily conflict causing priority inversion — a scheduled task that is waiting for a lower priority task. The classical nightmare case here is when a low priority task owns a resource, a high priority task is blocked waiting for the resource, and intermediate priority tasks keep preempting the low priority task so it cannot make progress towards releasing the resource. Here we have unbounded priority inversion. In 1980, Lampson and Redall concisely described the problem with reference to exclusive entry monitors. Unless care is taken, the assignment of priorities can be subverted by monitors.[2] Lampson and Redall explain that to avoid unbounded inversion, the programmer needs to analyze the program to determine the priority of the highest priority task that locks the resource. The lock operation can then be modified so that any task that holds the lock is temporarily promoted to this priority while it holds the lock. The low priority task is considered to be acting on behalf of the highest priority blocked task and the priority promotion prevents intermediate priority tasks from interfering. This method (now often called priority ceiling) works reliably, but has some drawbacks and the analysis can be difficult. Priority inheritance[3] promises a solution to unbounded priority inversion without code analysis. The basic idea of priority inheritance is to provide dynamic calculation of the ceiling priority. When a task blocks on a resource owned by a lower priority task, the lower priority task inherits the priority of the blocking task and continues. The RTLinux core does not support priority inheritance 1 for a simple reason: priority inheritance is incompatible with reliable real-time system design. Priority inheritance is neither efficient nor reliable. Implementations are either incomplete (and unreliable) or surprisingly complex and intrusive. In fact, the original