Deadlock auffinden
- Johannes
- Beiträge: 3203
- Registriert: 14.03.2009 22:36:06
- Aktuelle Projekte: Zusitools (http://git.io/zusitools)
Re: Deadlock auffinden
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.
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.
-
- Beiträge: 175
- Registriert: 12.12.2019 19:42:27
Re: Deadlock auffinden
Sehr schön. Ich habe es nicht getestet, glaube aber mal, dass es funktioniert.
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.
Du meinst, wenn ein Reisezug einen längeren Aufenthalt hat und damit eine mögliche Auflösung des Deadlocks blockiert, oder?Johannes hat geschrieben: ↑30.12.2012 13:04:01 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.
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.
-
- Beiträge: 166
- Registriert: 04.08.2014 07:31:24
- Wohnort: Im VGN (Verkehrsverbund Großraum Nürnberg)
Re: Deadlock auffinden
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.
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
- Administrator
- Beiträge: 33448
- Registriert: 04.07.2002 00:14:42
- Wohnort: Braunschweig
- Kontaktdaten:
Re: Deadlock auffinden
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
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
-
- Beiträge: 175
- Registriert: 12.12.2019 19:42:27
Re: Deadlock auffinden
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.Carsten Hölscher hat geschrieben: ↑02.01.2021 14:27:12 Das Problem an der ganzen Sache ist m.E., wie ein Zug überhaupt erkennen kann, welcher der blockierende Zug ist.
- Johannes
- Beiträge: 3203
- Registriert: 14.03.2009 22:36:06
- Aktuelle Projekte: Zusitools (http://git.io/zusitools)
Re: Deadlock auffinden
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:
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?
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 passt denn sonst noch mit den Datenstrukturen nicht?
- Carsten Hölscher
- Administrator
- Beiträge: 33448
- Registriert: 04.07.2002 00:14:42
- Wohnort: Braunschweig
- Kontaktdaten:
Re: Deadlock auffinden
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
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
- Beiträge: 3203
- Registriert: 14.03.2009 22:36:06
- Aktuelle Projekte: Zusitools (http://git.io/zusitools)
Re: Deadlock auffinden
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.Carsten Hölscher hat geschrieben: ↑02.01.2021 17:17:38 Es gibt auch Blockadeeffekte, die Dein Ansatz nicht erkennt, z.B. wenn der blockierende Zug selbst gar nicht blockiert ist und trotzdem da rumsteht.
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.
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:Carsten Hölscher hat geschrieben: ↑02.01.2021 17:17:38 Und dann müßte man irgendwie auch die wegen Abhängigkeiten nicht gestellten Fahrstraßen in die Betrachtung einbeziehen.
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.
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 hat geschrieben: ↑02.01.2021 17:17:38 Ein weiterer Fall sind Anzeigefahrstraßen, die Zusi nur stellt, wenn der Zug auch anzeigegeführt ist.
- Carsten Hölscher
- Administrator
- Beiträge: 33448
- Registriert: 04.07.2002 00:14:42
- Wohnort: Braunschweig
- Kontaktdaten:
Re: Deadlock auffinden
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.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.
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.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
- Johannes
- Beiträge: 3203
- Registriert: 14.03.2009 22:36:06
- Aktuelle Projekte: Zusitools (http://git.io/zusitools)
Re: Deadlock auffinden
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.Carsten Hölscher hat geschrieben: ↑02.01.2021 20:02:23 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.
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