Priority Inversion
● In the Operating System, one of the important concepts is
Task Scheduling.
● There are several Scheduling methods such as First Come
First Serve, Round Robin, Priority-based scheduling, etc
● Priority Inversion comes under Priority-based Scheduling.
● Each scheduling method has its pros and cons.
● In Priority-based scheduling, different tasks are given
different priority so that higher priority tasks can intervene in
lower priority tasks if possible.
So, in priority-based scheduling,
● if a lower priority task (L) is running and if a higher priority
task (H) also needs to run, the lower priority task (L) would
be preempted by higher priority task (H).
● Now, suppose both lower and higher priority tasks need to
share a common resource (say access to the same file or
device) to achieve their respective work.
● In this case, since resource sharing and task
synchronization is needed, several methods/techniques can
be used for handling such scenarios.
Example of a priority inversion
Consider two tasks H and L, of high and low priority respectively,either
of which can acquire exclusive use of a shared resource R.
● If H attempts to acquire R after L has acquired it, then H
becomes blocked until L relinquishes the resource.
● Sharing an exclusive-use resource (R in this case) in a
well-designed system typically involves L relinquishing R
promptly so that H (a higher priority task) does not stay
blocked for excessive periods of time.
● Despite good design, however, it is possible that a third task
M of medium priority (p(L) < p(M) < p(H), where p(x)
represents the priority for task (x)) becomes runnable during
L's use of R.
● At this point, M being higher in priority than L, preempts L
(since M does not depend on R), causing L to not be able to
relinquish R promptly, in turn causing H—the highest priority
process—to be unable to run (that is, H suffers unexpected
blockage indirectly caused by lower priority tasks like M).
Bounded priority inversion
● Bounded priority inversion , shown in Figure , occurs when
low-priority Task L acquires a lock on a shared resource, but
before releasing the resource is preempted by high-priority
Task H.
● Task H attempts to acquire the resource but is forced to wait
for Task L to finish its critical section. Task L continues
running until it releases the resource, at which point Task H
acquires the resource and resumes executing.
● The worst-case wait time for Task H is equal to the length of
the critical section of Task L. Bounded priority inversion
won't generally hurt an application provided the critical
section of Task L executes in a timely manner.
Unbounded priority inversion
● Unbounded priority inversion occurs when an intervening
task extends a bounded priority inversion, possibly forever.
● In the previous example, suppose medium-priority Task M
preempts Task L during the execution of Task L's critical
section.
● Task M runs until it relinquishes control of the processor.
Only when Task M turns over control can Task L finish
executing its critical section and release the shared
resource. This extension of the critical region leads to
unbounded priority inversion.
● When Task L releases the resource, Task H can finally
acquire the resource and resume execution. The worst-case
wait time for Task H is now equal to the sum of the
worst-case execution times of Task M and the critical section
of Task L..
● Unbounded priority inversion can have much more severe
consequences than a bounded priority inversion.
● If Task M runs indefinitely, neither Task L nor Task H will get
an opportunity to resume execution
Chain of nested resource locks
● Priority inversion can have an even more severe effect on an
application when there are nested resource locks , as shown
in Figure .
● Suppose Task 1 is waiting for Resource A. Resource A is
owned by lower-priority Task 2, which is waiting for
Resource B. Resource B is owned by still lower-priority Task
3, which is waiting for Resource C, which is being used by
an even lower priority Task 4. Task 1 is blocked, forced to
wait for tasks 4, 3, and 2 to finish their critical regions before
it can begin execution.
● Such a chain of nested locks is difficult to resolve quickly
and efficiently. The risk of an unbounded priority inversion is
also high if many tasks intervene between tasks 1 and 4.
Deadlock
● Deadlock , shown in Figure , is a special case of nested
resource locks, in which a circular chain of tasks waiting for
resources prevents all the tasks in the chain from executing.
● Deadlocked tasks can have potentially fatal consequences
for the application. Suppose Task A is waiting for a resource
held by Task B, while Task B is waiting for a resource held
by Task C, which is waiting for a resource held by Task A.
None of the three tasks is able to acquire the resource it
needs to resume execution, so the application is
deadlocked.
Priority ceiling protocol
● One way to solve priority inversion is to use the priority
ceiling protocol , which gives each shared resource a
predefined priority ceiling.
● When a task acquires a shared resource, the task is hoisted
(has its priority temporarily raised) to the priority ceiling of
that resource. The priority ceiling must be higher than the
highest priority of all tasks that can access the resource,
thereby ensuring that a task owning a shared resource won't
be preempted by any other task attempting to access the
same resource.
● When the hoisted task releases the resource, the task is
returned to its original priority level. Any operating system
that allows task priorities to change dynamically can be used
to implement the priority ceiling protocol.
● A static analysis of the application is required to determine
the priority ceiling for each shared resource, a process that
is often difficult and time consuming.
● To perform a static analysis, every task that accesses each
shared resource must be known in advance. This might be
difficult, or even impossible, to determine for a complex
application.
● The priority ceiling protocol provides a good worst-case wait
time for a high-priority task waiting for a shared resource.
The worst-case wait time is limited to the longest critical
section of any lower-priority task that accesses the shared
resource.
● The priority ceiling protocol prevents deadlock by stopping
chains of nested locks from developing.
● On the downside, the priority ceiling protocol has poor
average-case response time because of the significant
overhead associated with implementing the protocol.
● Every time a shared resource is acquired, the acquiring task
must be hoisted to the resource's priority ceiling. Conversely,
every time a shared resource is released, the hoisted task's
priority must be lowered to its original level. All this extra
code takes time.
● By hoisting the acquiring task to the priority ceiling of the
resource, the priority ceiling protocol prevents locks from
being contented. Because the hoisted task has a priority
higher than that of any other task that can request the
resource, no task can contend the lock.
● A disadvantage of the priority ceiling protocol is that the
priority of a task changes every time it acquires or releases a
shared resource. These priority changes occur even if no
other task would compete for the resource at that time.
● Medium-priority tasks are often unnecessarily prevented
from running by the priority ceiling protocol. Suppose a
low-priority task acquires a resource that's shared with a
high-priority task.
● The low-priority task is hoisted to the resource's priority
ceiling, above that of the high-priority task. Any tasks with a
priority below the resource's priority ceiling that are ready to
execute will be prevented from doing so, even if they don't
use the shared resource.
Priority inheritance protocol
● An alternative to the priority ceiling protocol is the priority
inheritance protocol , a variation that uses dynamic priority
adjustments.
● When a low-priority task acquires a shared resource, the
task continues running at its original priority level. If a
high-priority task requests ownership of the shared resource,
the low-priority task is hoisted above the requesting task.
● The low-priority task can then continue executing its critical
section until it releases the resource. Once the resource is
released, the task is dropped back to its original low-priority
level, permitting the high-priority task to use the resource it
has just acquired.
● Because the majority of locks in real-time applications aren't
contended, the priority inheritance protocol has good
average-case performance. When a lock isn't contended,
priorities don't change; there is no additional overhead.
● However, the worst-case performance for the priority
inheritance protocol is worse than the worst-case priority
ceiling protocol, since nested resource locks increase the
wait time.
● The maximum duration of the priority inversion is the sum of
the execution times of all of the nested resource locks.
Furthermore, nested resource locks can lead to deadlock
when you use the priority inheritance protocol. That makes it
important to design the application so that deadlock can't
occur
● Nested resource locks should obviously be avoided if
possible. An inadequate or incomplete understanding of the
interactions between tasks can lead to nested resource
locks. A well-thought-out design is the best tool a
programmer can use to prevent these.
● You can avoid deadlock by allowing each task to own only
one shared resource at a time. When this condition is met,
the worst-case wait time matches the priority ceiling
protocol's worst-case wait.
● In order to prevent misuse, some operating systems that
implement priority inheritance don't allow nested locks. It
might not be possible, however, to eliminate nested resource
locks in some applications without seriously complicating the
application.
● But remember that allowing tasks to acquire multiple priority
inheritance resources can lead to deadlock and increase the
worst-case wait time.
● Priority inheritance is difficult to implement, with many
complicated scenarios arising when two or more tasks
attempt to access the same resources. The algorithm for
resolving a long chain of nested resource locks is complex.
● It's possible to incur a lot of overhead as hoisting one task
results in hoisting another task, and another, until finally
some task is hoisted that has the resources needed to run.
After executing its critical section, each hoisted task must
then return to its original priority.
Simple priority inheritance
Figure shows the simplest case of the priority inheritance
protocol in which a low-priority task acquires a resource that's
then requested by a higher priority task.
1. Task L receives control of the processor and begins
executing.
○ The task makes a request for Resource A.
2. Task L is granted ownership of Resource A and enters its
critical region.
3. Task L is preempted by Task H, a higher-priority task.
○ Task H begins executing and requests ownership of
Resource A, which is owned by Task L.
4. Task L is hoisted to a priority above Task H and resumes
executing its critical region.
5. Task L releases Resource A and is lowered back to its
original priority.
○ Task H acquires ownership of Resource A and begins
executing its critical region.
6. Task H releases Resource A and continues executing
normally.
7. Task H finishes executing and Task L continues
executing normally.
8. Task L finishes executing.
Three-task, one-resource priority inheritance
1. Task 3 gets control of the processor and begins
executing.
○ The task requests ownership of Resource A.
2. Task 3 acquires Resource A and begins executing its critical region.
3. Task 3 is preempted by Task 2, a higher-priority task.
○ Task 2 begins executing normally and requests ResourceA, which is
owned by Task 3.
4. Task 3 is hoisted to a priority above Task 2 and resumes
executing its critical region.
5. Task 3 is preempted by Task 1, a higher-priority task.
○ Task 1 begins executing and requests Resource A,
which is owned by Task 3.
6. Task 3 is hoisted to a priority above Task 1.
○ Task 3 resumes executing its critical region.
7. Task 3 releases Resource A and is lowered back to its
original priority.
○ Task 1 acquires ownership of Resource A and begins
executing its critical region.
8. Task 1 releases Resource A and continues executing
normally.
9. Task 1 finishes executing. Task 2 acquires Resource A and
begins executing its critical region.
10. Task 2 releases Resource A and continues executing
normally.
11. Task 2 finishes executing. Task 3 resumes and continues
executing normally.
12. Task 3 finishes executing.
Three-task, one-resource priority inheritance
1. Task 3 gets control of the processor and begins
executing.
○ The task requests ownership of Resource A.
2. Task 3 acquires Resource A and begins executing its
critical region.
3. Task 3 is preempted by Task 2, a higher-priority task.
○ Task 2 begins executing normally and requests
Resource A, which is owned by Task 3.
4. Task 3 is hoisted to a priority above Task 2 and resumes
executing its critical region.
5. Task 3 is preempted by Task 1, a higher-priority task.
○ Task 1 begins executing and requests Resource A,
which is owned by Task 3.
6. Task 3 is hoisted to a priority above Task 1.
○ Task 3 resumes executing its critical region.
7. Task 3 releases Resource A and is lowered back to its
original priority.
○ Task 1 acquires ownership of Resource A and begins
executing its critical region.
8. Task 1 releases Resource A and continues executing
normally.
9. Task 1 finishes executing. Task 2 acquires Resource A and
begins executing its critical region.
10. Task 2 releases Resource A and continues executing
normally.
11. Task 2 finishes executing. Task 3 resumes and continues
executing normally.
12. Task 3 finishes executing.
Three-task, two-resource priority inheritance
1. Task 3 is given control of the processor and begins
executing. The task requests Resource A.
2. Task 3 acquires ownership of Resource A and begins
executing its critical region.
3. Task 3 is preempted by Task 2, a higher-priority task. Task 2
requests ownership of Resource B.
4. Task 2 is granted ownership of Resource B and begins executing its
critical region.
○ The task requests ownership of Resource A, which is owned by
Task 3.
5. Task 3 is hoisted to a priority above Task 2 and resumes executing its
critical region.
6. Task 3 is preempted by Task 1, a higher-priority task.
○ Task 1 requests Resource B, which is owned by Task 2.
7. Task 2 is hoisted to a priority above Task 1. However, Task 2 still can't
execute because it must wait for Resource A, which is owned by
Task 3.
○ Task 3 is hoisted to a priority above Task 2 and continues
executing its critical region.
8. Task 3 releases Resource A and is lowered back to its original
priority.
○ Task 2 acquires ownership of Resource A and resumes
executing its critical region.
9. Task 2 releases Resource A and then releases Resource B. The task
is lowered back to its original priority.
○ Task 1 acquires ownership of Resource B and begins executing
its critical region.
10. Task 1 releases Resource B and continues executing normally.
11. Task 1 finishes executing. Task 2 resumes and continues executing
normally.
12. Task 2 finishes executing. Task 3 resumes and continues executing
normally.
13. Task 3 finishes executing.
Avoid inversion
● The best strategy for solving priority inversion is to design
the system so that inversion can't occur. Although priority
ceilings and priority inheritance both prevent unbounded
priority inversion, neither protocol prevents bounded priority
inversion. Priority inversion, whether bounded or not, is
inherently a contradiction. You don't want to have a
high-priority task wait for a low-priority task that holds a
shared resource.
● Prior to implementing an application, examine its overall
design. If possible, avoid sharing resources between tasks
at all. If no resources are shared, priority inversion is
precluded.
● If several tasks do use the same resource, consider
combining them into a single task. The sub-tasks can access
the resource through a state machine in the combined task
without fear of priority inversion. Unless the competing
sub-tasks are fairly simple, however, the state machine
might be too complex to justify.
● Another way to prevent priority inversion is to ensure that all
tasks that access a common resource have the same
priority.
● Although one task might still wait while another task uses the
resource, no priority inversion will occur because both tasks
have the same priority. Of course, this only works if the
RTOS provides a non-preemptive mechanism for gracefully
switching between tasks of equal priority.
● If you can't use any of these techniques to manage shared
resources, consider giving a “server task” sole possession of
the resource. The server task can then regulate access to
the resource. When a “client task” needs the resource, it
must call upon the server task to perform the required
operations and then wait for the server to respond.
● The server task must be at a priority greater than that of the
highest-priority client task that will access the resource.
● This method of controlling access to a resource is similar to
the priority ceiling protocol and requires static analysis to
determine the priority of the server task.
● The method relies on RTOS message passing and
synchronization services instead of resource locks and
dynamic task-priority adjustments.
Prioritize
● Priority inversion is a serious problem that, if allowed to
occur, can cause a system to fail. It's generally simpler to
avoid priority inversion than to solve it in software.
● If possible, eliminate the need for shared resources
altogether, avoiding any chance of priority inversion. If you
can't avoid priority inversion, at least make sure it's
bounded.
● Unbounded priority inversions can leave high-priority tasks
unable to execute, resulting in application failure. Two
common methods of bounding priority inversion are the
priority ceiling protocol and the priority inheritance protocol.
● Neither protocol is perfect for all situations. Hence, good
analysis and design are always necessary to understand
which solution, or combination of solutions, is needed for
your particular application.