Monday, March 08, 2010

Priority inversion, priority inheritance, and priority ceiling

Remember polycom?

Priority inversion: a high priority task is indirectly preempted by a medium priority task. (a medium priority task preempts a low priority task, the low priority task is using a shared resource on which the high priority task is pending). The process from wiki is:
• There are 3 tasks A, B, and C, with priority from high to low. A and C share the resource
• C successfully locks the resource
• A attempts to acquire resource, being blocked and wait for C to release resource
• B became runnable before C release resource
• Now you don't know when C can release resource, and A is still blocked
• reversion happens: B is running and A is not
Solution 1: Priority inheritance - make the low priority task inherit the priority of any high task pending on a resource they share. This priority change should take place as soon as the high priority task begins to pend. It should end when resource is released.

Solution 2: Priority ceiling - each resource is assigned a priority ceiling, which equals to the highest priority of an task which may lock the resource. Once a task finishes with the resource, its priority returns to normal.