Deadlock (Eisenbahn)

Definition und grundlegende Fälle

Ein Deadlock ist im Eisenbahnbetrieb eine ausweglose Situation, in der sich Züge gegenseitig blockieren. Im Regelbetrieb ist dann keine Zugfahrt mehr möglich. Die Züge stehen nicht unbedingt unmittelbar vor einer Kollision; entscheidend ist, dass jeder Zug auf eine freie Strecke oder ein freies Gleis wartet, das wegen der anderen Züge nicht verfügbar wird.

Der einfachste Fall tritt auf einer eingleisigen Strecke auf, wenn sich zwei Züge entgegenstehen. Befindet sich jeder Zug noch in einem eigenen Zugfolgeabschnitt, droht zwar kein Zusammenstoß. Der Gegenfahrschutz verhindert diese Situation jedoch zur Sicherung der Zugfahrten.

Ein Deadlock kann auch entstehen, wenn ein Bahnhof an einer eingleisigen Strecke zwei Gleise besitzt. Sind dort bereits zwei in dieselbe Richtung fahrende Züge untergebracht, etwa weil ein Zug den anderen überholen soll, und kommt gleichzeitig ein Zug aus der Gegenrichtung, sind alle Bahnhofsgleise belegt. Eine Zugkreuzung ist dann nicht mehr möglich, sodass sich die Züge gegenseitig blockieren.

Deadlocks auf mehrgleisigen Strecken

Auch auf zweigleisigen Strecken kann ein Deadlock auftreten, wenn Gleiswechselbetrieb zugelassen ist. Treffen auf beiden Gleisen jeweils zwei Züge in entgegengesetzter Richtung aufeinander und ist es durch keinen weiteren Gleiswechsel mehr möglich, das Gegengleis zu verlassen, sind die Züge festgefahren. Für keinen Zug ist in seiner Fahrtrichtung ein freier Zugfolgeabschnitt vorhanden.

In größeren Bahnhöfen besteht die Gefahr insbesondere dann, wenn Züge die Zufahrtsstrecken blockieren, weil sie in den Bahnhof einfahren wollen, dort wegen überfüllter Bahnhofsgleise aber nicht aufgenommen werden können. Eine größere Sicherheit bieten zweigleisige Strecken, auf denen jede Richtung ausschließlich das jeweilige Regelgleis nutzt.

Die Beseitigung eines Deadlocks durch Rangieren ist im Eisenbahnbetrieb sehr aufwendig. Deshalb muss bereits vor der Einführung eines neuen Fahrplans geprüft werden, dass er keine Deadlocks enthält. In Europa wird die Einführung neuer Fahrpläne durch das Forum Train Europe koordiniert und findet seit 2002 immer am zweiten Samstag im Dezember um Mitternacht statt.

Erkennung und Verhinderung im Betrieb

Bei Verspätungen oder Umleitungen müssen die Fahrdienstleiter mögliche Deadlocks erkennen und verhindern. Dabei können sie teilweise durch Algorithmen in der Steuerungssoftware digitaler Stellwerke unterstützt werden. Eine solche Funktion wird als „Überfüllverhinderung“ bezeichnet. Sie erlaubt das automatische Stellen von Fahrstraßen nur, wenn dadurch die Gleisanlage nicht überfüllt wird.

Im Gleiswechselbetrieb kann die Software beispielsweise verhindern, dass eine vierte Fahrstraße auf eine Überleitstelle eingestellt wird. Dadurch bleibt eine Fahrstraße frei, die von der Überleitstelle wegführt und benötigt werden kann, um Züge aus dem kritischen Bereich herauszuführen.

Solche Systeme sind im Lötschberg-Basistunnel und im Gotthard-Basistunnel auf Grundlage des European Train Control Systems umgesetzt. Diese technische Lösung ist jedoch nur möglich, wenn die Anlagen auf beiden Seiten zum selben Stellwerksbereich gehören. In den übrigen Fällen schützt das Zugmeldeverfahren vor dem Festfahren: Soll eine Fahrt in einen Abschnitt mit Zweirichtungsbetrieb abgelassen werden, müssen die beteiligten Fahrdienstleiter dies zuvor durch Anbieten und Annehmen vereinbaren.

Theoretische Bedingungen und Folgen

Für einen Deadlock in der Eisenbahn gelten dieselben vier Bedingungen wie für einen Deadlock in der Informatik:

• Mutual Exclusion: Jeder Zugfolgeabschnitt, auch Blockabschnitt genannt, kann nur von einem Zug belegt werden. Für andere Züge ist er dann blockiert.
• Hold and Wait: Ein Zug wartet auf die Einfahrt in den nächsten Blockabschnitt und gibt den bisherigen Abschnitt erst frei, nachdem er weitergefahren ist.
• No Preemption: Züge können nicht einfach aus dem System entfernt werden.
• Wartekette beziehungsweise Zirkelbezug: Ein Zug wartet auf einen Blockabschnitt, der erst frei werden kann, nachdem ein anderer Zug seinen eigenen Abschnitt verlassen hat. Dadurch entsteht eine geschlossene Wartekette.

In einer gerichteten Darstellung weist jeder Pfeil auf den nächsten Blockabschnitt, in den ein Zug einfahren muss. Ein Deadlock ist daran erkennbar, dass der gerichtete Graph dieser Pfeile einen Zyklus enthält. Eine hypothetische Bahninfrastruktur mit einer von einem Zug belegten Schleife aus mehreren Zugfolgeabschnitten könnte dagegen so gestaltet sein, dass keine Deadlocks vorkommen.

Die ersten drei Bedingungen sind durch die Struktur der Eisenbahn und die Zugsicherung grundsätzlich erfüllt. Ob die vierte Bedingung entsteht, hängt von der Betriebssituation und den baulichen Voraussetzungen ab, insbesondere von der Mehrgleisigkeit, der Zahl verfügbarer Ausweichgleise und der Größe der Bahnhöfe. In komplexeren Systemen mit eingleisigen Strecken oder Gleiswechselbetrieb lassen sich Deadlocks daher nicht grundsätzlich ausschließen.

Anders als Softwareprozesse können Züge normalerweise nicht kurzfristig vom Gleis entfernt und anschließend neu gestartet werden. Deshalb müssen Deadlocks durch vorausschauende Planung und geeignete Steuerung verhindert werden. Für automatisierten Fahrbetrieb sowie für die Simulation und die Bestimmung der maximalen Kapazität von Eisenbahnsystemen sind spezielle Algorithmen erforderlich. Die Komplexitätstheorie zeigt, dass der Rechenaufwand bei steigender Zahl von Zügen und Blockabschnitten stark zunimmt; der von Dessouky und anderen untersuchte Algorithmus ist NP-schwer.