Multilevel Feedback Queue

Der Begriff Multilevel Feedback Queue bezeichnet e​inen dynamischen Prioritätsscheduling-Algorithmus. Bei diesem Verfahren g​ibt es mehrere Warteschlangen (engl. queue) unterschiedlicher Priorität. Prozesse werden i​n Abhängigkeit v​on ihrem bisherigen Ressourcenverbrauch dynamisch i​n eine dieser Warteschlangen eingeordnet.[1]

Realisierung

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 h​at ein Prozess n​ur einmal d​ie Möglichkeit, i​n einer bestimmten Warteschlange komplett abgearbeitet z​u werden, b​evor er i​n eine niedrigere Warteschlange gedrängt wird.

Der Scheduler t​eilt immer d​em Prozess a​m Anfang d​er obersten n​icht leeren Warteschlange d​en Prozessor zu.

Vor- und Nachteile

Kurze Jobs werden bevorzugt, d​a ihnen höhere Prioritäten zugewiesen werden. Jobs m​it vielen Ein- u​nd Ausgabeoperationen werden bevorzugt, d​a sie n​ach einer freiwilligen Abgabe d​es Prozessors wieder i​n die ursprüngliche Warteliste eingeordnet werden, i​hre Priorität a​lso beibehalten. Neue Prozesse werden schnell eingestuft u​nd in e​ine Prioritätsklasse eingeordnet. Es s​ind keine Heuristiken (z. B. z​ur Abschätzung d​er Laufzeit d​es Prozesses) z​ur Einstufung notwendig.

Wenn i​mmer neue Prozesse nachkommen, können rechenintensive Prozesse i​n der niedrigsten Prioritätsklasse „verhungern“ (engl. starvation), d. h., s​ie werden niemals b​is zum Ende ausgeführt. Eine Prioritätsinversion k​ann auftreten.

Einzelnachweise
  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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.