Priority inversion

from Wikipedia, the free encyclopedia

Priority inversion , and priority inversion called (English priority inversion is) a problem of computer science , that the priority scheduling may occur.

Priority inversion: Process 3 is waiting for Process 1 to be displaced by Process 2.

Several processes or threads with different priorities and one resource are involved in a priority inversion. The resource is exclusively assigned with mutual exclusion (e.g. by using a semaphore ).

A process with high priority wants to access a resource, but cannot because the resource is already being used by a process with a lower priority. The high-priority process has to wait until the other process releases the resource again. As a result, the process priorities are exchanged in a first form of priority inversion.

If there is a process with medium priority that does not use the resource in question, this medium-prioritized process can displace the low-priority one, i.e. H. the medium-prioritized process is executed instead of the low-prioritized process. The low-priority process can no longer release the resource, so that the high-priority process cannot be executed. The medium-prioritized process thus indirectly also prevents the high-priority process from executing, which it is not allowed to do according to the principle of priority scheduling. The priority of the high-priority process and the medium-prioritized process are thus exchanged in a second form of priority inversion.

A famous problem attributed to this bug is the near-loss of the Pathfinder spacecraft.

Although the problem has been known since the 1970s , no optimal solution has yet been found. Two well-known approaches are the priority limit or -schranke ( priority ceiling ) and the priority inheritance ( Priority Inheritance ). When accessing certain data structures, non-blocking synchronization techniques can also help.

Another approach to solving the problem is priority aging . Here, the priority of a waiting process is raised over time so that at some point it gets a higher priority than the running processes and is thus executed. Originally, this technology (. Was as a remedy for "starving" Starvation ) introduced. Applied to the case of priority inversion, priority aging would have the effect that the low-priority process would, over time, get a higher priority than the medium-prioritized process and would thus displace it. It could then run to the end and the resource it occupied would be released again, so that the high-priority process could now be executed and the priority inversion would thus be canceled.

See also

Individual evidence

  1. ↑ a b Author: Andrew S. Tanenbaum Modern Operating Systems. 2nd, revised edition. Translated by Prof. Dr. Uwe Baumgarten, Technical University of Munich. Pearson Studium / Prentice Hall, Munich 2003, ISBN 3-8273-7019-1 .
  2. ↑ "Starvation Protection - Whitepaper" (PDF; 95 kB)
  3. ↑ "Operating systems - Concurrency chapter" (PDF; 591 kB) Ulm University, Prof. Schulthess, lecture in the main course / SS 2010 / CS 5250, slide 33