• Introduction
• Priority Inversion Scenario
• Solutions
  • Priority Inheritance
  • Priority Ceiling

Introduction:

• Priority inversion is a scenario or a problem in scheduling in which a high-priority task is indirectly preempted by a low-priority task.
• Key things to remember that high priority task is not directly preempted by low priority one.

Priority Inversion Scenario:
Consider three process in ascending order of priority that is:

• LP: High Priority Process
• MP: Medium Priory Process
• HP: Low Priority Process

Where LP and HP share the same resources.

• LP acquires the lock and enters the Critical Section and starts executing.
• Before LP can finish that is it releases the lock, it is preempted by MP and it is put to sleep.
• Now new process MP starts executing.
• At the same time, the HP process wishes to run but cannot because the lock is still with LP.
• Now the HP waits for LP to release the lock and LP in turn waist for MP to finish so that it can start running again.
• So, effectively it means that until MP finishes, LP cannot execute, and hence HP cannot execute.
• So, it seems like HP is waiting for MP, even though they are not directly related.
• This is a priority inversion problem.

Diag-1: Priority Inversion

Priority Inversion Solution

Priority Inheritance:

• This is a solution to priority inversion where the lower priority task continues running in the CS with its existing priority.
• Once the high priority task request for running, its priority is made highest among all the task which are waiting for the same critical resource.
• Since the priority of the lower priority task is made highest, the medium priority task cannot preempt this task. This avoids the priority inversion problem.
• When the task which is given the highest priority among all tasks, finishes the job and releases the critical resource then it gets back to its original priority value (which may be less or equal).

Priority Ceiling:

• In this, the mutex is assigned a predefined priority ceiling and this must be the highest of all the tasks that can access the resources.
• When a task acquires a lock(mutex), the same priority is given to the task.
• Hence the mid-priority task cannot preempt as long as the low-priority task owns the mutex, nor that any task preempts that want the mutex.
• Once the task is done, it releases the lock and acquires the old priority.

Drawback:
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.

Categories: Operating system (OS)