Seven Concurrency Models in Seven Weeks

Jeder Programmierer, der die Leistungsfähigkeit heutiger Computer ausschöpfen möchte, muss sich zwangsläufig mit Parallelverarbeitung beschäftigen. Denn anders als noch vor zwanzig Jahren werden Computersysteme nicht mehr (nur) dadurch schneller, dass die Taktfrequenzen von Prozessor und Speichereinheiten immer weiter nach oben geschraubt werden. Beschleunigung findet heute vor allem durch Hinzufügen weiterer Recheneinheiten und Optimierung der Kommunikation dieser mit dem Speicher statt. Um das Potenzial auszuschöpfen, muss die Software in der Lage sein, diese Möglichkeiten der Parallelverarbeitung zu nutzen.

In der Anfangszeit wurden hierzu vor allem Mechanismen der Betriebssysteme genutzt, während die Programme an sich weiterhin sequentiell arbeiteten. Später gab es Erweiterungen für gängige Programmiersprachen in Form von Bibliotheken oder Präcompilern, die Parallelverarbeitung mehr oder weniger umständlich ermöglichten. Heute gibt es zahlreiche Sprachen mit direkter Unterstützung für parallele und nebenläufige Programmierung in der Sprache. Die Sprachen folgen dabei verschiedenen Konzepten und Programmiermodellen.

Mit Seven Concurrency Models in Seven Weeks ist das dritte Buch aus der “Seven” Reihe im O’Reilly Verlag erschienen. Den Anfang machten Programmiersprachen, danach folgten Datenbanken und nun Nebenläufigkeitsmodelle.

Das Buch beginnt mit einem Einführungskapitel, in dem zunächst mit den Begrifflichkeiten aufgeräumt wird. Wichtigster Inhalt ist hier die Unterscheidung zwischen concurrent (nebenläufig) und Parallel. Während mit Parallelismus die gleichzeitige Ausführung von Rechenschritten auf entsprechend geeigneter Hardware bezeichnet wird, bedeutet Nebenläufigkeit die logische Unabhängigkeit verschiedener Programmteile. Nebenläufigkeit bezieht sich also auf die Problemstellung, Parallelismus auf die Umsetzung der Lösung. In diesem Buch geht es um beides; dass nur die Nebenläufigkeit ihren Weg in den Buchtitel gefunden hat, begründet der Autor humorvoll mit dem begrenzten Platz auf dem Cover.

Wie in der Serie üblich gliedert sich das Buch nach einer Einleitung in sieben Hauptkapitel, in denen jeweils ein Nebenläufigkeitsmodell vorgestellt wird. Dieses ist unterteilt in drei Abschnitte, die Tage. Am ersten Tag wird das Modell einführend dargestellt, am zweiten Tag tiefer beleuchtet und am dritten geht es in die Feinheiten.

Das Buch ist als Lehrbuch konzipiert, welches von vorne nach hinten durchgearbeitet werden sollte. Auch wenn die für die Beispiele verwendeten Programmiersprachen teilweise (absichtlich) sehr exotisch gewählt wurden, sind die Beispiele gut nachvollziehbar; der Autor macht klar, dass es mehr um die Konzepte und weniger die konkreten Details der Implementierung geht. Eine gewisse Vorliebe des Autors für funktionale Sprachen ist nicht zu übersehen, weshalb diese bevorzugt eingesetzt werden. Die meisten Beispiele lassen sich aber mit etwas Phantasie leicht auf verbreitete imperative Sprachen übertragen. Als Nachschlagewerk eignet sich das Buch eher nicht, da es im Lehrbuch-Stil zwischen den Nebenläufigkeitsmodellen, den Programmiersprachen und Beispielen hin und her springt und es viele implizite Querbezüge zu früheren Kapiteln gibt.

Im folgenden eine kurze Beschreibung der sieben Wochen und der jeweils vorgestellten Modelle.

Threads und Locks

In der ersten Woche geht es um Threads und Locks, also Nebenläufigkeit/Parallelität mit Threads und Synchronisation des Datenaustausches über Sperrmechanismen (Locks). Dieses Modell bildet die technische Grundlage vieler anderer Modelle. Denn Threads werden von allen relevanten Betriebssystemen unterstützt und bilden die Grundlage für die Verteilung der Aufgaben auf mehrere CPUs oder CPU-Kerne. Den Zugriff auf gemeinsam genutzte Ressourcen wie den Hauptspeicher oder I/O Register schützen Sperrbefehle, die bei aktuellen CPUs Teil des Befehlssatzes sind. Die meisten der an den späteren Tagen beschriebenen Nebenläufigkeitsmodelle bauen in ihrer praktischen Implementierung auf Threads und Locks auf.

Der Autor zeigt die Verwendung von Threads und Locks exemplarisch mit der Sprache Java und spart dabei nicht an Kritik an diesem Modell. Viele der Beispiele werden zunächst fehlerhaft implementiert, um zu illustrieren, wie leicht man in Fallen laufen kann. Im einzelnen werden Race Conditions (unsynchronisierter paralleler Zugriff auf gemeinsame genutzte Ressourcen), Deadlocks (Blockierungen durch gegenseitiges Warten auf Sperren) und Lifelocks (Endlosschleifen durch wiederholtes Sperren und Freigeben von Locks in einer nicht gewünschten Reihenfolge) behandelt. Es werden aber auch Lösungen zu den kritisierten Gefahren präsentiert und insbesondere auf die umfangreichen Funktionen eingegangen, die zum Lieferumfang neueren Java-Versionen gehören.

Anhand eines größeren Beispiels wird schließlich gezeigt, dass Nebenläufigkeit nicht zwangsläufig zu Parallelität führt. Es werden verschiedene Variationen eines Algorithmus’ und ihre Auswirkung auf den Speedup, also die Beschleunigung in Relation zur Anzahl der verfügbaren Recheneinheiten, gezeigt.

Funktionale Sprachen

Die Betrachtung der Nebenläufigkeitsmechanismen in funktionalen Sprachen bildet das Thema des zweiten Tages. Da funktionale Sprache in der Regel keine Seiteneffekte wie etwa die Änderung einer globalen Variable unterstützen, lassen sich bestimmte Dinge wie iterative oder verkettete Funktionsaufrufe oft automatisch parallelisieren. Durch geringfügige Modifikation eines zunächst rein seriellen Programmes lässt sich so bereits ein messbarer Speedup erzielen.

Als Sprache für den zweiten und dritten Tag wurde Clojure gewählt. Clojure ist ein Dialekt der Sprache Lisp, des Urvaters der funktionalen Programmierung, und läuft in der Java Virtual Machine. Eine mit Clojure mitgelieferte Bibliothek bietet parallele Versionen zahlreicher Funktionen der Sprache. Die ersten beiden Tage der zweiten Woche beschäftigen sich mit Parallelität in Clojure. Am dritten Tag geht es um die Formulierung von Nebenläufigkeit, speziell die Möglichkeiten, Code in Threads auszulagern und bei Bedarf ausführen zu lassen.

Nebenläufigkeit durch Trennung von Zustand und Identität

Die dritte Woche widmet sich diesem etwas sperrigen Titel. Es geht im wesentlichen darum, Mechanismen aus der ersten Woche in einer funktionalen Sprache wie Clojure zu nutzen. Dabei wird am ersten Tag zunächst das Konzept Atom vorgestellt, eine Variable, die sich atomar, d.h. ohne der Gefahr von Race Conditions und Deadlocks, verändern lässt. Atome sind sehr leistungsfähig und können mit Zusatzfunktionen wie Validators (Prüfung auf Einhaltung von Konsistenzregeln) oder Watchers (Trigger, die bei Verändungen ausgelöst werden) ausgestattet werden. Der zweite Tag widmet sich Agents. Diese sind den Atomen sehr ähnlich, sehen aber eine asynchrone (blockierungsfreie) Benutzung vor, die lediglich im Hintergrund serialisiert wird.

Das Highlight dieses Kapitels bildet Software Transaktional Memory, gemeinsame Datenstrukturen im Hauptspeicher, deren Zugriff mit ACI Garantien (Atomic, Consistens, Isolated) geschützt ist. Bis auf die Durability sind das die ACID Eigenschaften relationaler Datenbanken. Am Ende gibt es wenigstens einen kurzen Hinweis darauf, dass Transaktionaler Speicher keine Eigenheit von Clojure ist, sondern auch in vielen anderen Sprachen und Programmierumgebungen bereit steht, beispielsweise als Bibliothek für die Sprachen der GNU Compiler Collection (GCC), dem Standardcompiler der meisten Linux-Distributionen.

Das Aktorenmodell

Richtig interessant wird es ab der vierten Woche. Mit dem Aktorenmodell wird ein generelles theoretisches Modell für nebenläufige Programmierung vorgestellt. Es ist unabhängig von einer speziellen Programmiersprache oder einem Programmierparadigma (funktional, imperativ, objektorientiert). Einige Sprachen wie Erlang oder Elixir unterstützen das Aktorenmodell direkt, viele andere über Bibliotheken.

Beim Aktorenmodell geht es darum, Programmcode in Form von unabhängigen Teilen, den Aktoren, zu formulieren. Die Aktoren laufen nebenläufig auf dem System und kommunizieren mit Hilfe von Nachrichten. Jeder Aktor hat eine Mailbox, über die Nachrichten ihn erreichen können. Nachrichten werden in FIFO (first in, first out) Reihenfolge ausgeliefert. Nachrichten sind asynchron und werden vom System in einer potenziell beliebig langen Queue zwischengespeichert, bis sie zur Auslieferung kommen. Aktoren müssen nicht im selben Prozess oder Adressraum laufen, sondern können sogar über verschiedene Computer im Netzwerk verteilt sein.

Mit dem Aktorenmodell ist das Paradigma “Let it Crash” verbunden. Aktoren können an andere Aktoren gekoppelt werden und werden dann benachrichtigt, wenn in einem Aktor ein Fehler auftritt. Auf diese Weise lassen sich normaler Ablauf und Fehlerbehandlung voneinander trennen. Das Paradigma besagt, bei (möglichst) vielen Fehlerklassen die Aktoren kontrolliert abstürzen zu lassen und dann neu zu starten und den Fehler an übergeordneter Stelle zu analysieren und zu protokollieren.

Communicating Sequential Processes

Das Modell der Communicating Sequential Processes (CSP) teilt sich mit dem Aktorenmodell die selbe Grundidee, die nebenläufige Ausführung verschiedener Codeteile, die über Nachrichten kommunizieren. Damit enden jedoch weitgehend die Gemeinsamkeiten. Beim CSP liegt der Fokus nicht auf den Prozessen, sondern den Kommunikationskanälen. Kanäle können von einem oder mehreren Prozessen zum Lesen und/oder zum Schreiben genutzt und sogar über andere Kanäle verschickt werden. Sie sind normalerweise synchron, d.h. der Sender blockiert solange, bis ein Empfänger die Nachricht liest. Es ist jedoch auch möglich, gepufferte Kanäle zu verwenden, die eine (begrenzte) Anzahl von Nachrichten zwischenspeichern können.

CSP wurden bereits in den 70er Jahren erdacht, haben aber in den letzten zwei Jahren enorm an Popularität gewonnen, hauptsächlich wegen der Integration in die Sprache Go. Das Buch zeigt CSP jedoch mit Clojure, wo sie in Form einer Makrobibliothek zur Verfügung stehen. Diese ist noch relativ jung und gilt noch nicht als stabil. Nach einigen allgemeinen Beispielen wird ein nebenläufiger Webservice auf Basis von CSP vorgestellt. Mit Hilfe von ClojureScript, einem Clojure-to-Javascript Crosscompiler, kann dabei auch die Clientseite nebenläufig implementiert werden.

Datenparallelität

Für die bisher vorgestellten Nebenläufigkeitsmechanismen gilt der Grundsatz, dass Nebenläufigkeit nicht das gleiche, aber eine Voraussetzung für Parallelität ist. Diese Aussage gilt am sechsten Tag nicht mehr. Hier geht es um das Prinzip Single Instruction, Multiple Data (SIMD), also der gleichartigen Anwendung von Rechenoperationen auf mehrere Daten. SIMD führte in der IT lange Zeit ein Schattendasein, bis es zum Arbeitsprinzip leistungsfähiger intelligenter Grafikkarten wurde und seither in jedem modernen PC integriert ist.

Für die Programmierung von SIMD Berechnungen hat sich die Sprache OpenCL durchgesetzt und wird daher für die Beispiele im Buch verwendet. Es werden zunächst einfache mathematische Operationen mit Vektor- und Matrizen behandelt und dabei auch gezeigt, wie Optimierungen und Fehlerbehandlung in OpenCL erfolgen. Der dritte Tag beinhaltet eine einfache physikalische Simulation der Bewegung einer Wasseroberfläche, wenn ein Tropfen darauf fällt.

Big Data

Unter dem geheimnisvollen Namen Lambda Architektur führt die siebte Woche in die Welt der Big Data Algorithmen. Diese werden als eine Generalisierung des SIMD Prinzips auf massiv parallele Rechnercluster und Architekturen betrachtet, über die Aufgaben auf Basis sehr großer Datenmengen (im Petabyte-Bereich) verteilt werden.

Als de-facto Standard für Big Data Berechnungen diente jahrelang das MapReduce Framework, dessen bekannteste Implementierung das Projekt Apache Hadoop ist. Eine MapReduce Berechnung besteht aus zwei Phasen. In der ersten Phase werden die Eingabedaten analysiert und umsortiert (Map), so dass sich eine sinnvolle Gruppierung für die zweite Phase ergibt. In der zweiten Phase werden die gruppierten Datenblöcke zu einem Ergebnis verarbeitet (Reduce). Für die Speicherung der Zwischenergebnisse, die oft genauso groß oder sogar größer als die Eingabedaten sind, werden Key-Value Datenspeicher verwendet, beispielsweise das Hadoop Filesystem (HDFS).

Hadoop ist in Java geschrieben, Map/Reduce Funktionen können jedoch in vielen verschiedenen Sprachen implementiert werden. Für die Beispiele im Buch wird ebenfalls Java verwendet. Der erste Tag behandelt das typische Standardbeispiel für MapReduce Algorithmen, das Zählen von Wörtern in großen Texten. An den beiden folgenden Tagen werden der Batch Layer und der Speed Layer von Hadoop vorgestellt, mit deren Hilfe sich größere BigData Probleme strukturieren und in Bezug auf Aktualität und Latenzen optimieren lassen.