Problem: Priority inversion
Priority inversion causes a high priority task to wait for a lower priority task to complete. In this example we have three tasks of different priorities, low, medium, and high.
Initially the low priority task is running. The other tasks are inactive. The situation starts when the low priority task reserves the shared resource. This seems safe because the low priority task is not going to use much CPU time before releasing the resource.
Next the high priority task is started by an interrupt and requests the resource. As the resource is in use the high priority task is blocked until the low priority task releases the resource. So far everything seems Ok.
Next the medium priority task is started by another interrupt. Because no higher priority task is ready for execution, the medium priority task is started and the low priority task is pre-empted. Now the low priority task waits for the medium priority task and the high priority task waits for the low priority task. We have a problem!
Because the medium priority task does not have any logical connection to either of the other tasks, it is possible that none of the designers considers the possibility of this problem until it is too late.
Solution: Priority ceiling protocol
There are several ways to solve the problem. A simple solution is the so called Priority Ceiling Protocol. In this method each resource is assigned a priority that is equal to (or higher than) the highest priority of the tasks that may reserve the resource. When a task reserves the resource the task is temporarily given the priority of the resource. When the task releases the resource the original priority is restored. If any task of medium priority is activated when the resource is reserved, its execution is delayed until the resource is released.
Moreover, there is no possibility of cyclic reservation and resulting deadlock, when the priority ceiling protocol is used. When a task has a resource reserved, no other task capable of reserving the same resource can run and reserve other resources.
The ReaGOS kernel uses the Priority Ceiling Protocol whenever its resource locking mechanism is used.
Priority Inversion, Wikipedia.
Michael Barr: Introduction to Priority Inversion, EE|Times, 2002-04-01.
L. Sha, et al.: Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, Volume 39 Issue 9, September 1990.
OBP Research Oy, c/o Ari Okkonen, Mielikintie 6 A 7, FI-90550 OULU, FINLAND
Tel: +358 40 542 2059, Email: firstname.lastname@example.org