Priority inversion problem

Consider the following context - 2 tasks of different priorities ; task A has a higher priority then task B, both running in a multitasking system governed by priority based scheduler.
In such system, task A will be scheduled before task B provided that  task A is ready to run.Let us assume that task A is not ready to run  and task B is running, entering a synchronized protected(some sort of lock or mutex synchr variable) portion of its code.
Imagine that right at the middle of the protected code of task B its time quantum expires and Task A is scheduled to run since it has already become ready to run in the meantime. Imagine that Task A which is of higher priority meets a synchronized portion of its code protected by the same mutex or lock we use in task B - the task will start waiting for the mutex but Task B will never release it since it is of lower priority and will never be scheduled to run!!!!
This situation is called priority inversion problem.  There are 2 was to battle this problem.


Priority Ceiling

In priority ceiling each synchr variable gets a priority value. The priority of a task is automatically raised to this priority ceiling value of the synchr variable, whenever the task locks the synchr variable. The task keeps this priority as long as it is the owner of the synchr variable. Thus, a task A cannot be interrupted by another task B with a lower priority than the priority of the synchr variable as long as A is the owner of the synchr variable. The owning task can therefore work without interruption and can release the synchr variable as soon as possible and lower itself to its previous priority. Priority inversion is avoided if the highest priority at which a  task will ever be running is used as priority ceiling value.

Priority Inheritance

When using the priority inheritance, the priority of a task which is the owner of a synchr variable is automatically raised, if a task with a higher priority tries to lock the synchr variable and is therefore blocked on the synchr variable. In this situation, the priority of the owner task is raised to the priority of the blocked task. Thus, the owner of a synchr variable always has the maximum priority of all tasks waiting for the synchr variable. Therefore, the owner task cannot be interrupted by one of the waiting tasks, and priority inversion cannot occur.When the owner task releases the synchr variable again, its priority is lowered again to the original priority value.


In the context of ACORN kernel we have a round robin scheduler with 2 task-priority levels.The higher priority is the DEVICE priority and usually services  interrupt dispatch processing - code execution outside of the interrupt handler -  with all interrupts enabled. The priority inversion problem is indeed possible so be careful what and how you synchronize the tasks' code :).


Be the first to comment.

 Add Comment

  Comments 1 - 0 of 0  

Screen Name