Prioritätsumkehrproblem

Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Bitte entferne erst danach diese Warnmarkierung.

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 mindestens drei 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. Er muss warten, bis der niederpriore Prozess die Ressource wieder freigibt. Existiert nun ein Prozess mit mittlerer Priorität, darf dieser den niederprioren Prozess beliebig lange verdrängen. Damit verdrängt er aber indirekt auch den hochprioren Prozess, was er nach dem Prinzip des Prioritätsschedulings nicht darf. Die Priorität vom hochprioren Prozess und dem mittelprioren Prozess sind invertiert.

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

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)

Weblinks

• Priority Inversion and the Mars Pathfinder (englisch)