Parallelität und Asynchronität

Freitag und Samstag war ich auf dem Architecture Open Space 2010, wo ich an vielen interessanten Sessions teilnehmen durfte. Lars hat eine spannende Session zum Thema (A)Synchronität und CQS initiiert. Während der Diskussion kam unter anderem die Frage nach dem Unterschied von Parallelität und Asynchronität auf, für die — wie Jörg zurecht anmerkt — auch meiner Meinung nach keine zufriedenstellende Antwort gefunden werden konnte. Ich möchte daher aus meiner Sicht im Nachgang an die Session hier kurz nochmal den Unterschied abstrakt darstellen.

Warnung: Ich werde mich einiger Notationen aus dem π-Kalkül bedienen. Aus formaler Sicht und mit direktem Bezug zum π-Kalkül sind die nachfolgenden Betrachtungen nicht ganz sauber. Sie sollen lediglich einem programmiersprachenunabhängigen Abstraktionsniveau dienen.

Parallelität

Gehen wir zunächst davon aus, dass wir einen Prozess P haben. Unter einem Prozess verstehe ich hier eine Abstraktion eines unabhängigen Kontrollflusses.
Ein Prozess P kann vereinfacht ausgedrückt nichts tun (und sich anschließend beenden) oder eine Aktion a ∈ Act ausführen und anschließend einen weiteren Prozess ausführen. Nachfolgend werden Großbuchstaben P, Q für Prozessnamen genutzt die Kleinbuchstaben a, b, c für Aktionen.

Ein Prozess kann daher durch folgende Grammatik dargestellt werden:
P ::= a.P | 0

Wenn ein Prozess P = a.P' eine Aktion a ausführt, kommt er danach in einen Zustand P'. Wir können das durch folgende Regel beschreiben:
a.P' --> P'

Ein solcher Prozess beschreibt einen ganz simplen Automaten, dessen Zustände durch Prozessausdrücke (a.P', P') definiert werden und die Zustandsübergänge durch Aktionen (a) definiert sind. Offensichtlich werden diese Aktionen immer nacheinander bzw. sequentiell ausgeführt und es ergibt sich ein entsprechender Trace.
Beispielsweise ist der Trace für den Prozess a.b.c.0 gleich traces(a.b.c.0) = {a -> b -> c}.
Parallelität kommt ins Spiel, wenn man zwei solcher Prozesse gleichzeitig betrachtet, diese also nebenläufig abgearbeitet werden. Um das zu beschreiben, kann o.g. Grammatik um einen Paralleloperator (||) erweitert werden:
P ::= P||P | a.P | 0

Die Tatsache, dass voneinander unabhängige Kontrollflüsse ausgeführt werden, kann durch weitere Regel beschrieben werden:
1) Wenn P --> P' dann gilt: P || Q --> P' || Q
2) Wenn P --> P' dann gilt: Q --> Q' falls P = Q und P' = Q'

Zwei Prozesse können sich somit unabhängig voneinander entwickeln. Dies schlägt sich entsprechend in den Traces nieder. Fasst man zwei Prozesse a.b.0 und c.0 z.B. als Funktionen auf, die in unterschiedlichen Threads eines Programms ausgeführt werden, so würden sich die folgenden möglichen Traces für das gesamte Programm ergeben: traces(a.b.0 || c.0) = {a -> b -> c, a -> c -> b, c -> a -> b}

Asynchronität

Die ursprüngliche Frage war nun, worin der Unterschied zwischen Parallelität und Asynchronität besteht. Aus meiner Sicht beschreibt Parallelität die zuvor beschriebene unabhängige Ausführung mehrerer Prozesse. (A)Synchronität kommt ins Spiel, wenn zwei solcher Prozesse miteinander kommunizieren wollen. Dies kann prinzipiell synchron oder asynchron geschehen. Um dies zu erläutern wird obige Grammatik um Kommunikationskanäle, die mit Kleinbuchstaben x, y, z abgekürzt werden, ergänzt. Nachfolgend beschreibe x<> das Senden einer Nachricht über den Kanal x und x() das Empfangen einer Nachricht über den Kanal x. Außerdem können Kanäle über Kanäle gesendet werden. x<y> beschreibt das Senden des Kanals y über den Kanal x. x(y) beschreibt das Empfangen des Kanals y über Kanal x. Außerdem können neue Kanäle erzeugt werden (new z), wobei ein neu erzeugter Kanal immer nur in einem bestimmtem Prozess gebunden ist. Die o.g. Grammatik verändert sich entsprechend wie folgt:
P ::= new x(P) | x().P | x<>.P | x(y).P | x<y>.P | P||P | a.P | 0

Zur Beschreibung der Kommunikation zwischen zwei Prozessen sind folgenden zwei Regeln relevant:

1. x<>.P || x().Q --> P || Q
2. x<y>.P || x(z).Q --> P || {y/z}Q

Dabei meint {y/z}Q, dass in Q alle z durch y ersetzt werden.

Ein synchroner Aufruf eines Prozesses P durch Q (Q sync P) kann wie folgt modelliert werden:
Q sync P ::= new z(Q) || P mit Q = y<z>.z().Q' und P = y(x).P'.x<>

Man kann sich z.B. P als eine Funktion vorstellen, die von Q aufgerufen wird. Dabei ruft Q die Funktion auf und blockiert dann solange bis P seine Aktionen P' ausgeführt hat. Erst im Anschluss kann Q seine Aktionen Q' ausführen. Dieses spiegelt sich auch in den Traces der Aktionen wieder:
traces(Q sync P) = {p' -> q' | ∀p' ∈ traces(P'), ∀q' ∈ traces (Q')}

Ein asynchroner Aufruf benötigt in der Praxis hingegen in aller Regel die Mithilfe eines dritten Prozesses, z.B. einer MessageQueue oder eines ThreadPools. Die Notation !P :== P || !P beschreibt die unendlich parallele Ausführung eines Prozesses P. Außerdem seien die Kleinbuchstaben t(hread), e(xecute), j(oin), r(eturn) weitere Bezeichner für Kommunikationskanäle. Der dritte Prozess ENV kann demnach wie folgt modelliert werden:
ENV = !(new r(t(e).e<r>.r().0))

Ein asynchroner Aufruf eines Prozesses P durch Q (Q async P) kann dann wie folgt modelliert werden:
Q async P :== Q || P mit Q = t<y>.Q'.0 und P = y(z).P'.z<>.0

Man kann sich P als eine Funktion vorstellen, die von Q aufgerufen wird. Diesmal bedient sich Q allerdings mittels t<y> einem ThreadPool und kann daher seine Aktionen Q' direkt nach dem Starten des Threads ausführen. Der Thread aktiviert P, so dass P und Q unabhängig voneinander ausgeführt werden. Auch hier sieht man dies in den Traces der Aktionen:
traces(Q async P) = traces(Q || P)

Möchte man dem Prozess Q zusätzlich die Möglichkeit einräumen auf die Beendigung von P zu reagieren, ist dies wie folgt modellierbar:
ENV = !(new r(t(e,j).e<r>.r().j<>.0)) || !(new r(t(e).e<r>.r().0))

Q asyncjoin P :== new z(Q) || P mit Q = t<y,z>.Q'.z().Q''.0 und P = y(x).P'.x<>.0

Die Traces der Aktionen sehen wie folgt aus: traces(Q asyncjoin P) = {o' -> q'' | ∀o' ∈ traces(Q' || P'), q'' ∈ traces(Q'')}

Betrachtet man die Definition der Traces von async(join), stellt man fest, dass diese nicht ohne Parallelität auskommen. Aus meiner Sicht ist daher Asynchronität von Parallelität abhängig, in dem Sinne, dass Asynchronität die Möglichkeit der Ausführung unabhängiger Kontrollflüsse voraussetzt. Parallelität beschreibt diese unabhängige Ausführung; (A)Synchronität bezieht sich hingegen auf die Kommunikationsweise zwischen diesen unabhängigen Kontrollflüssen.