Deadlock (Eisenbahn)
# Deadlock (Eisenbahn)

Ein Deadlock (englisch für „ausweglose Situation“) ist bei der Eisenbahn eine Situation, in der sich Züge gegenseitig blockieren, so dass keine Zugfahrt im Regelbetrieb mehr möglich ist.

## Bedeutung

Der einfachste Fall eines Deadlocks ist eine eingleisige Strecke, auf der sich zwei Züge gegenüberstehen. Solange sich jeder der Züge in einem eigenen Zugfolgeabschnitt befindet, droht in dieser Situation zwar kein Zusammenstoß, trotzdem wird diese Behinderung vom sogenannten Gegenfahrschutz zur Sicherung von Zugfahrten verhindert. Ein auch mit Zugsicherung möglicher Deadlock ist, wenn bei eingleisigem Zugbetrieb ein Bahnhof mit zwei Gleisen mit zwei in dieselbe Richtung fahrenden Zügen belegt ist (beispielsweise zum Überholen), aber zugleich ein Zug auf dem eingleisigen Abschnitt entgegenkommt. Da alle Gleise im Bahnhof belegt sind, ist keine Zugkreuzung möglich und die Züge blockieren sich gegenseitig.
Ein Deadlock kann auch auf zweigleisigen Strecken auftreten, die im Gleiswechselbetrieb befahren werden, wenn sich auf beiden Gleisen jeweils zwei Züge entgegenkommen und es durch keinen Gleiswechsel mehr möglich ist, das Gegengleis zu verlassen. In größeren Bahnhöfen ist die Bedingung für einen Deadlock, dass die Strecken durch Züge blockiert werden, die einfahren wollen, aber wegen überfüllter Bahnhofsgleise nicht mehr einfahren können. Eine große Sicherheit bieten hingegen zweigleisige Strecken, bei denen in jede Richtung nur das Regelgleis befahren wird.
Der Aufwand, eine solche Situation durch Rangieren zu beseitigen, ist im Eisenbahnbetrieb sehr hoch. Es ist jedoch unmöglich, die Bahninfrastruktur eines komplexen Streckennetzes so zu bauen, dass Deadlocks grundsätzlich ausgeschlossen sind. Erstens muss daher vor der Einführung eines neuen Fahrplans, die in Europa durch das Forum Train Europe koordiniert seit 2002 immer am zweiten Samstag im Dezember an Mitternacht stattfindet, sichergestellt sein, dass er keine Deadlocks enthält. Zweitens ist es bei Verspätungen oder Umleitungen Aufgabe der Fahrdienstleiter, teilweise unterstützt durch Algorithmen in der Steuerungssoftware von digitalen Stellwerken, potentielle Deadlocks zu erkennen und zu verhindern. Die Software enthält dann einen Algorithmus als sogenannte „Überfüllverhinderung“, die das automatische Stellen von Fahrstraßen nur dann zulässt, wenn dadurch die Gleisanlage nicht überfüllt wird: Beispielsweise wird im Gleiswechselbetrieb das Einstellen einer vierten Fahrstraße auf die Überleitstelle verhindert und so eine davon wegführende Fahrstraße freigehalten.
Derartige Systeme sind im Lötschberg-Basistunnel sowie im Gotthard-Basistunnel auf Basis des European Train Control Systems umgesetzt. Allerdings ist dies technisch nur dann möglich, wenn die Anlagen auf beiden Seiten zum selben Stellwerksbereich gehören. In den übrigen Fällen dient das Zugmeldeverfahren, bei dem das Ablassen einer Fahrt in einen Abschnitt mit Zweirichtungsbetrieb vorher durch Anbieten und Annehmen zwischen den beteiligten Fahrdienstleitern zu vereinbaren ist, als Schutz vor dem Festfahren.

## Theoretische Beschreibung

Für die Entstehung eines Deadlocks in der Eisenbahn gelten dieselben vier Bedingungen wie beim Deadlock in der Informatik. Die ersten drei Kriterien sind dabei aufgrund der Struktur der Eisenbahn bzw. Zugsicherung immer erfüllt.
* Jeder Zugfolgeabschnitt (Blockabschnitt) kann von nur einem Zug belegt werden und ist dann für andere blockiert („Mutual Exclusion“).
* Jeder Zug wartet, bis er in den nächsten Blockabschnitt einfahren kann, und gibt erst danach das bisherige Gleis frei („Hold and Wait“).
* Es können keine Züge aus dem System entfernt werden („No Preemption“).
* Es besteht eine „Wartekette“, dass ein Zug in einen Blockabschnitt einfahren muss, der wegen eines Zirkelbezugs aber erst dann frei werden kann, nachdem der Zug seinen eigenen Blockabschnitt verlassen hat.
Das entscheidende, vierte Kriterium hängt von der Betriebssituation und den baulichen Bedingungen ab, also der Mehrgleisigkeit, der Verfügbarkeit von Ausweichgleisen und der Größe der Bahnhöfe. In einem etwas komplexeren Bahnsystem mit eingleisigen Strecken oder Gleiswechselbetrieb ist es unmöglich, Deadlocks prinzipiell zu verhindern. Anders als bei Softwareprozessen, die grundsätzlich abgebrochen und neu gestartet werden können, ist es bei der Bahn im Normalfall unmöglich, Züge kurzfristig vom Gleis zu nehmen und „neu zu starten“. Daher bleibt als Ausweg nur, Deadlocks durch Vorausschau und geeignete Steuerung zu verhindern. Für den automatisierten Fahrbetrieb sowie für die Simulation und Bestimmung der maximalen Kapazität von Eisenbahnsystemen sind daher spezielle Algorithmen nötig, die Deadlocks ausschließen und einen effizienten Bahnbetrieb ermöglichen. Mittels Komplexitätstheorie lässt sich berechnen, dass bei steigender Anzahl von Zügen und Blockabschnitten die nötige Rechenleistung stark zunimmt: der von Dessouky u. a. untersuchte Algorithmus ist NP-schwer.