The priority inversion problem

The priority inversion problem in not “academic”!

What really happened to the software on the Mars Pathfinder spacecraft?

(July 4th 1997)... the Mars Pathfinder landed to a media fanfare and began to transmit data back to Earth. Days later and the flow of information and images was interrupted by a series of total systems resets. ...

Shared resources with exclusive access

Tasks: the Blocked state

When a running task tries to access a shared resource (e.g. a buffer, a communication port) that is already taken (i.e. in use) by another task, it gets blocked . When the resource becomes free, the blocked task becomes again ready for execution. To handle this scenario the state diagram is updated as follows:

The priority inversion phenomenon

On a real-time system with preemption and independent tasks, the highest priority ready task is always the one in execution.

However, when tasks share resources with exclusive access, the case is different. An higher priority task may be blocked by another ( lower priority ) task, whenever this latter one owns a resource needed by the first one. In such scenario it is said that the higher priority task is blocked.

When the blocking task (and eventually other tasks with intermediate priority) execute, there is a priority inversion.

The priority inversion is an unavoidable phenomenon in the presence of shared resources with exclusive access.

However, in real-time systems, it is of utmost importance to bound and quantify its worst-case impact, to allow reasoning about the schedulability of the task set.

Therefore, the techniques used to guarantee the exclusive access to the resources (synchronization primitives) must restrict the duration of the priority inversion and be analyzable , i.e., allow the quantification of the maximum blocking time that each task may experience in any shared resource.