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 einem Semaphor).

Ein Prozess mit hoher Priorität will auf eine Ressource zugreifen, kann dies aber nicht, da die Ressource bereits von einem niederprioren Prozess belegt ist. Der hochpriore Prozess muss warten, bis der niederpriore Prozess die Ressource wieder freigibt. Dadurch sind die Prioritäten vom hochprioren Prozess und dem niederprioren Prozess in einer ersten Form der Prioritätsinversion vertauscht.

Existiert nun ein Prozess mit mittlerer Priorität, der die fragliche Ressource nicht verwendet, kann dieser mittelpriore Prozess den niederprioren Prozess verdrängen, d.h. der mittelpriore Prozess wird an Stelle des niederprioren Prozesses ausgeführt. Der niederpriore Prozess kann die Ressource nun nicht mehr freigeben, so dass der hochpriore Prozess nicht zur Ausführung kommt. Damit hindert der mittelpriore Prozess indirekt auch den hochprioren Prozess an der Ausführung, was er nach dem Prinzip des Prioritätsschedulings nicht darf. Die Priorität des hochprioren Prozesses und des mittelprioren 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.

Siehe auch: Präemptives Multitasking, Verklemmung (deadlock)

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.