Multilevel Feedback Queue

Der Begriff Multilevel Feedback Queue bezeichnet einen dynamischen Prioritätsscheduling-Algorithmus. Bei diesem Verfahren gibt es mehrere Warteschlangen (engl. queue) unterschiedlicher Priorität. Prozesse werden in Abhängigkeit von ihrem bisherigen Ressourcenverbrauch dynamisch in eine dieser Warteschlangen eingeordnet.^[1]

Es werden mehrere FIFO-Warteschlangen benutzt.^[2] Die Abarbeitung erfolgt so:

1. Ein neuer Prozess wird am Ende der obersten FIFO-Warteschlange eingefügt.
2. Nach einiger Zeit erreicht der Prozess den Anfang der Warteschlange und wird dem Prozessor zugewiesen.
3. Ist der Prozess vollständig abgearbeitet, so verlässt er das System.
4. 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.
5. Falls der Prozess die gesamte Zeitscheibe in Anspruch nimmt, wird er unterbrochen und an das Ende der nächstniedrigeren Warteschlange gesetzt.
6. Dieser Ablauf setzt sich fort, bis der Prozess entweder vollständig abgearbeitet ist oder die niedrigste Warteschlange erreicht hat.
7. In der niedrigsten Warteschlange rotieren die Prozesse im 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 Scheduler teilt den Prozessor dem Prozess am Anfang immer der obersten nicht leeren Warteschlange zu.

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

1. ↑ Abraham Silberschatz, Peter B. Galvin, Greg Gagne: Operating system concepts. 7. Auflage. John Wiley & Sons, Hoboken 2005, ISBN 0-471-69466-5, S. 168 (englisch). 
2. ↑ 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