Gestern erreichte ein interaktiver Erklärartikel über die Funktionsweise von Aufzugsteuerungen den ersten Platz in der weltweiten Entwickler-Community Hacker News – mit 771 Punkten und 198 Kommentaren. Entwickler debattierten einen ganzen Tag lang intensiv über die Logik von Fahrstühlen.
Der Ausgangspunkt der Diskussion war eine überraschende Beobachtung: In vielen modernen Bürogebäuden wurden die Etagentasten aus der Kabine entfernt und durch Terminals in der Eingangshalle ersetzt. Dort wählt man vor dem Betreten sein Zielgeschoss aus, woraufhin das System eine bestimmte Kabine zuweist. Dieses System – bekannt als Zielrufsteuerung (Destination Dispatch) – schneidet jedoch in den meisten Simulationsszenarien langsamer ab als klassische Auf- und Ab-Tasten. In den Kommentaren meldeten sich Aufzugingenieure, Entwickler von Festplattentreibern und Hotelmanager zu Wort.
Aufzüge werden von fast jedem täglich genutzt, doch die dahinterstehende Komplexität ist den wenigsten bewusst. Der Artikel erklärt die Mechanik anhand interaktiver Simulationen: Jeder Algorithmus ist mit einer animierten Darstellung ausgestattet, bei der Leser selbst Etagen und Aufzüge hinzufügen können, um live zu beobachten, wie sich die Wartezeitverteilung verändert. Die Kommentare auf HN lieferten zudem wertvolle Praxisdetails.
Warum Aufzugsteuerung so schwierig ist
Zunächst gelten physikalische Gesetzmäßigkeiten. Ein Aufzug kann sich zur selben Zeit nur in eine Richtung bewegen; die Kapazität ist begrenzt; und je mehr Etagen vorhanden sind, desto mehr Kombinationsmöglichkeiten entstehen. Wenn mehrere Kabinen gleichzeitig laufen, wird die Entscheidung, wer wann abgeholt und in welcher Reihenfolge bedient wird, zu einem komplexen Scheduling-Problem.
Hinzu kommt die Asymmetrie der Passagierströme. In Bürogebäuden fahren morph morgens fast alle Menschen von der Lobby in die oberen Stockwerke; am Feierabend kehrt sich der Strom um; mittags herrscht ein gemischter Betrieb. Dieselben Steuerungsregeln führen zu völlig unterschiedlichen Ergebnissen je nach Tageszeit. Die Optimierung der Wartezeiten während der morgendlichen Stoßzeit gehört zu den schwierigsten Aufgaben.
Eine weitere Hürde bildet die Gruppensteuerung: In Bürogebäuden teilen sich meist fünf bis sechs Kabinen ein gemeinsames Ruffeld. Drückt man die Aufwärts-Taste, muss das System entscheiden, welche Kabine zugewiesen wird. Diese Entscheidung wird kontinuierlich neu bewertet, während sich Fahrstühle bewegen, Fahrgäste einsteigen und neue Anfragen eingehen. Das macht die Steuerung so anspruchsvoll: Die Regeln für eine einzelne Kabine sind simpel, die Koordination einer ganzen Flotte ist hochkomplex.
Wie klassische Aufzüge funktionieren
Der weitestverbreitete Standardalgorithmus heißt SCAN und wurde bereits 1961 patentiert. Der Aufzug fährt von der Lobby bis ins oberste Stockwerk und kehrt dann um, wobei er unterwegs Passagiere mitnimmt, die in dieselbe Richtung wollen – ähnlich wie ein Linienbus. Informatiker erkannten schnell, dass Schreib-Lese-Köpfe von Festplatten exakt demselben Muster folgen, und übernahmen die Bezeichnung „Aufzug-Algorithmus“ (Elevator Algorithm).
Da selten alle Fahrgäste ins oberste Stockwerk müssen, entstand die optimierte Variante LOOK. Hier fährt der Aufzug nur bis zum entferntesten angeforderten Stockwerk in der aktuellen Fahrtrichtung und dreht dann um. Das entspricht dem gewohnten Verhalten: Richtung beibehalten, Zwischenstopps mitnehmen und erst umkehren, wenn keine Anfragen mehr vor liegen.
Abbildung: Interaktive Aufzug-Simulationsdemo von John.fun. Quelle: john.fun/elevators
Der Maßstab für die Qualität einer Aufzugsteuerung ist die Wartezeit, genauer gesagt deren statistische Verteilung. p50 gibt an, wie lange die Hälfte der Passagiere wartet, während p90 die Wartezeit für 90 % der Fahrgäste abbildet. Durchschnittliche Wartezeiten geraten schnell in Vergessenheit; woran man sich erinnert, sind die wenigen Momente, in denen man „gefüglt eine Ewigkeit“ gewartet hat. Die Optimierung von Algorithmen zielt daher meist darauf ab, das p90-Tail-Latency einzudämmen.
Abbildung: Wartezeitverteilung in der Simulation von John.fun. Quelle: john.fun/elevators
Hier existiert ein Zielkonflikt: Kurze Wartezeiten bedeuten nicht zwangsläufig kurze Fahrzeiten. Um mehr Menschen unterwegs mitzunehmen, hält der Aufzug häufiger, was die Verweildauer in der Kabine verlängert. Die Minimierung der Wartezeit geht oft auf Kosten der Fahrtzeit – der Algorithmus muss die Waage halten.
Intelligenter heißt nicht zwingend besser
Bei mehreren Aufzügen besteht der einfachste Ansatz in einer zentralen Steuerung: Neue Anfragen werden der nächstgelegenen Kabine zugewiesen. Ingenieure gaben sich damit jedoch nicht zufrieden. Otis entwickelte den RSR-Algorithmus (Relative System Response), der jeder Kabine dynamische Punkte verleiht: voraussichtliche Ankunftszeit, aktuelle Auslastung, Vermeidung von Gruppenbildung (Anti-Clustering), Fahrtrichtung und Verfügbarkeit nahegelegener leerer Fahrstühle. Die Kabine mit der besten Bewertung erhält den Zuschlag. Das System berechnet die Zuweisungen alle 5 Sekunden neu; verspätet sich Kabine A, kann der Auftrag an Kabine B übertragen werden.
RSR enthält eine Antiklumpungs-Regel: Steuert bereits eine Kabine ein Stockwerk an, reagiert keine zweite auf denselben Ruf. Wenn in einem Bürogebäude zwei Fahrstühle gleichzeitig ankommen und die Türen öffnen, ist dies das Ergebnis einer versagenden Antiklumpungs-Logik. Die Bewertung erfolgt in Echtzeit und ändert sich mit jedem Stockwerk, das eine Kabine zurücklegt.
Die Testergebnisse der Simulation zeigen jedoch ein ernüchterndes Bild: Bei hohem Verkehrsaufkommen schlägt der einfache LOOK-Algorithmus oft das hochkomplexe RSR-System. Auch in kleineren Gebäuden mit wenigen Aufzügen gewinnt LOOK regelmäßig. Mehr Regeln bedeuten nicht automatisch mehr Geschwindigkeit – manchmal ist Einfachheit überlegen. Für die Ingenieurpraxis ist dies eine Erinnerung: Zwischen Algorithmenkomplexität und tatsächlichem Leistungsgewinn liegt das konkrete Einsatzszenario.
Die Debatte um moderne Zielwahl-Steuerungen
Die Logik der Zielrufsteuerung (Destination Dispatch) klingt einleuchtend: Da das System vorab weiß, wohin jeder Fahrgast möchte, kann es Personen mit demselben Zielgeschoss in dieselbe Kabine sortieren und so Zwischenstopps reduzieren. Mit vollständiger Information sollte das System theoretisch effizienter sein. In Hotels, Krankenhäusern und Wolkenkratzern sind solche Kiosk-Terminals inzwischen weit verbreitet.
Die Simulation im Artikel kommt jedoch zum gegenteiligen Ergebnis: In den meisten Fällen ist die Zielrufsteuerung langsamer als die traditionelle Tastensteuerung. Der Grund liegt im Verlust an Flexibilität. Traditionelle Aufzüge können ihre Route alle 5 Sekunden neu anpassen. Die Zielrufsteuerung hingegen bindet Fahrgäste fest an eine zugewiesene Kabine, sobald sie das Terminal bedienen. Ändert sich die Situation 30 Sekunden später grundlegend, kann das System die Zuweisung nicht mehr korrigieren. Der Vorteil der Vorabinformation wiegt den Verlust der Echtzeit-Adaptivität nicht auf.
In den Kommentaren regte sich jedoch Widerspruch. Ingenieure wiesen darauf hin, dass in echten Bürogebäuden zur Mittagszeit große Menschenmengen gleichzeitig zum Restaurant-Geschoss fahren – ein Szenario, in dem die Zielrufsteuerung durch Bündelung ihre Stärken ausspielt. Ebenso schalten Hotel-Aufzüge morgens in spezielle Frühstücks-Modi. Da die Simulation diese speziellen Verkehrsmuster nicht abbildete, fielen die Ergebnisse zu Gunsten der älteren Algorithmen aus. Beide Argumente haben ihre Berechtigung: Die Effizienz der Zielrufsteuerung hängt stark vom konkreten Passagieraufkommen ab. Obwohl sie in vielen modernen Wahrzeichen eingebaut wird, gilt die Behauptung „Neuer ist immer schneller“ nicht uneingeschränkt.
Abbildung: Demonstration der Zielrufsteuerung von John.fun. Quelle: john.fun/elevators
Eine Festplatte ist ein eingerollter Aufzug
Ein Detail aus den Kommentaren stach besonders hervor: Der SCAN-Algorithmus entspricht exakt dem Festplatten-Header-Scheduling in Computern. Auf Wikipedia ist der Eintrag sowohl unter „Elevator Algorithm“ als auch unter „SCAN“ zu finden. Er wurde ursprünglich entwickelt, um Lese- und Schreibanfragen auf Festplatten zu koordinieren.
In einer mechanischen Festplatte bewegt sich der Lese-/Schreibkopf über die Festplattenspuren, genau wie ein Aufzug zwischen den Stockwerken Passagiere befördert. Die Lese- und Schreibanfragen sind über die Plattenoberfläche verteilt; der Kopf streicht in eine Richtung über die Platte, arbeitet unterwegs Anfragen ab und kehrt am Ende um. Die Positionierung (Seek) des Festplattenkopfes gehört zu den langsamsten mechanischen Vorgängen im gesamten Computer – die Ersparnis durch das Scheduling liegt genau in dieser mechanischen Zeit. Ein Entwickler scherzte treffend: „Eine Festplatte ist nichts anderes als ein eingerollter Aufzug.“
In Lehrbüchern der Informatik ist SCAN das klassische Kapitel für Festplatten-I/O-Scheduling. Das Patent der Aufzugsfirma von 1961 und Betriebssystem-Lehrbücher greifen auf dieselbe Idee zurück. Als Donald Knuth in The Art of Computer Programming Koroutinen erläuterte, wählte er als primäres Beispiel die Simulation eines Aufzugs. Der eine befördert Menschen, der andere Daten – die Steuerungslogik ist identisch.
In modernen Festplatten geht dieser Algorithmus allmählich in den Ruhestand, da Solid-State-Drives (SSDs) Suchzeiten nahezu auf Null reduzieren. In Fahrstühlen verrichtet er jedoch nach wie vor täglich seinen Dienst. Dieselbe Grundidee begleitet uns seit dem Patent von 1961 über die Grenzen von Maschinenbau und Informatik hinweg.
Fazit
Wenn der Aufzug auf sich warten lässt, ignoriert er Sie nicht – er muss lediglich zahlreiche Variablen gegeneinander abwägen. Wenn Sie das nächste Mal auf einen Fahrstuhl warten, denken Sie daran: Hinter jedem Knopfdruck steckt die Arbeit von Generationen von Ingenieuren, die darüber gestritten haben, wie Algorithmen schneller werden können – und manche dieser Debatten sind bis heute nicht abgeschlossen.
Referenzlinks:
- John.fun: Elevators Interaktiver Erklärartikel
- HN-Diskussion (item?id=49124218)
