Alternative to Priority Inheritance: Operating System

Question

I just came across priority inheritance which is a solution to priority inversion problem in Operating Systems. Can anyone suggest any other solution apart from this?

Thanks

Answer 1

Alternatives

1. Priority ceiling promotion
2. A combination of priority inheritance and priority ceiling can be used.

How is prio ceiling promotion different from prio inheritance?

Priority Inheritance: When a higher priority task starts waiting on a mutex captured by a lower priority task, the priority of the lower priority task is temporarily boosted to that of the higher priority task. This enables the lower priority task to continue to run even when preempted by a medium priority task.

Disadvantages:

a. The wait period of medium-prio tasks for a promoted low prio task cannot be easily determined if the prio inheritance of low priority is based on several random sequence of events.

b. If the promoted task waits for another mutex held by another task , then this task's priority must also be promoted. This is called priority propagation. System behaviour becomes difficult to determine.

c. Again if an even higher priority task now starts waiting for this promoted low prio task, the promoted low prio task must be promoted again and also propagated again making the system behaviour even more tougher to determine.    

Priority Ceiling Promotion: A priority ceiling is specified for every mutex when created. This is equal to the priority of the highest priority task that can take the mutex. When a low prio task takes this mutex it's prio is immediately boosted to the ceiling. Hence a mid prio task cannot preempt this task as long as it owns the mutex.

Disadvantage:

a. If a low prio task frequently uses the mutex and a high prio task seldomly, then unnecessarily a mid-prio task will be disallowed from preempting the low- prio task.

Answer 2

I know this is an old question, but I've just been researching the topic myself and need a place to put my conclusions. Here's the idea behind random boosting, which you asked about in a comment:

When a high-priority thread blocks on a resource, pick a random ready thread of lower priority. Boost that thread's priority to the priority of the blocked thread for a certain amount of time assumed to be enough to release the resource. Then drop the priority back and pick another thread. Repeat this until the resource is released.

I don't know about any formal analyses of the algorithm, but it should be obvious that priority inheritance and priority ceiling, covered by @ShreyasS, are more efficient at reducing priority inversion time. How much more efficient they are, I have no idea. Surely it depends on the application so testing would be needed anyway.

However, a big drawback of both priority inheritance and ceiling is that they only work on resources with the concept of an owner (e.g. mutexes). In other words, the scheduler knows which thread can release the resource if given the opportunity. Priority boosting, on the other hand, is more general and solves priority inversion even on non-owned resources (e.g. semaphores).

Conceptually, all three algorithms can be combined if you're willing to invest the time. Here are some quick thoughts. Owned resources can use inheritance in general and ceiling only when specifically configured for it. Non-owned resources can use priority boosting. But even in this case the set of boostable threads can be limited, for instance to only those in processes that own a handle to the resource. Boost duration can also be adaptive if times between resource claims and releases are tracked.