Visualisierung von Prozesssynchronisation mit Semaphoren

Abstract

In der Informatik wird Parallelprogrammierung einerseits eingesetzt, um reale, parallele Prozesse in Software abzubilden, andererseits, um komplexe Rechenaufgaben auf verschiedene Rechnerknoten oder auch Prozessorkerne zu verteilen und sie damit effizienter zu bewältigen. Im Gegensatz zu sequenziellen Programmen sind parallele Algorithmen jedoch schwerer zu verstehen, da mehrere Prozesszustände gleichzeitig betrachtet werden müssen. Auch Fehlerquellen wie Race Conditions oder Deadlocks erschweren das Entwickeln von parallelen Algorithmen.<br />Das Ziel dieser Diplomarbeit ist es, ein Visualisierungstool für parallel ablaufende Programme (Tasks) zu entwerfen. Diese Tasks sollen wie Prozesse eines Betriebssystems voneinander unabhängig laufen und über einen gemeinsamen Speicher und Synchronisationskonstrukte (Semaphore) kommunizieren können. Der Ablauf der Programme soll vom Benutzer gesteuert werden können und der Zustand der einzelnen Tasks, der Semaphore und des gemeinsamen Speichers geeignet visualisiert werden. Als Hilfsmittel für die Untersuchung eines Algorithmus, der Locks verwendet, soll das Tool um ein Analyseverfahren erweitert werden, das Deadlocksituationen erkennt und visualisiert. Das Tool soll für didaktische Zwecke, z.B. für Vorlesungen wie "Betriebssysteme", geeignet sein.<br />Das zentrale Ergebnis der Arbeit ist die Implementierung des Visualisierungstools, eine plattformübergreifende Desktopsoftware, die auf einer Open-Source-Hostingplattform veröffentlicht wurde.<br />Taskprogramme werden darin mit der simpel aufgebauten Programmiersprache Lua beschrieben. Zugriffe auf den gemeinsamen Speicher (z.B. SHM.varx =42) und die Semaphore (z.B. SHM.SEM.wait('l')) sind durch einfache Anweisungen im Programmcode möglich. Mit Debugging-Befehlen wie Run, Step und Stop bzw. mit Breakpoints im Codeeditor kann der Programmfluss, wie von Standard-IDEs bekannt, gesteuert werden. In der Benutzeroberfläche wird der gemeinsame Speicher mit den Semaphoren in einer Baumstruktur visualisiert und alle Taskprogramme nebeneinander dargestellt, um zu jedem Zeitpunkt den gesamten Zustand des untersuchten Algorithmus erfassen zu können.<br />Für die Deadlockanalyse wurden zwei Laufzeitanalyseverfahren, die in dieser Arbeit ausführlich beschrieben werden, ausgewählt und implementiert. Die Verfahren zeichnen während der Ausführungszeit Lockgraphen auf und suchen innerhalb dieser Graphen nach Zyklen, die potenzielle Deadlocksituationen darstellen.<br />

In computer science, parallel programming is used to model real-world, parallel processes in software. In addition, parallel programming is used to distribute computational tasks over cluster nodes or processor cores to increase efficiency of their computation. In contrast to sequential programs, parallel algorithms are more challenging to understand because it is necessary to follow many different process states. Issues like race conditions or deadlocks make it also difficult to write parallel algorithms.<br />The aim of this diploma thesis is to design a visualization tool for parallel programs (tasks). Like processes in an operating system, these tasks should run independently and be able to communicate using shared memory and synchronization primitives (semaphores). The user should be able to control the execution of the programs. The state of the individual tasks, semaphores and the shared memory should be visualized in a clear manner. To support the user examining an algorithm containing locks, the tool should contain an analysis method to detect and visualize deadlock potentials. One aim of this tool is to use it for academic purposes, e.g. in the "operating systems" lecture.<br />The principal outcome of this thesis is the implementation of the visualization tool, a platform independent desktop software, published on an open source hosting platform. Task programs can be written in the simple programming language Lua. It offers an easy access to the shared memory (e.g. SHM.varx =42) and to the semaphores (e.g.<br />SHM.SEM.wait('l')) in the program code. Debugging commands like Run, Step, or Stop and breakpoints can be used to control the program flow, similar to most standard IDEs. The user interface displays the shared memory and the semaphores in a tree structure and simultaneously shows all running task programs to provide information about the whole state of the executed parallel algorithm to the user.<br />To implement the deadlock analysis, two runtime analysis methods have been chosen and are described in detail in this thesis. Basically, they record lock graphs during the execution of the task programs in order to search for lock cycles within these graphs.