Priority Inheritance

A technique for dealing with PriorityInversion.

PriorityInversion occurs when a high-priority task blocks on a resource owned by a low-priority tasks; the low priority task may take a long time to exit its critical section. With PriorityInheritance, the low priority task has its priority elevated to that of the highest-priority task pending on the resource--it inherits the priority of the task that is waiting for it. When the critical section is exited, the low-priority task has its priority reset to its base value.

However, there is a fly in this ointment: It is often the case that a low-priority task may be blocked on multiple resources, each with a higher priority task waiting. In which case, the low-priority task should have its priority elevated to that of the highest-priority waiting task. Which is simple enough to implement. The problem occurs when the low-priority task releases one of the resources. The correct thing to do would be for the priority analysis to be re-run, and the low-priority task having the highest priority of the remaining blocked tasks.

But doing that (assuming the list of waiting tasks is not sorted) requires O(n) time, where n is the number of waiting tasks. In a RealTime OperatingSystem, this is not acceptable. Sorting the list of waiting tasks can reduce the overhead to constant time, but then the blocking operation requires greater than constant time (in order to sort the list). [Can't you fix that with a FibonacciHeap??]

A common approximation found in many RTOS's (such as VxWorks) is to not reduce the inherited priority of a low-priority task until it releases all of its resources. This can lead to some rather nasty surprises. (This "feature" of VxWorks is poorly documented, unfortunately.)

CategoryConcurrencyPatterns