Nebenläufigkeit
Nebenläufigkeit bezeichnet das Verhältnis von Ereignissen, die nicht kausal abhängig sind, die sich also nicht beeinflussen. Ereignisse sind nebenläufig, wenn keines eine Ursache des anderen ist. Oder anders ausgedrückt: Aktionen können nebenläufig ausgeführt werden (sie sind parallelisierbar), wenn keine das Resultat der anderen benötigt. Ein Modell, das diese Abhängigkeiten sehr gut wiedergibt, sind Petri-Netze.
Kausalordnung
Die Nebenläufigkeit beschreibt einen relativistischen Begriff der Gleichzeitigkeit, der im Kausalitätsprinzip begründet ist (siehe Relativität der Gleichzeitigkeit und Happened-Before). Man kann sich das anhand eines Minkowski-Diagramms verdeutlichen: Ein Ereignis ist nebenläufig zu einem anderen, wenn es im Anderswo des anderen Ereignisses liegt. Das heißt, das eine Ereignis befindet sich weder in der Zukunft noch in der der Vergangenheit des anderen, bzw. keines der Ereignisse ist Ursache oder Wirkung des anderen. Die drei Relationen "ist Ursache von", "ist Wirkung von" und "ist nebenläufig zu" definiert die Kausalordnung, eine Halbordnung, die zu einer Sequentialisierung der Ereignisse benutzt werden kann.
Dies macht man sich zum Beispiel in der Netzwerktechnik zunutze, da hier die Kausalordnung nur durch die Übermittlung von Nachrichten definiert ist: zur Sequentialisierung von verteilten Prozessen werden hier Logische Uhren eingesetzt, die den relativistischen Zeitbegriff widerspiegeln.
Planung
Man kann das Konzept der Nebenläufigkeit nicht nur auf die Betrachtung von Ereignissen anwenden, sondern auch zu Planung von Aktionen: Dabei wird festgelegt, welche Aktion eine Voraussetzung einer anderen ist. Die Nebenläufigkeit ist dann so definiert, dass zwei Aktionen nebenläufig sind, wenn keine von ihnen Voraussetzung der anderen ist. Auf Grund der sich daraus ergebenden Halbordnung lassen sich dann Abläufe planen, optimieren und gegebenenfalls parallelisieren. Als Beispiel (nicht das gleiche wie in der Abbildung!) hier ein kleines Programm in Pseudocode mit (Zeilennummern):
Z1 a= 2; Z2 b= 3; Z3 p= a + b; Z4 q= a * b; Z5 r= q - p; |
Die (kausalen) Abhängigkeiten ergeben sich dadurch, welches Kommando das Ergebnis eines anderen benötigt. Insbesondere sind die folgenden Zeilen-Paare (potentiell) nebenläufig, weil nicht eine von dem Ergebnis der anderen abhängt: Z1 || Z2 und Z3 || Z4. Auf einem Massiv-Parallelen Computer könnten diese Befehle jeweils parallel ausgeführt werden. Einige moderne CPUs sind sogar in der Lage, solche Situationen zu erkennen und einzelne Befehle gleichzeitig in verschiedenen Teilen des selben Prozessorts auszuführen (siehe Hyperthreading).
Parallele Programmierung
Daraus ergibt sich ein etwas weniger strenger Begriff der Nebenläufigkeit, wie er häufig in der Programmierung verwendet wird: Nebenläufigkeit bezeichnet dort die Eigenschaft von Programmcode nicht linear hintereinander ausgeführt zu werden, sondern parallel ausführbar zu sein. Die Nebenläufigkeit von mehreren unabhängigen Prozessen bezeichnet man als Multitasking; Nebenläufigkeit innerhalb eines Prozesses als Multithreading.
Sobald die einzelnen Prozesse oder Threads aber untereinander kommunizieren, sind sie streng genommen nicht mehr als Ganzes nebenläufig (sie beeinflussen sich ja) - nur noch einzelne Teilabläufe sind zueinander nebenläufig. Wenn nun die Reihenfolge der Ausführung der Kontaktpunkte (oder Kommunikationspunkte) nicht entsprechend vorgegeben ist, können sich daraus Konflikte ergeben, insbesondere so genannte Deadlocks wenn zwei Abläufe gegenseitig aufeinander warten (bzw. sich gegenseitig blockieren). Zur Lösung dieser Problematik werden verschiedene Techniken herangezogen:
Der Kontext jedes Programmteils muss vor unerwarteter Veränderung durch andere Teile geschützt werden (Synchronisierung). Soll ein gemeinsamer Zugriff für Daten realisiert werden, dann muss der Zugriff synchronisiert werden, z.B. durch gegenseitigen Ausschluss (Mutex) unter Benutzung von Monitoren oder von Semaphoren. Alternativ kann auch verlangt werden, dass bestimmte Aktionen von zwei Prozessen gemeinsam ausgeführt werden, mit so genannten Rendezvous. Eine weitere sichere Art der Kommunikation sind Warteschlangen. Diese Techniken lösen das Problem des gleichzeitigen Zugriffs auf Ressourcen, verhindern jedoch keine Deadlocks (ganz im Gegenteil).
Besonders wichtig sind solche Techniken in verteilten Systemen, vor allem um die Integrität von verteilten Transaktionen zu gewährleisten.
Weitere Informationen
Siehe auch
Literatur
- Douglas Schmidt, Michael Stal, Hans Rohnert, Frank Buschmann: Pattern-orientierte Softwarearchitektur, Muster für nebenläufige und vernetzte Objekte, dpunkt 2002, ISBN 3-89864-142-2