Mumbai University > Electronics Engineering > Sem 7 > Embedded System Design

Marks: 10 Marks

Year: Dec 2015

Problem of priority inversion:

1. Priority inversion is the condition in which a high priority task needs to wait for a low priority task to release a resource between the medium priority task and a low priority task.
2. Priority based pre-emptive scheduling allows a higher priority task to execute first whereas lock based process synchronization using a mutex or semaphore allows the resource to be used only by one task. This two concepts lead to the problem of priority inversion.
3. If a high priority task is being executed and if it requires a shared resource which is currently with a low priority task. Then in such a case the kernel does not allow high priority task to execute and low priority task takes control of the CPU. The priority of the high priority task is inverted. The problem becomes severe if some medium priority task interrupts the low priority task.

The diagram below explains the problem of priority inversion in detail

Consider 3 tasks, task 1 with highest priority, task2 medium priority and task3 with the lowest priority. From the above diagram:

1. Task 1 and Task 2 are both waiting for an event to occur and Task 3 is executing.
2. At some point, Task 3 acquires a semaphore, which the task needs before it can access a shared resource.
3. Task 3 performs some operations on the acquired resource.
4. The event for which Task 1 was waiting occurs, and thus the kernel suspends Task 3 and starts executing Task 1 because Task 1 has a higher priority.
5. Task 1 continues execution
6. Task 1 executes for a while until it also wants to access the resource (i.e., it attempts to get the semaphore that Task 3 owns). Because Task 3 owns the resource, Task 1 is placed in a list of tasks waiting for the kernel to free the semaphore.
7. Task 3 resumes execution since the CPU control is now transferred from task1 to task3.
8. Task 3 resumes and continues execution until it is preempted by Task 2 because the event for which Task 2 was waiting occurred.
9. Task 2 continues execution
10. Task 2 handles the event for which it was waiting, and, when it’s done, the kernel relinquishes the CPU back to Task 3.
11. Task 3 continues execution
12. Task 3 finishes working with the resource and releases the semaphore. At this point, the kernel knows that a higher priority task is waiting for the semaphore and performs a context switch to resume Task 1.
13. At this point, Task 1 has the semaphore and can access the shared resource.

The priority of Task 1 has been virtually reduced to that of Task 3 because Task 1 was waiting for the resource that Task 3 owned. The situation was aggravated when Task 2 preempted Task 3, which further delayed the execution of Task 1

Solving the problem of priority inversion:

1. In the above example since task 3 was stopped from executing by task2 at step 8 due to its lower priority, priority inversion was observed.
2. The problem can therefore solved increasing the priority if task3 equal to that of task1 from the moment task1 starts waiting for the semaphore, i.e. at step 4.
3. Task 3 can now execute without any interruption from task2 because of its higher priority.
4. On completing execution, task3 releases semaphore which is then acquired by task1. Thus task1 continue its execution. This work around for solving the priority inversion problem is known as priority inheritance.
5. Thus priority inheritance is mechanism where a low-priority task that is currently accessing a shared resource requested by a high-priority task temporarily inherits the priority of that high-priority task, from the moment high priority task raises request.