Deadlock auffinden

[Johannes]

Unter https://github.com/zusitools/deadlock_c ... si3_delphi habe ich eine Delphi-Klasse zum Auffinden von Deadlocks implementiert (Download als Zip-Archiv: https://github.com/zusitools/deadlock_c ... ennung.zip). Sie steht unter einer Lizenz, die auch die kommerzielle Verwendung in Zusi ohne weitere Bedingung erlauben würde. Ein Testprojekt mit Anwendungsbeispielen ist dabei.

Der Algorithmus ist so gestaltet, dass er bei Bedarf in viele kleine Berechnungsschritte aufgeteilt werden kann. So könnte man die Auswirkung auf die Simulator-Performance minimieren, indem man in jedem Frame einen Berechnungsschritt durchführt und dann nach ein paar Frames das Ergebnis hat. Der Algorithmus ist aber auch so sehr schnell, in einem normalen Fahrplan schafft er bei mir etwa 10000 Deadlock-Prüfungen pro Sekunde.

[Nachzugler]

Sehr schön. Ich habe es nicht getestet, glaube aber mal, dass es funktioniert.

Es ist sinnvoll, nur Züge zu betrachten, die vor einem haltzeigenden Signal stehen.

Man könnte das anhand der folgenden Informationen feststellen: die Entfernung zum Ende der letzten gestellten Fahrstraße für diesen Zug sowie bei Reisezügen ggf. der aktuelle Planhalt.

Du meinst, wenn ein Reisezug einen längeren Aufenthalt hat und damit eine mögliche Auflösung des Deadlocks blockiert, oder?
Ein haltender Zug muss ja nicht vor einem haltzeigenden Signal stehen, sondern kann auch einfach nur auf die Abfahrtszeit warten. Dann wäre es zwar offiziell kein Deadlock (sondern nur ein Unconsiouslock ), aber je nach Haltezeit trotzdem blöd.

[Dirk1970]

Vielen Dank für das Tool, darauf habe ich immer gehofft.
Werde es übers Wochenende ausgiebig ausprobieren.

Edit: War wohl bissl zu voreilig, bin leider nicht mit delphi vertraut. Ist wohl noch für die Profis, aber schön, dass Bewegung in Sachen deadlock kommt.

[Carsten Hölscher]

Angesicht s der gewählten Programmiersprache höre ich einen Wunsch heraus

So ein Testprogramm hilft aber bei der konkreten Umsetzung nicht so riesig. Im Zusammhang mit meinen Datenstrukturen würde man das vermutlich sowieso etwas anders aufbauen.
Das Problem an der ganzen Sache ist m.E., wie ein Zug überhaupt erkennen kann, welcher der blockierende Zug ist.

Carsten

[Nachzugler]

Das Problem an der ganzen Sache ist m.E., wie ein Zug überhaupt erkennen kann, welcher der blockierende Zug ist.

Ist in einem Deadlock nicht jeder Zug der blockierende? Die Frage ist doch eher, welchen man mit dem wenigsten Schaden entfernen kann, um den Deadlock aufzulösen.

[Johannes]

Ist ja auch nur ein Beweis der grundsätzlichen Machbarkeit. Das Projekt mit den Tests muss man bei testgetriebener Entwicklung eh mitentwickeln, dann kann man es als "lebende" Doku auch gleich mitliefern.

Eine mögliche Integration der Klasse in Zusi stelle ich mir etwa wie folgt vor:

Code: Alles auswählen

de := TDeadlockErkennung.Create(Zugliste.Count);
for i := 0 to Zugliste.Length - 1 do
begin
  zug := Zugliste.Items[i];
  if {zug ist aktuell in Bewegung oder kann sich nochmals in Bewegung setzen} then
  begin
    Continue;
  end;

  if { zug hat keine Folgefahrstraße und wird auch nicht abgegleist, wird also nie weiterfahren können } then
  begin
    fstrAlternative := de.NeueFstrAlternative(i);
    de.WartetAuf(fstrAlternative, i); { Zug wartet auf sich selbst }
    Continue;
  end;

  for j := 0 to zug.MoeglicheFolgefahrstraßen.Count do
  begin
    fstrAlternative := de.NeueFstrAlternative(i);
    for k := 0 to zug.MoeglicheFolgefahrstraßen[j].Register do
    begin
      if { Register ist durch Zug x belegt oder für Zug x reserviert } then
      begin
        de.WartetAuf(fstrAlternative, x);
      end;
    end;
  end;
end;

Was ich nicht weiß: ob Zusi für reservierte, aber nicht belegte Register den Zug mitspeichert. Im Fahrstraßenfenster sehe ich diese Info nur für belegte Register. Aber das ließe sich ja noch ergänzen.

Was passt denn sonst noch mit den Datenstrukturen nicht?

[Carsten Hölscher]

Der Zug ist dem Register nur bekannt, wenn er drauf steht. Das hat auch irgendeinen Grund ...
Aber das Datenmmodell ließe sich an der Stelle natürlich aufbohren.

Es gibt auch Blockadeeffekte, die Dein Ansatz nicht erkennt, z.B. wenn der blockierende Zug selbst gar nicht blockiert ist und trotzdem da rumsteht.
Und dann müßte man irgendwie auch die wegen Abhängigkeiten nicht gestellten Fahrstraßen in die Betrachtung einbeziehen. Ein weiterer Fall sind Anzeigefahrstraßen, die Zusi nur stellt, wenn der Zug auch anzeigegeführt ist.

Carsten

[Johannes]

Es gibt auch Blockadeeffekte, die Dein Ansatz nicht erkennt, z.B. wenn der blockierende Zug selbst gar nicht blockiert ist und trotzdem da rumsteht.

Das ist auch kein Deadlock, zumindest wenn dieser Zug irgendwann noch weiterfahren wird. Wenn nicht (z.B. weil kein Fahrweg gefunden wurde), sollte man ihn manuell als blockiert markieren, indem man ihn als „auf sich selbst wartend” markiert.

Grundsätzlich ist das Verfahren mit dem Abhängigkeitsgraphen so allgemein, dass es immer funktionieren sollte. Relevant ist also nur:
- Es muss sichergestellt sein, dass eine Abhängigkeit im Graphen nicht „von selbst” wieder aufgelöst werden kann – kann man sicherstellen, indem man nur Züge in die Berechnung mit einbezieht, die vor einem Halt zeigenden Signal stehen. Diese Erkennung scheint es in Zusi zu geben, weil man vor einem Halt zeigenden Signal auch den Zeitsprung aktivieren kann.
- Es muss festgestellt werden, auf welche Züge ein Zug wartet. Je besser, desto mehr Deadlocks werden erkannt. Ich glaube, dass sich die allermeisten Deadlocks trotzdem über die Registerbelegungen identifizieren lassen, und fände allein das schon eine sehr nützliche Funktion.

Und dann müßte man irgendwie auch die wegen Abhängigkeiten nicht gestellten Fahrstraßen in die Betrachtung einbeziehen.

Könnte man optional auch machen, ja. Wegen der komplexen Struktur der Bedingungen ist das nicht trivial, aber machbar, wenn man nur stehende Züge in die Deadlock-Berechnung mit einbezieht:
Die meisten Bedingungen ändern sich im Stillstand des Zuges nicht:
- Weg gefahren seit Fahrplaneintrag größer oder gleich [m]:
- Weg bis Hauptsignal kleiner oder gleich [m]:
- km-Wert kleiner/größer oder gleich [km]:
- Geschwindigkeit kleiner/größer oder gleich [km/h]:

- Zufallswert [0...100%] ist nur relevant, wenn der Wert so gewählt ist, dass die Bedingung nie wahr werden kann, das kann man statisch erkennen.

- Gefahrene Zeit seit Fahrplaneintrag größer oder gleich [s]: Diese Bedingung wird zwangsläufig irgendwann wahr.

- Anderer Zug (Abstand Zugspitzen) ist näher/weiter weg als [m]: Wenn beide beteiligten Züge im Stillstand sind und sich nicht weiter fortbewegen werden, kann man eine "Wartet auf"-Verknüpfung zum anderen Zug anlegen. Wenn der Zug sich per "Oder"-Verknüpfung auf die Position zweier anderer Züge bezieht, legt man entsprechend zwei Fahrstraßenalternativen an.

Ein weiterer Fall sind Anzeigefahrstraßen, die Zusi nur stellt, wenn der Zug auch anzeigegeführt ist.

Der einzige Fall, der mir da einfällt, ist die Aufnahme des Spielerzuges in ETCS im Stand. Ist es da so, dass bis zur ETCS-Aufnahme Zusi keine Folgefahrstraßen findet und den Zug als blockiert markieren würde?

[Carsten Hölscher]

Das ist auch kein Deadlock, zumindest wenn dieser Zug irgendwann noch weiterfahren wird. Wenn nicht (z.B. weil kein Fahrweg gefunden wurde), sollte man ihn manuell als blockiert markieren, indem man ihn als „auf sich selbst wartend” markiert.

Wenn ein Zug irgendwo mal 2h rumsteht zur Dekoration z.b. und ein anderer Zug in der Gleis will, dann wirkt das wie Deadlock, auch wenn es sich vielleicht nach ein paar Stunden langsam wieder auflöst.

Der einzige Fall, der mir da einfällt, ist die Aufnahme des Spielerzuges in ETCS im Stand. Ist es da so, dass bis zur ETCS-Aufnahme Zusi keine Folgefahrstraßen findet und den Zug als blockiert markieren würde?

Man wird sich schon etwas Mühe geben müssen - oder komisch gebaute Strecken brauchen. EIne Möglichkeit, sowas selbst auszulösen wäre eine manuell durchgeführte Entlassung aus der LZB-Führung. Sowas müßte man aber wohl nicht unbedingt berücksichtigen.

Carsten

[Johannes]

Wenn ein Zug irgendwo mal 2h rumsteht zur Dekoration z.b. und ein anderer Zug in der Gleis will, dann wirkt das wie Deadlock, auch wenn es sich vielleicht nach ein paar Stunden langsam wieder auflöst.

Wenn man so was wirklich will, kann man diese Züge so behandeln wie Züge ohne Fahrweg, also als auf sich selbst wartend markieren. Dann muss man sie aber aus der Auswertung nachher rausnehmen.

Dann aber doch besser die Deadlock-Funktion nur für echte Deadlocks nutzen und für die anderen Fälle eine Funktion "Hilfe"->"Fdl anrufen" bauen. Der sagt einem dann, warum es nicht weiter geht, liest einem also den Abhängigkeitsgraphen vor