Nebenläufigkeit

aus Wikipedia, der freien Enzyklopädie

Nebenläufigkeit liegt vor, wenn mehrere Ereignisse in keiner kausalen Beziehung zueinander stehen, 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.

[Bearbeiten] Kausalordnung

Beispiel von nebenläufigen Aktionen

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 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.

[Bearbeiten] Planung

Beispiel zur kausalen Abhängigkeit

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 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 Prozessors auszuführen (siehe Pipeline-Architektur).

[Bearbeiten] Siehe auch

• Parallele Programmierung
• Paralleler Algorithmus
• Multithreading
• Synchrone Kommunikation
• Asynchrone Kommunikation
• Philosophenproblem
• Race Condition

[Bearbeiten] 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-2