Unbounded Priority Inversion
Problem with using counting or binary semaphores for controlling access to critical resources is called unbounded priority inversion. Priority inversion occurs when a low-priority task owns a semaphore, and a high-priority task is forced to wait on the semaphore until the low-priority task releases it. If, prior to releasing the semaphore, the low priority task is preempted by one or more mid-priority tasks, then unbounded priority inversion has occurred because the delay of the high-priority task is no longer predictable
Sharing a critical resource between high and low priority tasks is not a desirable design practice.It is better to share a resource only among equal priority tasks or to limit resource accesses to a single resource server task.
Priority Inheritance
The most common approach is priority inheritance. Since the mutex knows its current owner, it is possible to promote the priority of the owner whenever a higher-priority task starts waiting on the mutex. The current owner temporarily assumes the priority of the highest priority taskwaiting on the mutex. This allows the owner to resume running if it was preempted by a mid-priority task,When theowner releases the mutex, it drops back to its original priority.
Problems with Priority Inheritance
1.Since promotion of low-priority tasks to higher priority levels is caused by random sequences of events, it is not possible to predict how long mid-priority tasks will be
blocked by lower-priority promoted tasks
2.Priority inheritance can cause extra task switching.
3.Priority inheritance increases the likelihood of deadlocks, because priorities change unpredictably.
Priority Ceiling Promotion
An alternative to priority inheritance is priority ceiling promotion. With it, a priority
ceiling is specified for a mutex, when it is created. The ceiling is set equal to the priority
of the highest-priority task that is expected to get the mutex. When a lower-priority task
obtains the mutex, its priority is immediately boosted to the mutex’s ceiling. Hence, a
mid-priority task cannot preempt as long as the low-priority task owns the mutex, nor can
any other task preempt that wants the mutex. Interestingly, priority ceiling is a simply an
automatic method for forcing tasks to be of the same priority while using a resource.
Problems with Priority Ceiling Promotion
1.If the high-priority task seldom uses the resource and the low-priority task frequently uses the resource, this needlessly blocks mid-priority tasks from running. In this situation, priority inheritance is more attractive
2. A mutex ceiling is static. It is possible that a user task may have had its priority increased by the programmer, or increased dynamically, to a value above the mutex’s ceiling. Then priority ceiling promotion would not be working fully and some priority inversion could occur.
Summary of Methods for Mutual Exclusion
1. Counting Semaphore. Adequate for minimal systems, but has the following limitations: protection failure due to spurious signals, task lockup, premature release, and unbounded priority inversion.
2. Binary Semaphore. Better because it ignores spurious signals, but it still has these limitations: task lockup, premature release, and unbounded priority inversion.
3. Simple Mutex. Permits nesting, but does not deal with priority inversion.
4. Priority Inheritance Mutex. Less blocking of mid-priority tasks than priority ceiling, but can lead to excessive task switches, thus increasing overhead.
5. Priority Ceiling Mutex. Less task switches than inheritance, but may block mid-priority tasks too much. Provides a good method to prevent deadlocks
