Die Multilevel Feedback Queue (MLFQ) ist ein CPU-Scheduling-Verfahren, das mehrere Warteschlangen mit unterschiedlichen Prioritäten kombiniert und Prozesse dynamisch zwischen ihnen verschiebt. Sie gilt als Grundmodell moderner Betriebssystem-Scheduler, weil sie interaktive Reaktionszeit und hohen Durchsatz gleichzeitig anstrebt.
Wie funktioniert die MLFQ?
Der Scheduler unterhält mehrere Ready-Queues mit absteigender Priorität. Prozesse in einer höheren Queue werden zuerst ausgeführt; die oberen Queues arbeiten meist mit Round Robin und kurzen Zeitquanten, die unteren mit längeren Quanten oder FCFS. Entscheidend ist das Feedback: Ein Prozess, der sein Quantum voll ausschöpft, gilt als CPU-gebunden und wird eine Stufe tiefer eingestuft. Ein Prozess, der vor Ablauf des Quantums blockiert (z. B. auf I/O wartet), gilt als interaktiv und bleibt in einer hohen Queue.
Priority Boost gegen Starvation
Ohne Korrektur würden tief eingestufte Prozesse möglicherweise nie wieder an die Reihe kommen. Die MLFQ begegnet dem mit einem periodischen Priority Boost: In festen Intervallen werden alle Prozesse in die oberste Queue angehoben. So wird Starvation verhindert und Aging auf elegante Weise nachgebildet.
Eigenschaften
- Adaptiv: misst das Verhalten jedes Prozesses und passt die Einstufung laufend an.
- Kombiniert Interaktivität (kurze Quanten oben) mit Durchsatz (lange Jobs unten).
- Parameterwahl ist anspruchsvoll: Anzahl Queues, Quanten und Boost-Intervall müssen aufeinander abgestimmt sein.
- Die Prioritätswarteschlange ist die zentrale Datenstruktur der oberen Ebenen.
Linux setzt seit Kernel 6.6 auf EEVDF statt eines klassischen MLFQ; das Grundprinzip mehrerer Ebenen mit Verhaltensrückkopplung steckt aber in vielen Systemen, etwa im Scheduler von FreeBSD (ULE) oder in älteren Windows-Designs.
Verwandte Grundlagen: Preemption, Zeitscheibe, Scheduling-Policies, Algorithmus.