Eine Prio-Queue (Prioritätswarteschlange) ist eine Warteschlange, in der Elemente nicht nach Eingangsreihenfolge (FIFO), sondern nach einer Priorität geordnet werden: Das Element mit der höchsten Priorität wird immer zuerst bedient. In der Betriebssystem-Prozessverwaltung ist die Prio-Queue das zentrale Organisationsprinzip des Schedulers.
Einsatz im Scheduler
Laufbereite Prozesse stehen in der Runqueue des Systems. Ein Prioritäts-Scheduler sortiert diese Warteschlange nach Prioritäten: Je höher die Priorität eines Prozesses, desto eher erhält er die CPU. Klassische Linux-Scheduler führten für jede Prioritätsstufe eine eigene Warteschlange (Bitmap über alle Stufen, im O(1)-Scheduler als aktive und abgelaufene Arrays). Der Scheduler wählt dann immer aus der höchsten nicht-leeren Stufe.
Als Datenstruktur
Abstrakt betrachtet ist die Prioritätswarteschlange ein Datentyp mit den Operationen insert und extract-min/extract-max. Die effizienteste klassische Implementierung ist der Heap: Einfügen und Entnehmen kosten je O(log n) statt O(n) bei einer sortierten Liste. Prioritätswarteschlangen stecken außer im Scheduling auch in Dijkstras kürzestem Weg, in Huffman-Codierung und in Ereignis-Warteschlangen von Simulationssystemen.
Zusammenspiel mit Zeitscheiben
Bei präemptivem Scheduling beendet die Prio-Queue die Auswahl nach jeder Zeitscheibe neu: Läuft ein Prozess mit höherer Priorität ein, kann er den laufenden Prozess verdrängen. Ohne Gegenmaßnahmen droht dabei Starvation niederpriorer Prozesse — Scheduling-Policies legen fest, welche Auswahlregeln konkret gelten.
Verwandte Grundlagen: Algorithmus, Multitasking.