Nebenläufigkeit

Beim Philosophenproblem (engl. Dining Philosophers Problem) handelt es sich um ein Fallbeispiel aus dem Bereich der Theoretischen Informatik.

Die Nebenläufigkeit, mitunter auch Parallelität (englisch concurrency) genannt, ist in der Informatik die Eigenschaft eines Systems, mehrere Aufgaben, Berechnungen, Anweisungen oder Befehle gleichzeitig ausführen zu können. Es kann sich dabei um völlig unabhängige Anweisungen handeln, bis hin zur gemeinsamen Bearbeitung einer Aufgabe. Sie können dabei auch miteinander interagieren (z. B. um Zwischenergebnisse auszutauschen).

Die Operationen können dabei nur scheinbar nebenläufig (parallel), beispielsweise im sogenannten Multitasking, auf einem Prozessor ausgeführt werden oder auch echt nebenläufig, beispielsweise auf einem Mehrkernprozessor oder auf einem Rechnerverbund bestehend aus mehreren getrennten und über ein Netzwerk verbundenen Computern. Die Grenze zum Parallelrechner im eigentlichen Sinne ist bei den Ansätzen zur echten Parallelität fließend.

Nebenläufige Prozesse können u. a. durch Parallel Random Access Machines, Message passing oder Petri-Netze beschrieben und analysiert werden.

Engere Begriffsauffassung

Mitunter wird auch exakter unterschieden zwischen „nebenläufiger Behandlung“ (englisch concurrency) und „Parallelverarbeitung“ (englisch parallelism): Die nebenläufige Behandlung wird dann vor allem als ein Konzept verstanden, reale Vorgänge abzubilden, das auch sinnvoll ist, wenn zur Ausführung nur ein einziger CPU-Kern zur Verfügung steht; im Gegensatz dazu fokussiert in diesem Begriffsverständnis die Parallelverarbeitung auf echt-gleichzeitige Mehrkern-Berechnung meist eines Problems.

Parallelisierbarkeit und Serialisierbarkeit

Sind Ablaufschritte so voneinander abhängig, dass sie in einer festen Reihenfolge nacheinander ausgeführt werden müssen, sodass es nicht möglich ist, sie nebenläufig auszuführen, dann sind sie nicht parallelisierbar. Müssen Abläufe echt-gleichzeitig stattfinden, so dass es absolut keine Möglichkeit gibt, sie nacheinander auszuführen, so sind sie nicht serialisierbar.

Die Parallelisierbarkeit zweier oder mehrerer Abschnitte oder Iterationen eines Ablaufs oder von Ereignissen ist die Beurteilung, ob diese nebenläufig ausgeführt/berechnet werden können, ohne zu einem abweichenden Resultat zu führen.

„Aktionen können nebenläufig ausgeführt werden, wenn keine das Resultat des anderen benötigt.“

– Wolfgang Schröder-Preikschat: Vortrag „Systemprogrammierung: Prozesssynchronisation: Nichtsequentialität“

Die Programmabschnitte dürfen also nicht kausal voneinander abhängen. Anders ausgedrückt sind mehrere Transaktionen oder Prozesse/Threads genau dann parallelisierbar, wenn die parallele, verzahnte oder in umgekehrter Reihenfolge stattfindende Ausführung zum selben Resultat führt wie das sequentielle Ausführen.

Sind die Programmabschnitte (teilweise) voneinander abhängig, so müssen sie bezüglich dieser Abhängigkeiten synchronisiert werden, was eine Sequentialisierung (bzgl. dieser Abhängigkeit) bewirkt.

„Viele praxisrelevante Probleme besitzen Lösungsverfahren, die direkt in einen parallelen Algorithmus umgesetzt werden können. Man sagt in diesem Fall, daß das Problem eine natürliche Parallelität besitzt.“

– B. Monien, J. Schulze, S. Grothklags: „Parallele Algorithmen“

Verfahren zur Parallelisierung sind

• Binärbaummethode,
• list ranking,
• pointer doubling,
• parallel prefix,
• symmetry breaking.
• Gebietszerlegung (engl. domain decomposition)

Siehe auch

• Philosophenproblem
• Multitasking
• Parallele Programmierung
• Paralleler Algorithmus
• Race Condition

Literatur

• Peter Ziesche: Nebenläufige & verteilte Programmierung. W3L, 2004, ISBN 3-937137-04-1.
• 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.