Prioritätsinversion

Prioritätsinversion, auch Prioritätsumkehr genannt, (englisch priority inversion) ist ein Problem der Informatik, das beim Prioritätsscheduling auftreten kann.

Prioritätsinversion: Prozess 3 wartet auf Prozess 1, der von Prozess 2 verdrängt wird.

An einer Prioritätsinversion sind mehrere Prozesse oder Threads mit unterschiedlicher Priorität und eine Ressource beteiligt. Die Ressource wird hierbei mit wechselseitigem Ausschluss exklusiv belegt (etwa durch die Verwendung eines Semaphores).

Ein Prozess mit hoher Priorität will auf eine Ressource zugreifen, kann dies aber nicht, da die Ressource bereits von einem niedriger priorisierten Prozess belegt ist. Der hoch priorisierte Prozess muss warten, bis der andere Prozess die Ressource wieder freigibt. Dadurch sind die Prozess-Prioritäten in einer ersten Form der Prioritätsinversion vertauscht.

Existiert nun ein Prozess mit mittlerer Priorität, der die fragliche Ressource nicht verwendet, kann dieser mittel priorisierte Prozess den niedrig priorisierten verdrängen, d. h. der mittel priorisierte Prozess wird anstelle des niedrig priorisierten Prozesses ausgeführt. Der niedrig priorisierte Prozess kann die Ressource nun nicht mehr freigeben, so dass der hoch priorisierte Prozess nicht zur Ausführung kommt. Damit hindert der mittel priorisierte Prozess indirekt auch den hoch priorisierten Prozess an der Ausführung, was er nach dem Prinzip des Prioritäts-Schedulings nicht darf. Die Priorität des hoch priorisierten Prozesses und des mittel priorisierten Prozesses sind somit in einer zweiten Form der Prioritätsinversion vertauscht.^[1]

Ein berühmtes Problem, das auf diesen Fehler zurückgeführt wurde, ist der Beinahe-Verlust der Pathfinder-Marssonde.^[1]

Obwohl das Problem seit den 70er Jahren bekannt ist, ist noch keine optimale Lösung gefunden worden. Zwei bekannte Lösungsansätze sind die Prioritätsgrenze oder -schranke (Priority Ceiling) und die Prioritätsvererbung (Priority Inheritance). Beim Zugriff auf bestimmte Datenstrukturen können auch nicht-blockierende Synchronisationstechniken Abhilfe schaffen.

Einen weiteren Ansatz, um das Problem zu lösen, bietet Priority Aging. Hierbei wird die Priorität eines wartenden Prozesses mit der Zeit immer weiter angehoben, so dass er irgendwann einmal eine höhere Priorität als die laufenden Prozesse bekommt und damit zur Ausführung gelangt. Ursprünglich wurde diese Technik als Mittel gegen „Aushungern“ (engl. Starvation) eingeführt.^[2] Angewandt auf den Fall der Prioritätsinversion, würde das Priority Aging bewirken, dass der niedrig priorisierte Prozess mit der Zeit eine höhere Priorität als der mittel priorisierte Prozess bekäme und diesen somit verdrängen würde. Damit könnte er zu Ende laufen, und die von ihm belegte Ressource würde wieder freigegeben, so dass nun der hoch priorisierte Prozess zur Ausführung kommen könnte und die Prioritätsinversion somit aufgehoben wäre.^[3]

Siehe auch

• Verklemmung (deadlock)
• Präemptives Multitasking

Einzelnachweise

1. ↑ ^{a b} Autor: Andrew S. Tanenbaum Moderne Betriebssysteme. 2., überarbeitete Auflage. Übersetzt von Prof. Dr. Uwe Baumgarten, Technische Universität München. Pearson Studium / Prentice Hall, München 2003, ISBN 3-8273-7019-1.
2. ↑ "Starvation Protection - Whitepaper" (PDF; 95 kB)
3. ↑ "Betriebssysteme - Kapitel Nebenläufigkeit" (PDF; 591 kB) Uni Ulm, Prof. Schulthess, Vorlesung im Hauptstudium / SS 2010 / CS 5250, Folie 33