Nebenlunge

Nebenläufigkeit bezeichnet das Verhältnis von Ereignissen, die nicht kausal abhängigsind, die sich also nicht beeinflussen. Ereignisse sind nebenläufig, wenn keines eine Ursachedes 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 relativistischenBegriff der Gleichzeitigkeit, der im Kausalitätsprinzipbegründet ist (siehe Relativität der Gleichzeitigkeitund Happened-Before). Man kann sich das anhand eines Minkowski-Diagrammsverdeutlichen: 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 Sequentialisierungder Ereignisse benutzt werden kann.

Dies macht man sich zum Beispiel in der Netzwerktechnikzunutze, da hier die Kausalordnungnur durch die Übermittlung von Nachrichtendefiniert ist: zur Sequentialisierung von verteilten Prozessen werden hier Logische Uhreneingesetzt, die den relativistischen Zeitbegriff widerspiegeln.

Planung

Man kann das Konzept der Nebenläufigkeit nicht nur auf die Betrachtung von Ereignissen anwenden, sondern auch zur 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 Pseudocodemit (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 Computerkönnten diese Befehle jeweils parallel ausgeführt werden. Einige moderne CPUssind sogar in der Lage, solche Situationen zu erkennen und einzelne Befehle gleichzeitig in verschiedenen Teilen des selben Prozessors auszuführen (siehe Pipeline-Architektur).

Parallele Programmierung

Daraus ergibt sich ein etwas weniger strenger Begriff der Nebenläufigkeit, wie er häufig in der Programmierungverwendet wird: Nebenläufigkeit bezeichnet dort die Eigenschaft von Programmcodenicht linearhintereinander ausgeführt zu werden, sondern parallelausführbar zu sein.

Oder anders gesagt: Zwei Transaktionen oder Prozesse/Threadssind genau dann parallelisierbar, wenn die parallele, verzahnte oder verdrehte Ausführung zum selben Resultat führt wie das sequentielle Ausführen. (Parallelisierbarkeit).

Die Nebenläufigkeit von mehreren unabhängigen Prozessenbezeichnet man als Multitasking; Nebenläufigkeit innerhalb eines Prozesses als Multithreading. In den Frühzeiten der Computerentwicklung waren auch reine Time-Sharing-Systeme weit verbreitet, die eine Nebenläufigkeit auf Benutzerebene ermöglichten.

Sobald die einzelnen Prozesse oder Threadsaber 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 eine so genannte Verklemmung(deadlock), wenn zwei Abläufe gegenseitig aufeinander warten (bzw. sich gegenseitig blockieren). Zur Lösung dieser Problematik werden verschiedene Techniken herangezogen:

Der Kontextjedes Programmteilsmuss vor unerwarteter Veränderungdurch andere Teile geschützt werden (Synchronisierung). Soll ein gemeinsamer Zugrifffür Datenrealisiert werden, dann muss der Zugriff synchronisiert werden, z.B. durch gegenseitigen Ausschluss (Mutex) unter Benutzung von Monitorenoder 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 Verklemmungen (ganz im Gegenteil).

Besonders wichtig sind solche Techniken in verteilten Systemen, vor allem um die Integritätvon verteilten Transaktionenzu gewährleisten.

Auf Einprozessorsystemen führt parallele Programmierung nur dann zu einer Verkürzung der effektiven Ausführungszeit, wenn die einzelnen Threads bzw. Prozesse viel Zeit mit warten verbringen (z.B. blockiert an einem Lockoder Monitor). Aufgrund des zusätzlichen Verwaltungsaufwandes ergeben sich zum Teil sogar Geschwindigkeitsnachteile. Um parallele Programmierung voll auszunutzen, sind mehrere Ausführungseinheiten nötig. Technologien dafür sind Simultaneous Multithreading(SMT), z.B. Hyper-Threading(HTT), Symmetrisches Multiprocessing(SMP), z.B. mittels Multicore-Prozessoroder mehrerer CPUs. Den Extremfall bildet das Massively Parallel Processingmit zum Teil mehreren tausend Prozessoren.

Weitere Informationen

Siehe auch

• Nichtsequentielle Programmierung
• Multithreading
• Paralleler Algorithmus
• Synchrone Kommunikation
• Asynchrone Kommunikation

Literatur

• Peter Ziesche: Nebenläufige & verteilte Programmierung, W3L, 2004, ISBN 3937137041
• 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-2en:Parallel programming

es:Programación paralela fr:Parallélisation

Dieser Artikel basiert auf dem Artikel aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation.
In der Wikipedia ist eine Liste der Autoren verfügbar.