Nebenläufigkeit

Grundbegriff und Ausprägungen

Nebenläufigkeit, auch Parallelität oder englisch concurrency genannt, ist die Eigenschaft eines Systems, mehrere Aufgaben, Berechnungen, Anweisungen oder Befehle gleichzeitig auszuführen. Die Aufgaben können unabhängig voneinander sein oder gemeinsam eine Aufgabe bearbeiten. Dabei können sie miteinander interagieren, etwa um Zwischenergebnisse auszutauschen.

Nebenläufigkeit kann nur scheinbar gleichzeitig sein: Beim Multitasking führt ein einzelner Prozessor verschiedene Aufgaben abwechselnd aus. Echt nebenläufige Ausführung findet dagegen beispielsweise auf einem Mehrkernprozessor oder in einem Rechnerverbund aus mehreren getrennten, über ein Netzwerk verbundenen Computern statt. Die Grenze zum Parallelrechner im eigentlichen Sinne ist bei echter Parallelität fließend. Zur Beschreibung und Analyse nebenläufiger Prozesse dienen unter anderem Parallel Random Access Machines, Message Passing und Petri-Netze. Das Philosophenproblem ist ein Fallbeispiel aus der Theoretischen Informatik.

Nebenläufigkeit und Parallelverarbeitung

In einer engeren Begriffsauffassung wird zwischen nebenläufiger Behandlung (concurrency) und Parallelverarbeitung (parallelism) unterschieden. Nebenläufigkeit ist dabei vor allem ein Konzept zur Abbildung realer Vorgänge. Sie ist auch sinnvoll, wenn nur ein einziger CPU-Kern zur Verfügung steht. Parallelverarbeitung bezeichnet in diesem Verständnis dagegen vor allem die echt gleichzeitige Berechnung auf mehreren Kernen, meist zur Bearbeitung eines Problems.

Parallelisierbarkeit, Abhängigkeiten und Verfahren

Parallelisierbarkeit beschreibt, ob zwei oder mehr Abschnitte, Iterationen oder Ereignisse nebenläufig ausgeführt werden können, ohne ein anderes Ergebnis zu erzeugen. Aktionen können nebenläufig ausgeführt werden, wenn keine das Resultat der anderen benötigt. Programmabschnitte dürfen daher nicht kausal voneinander abhängen. Mehrere Transaktionen, Prozesse oder Threads sind genau dann parallelisierbar, wenn ihre parallele, verzahnte oder umgekehrte Ausführung zum selben Resultat führt wie die sequentielle Ausführung.

Sind Ablaufschritte so voneinander abhängig, dass sie in einer festen Reihenfolge nacheinander ausgeführt werden müssen, sind sie nicht parallelisierbar. Teilweise abhängige Programmabschnitte müssen bezüglich dieser Abhängigkeiten synchronisiert werden; dadurch entsteht eine Sequentialisierung. Umgekehrt sind Abläufe nicht serialisierbar, wenn sie echt gleichzeitig stattfinden müssen und sich nicht nacheinander ausführen lassen.

Viele praxisrelevante Probleme besitzen eine natürliche Parallelität, wenn ihr Lösungsverfahren direkt in einen parallelen Algorithmus umgesetzt werden kann. Genannte Verfahren zur Parallelisierung sind die Binärbaummethode, list ranking, pointer doubling, parallel prefix, symmetry breaking und Gebietszerlegung (domain decomposition).

Ein modernes Anwendungsbeispiel ist die Distributed-Ledger-Technologie. Klassische Blockchains ordnen Transaktionen häufig sequentiell in einer Total Order. Neuere Ansätze wie das Cerberus-Protokoll verwenden dagegen partiell geordnete Graphen. Transaktionen, die unterschiedliche Objekte beziehungsweise Assets betreffen, sind nicht kausal voneinander abhängig und können deshalb echt nebenläufig verarbeitet werden. Theoretisch ist dadurch eine lineare Skalierbarkeit möglich.