Priority inversion

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 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


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

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

  • Priority inversion — In scheduling, priority inversion is the scenario where a low priority task holds a shared resource that is required by a high priority task. This causes the execution of the high priority task to be blocked until the low priority task has… …   Wikipedia

  • Priority inheritance — In real time computing, priority inheritance is a method for eliminating priority inversion problems. Using this programming method, a process scheduling algorithm will increase the priority of a process to the maximum priority of any process… …   Wikipedia

  • Priority ceiling protocol — In real time computing, the priority ceiling protocol is a synchronization protocol for shared resources to avoid unbounded priority inversion and mutual deadlock due to wrong nesting of critical sections. In this protocol each resource is… …   Wikipedia

  • Rate-monotonic scheduling — In computer science, rate monotonic scheduling [citation|first1=C. L.|last1=Liu|authorlink1=Chung Laung Liu|first2=J.|last2=Layland|title=Scheduling algorithms for multiprogramming in a hard real time environment|journal=Journal of the ACM|volume …   Wikipedia

  • Non-blocking synchronization — In computer science, non blocking synchronization ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. Literature up to the turn of the century used non blocking synonymously …   Wikipedia

  • Real-time operating system — A real time operating system (RTOS; generally pronounced as are toss ) is a multitasking operating system intended for real time applications. Such applications include embedded systems (programmable thermostats, household appliance controllers,… …   Wikipedia

  • Inverse — or inversion may refer to:* Inverse (program), a program for solving inverse and optimization problems * Inversion (music) * Inversion (prosody), the reversal of the order of a foot s elements * Inversion (linguistics) * Inversion (law),… …   Wikipedia

  • Non-blocking algorithm — In computer science, a non blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non blocking algorithm is lock free if there is guaranteed system wide… …   Wikipedia

  • Lock-free and wait-free algorithms — In contrast to algorithms that protect access to shared data with locks, lock free and wait free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. Lock free refers to the …   Wikipedia

  • Software transactional memory — In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. It is an alternative to lock based synchronization. A… …   Wikipedia

Share the article and excerpts

Direct link
https://de-academic.com/dic.nsf/dewiki/1131853 Do a right-click on the link above
and select “Copy Link”