Quelltext der Seite Multilevel Feedback Queue

Der Begriff '''Multilevel Feedback Queue''' bezeichnet einen dynamischen [[Prioritätsscheduling]]-Algorithmus. Bei diesem Verfahren gibt es mehrere [[Warteschlange (Datenstruktur)|Warteschlangen]] (engl. queue) unterschiedlicher Priorität. [[Prozess (Informatik)|Prozesse]] werden in Abhängigkeit von ihrem bisherigen Ressourcenverbrauch dynamisch in eine dieser Warteschlangen eingeordnet.<ref>{{bibISBN|0471694665|Seite=168}}</ref>

== Realisierung ==
Es werden mehrere [[FIFO]]-Warteschlangen benutzt.<ref>Markus Weinländer: ''Entwicklung Paralleler Betriebssysteme – Design und Implementierung von Multithreading-Konzepten in C++'', Vieweg+Teubner 1995, ISBN 3-322-83080-2. ab. S. 106</ref> Die Abarbeitung erfolgt so:
# Ein neuer Prozess wird am Ende der obersten FIFO-Warteschlange eingefügt.
# Nach einiger Zeit erreicht der Prozess den Anfang der Warteschlange und wird dem [[Prozessor]] zugewiesen.
# Ist der Prozess vollständig abgearbeitet, so verlässt er das System.
# Wenn der Prozess den Prozessor freiwillig abgibt, so verlässt er die Warteschlange. Sobald der Prozess wieder bereit wird, wird er wieder in dieselbe Warteschlange eingereiht.
# Falls der Prozess die gesamte Zeitscheibe in Anspruch nimmt, wird er unterbrochen und an das Ende der nächstniedrigeren Warteschlange gesetzt.
# Dieser Ablauf setzt sich fort, bis der Prozess entweder vollständig abgearbeitet ist oder die niedrigste Warteschlange erreicht hat.
# In der niedrigsten Warteschlange rotieren die Prozesse im [[Round Robin (Informatik)|Round-Robin]]-Verfahren, bis sie beendet werden und das System verlassen.

Im Multilevel-Feedback-Queue-Verfahren hat ein Prozess nur einmal die Möglichkeit, in einer bestimmten Warteschlange komplett abgearbeitet zu werden, bevor er in eine niedrigere Warteschlange gedrängt wird.

Der [[Prozess-Scheduler|Scheduler]] teilt den Prozessor dem Prozess am Anfang immer der obersten nicht leeren Warteschlange zu.

== Vor- und Nachteile ==

Kurze [[Job (EDV)|Jobs]] werden bevorzugt, da ihnen höhere Prioritäten zugewiesen werden. Jobs mit vielen Ein- und Ausgabeoperationen werden bevorzugt, da sie nach einer freiwilligen Abgabe des Prozessors wieder in die ursprüngliche Warteliste eingeordnet werden, ihre Priorität also beibehalten. Neue Prozesse werden schnell eingestuft und in eine Prioritätsklasse eingeordnet. Es sind keine Heuristiken (z.&nbsp;B. zur Abschätzung der Laufzeit des Prozesses) zur Einstufung notwendig.

Wenn immer neue Prozesse nachkommen, können rechenintensive Prozesse in der niedrigsten Prioritätsklasse „verhungern“ (engl. starvation), d. h., sie werden niemals bis zum Ende ausgeführt. Eine [[Prioritätsinversion]] kann auftreten.

== Einzelnachweise ==
<references />

[[Kategorie:Betriebssystemtheorie]]
[[Kategorie:Algorithmus]]