Embedded Systems -> Priority inversion scenario with a binary semaphore

Priority inversion scenario with a binary semaphore
By David Kalinsky, Enea OSE Systems, EE Times
April 6, 2001 (2:26 p.m. EST)
URL: http://www.eetimes.com/story/OEG20010406S0056

In a classic scenario of priority inversion, a binary semaphore is named 'PRNT' to symbolize that it is being used to regulate the access of tasks to a printer. It is initialized with a count of one or one "token" to indicate that initially, one printer is available.

Tasks in this scenario are designed with disciplined access to the printer: Whenever a task wishes to print, it must first obtain the count (token) from the semaphore. If no token is available, the task will be blocked from running. When the task later finishes printing, it must return the token to the semaphore.

The scenario begins with low-priority Task A requesting and getting the token from the semaphore PRNT. With the token in hand, Task A begins to print. A short while later, high-priority Task B requests the token from PRNT. There's no token in PRNT since Task A still has it, so Task B is blocked from running. This is true despite Task B's higher priority, since unavailability of a token in a semaphore takes precedence over a task's priority. Task A continues to run and continues printing. All is as expected, up to this point.

Now Task C, for some unrelated reason, becomes ready to run. Task C is not interested in printing, hence it does nothing to semaphore PRNT. But Task C has higher priority than Task A, which is currently running. Hence the operating system's scheduler will stop (pre-empt) Task A and allow Task C to run.

To summarize the situation: Task C is of lower priority than Task B. And Task C is running, while Task B is prevented from running. This is a priority inversion.

It's as if Task B has become entrapped: Task B can't run because it's waiting for Task A to release the semaphore token. But Task A can't release the semaphore token or even make any progress, because it's been pre-empted by Task C.

The situation could get even worse. For example, another task, Task D, of slightly higher priority than Task C, may for some unrelated reason, also become ready to run. Task D would then begin running, preempting Task C, which already preempted Task A, which is prevented from finishing its printing and thus prevented from returning the token to the semaphore. All this time, Task B, which is of higher priority than all the others, is "stuck," blocked while waiting for the semaphore token. There may be many tasks behaving like Task D, causing greater and greater delays for Task B. This is called chained blocking or unbounded priority inversion.