Prioritätsinversion

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.

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Priority Inheritance — 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… …   Deutsch Wikipedia

  • Priority Inheritance Protocol — 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… …   Deutsch Wikipedia

  • Priority inversion — 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… …   Deutsch Wikipedia

  • Prioritätsumkehr — 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… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Prioritätsvererbung — Die Prioritätsvererbung (englisch: priority inheritance) ist neben der der Prioritätsgrenze oder schranke (Priority Ceiling) eine Methode zur Behebung des Problems der Prioritätsinversion. Zu Prioritätsinversion kann es bei mindestens drei Tasks… …   Deutsch Wikipedia

  • Gegenseitiger Ausschluss — Der Begriff Wechselseitiger Ausschluss bzw. Mutex (Abk. für engl. mutual exclusion, auf deutsch etwa wechselseitiger Ausschluss) bezeichnet eine Gruppe von Verfahren, mit denen das Problem des kritischen Abschnitts gelöst wird. Mutex Verfahren… …   Deutsch Wikipedia

  • NPTL — Die Native POSIX Thread Library (NPTL) ist eine moderne Implementierung einer Threading Bibliothek für Linux. Sie wird in Verbindung mit der GNU C Library (glibc) verwendet und erlaubt Linux Programmen die Verwendung von POSIX Threads. Geschichte …   Deutsch Wikipedia

  • Nicht-blockierende Synchronisation — (engl. non blocking oder auch lock free synchronization) ist eine Technik in der Informatik, um parallele Prozesse zu synchronisieren, ohne dabei bestimmte Programmabschnitte sperren zu müssen. Insbesondere dient sie zur Implementierung von nicht …   Deutsch Wikipedia

  • Priority Ceiling Protocol — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Die Prioritätsgrenze, engl. priority ceiling protocol ist eine… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”