FIFO-Queue
Eine FIFO-Queue ist eine Warteschlange, in der das zuerst Hineingelegte auch zuerst wieder herauskommt. Computer nutzen dieses Prinzip überall dort, wo Aufgaben, Nachrichten oder Daten der Reihe nach abgearbeitet werden sollen.
Eine FIFO-Queue ist eine Warteschlange nach dem Prinzip der Supermarktkasse. Wer sich zuerst anstellt, wird zuerst bedient. Die Abkürzung FIFO steht für « First In, First Out », also « zuerst hinein, zuerst hinaus ». Computer speichern Dinge oft in solchen Warteschlangen: Druckaufträge, Nachrichten, Rechenaufgaben. Neue Einträge werden hinten angehängt, entnommen wird immer vorne. Die Reihenfolge bleibt dabei garantiert erhalten, niemand darf sich vordrängeln.
Warum Reihenfolge und Fairness zählen
In einem Programm passieren viele Dinge gleichzeitig, aber die Rechenleistung ist begrenzt. Eine Warteschlange entkoppelt deshalb das Entstehen einer Aufgabe von ihrer Bearbeitung. Wer eine Nachricht abschickt, muss nicht warten, bis sie fertig verarbeitet ist. Sie landet in der Queue, und ein anderer Programmteil holt sie später ab. Das macht Systeme belastbarer, weil kurze Lastspitzen einfach in der Schlange gepuffert werden.
Das FIFO-Prinzip sorgt außerdem für Fairness. Ohne feste Regel könnten einzelne Aufgaben ewig liegen bleiben, weil ständig neue dazukommen. Fachleute nennen das Verhungern, englisch « starvation ». Bei FIFO kann das nicht passieren: Jeder Eintrag rückt mit der Zeit garantiert nach vorne. Auch die Korrektheit hängt oft an der Reihenfolge. Wenn eine Bank erst eine Einzahlung und dann eine Abbuchung verarbeitet, ist das Ergebnis ein anderes als umgekehrt.
Anhängen hinten, entnehmen vorne
Eine FIFO-Queue kennt im Kern nur zwei Befehle. « Enqueue » legt ein Element hinten an, « Dequeue » nimmt das vorderste heraus. Dazwischen darf man nichts anfassen. Auf ein Element in der Mitte kann man also nicht zugreifen, anders als bei einer Liste. Diese Beschränkung ist Absicht: Sie macht die Datenstruktur einfach, schnell und leicht zu überprüfen.
Technisch merkt sich das Programm zwei Positionen: den Kopf und das Ende der Schlange. Beide Operationen brauchen deshalb konstant wenig Zeit, egal ob zehn oder zehn Millionen Einträge warten. Viele Systeme nutzen dafür einen Ringpuffer, also einen festen Speicherbereich, in dem Kopf und Ende im Kreis wandern. Ist der Puffer voll, muss das System entscheiden: warten lassen, ablehnen oder Einträge verwerfen.
Zur Abgrenzung hilft der Gegenbegriff Stack. Ein Stack arbeitet nach LIFO, « Last In, First Out », wie ein Stapel Teller: Der zuletzt aufgelegte Teller wird zuerst genommen. Daneben gibt es Prioritätswarteschlangen, bei denen wichtige Einträge sich vordrängeln dürfen. Ein häufiger Irrtum ist, dass FIFO auch bei mehreren parallelen Bearbeitern die Reihenfolge des Ergebnisses garantiert. Die Entnahme ist geordnet, aber wer schneller fertig wird, ist damit nicht festgelegt.
Von der Druckerschlange bis zur KI-Anfrage
Im Alltag begegnet dir das Prinzip beim Drucken. Drei Dokumente hintereinander abgeschickt heißt: Sie kommen in genau dieser Reihenfolge aus dem Gerät. Auch Tastatureingaben, Netzwerkpakete und Videostreams werden in Warteschlangen zwischengespeichert. Der Ladebalken bei einem Video ist nichts anderes als eine gefüllte Puffer-Queue.
In der Software-Welt sind Warteschlangen eigene Produkte. Systeme wie Apache Kafka, RabbitMQ oder Amazon SQS verschieben täglich Milliarden Nachrichten zwischen Programmen. Amazon bietet sogar ausdrücklich « FIFO-Queues » an, die mehr kosten als die normale Variante. Der Aufpreis existiert, weil strenge Reihenfolge über viele Server hinweg technisch aufwendig ist.
Auch bei KI-Diensten steckt eine Queue im Hintergrund. Anfragen an ein Sprachmodell landen zunächst in einer Warteschlange, bevor Grafikkarten sie abarbeiten. Wenn ein Anbieter in News von langen Wartezeiten oder überlasteten Servern spricht, ist meist diese Schlange gemeint. Reine FIFO-Bearbeitung ist dort allerdings selten: Zahlende Kunden bekommen oft Vorrang, was strenggenommen schon eine Prioritätswarteschlange ist.