Multilevel Feedback Queue

Multilevel Feedback Queue

Der Begriff Multilevel Feedback Queue bezeichnet einen dynamischen Prioritätsscheduling-Algorithmus. Bei diesem Verfahren werden Prozesse nach ihrem bisherigen Ressourcenverbrauch dynamisch in mehrere Warteschlangen (engl. queue) unterschiedlicher Priorität eingeordnet.

Realisierung

Es werden mehrere FIFO-Warteschlangen benutzt. 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ächst niedrigeren 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 immer dem Prozess am Anfang der obersten nicht leeren Warteschlange den Prozessor zu.

Vorteile

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

Nachteile

  • 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.
  • Prioritätsinversion kann auftreten.

Wikimedia Foundation.

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

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

  • Multilevel feedback queue — In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems: Give preference to short jobs. Give preference to I/O bound processes. Separate processes… …   Wikipedia

  • Multilevel queue — Multi level queueing, used at least since the late 1950s/early 1960s, is a queue with a predefined number of levels. Unlike the multilevel feedback queue, items gets assigned to a particular level at insert (using some predefined algorithm), and… …   Wikipedia

  • Scheduling (computing) — This article is about processes assignment in operating systems. For other uses, see Scheduling (disambiguation). Scheduling is a key concept in computer multitasking, multiprocessing operating system and real time operating system designs.… …   Wikipedia

  • Prozessverwaltung — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Schedule (Informatik) — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Scheduler (Informatik) — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Scheduling (Informatik) — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Shortest-Remaining-Time — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Prozess-Scheduler — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, die die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Prioritäts-Scheduling — Das Prioritätsscheduling (auch PS – priority scheduling) ist ein in Betriebssystemen häufig verwendetes Scheduling Verfahren. Das Prinzip ist einfach: Jedem Prozess wird eine Priorität zugewiesen und nur der lauffähige Prozess mit höchster… …   Deutsch Wikipedia

Share the article and excerpts

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