- Titel
- Nichtblockierende Graphalgorithmen für zyklische Echtzeitsysteme
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:l189-qucosa2-1025603
- Datum der Einreichung
- 07.10.2025
- Abstract (DE)
- Parallele Zugriffe auf Datenstrukturen können in Echtzeitfähigen Systemen nicht mithilfe der klassischen, blockierenden Techniken synchronisiert werden, da diese dann ihre Zeitgarantien nicht erfüllen können. Graphen bieten vielfältige Anwendungsmöglichkeiten bei der Lösung algorithmischer Probleme. Um diese auch in parallelen Echtzeitsystemen nutzen zu können, wird ein nichtblockierender Graph entwickelt. Um die Korrektheit des Graphen bei paralleler Ausführung nachzuweisen, wird das Kriterium der Linearisierbarkeit verwendet. Im Gegensatz zu bisherigen Arbeiten, die sich mit nichtblockierenden Datenstrukturen beschäftigen, werden die erforderlichen Schnittstellen und Synchronisationen unabhängig von einer konkreten Datenstruktur entwickelt. Dazu werden diese mithilfe der Spezifikationssprache Object-Z dargestellt. Die in dieser Arbeit entwickelte Graphdatenstruktur ermöglicht paralleles Einfügen und Entfernen von Knoten und Kanten. Weiterhin kann parallel geprüft werden, ob bestimmte Knoten oder Kanten im Graphen enthalten sind. Es wird beispielhaft eine parallele Breitensuche spezifiziert, die durch den Einsatz eines Visitorpatterns flexibel zu weiteren Analysealgorithmen wie der Tiefensuche oder der Ermittlung der kürzesten Wege abgewandelt werden kann. Da viele Echtzeitsysteme nicht über eine Garbage-Collection verfügen, werden die Möglichkeiten zur Speicherverwaltung analysiert sowie eine mögliche Lösung präsentiert. Diese wird nicht formal spezifiziert. Für alle Methoden wird gezeigt, dass diese lock-free umsetzbar sind. Dadurch können diese durch eine vorgestellte Simulation wait-free umgesetzt werden. Das bedeutet, dass die Methoden unabhängig von parallelen Veränderungen im Graphen in endlich vielen Schritten beendet werden. Diese Eigenschaft ist notwendig, um die Datenstruktur in Echtzeitsystemen verwenden zu können.
- Freie Schlagwörter (DE)
- Linearisierbarkeit, Nichtblockierende Synchronisation, Wait-Free, Graph-Algorithmen, Object-Z
- Den akademischen Grad verleihende / prüfende Institution
- Hochschule für Technik, Wirtschaft und Kultur Leipzig, Leipzig
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:l189-qucosa2-1025603
- Veröffentlichungsdatum Qucosa
- 24.02.2026
- Dokumenttyp
- Masterarbeit / Staatsexamensarbeit
- Sprache des Dokumentes
- Deutsch
- Lizenz / Rechtehinweis
CC BY 4.0- Inhaltsverzeichnis
Abkürzungsverzeichnis 5 Symbolverzeichnis 6 1. Einleitung 7 2. Grundlagen 9 2.1. Dynamische Graphalgorithmen 9 2.2. Zyklische Echtzeitsysteme 10 2.3. Nebenläufige Systeme 11 2.3.1. Blockierende Synchronisation 12 2.3.2. Nichtblockierende Synchronisation 12 2.3.3. Multitasking IEC61131-3 13 2.4. Linearisierbarkeit 14 2.4.1. Formale Definition 15 2.4.2. Mehrzyklische Methoden 20 2.5. IEC61131-3 und TwinCAT 3 22 2.6. Atomare Primitive 23 2.7. Spezifikation mit Object-Z 24 2.7.1. Klassendefinition 25 2.7.2. Methoden 26 2.7.3. Typen in Object-Z 27 2.7.4. Operatoren 28 2.7.5. Generische Klassen 32 2.8. Notation in Pseudocode 32 3. Stand der Wissenschaft 34 4. Dynamische Graph-Datenstruktur 38 4.1. Formale Graphdefinition 39 4.2. Einfügen von Knoten 43 4.3. Einfügen von Kanten 44 4.4. Existenzprüfung von Knoten und Kanten 52 4.5. Entfernen von Knoten und Kanten 53 4.5.1. Logisches Entfernen 54 4.5.2. Physisches Entfernen 61 4.5.3. Speicherverwaltung 68 4.6. Breitensuche 71 4.6.1. Konzept zur Linearisierbarkeit 71 4.6.2. Zugriff auf Knoten und Kanten 72 4.6.3. Visitor-Konzept 74 4.6.4. Graphtraversierung 77 5. Transformation zu einer wait-free-Datenstruktur 81 5.1. Nachweis von Lock-freedom 82 5.2. Die Simulation von Wait-freedom 86 5.2.1. Normalisierte lock-free-Datenstrukturen 86 5.2.2. Hilfsmechanismus 87 5.2.3. Erfassen von Kollisionen 88 5.2.4. Transformation der Graphdatenstruktur 89 6. Fazit und Ausblick 91 Literatur 93 Algorithmenverzeichnis 97 Spezifikationsverzeichnis 98 A. Spezifikationen 99 A.1. Queue 99 A.2. BFS-Visitor 100 B. Algorithmen 102 B.1. Breitensuche 102