Priority inversion

Priority inversion, also called priority inversion, (English priority inversion ) is a problem of computer science, which can occur when priority scheduling.

At one priority inversion multiple processes or threads with different priorities and resource involved. The resource range are used exclusively with mutual exclusion (such as a semaphore ).

A high priority process wants to access a resource, but this can not, because the resource is already occupied by a lower priority process. The high-priority process must wait until the other process releases the resource again. Characterized the process priorities are exchanged in a first form of priority inversion.

There is now a process medium priority, does not use the resource in question, this medium -priority process can displace the low-priority, ie the medium -priority process is executed instead of the low-priority process. The low-priority process the resource can no longer release, so that the high-priority process is not executed. This prevents the medium -priority process, indirectly, the high-priority process from running, which it is prohibited according to the principle of the priority scheduling. The priority of the process and the high priority medium priority process are thus reversed in a second form of priority inversion.

A famous problem that has been attributed to this error, the near- loss of the Mars Pathfinder probe.

Although the problem has been known since the 70s, has not yet found an optimal solution. Two well-known approaches are the priority boundary or barrier ( Priority Ceiling ) and priority inheritance (Priority Inheritance ). When accessing certain data structures and non- blocking synchronization techniques can help.

Another approach to solve the problem, Priority Aging offers. Here, the priority of a waiting process with time is increasingly raised so that he eventually gets a higher priority than the currently running processes and thus comes to be executed. Originally this technique was introduced as a remedy for "starving " (English Starvation ). Applied to the case of priority inversion, the priority aging would cause the low-priority process would get a higher priority than the medium -priority process with time and this would therefore displace. He could run to the end, and the area occupied by him resource would be released again so now the high-priority process might result in the execution and priority inversion would therefore be repealed.