3  Concurrency

Dem englischen Begriff „Concurrency“ haftet durch seinen Wortstamm die passende Konnotation von miteinander um Ressourcen konkurrierenden Einheiten an, was den Kern des Concurrent Programming gut beschreibt. Die Threads eines Prozesses konkurrieren um die Ressourcen: die Daten, die der Prozess im Speicher vorhält. Clojure bietet (über die Mechanismen von Java hinaus) kein Werkzeug, um die Veränderungen der Welt außerhalb des eigenen Prozesses – in einem verteilten System – zu verarbeiten; Clojure konzentriert sich auf lokale Veränderungen im eigenen Prozess, die durch verschiedene Threads entstanden sein können.

Im November 2009 führte die TOP500 der schnellsten Computer der Welt der „Jaguar“ der Firma Cray an, der am Oak Ridge National Laboratory unter anderem bei der Suche nach neuen Energiequellen zum Einsatz kommt [69]. In diesem Rechner arbeiten mehr als 37 000 Prozessoren mit je sechs Kernen, also insgesamt mehr als 220 000 Prozessoreinheiten. Dabei blickt die Firma Cray auf eine lange Geschichte von Supercomputern zurück, seit der erste Computer dieser Firma, die Cray-1, 1976 in Betrieb genommen wurde. Die parallele Verarbeitung in Computern ist also kein wirklich neues Phänomen, wenngleich sie sich zu Beginn im High-End-Bereich abspielte.

3.1  Zustand und Zeit

Um die Lösungen von Clojure zu verstehen und sie sinnvoll einsetzen zu können, sind einige Sätze zu den Begriffen Zustand, Identität und Wert vonnöten, die Rich Hickey auf der Webseite von Clojure [29] ausführlich beschreibt und deren Bedeutung er als Video auf InfoQ [32] überzeugend präsentiert.

Eine Identität in diesem Zusammenhang ist eine logische Einheit, die im Laufe der Zeit verschiedene Zustände einnehmen kann. Ein Zustand einer Identität ist die Verknüpfung mit einem Wert zu einem bestimmten Zeitpunkt, und ein Wert schließlich ist eine unveränderliche Größe.

Bei Zahlen und Namen entspricht diese Anschauung noch der der meisten Programmierer. Es gilt aber, dieses Konzept auch auf zusammengesetzte Datentypen wie Listen, Vektoren oder Maps auszuweiten. Eine Liste mit den Zahlen Eins, Zwei und Drei wird immer diese Liste bleiben. Würde eine Vier hinzugefügt, entstünde eine neue Liste mit den Zahlen Eins, Zwei, Drei und Vier.

1. Betrachte den linken Fuß.
2. Ist der auf dem Boden, ist alles in Ordnung.
3. Ist der in der Luft, betrachte den rechten Fuß.
4. Ist der ebenfalls in der Luft, liegt ein Foul vor.

Offensichtlich sind aber das Rennen und die Bewegung des Läufers während der Messung weitergegangen (oder -gelaufen, je nachdem), so dass wir bei der Messung des Zustands des rechten Fußes nicht mehr voraussetzen können, dass der linke noch in der Luft schwebt. Genau das aber ist es, was die meisten unserer Programme heute tun. Sie nehmen an, die Welt steht still, solange sie selbst nicht weiter voranschreiten. Was wir brauchen, ist ein Snapshot, eine Fotografie des Läufers, die beide Füße gleichzeitig zeigt. Auf diesem Snapshot können wir dann in Ruhe die Auswertung durchführen und somit ein eventuell vorliegendes Foul sicher feststellen. Eine Lösung ohne Snapshot, sondern mit Locking-Mechanismen würde, übertragen auf das Beispiel, zu der unsinnigen Notwendigkeit führen, den Läufer vor der Prüfung seines Zustands zu bitten, er möge kurz innehalten. Speziell wenn er zu diesem Zeitpunkt gerade ein Foul beginge, würden wir in arge Probleme mit der Physik kommen. (Natürlich hinkt der Vergleich.)

Clojure gibt uns Werkzeuge, um Veränderungen an Identitäten im Laufe der Zeit zu handhaben. Diese Werkzeuge und deren Grundlagen werden in den nächsten Abschnitten beschrieben.

Wer mit Clojure erfolgreich sein möchte, muss sich dieses Gedankengut zu eigen machen und beim Design seiner Programme beachten. Wer das nicht tut, programmiert gegen die verwendete Programmiersprache und wird mit hoher Wahrscheinlichkeit nicht damit glücklich werden.

3.2  Besonderheiten der Datenstrukturen

Ein wesentlicher Bestandteil von Clojures Concurrency-Maschinerie sind die Datenstrukturen, die zuvor in Abschnitt 2.6.6 eingeführt wurden. Für das schlüssige Gesamtbild von Clojure sind zwei Eigenschaften dieser Datenstrukturen von großer Bedeutung. Zum einen sind die gespeicherten Informationen nicht mehr zu verändern, zum anderen ist die Implementation hinreichend geschickt, dass zu großer Overhead beim Kopieren vermieden wird.

3.2.1  Unveränderlichkeit

Datentypen in Clojure enthalten Werte. Werte sind, wie beschrieben, unveränderlich. Alle Daten in Clojure sind somit unveränderlich, immutable. Diese Feststellung ist von zentraler Bedeutung. Wenn ein Programm einer Liste einen Wert hinzufügen will, muss es eine neue Liste anlegen, in der alle alten Werte und der neue Wert enthalten sind. Wenn ein Programm zu einer zuvor gemerkten Zahl einen weiteren Wert addieren will, wird die Addition eine neue Zahl zurückliefern. Eine Zuweisung in der Form x = x + 2 ist für Clojures Datentypen nicht vorgesehen; für veränderliche Daten existieren spezielle Referenztypen.

Es widerspricht der Erfahrung – vor allem der objektorientierter Programmierer –, Zustandsinformationen nicht an vielen Stellen im Programm speichern zu sollen. Dennoch ist diese Eigenschaft für die Verteilung von Programmarbeit auf mehrere Threads essenziell, da auf diese Weise Nebenffekte sicher vermieden werden. Programmierer mit Erfahrungen im Bereich der funktionalen Programmiersprachen sind mit dem Umgang mit unveränderlichen Daten in der Regel vertraut; aber auch Java-Programmierer kennen beispielsweise unveränderliche Strings.

3.2.2  Hintergrund: Persistente Datenstrukturen

Bevor wir uns mit dem eigentlichen Inhalt dieses Abschnittes befassen, gilt es, die Verwendung des Begriffes „persistent“ zu erklären. In den meisten Fällen bedeutet „Persistieren“ das Speichern von Daten auf einen nichtflüchtigen Datenträger, meist eine Festplatte. Das geschieht entweder durch eine Datenbank, die zwischen der Festplatte und dem Programm vermittelt, oder aber direkt in Form von Dateien. Eine „persistente Datenstruktur“ hingegen hat mit Persistenz im Sinne von dem Erhalt der Werte auch nach einem Stromausfall nichts zu tun, sondern bezeichnet das beobachtete Verhalten, dass nach einer Manipulation der Datenstruktur auch die vorherige Version noch vorhanden ist [19]. In diesem Sinne sind Clojures persistente Datenstrukturen nichtflüchtig. Die von Sprachen wie Java oder C bekannten Datenstrukturen hingegen, die eine direkte Manipulation erlauben, sind flüchtig: Nach einer Manipulation ist die vorherige Version nicht mehr erreichbar.

Clojures Datenstrukturen sind unveränderlich, das Hinzufügen eines Wertes zu einer Liste von Werten erzeugt eine neue Datenstruktur. In einer naiven Umsetzung, die eine neue Datenstruktur durch eine vollständige Kopie erzeugt, könnte das sehr viel Speicher benötigen und die Performance spürbar negativ beeinflussen. Clojure begegnet dem Problem mit einer effizienten Organisation von persistenten Datenstrukturen, bei der sich die Datenstrukturen die im Speicher vorgehaltenen Werte teilen. Shared StructureWird einem Vektor mit zehn Werten ein weiterer Wert hinzugefügt, entsteht ein Vektor, der Verknüpfungen zu den ersten zehn Werten enthält und zusätzlich noch eine weitere Verknüpfung zum neuen Wert. Dieses Konzept, im Englischen mit „shared structure“ bezeichnet, verlangt nach einer effizienten Implementation und bildet dann die Grundlage dafür, dass Datenstrukturen bei akzeptabler Performance unveränderlich sein können. Umgekehrt kann eine solche Organisation des Speichers aber nur erfolgreich sein, wenn die referenzierten Daten unveränderlich sind, da sonst alle Änderungen überwacht und hinsichtlich der Verfügbarkeit für alle Verwendungen der Datenstruktur im Programm überprüft werden müssten.

Abbildung 3.1:

Bit-Vektor-Indizierung in persistenten Datenstrukturen

Das Beispiel in Abbildung 3.1 zeigt den Zugriff auf den Index 3008. In binärer Schreibweise ist das:

Die Tiefe des Baums ist drei, es werden also Indizes in drei Ebenen benötigt. Dabei kodieren die niedrigstwertigen Bits die letzte Ebene im Baum: den Zugriff auf die gespeicherten Werte. Clojure beginnt somit bei einem Baum mit drei Ebenen bei der dritten Fünfergruppe, im Beispiel 00010, was Zahl zwei kodiert, deren Auftreten im Knoten hervorgehoben ist. Für die zweite Ebene findet Clojure die Gruppe 11110, also den Index 30, in der Abbildung ebenfalls hervorgehoben, und für die dritte Ebene Index 0. In der dritten Ebene zeigt das gefundene Element schließlich auf den Dateninhalt, im Beispiel „Hello“.

Auf diese Art und Weise kann Clojure bis zu 32⁶ = 2³⁰ Werte in einer Datenstruktur speichern und einen Zugriff auf persistente Datenstrukturen innerhalb von (log ₃₂N) garantieren.

Abbildung 3.2:

Shared Structure: Weiterverwendung von Teilbäumen

Die tatsächliche Implementation enthält kleinere Abweichungen von diesem Prinzip, die der Verbesserung der Performance dienen. Diese bitpartitionierten Bäume liegen auch den Hash-Maps zugrunde, wenngleich dort etwas mehr Aufwand betrieben werden muss, um die Implementation praktikabel zu gestalten (Hash-Kollisionen, Performance und Speicherbelegung…).

3.3  Handhabung veränderlicher Identitäten

Zeit vergeht, Identitäten verändern sich. Das Ändern einer Datenstruktur an sich ist kein Problem. Erst wenn während der Änderung ein anderer Thread auf die Daten zugreift und durch die Bedingungen zur Laufzeit einen inkonsistenten Zustand vorfindet, ergeben sich Fehler. Diese Art von Fehlern ist von anderer Natur als die Fehler, die bei einem Singlethreaded-Programm auftreten. Sie sind deutlich schwerer zu reproduzieren, da sie sehr stark vom zeitlichen Ablauf der Programmteile abhängen.

3.3.1  Gängige Modelle

Die Informatik kennt die Probleme, die sich aus konkurrierenden Zugriffen auf geteilte Ressourcen ergeben, seit bald 40 Jahren und hat im Laufe der Zeit drei wichtige Modelle entwickelt und verfeinert, um dieser Probleme Herr zu werden. Der aktuelle Abschnitt stellt diese Modelle vor, ohne jedoch zu sehr in die Tiefe zu gehen. In der Literatur finden sich zahlreiche detaillierte Beschreibungen. Die Artikel der Wikipedia zu diesen Themen [82][81][80] sind ein guter Anfangspunkt, von dem aus in die weitergehende Fachliteratur eingestiegen werden kann.

Locking

Das am weitesten verbreitete Modell, um den Zugriff von verschiedenen Threads auf geteilte Ressourcen zu koordinieren, ist Locking. Dabei wird der Zugriff auf eine Ressource kurzzeitig während einer Änderung gesperrt, bis wieder ein Konsistenter Zustandkonsistenter Zustand herrscht. Um das Auslesen inkonsistenter Zustände zu vermeiden, wird unter Umständen sogar während des Lesens der Zugriff für andere Programmteile gesperrt. Dieses Lösungsverfahren beruht historisch darauf, dass frühe Erfahrungen mit Concurrency nur mit einer Simulation erfolgten, die tatsächlich auf nur einer Recheneinheit stattfand. In dem Szenario erscheint eine Lösung, die einen exklusiven Zugriff regelt, sinnvoll, da ohnehin nie ein wirklich gleichzeitiger Zugriff erfolgen kann.

Locking ist in allen nennenswerten Programmiersprachen vorhanden, und sehr viele Programmierer verfügen bereits über Erfahrungen damit. Zudem erlaubt es eine sehr direkte Steuerung, da der Entwickler die Kontrolle über alle Locks hat. Doch Locking korrekt zu implementieren, ist schwierig – vor allem unter Berücksichtigung aller möglicher Fehlerszenarien und bei Einsatz von mehreren Prozessorkernen.

Korrektes Concurrent Programming mit Locks ist möglich, aber schwierig in der Umsetzung. Da Javas Technologien für Concurrency in Clojure verwendet werden können, stehen somit auch Locks in Clojure zur Verfügung.

Aktoren

Eine alternative Möglichkeit für die Kontrolle des Zugriffs auf eine geteilte Ressource ist das Aktoren-Modell, das beispielsweise in der Programmiersprache Erlang [4] eine zentrale Rolle spielt. Wesentlich für dieses Modell ist, dass die zahlreichen Programmeinheiten keine Ressourcen miteinander teilen, sondern sich die jeweiligen Daten zusenden. Ein Aktor ist eine Einheit, die Nachrichten empfangen und darauf entweder durch Versenden neuer Nachrichten an andere Aktoren, durch Veränderung seines internen Zustands oder auch durch Erzeugen weiterer Aktoren reagieren kann. Eine solche Einheit kann durch einen Prozess, einen Thread oder etwas Vergleichbares dargestellt sein. Alle Reaktionen können dabei in beliebiger Reihenfolge oder auch parallel erfolgen.

Software Transactional Memory

Datenbanken koordinieren seit langer Zeit konkurrierende Zugriffe auf die in ihnen gespeicherten Daten. Das Mittel der Wahl sind dort Transaktionen, deren wichtigste Eigenschaft es ist, dass sie entweder ganz oder gar nicht stattfinden. Im Datenbankumfeld ist dieses Verfahren erprobt, und der Gedanke liegt nahe, diese Technologie auf Daten im Speicherbereich eines Programms anzuwenden. Transaktionen in einer Datenbank weisen vier wichtige Eigenschaften auf:

A

Sie sind atomar (atomic), das heißt, egal wie viele Daten in einer Transaktion manipuliert werden, von außen betrachtet erfolgen alle Änderungen, wenn überhaupt, dann in einem einzigen Schritt.

C

Sie sind konsistent (consistent). Die Daten, die eine Transaktion selbst zu Gesicht bekommt, befinden sich ebenfalls in einem konsistenten Zustand, sowohl am Start der Transaktion als auch am Ende.

I

Sie sind isoliert (isolated). Änderungen, die innerhalb einer Transaktion an den Daten erfolgen, sind nicht von außen sichtbar, bevor die Transaktion nicht (erfolgreich) beendet wird.

D

Sie sind dauerhaft (durable), das heißt, wenn eine Transaktion erfolgreich beendet wurde, sind die Daten auf ein Medium (die Festplatte) gesichert, das eine Störung in Form von Software- oder Hardwarefehlern übersteht.

Das Verfahren basiert auf einer Transaktionsmaschinerie, die gleichzeitigen Transaktionen jeweils einen eigenen Zugriff auf die zu manipulierenden Daten gewährt, alle agieren lässt und erst, wenn eine Transaktion signalisiert, dass sie fertig ist, entscheidet, was zu tun ist. CommitDen abschließenden Schritt, der die Manipulation der Daten einer Transaktion auch für andere Programmteile manifestiert, nennt man Commit. Diesen Abschluss kann von gleichzeitigen Transaktionen nur eine durchführen: diejenige, die zuerst ihren Commit versucht. Alle anderen müssen in der Regel ihre Arbeit erneut beginnen. Wiederholungen: Keine NebeneffekteDiese Wiederholungen stellen eine wichtige Anforderung an die Funktionen, die in einer Transaktion durchgeführt werden: Sie dürfen keine Effekte haben, die nicht zurücksetzbar sind. Meist bedeutet das, dass sie keine Nebeneffekte haben dürfen. Reine Funktionen erfüllen diese Anforderung.

3.3.2  Indirekte Referenzen

Clojure lädt dazu ein, sich genau zu überlegen, an welchen Stellen es sinnvoll ist, Zustände zu speichern. Alleine das kann schon helfen, robustere Programme zu schreiben, die sich besser auf mehrere Prozessoren verteilen lassen. Dennoch bleibt die Notwendigkeit, die Veränderung mancher Identitäten über die Zeit zu verwalten. Es ist notwendig, das Fortschreiten der Zeit außerhalb eines Threads zu modellieren. Das Mittel zur Lösung sind hier indirekte Referenzen. Es ist gängige Praxis, dass ein Programm Referenzen auf die Daten hält. In Clojure sind diese aber vor Konflikten durch das Fortschreiten der Zeit, also Manipulation durch andere Programmteile, durch ihre Unveränderlichkeit geschützt. Um eine Identität mit einem Zustand zu versehen, erzeugt der Programmierer eine weitere Referenz auf einen beliebigen Datentyp aus Clojures Ensemble.

Abbildung 3.3:

Indirekte Referenzen

Abbildung 3.3 zeigt, wie sich indirekte Referenzen vorteilhaft auf ein Programm auswirken können. Im linken Teil der Abbildung ist dargestellt, wie üblicherweise mit gespeicherten Daten vorgegangen wird. Das Programm hält eine Referenz auf einen Block, in dem sich die Daten, im Beispiel die Namen von Mitgliedern der Lisp-Sprachenfamilie, befinden. Ob dieser Block ein Speicherbereich und die Referenz ein Zeiger, wie in C, oder aber der Block ein Objekt ist, spielt dabei keine Rolle. Wichtig ist, sich zu verdeutlichen, dass es keinen einfachen und direkten Weg gibt, diese Daten atomar, also in einem einzigen Schritt, zu verändern. Das gilt nicht nur für zusammengesetzte Datenstrukturen; schon das Verändern des primitiven Datentyps long in Java ist nicht unbedingt ein atomarer Vorgang.

3.4  Referenztypen

Clojure implementiert vier Referenztypen mit unterschiedlichen Eigenschaften, die sich damit für verschiedene Anwendungsfälle empfehlen:

• Var
• Atom
• Ref
• Agent

Allen ist gemein, dass die durch sie referenzierten Daten veränderlich sind. Wie im Abschnitt über indirekte Referenzen (3.3.2) beschrieben, verändern sich dabei aber nicht die Daten selbst, es wird lediglich eine Referenz von einem Wert auf einen anderen umgehängt. Als referenzierte Information sind Clojures unveränderliche Datentypen vorgesehen, Java-Objekte sind für diesen Einsatz in der Regel nicht geeignet.

Wir verwenden in diesem Text durchgehend die englischen Bezeichnungen, da wir diese als Fachbegriffe betrachten. Im Folgenden werden wir zunächst diese Typen beschreiben, um dann abschließend eine zusammenfassende Betrachtung und einen Vergleich dieser Typen zu liefern.

3.4.1  Var

Die bereits in Abschnitt 2.7.1 beschriebenen Vars sind ebenfalls Referenztypen und haben ein definiertes Verhalten im Multithreading-Kontext. Sie unterscheiden sich jedoch von den noch vorzustellenden drei anderen Typen. So werden sie nicht explizit dereferenziert, und Änderungen des enthaltenen Wertes gelten immer nur lokal pro Thread, sind also nicht in anderen Threads sichtbar. Damit entfällt die Notwendigkeit der Koordination konkurrierender Zugriffe. Beispielhaft wurde das Verhalten von Vars im Kontext mehrerer Threads im Abschnitt 2.7.4 beschrieben.

3.4.2  Atom

Clojure stellt mit dem Typ Atom einen Referenztypen bereit, der einen beliebigen Datentyp aus Clojures Portfolio aufnehmen kann. Dafür verwendet es unter der Haube eine AtomicReference aus java.util.concurrent.atomic. Zur Erzeugung eines Atom dient die Funktion atom, die den zu referenzierenden Wert als Argument erwartet:

Das folgende Beispiel zeigt die Verwendung von reset!. Es legt ein Atom an, dereferenziert es mit deref, setzt den Wert neu und zeigt den neuen Wert durch Dereferenzieren mit der Read-Syntax.

In diesem Beispiel spielt sich das Entscheidende in der Funktion packe-ein-thread ab, in der der Aufruf von swap! an einen neuen Thread mit einer variablen Verzögerung delegiert wird. Die Update-Funktion ist in diesem Falle die Funktion str, die die ihr übergebenen Strings zusammenfügt. Da die Update-Funktion als erstes Argument den aktuellen Wert des Atom bekommt und als weitere Argumente die, die an swap! übergeben wurden, bewirkt dieser Ausdruck letztlich, dass an den String im Atom koffer verschiedene Strings angehängt werden. Somit liest sich der Ausdruck mit swap! im Einzelnen wie folgt:

1. swap! ändert den Wert eines Atom,
2. koffer ist das zu ändernde Atom,
3. str ist die Update-Funktion, der swap! als erstes Argument den aktuellen Wert übergibt, und
4. ding sowie ", " sind weitere Argumente, die alle an die Update-Funktion übergeben werden.

Also wird str unter der Haube in der Form

aufgerufen, so dass ding an den aktuellen Kofferinhalt angehängt wird.

Die Funktion koffer-packen konzertiert das ganze Szenario und ruft die Thread-erzeugende Funktion packe-ein-thread mit den einzupackenden Dingen und verschiedenen Verzögerungen auf. Die Manipulation in den Threads erfolgt atomar, es kann also keine Konflikte beim Zugriff aus verschiedenen Threads geben. Zudem finden lesende Zugriffe, die das Beispiel nicht explizit demonstriert, jederzeit einen konsistenten Zustand vor.

Das Atom countdown dient als primäres Atom, dessen Veränderungen untersucht werden sollen, während aufrufe einen Zähler für die Aufrufe bereitstellt. Die Funktion tick simuliert das Ticken des Countdowns und liefert den aktuellen Wert um eins verringert zurück. Vorher jedoch erhöht sie den Wert des Aufrufzählers. Erfolgreiche Änderungen an countdown führen also zum Runterzählen des Countdowns und zum Hochzählen des Aufrufzählers, während nicht erfolgreiche Durchläufe nur den Aufrufzähler erhöhen. Die Iteration mit dotimes startet die tick-Funktion jeweils in einem neuen Thread. Nach Ablauf dieser Schleife enthält countdown wie zu erwarten den Wert 0, es gab also exakt 1000 erfolgreiche Läufe, der Aufrufzähler aufrufe hingegen zeigt, dass 76 Kollisionen beim Verändern zu einer Wiederholung geführt haben.

3.4.3  Ref

Wenn es darum geht, mehrere Werte koordiniert zu verändern, kommt mit der Ref ein weiterer Referenztyp ins Spiel. Ein klassisches Beispiel ist eine Überweisung bei einer Bank, bei der ein Betrag von einem Konto abgehoben und einem anderen Konto gutgeschrieben wird. (In der Praxis scheint dieses häufig verwendete Beispiel zumindest aus Sicht der Bankkunden wenig relevant, tauchen doch die überwiesenen Beträge teilweise mit mehreren Tagen Verspätung erst auf dem Zielkonto auf. Wir Kunden lesen also sehr wohl einen Zustand, in dem das Geld vom Quellkonto verschwunden und auf dem Zielkonto noch nicht angekommen ist.) Refs werden mit der Funktion ref angelegt, die – wie im Falle eines Atom auch – den zu referenzierenden Wert übergeben bekommt:

Dabei unterscheiden sich alter und commute nicht in ihrer Signatur.

Interessant wird es erst, wenn die STM-Maschinerie etwas mehr Arbeit in Form von mehreren zu koordinierenden Refs bekommt. Im Folgenden demonstriert dies ein Beispiel, das zwei Refs von einem Thread aus einige Male liest und von einem anderen schreibt.

Dieses Beispiel ähnelt dem in Abschnitt 2.7.4, in dem das dynamische Verhalten von Vars demonstriert wurde. Nach drei Lesevorgängen wechseln beide Refs ihren Wert vom ersten Thread aus betrachtet gleichzeitig von 1 zu 2. Dieses Verhalten ist sicher, und beliebig viele Ausführungen werden nie einen inkonsistenten Zustand lesen.

An einem etwas ausführlicheren Beispiel zeigen wir die Verwendung von alter und starten auch hier einen separaten, immer wieder lesenden Thread. Zunächst die Anlage der Refs:

Abschließend sorgt ein Aufruf von do am REPL-Prompt dafür, dass die Hilfsfunktionen mit verschiedenen Werten in eigenen Threads aufgerufen werden. Die Sleep-Zeiten der Threads sind so aufeinander abgestimmt, dass die Ausgabe möglichst lesbar bleibt und die Effekte der STM-Maschinerie sichtbar werden.

Hier wird die dereferenzierende Funktion wiederholt, da zwischenzeitlich ein schreibender Zugriff auf die Ref erfolgte. Beim zweiten Dereferenzieren bemerkt die Transaktion den schreibenden Zugriff und löst die Wiederholung aus.

Demgegenüber wird bei Verwendung von ensure die schreibende Funktion wiederholt, da ihr Commit durch die noch laufende Transaktion behindert wird:

Die drei Wiederholungen von brennen sind durch die Sleep-Zeiten verständlich. Die erste Wiederholung wartet bis 600 ms, die zweite bis 1200 ms und die dritte bis 1800 ms. Erst die vierte Wiederholung der schreibenden Funktion ist erfolgreich, da dann die 2000 ms der Transaktion, die ensure aufgerufen hat, abgelaufen sind.

3.4.4  Agent

Der Referenztyp Agent bietet die Möglichkeit, Änderungen am verknüpften Wert asynchron und serialisiert durchzuführen. Die Berechnung erfolgt in einem anderen Thread, und die Änderungen integrieren sich in das Transaktionssystem der Refs.

Agents bieten sich somit für Anwendungsfälle an, in denen das Aktualisieren einer Ressource nicht zeitkritisch ist; etwa wenn sich eine aufwendige Rechnung auf viele Prozessoren verteilt und ein separater Thread gelegentlich den Fortschritt grafisch darstellen soll. Gleichermaßen sind sie für Informationen geeignet, deren Änderungen eine Queue-Semantik besitzen sollen.

An der aufrufenden Stelle im Programm wird sofort weitergearbeitet, ohne das Resultat der Aktion abzuwarten, die an einen separaten Thread aus einem dedizierten Thread-Pool weitergereicht wird.

Das folgende Beispiel demonstriert die Verwendung eines Vektors von Strings als Wert im Agent. Dieser Vektor wird – mit Hilfe von send und conj – mit einer wachsenden Anzahl von Strings gefüllt. Ein dedizierter Thread übernimmt das Senden an den Agent, und ein zweiter Thread überwacht zehnmal die Anzahl der enthaltenen Strings.

Eine interessantes Muster ist das Senden einer Aktion aus der Aktion selber. Auf diese Weise kann ein System von sich gegenseitig oder selber immer wieder aufrufenden Agents erstellt werden, eine Multithreading-Rekursion. Das nächste Beispiel zeigt exemplarisch ein solches Verfahren. Die Funktion zeige-thread-action sendet sich selber wieder an den Agent *t-1000*. In diesem Falle wird ein benannter Agent verwendet, die Funktion könnte aber auch die Var *agent* verwenden. Das ausführliche Beispiel in Abschnitt 3.8 setzt ebenfalls self-calling Agents ein und verwendet dabei *agent*.

Fehlerbehandlung

Die asynchrone Natur von Agents macht es notwendig, Fehlerszenarien besonders zu behandeln. Konnten bei Atoms noch Exceptions aus einer Update-Funktion entstehen, die im Code an der Stelle, die das Update ausgelöst hat, behandelt werden können, ist das bei Agents nicht mehr der Fall. Der Grund dafür ist schlicht, dass ihre Updates zu einem späteren Zeitpunkt in einem anderen Thread ausgeführt werden. Die auslösende Funktion aber kann, ohne zu warten, weiterarbeiten.

Im Modus :fail verwirft der Agent das Update, behält also den alten Wert und akzeptiert darüber hinaus keine weiteren Aktionen.

Etwas weniger streng verhalten sich Agents, deren Fehlermodus mit Hilfe von set-error-mode! auf :continue gesetzt wurde. In diesem Falle verwirft der Agent einfach das Update und verhält sich so, als wäre das Update nie begonnen worden.

Beide Eigenschaften, Fehlermodus und Error-Handler, können bei der Anlage eines Agent auch als Keyword-Argumente übergeben werden.

Das folgende Beispiel stellt dar, wie eine Rückruffunktion aufgerufen wird und welche Argumente sie bekommt. Dazu wird eine Funktion als Aktion an einen Agent geschickt, die lediglich eine Exception wirft.

Beispiel: Produzenten und Verbraucher

Ein klassisches Beispiel für die Synchronisierung mehrerer Threads ist die Interaktion zwischen Programmteilen, die Daten erzeugen, und anderen, die diese weiterverarbeiten. Für solche Szenarien bieten sich Agents vor allem durch ihr serielles Verhalten an.

Eine denkbare Anwendung ist das Parsen von Logdateien: Ein Programmteil liest ein zeilenbasiertes Format ein, ein anderer ermittelt die gewünschten Statistiken. Der Gewinn durch Parallelisierung hängt hier stark von der verarbeitenden Funktion ab, kann auch durch die I/O-Leistung limitiert sein.

Im Vergleich zu den üblichen Implementationen gibt es hier keine explizite blockierende Queue oder andere Synchronisationsmechanismen, die Kommunikation zwischen dem synchron im Hauptthread laufenden Produzenten und der asynchronen Verarbeitung geschieht einzig durch die Funktion send.

3.4.5  Validierung

Das Transaktionssystem der Refs und die atomare Behandlung von Änderungen implementieren das „A“ und „I“ der ACID-Transaktionseigenschaften, „D“ kann bei Transaktionen im Speicher, also ohne Persistenzschicht, nicht erfüllt werden. Die Sicherstellung der Konsistenz, das „C“, erfüllen die Datentypen Atom, Ref und Agent, indem sie bei der Anlage eine Funktion, die die Validierung vornimmt, akzeptieren. Ein einfaches Beispiel ist die Prüfung des Typs, etwa einer ganzen Zahl.

Natürlich lassen sich hier auch beliebige andere Funktionen angeben, die alle ein Argument, den zu testenden neuen Wert, akzeptieren müssen:

Wenn die Definition eines Referenztypen bereits erfolgt ist, kann auf die Validierungsfunktion mit den Funktionen get-validator und set-validator! zugegriffen werden. Erstere liefert die Funktion zurück, zweitere setzt sie erneut. Im Beispiel mit den Ordnungszahlen könnte ein anerkannter wissenschaftlicher Durchbruch eine neue Validierungsfunktion notwendig machen.

3.4.6  Watcher

Alle vier Referenztypen unterstützen in Clojure 1.2 sogenannte Watcher. Es handelt sich dabei um Funktionen, die bei Änderungen am Referenztypen aufgerufen werden. Watcher werden mit der Funktion add-watch angelegt und mit remove-watch wieder entfernt. Die Dokumentation dieser Funktionen kennzeichnet sie ausdrücklich als Alpha-Versionen, so dass wir von einer tiefergehenden Beschreibung absehen. Ein ganz kurzes Beispiel zeigt die generelle Funktionsweise.

Watcher eignen sich beispielsweise für die Protokollierung von Änderungen und – mit Abstrichen – auch für das Speichern einer Datenstruktur auf einem nichtflüchtigen Medium. Das letztgenannte Verfahren ist aber ausdrücklich nicht transaktionssicher.

3.4.7  Zusammenfassung

Clojures Daten sind unveränderlich bis auf die Referenztypen und aus Java importierte Objekte. Die Unveränderlichkeit der Daten bringt im Zusammenspiel mit anderen Technologien Vorteile. Wenn wirklich Daten verändert werden müssen, um den Verlauf von Zeit zu modellieren, bietet Clojure hierfür mit den Referenztypen verschiedene Vorgehensweisen.

Eine Hilfestellung für die Entscheidung, welcher Referenztyp für das vorliegende Problem geeignet ist, gibt die folgende Gegenüberstellung der verschiedenen Typen.

Atom

Atoms koordinieren Thread-übergreifend Lesen und Schreiben eines einzelnen Werts. Änderungen sind in anderen Threads sichtbar. Zum Zugriff auf den Wert wird das Atom dereferenziert.

Ref

Refs verhalten sich weitgehend so wie Atoms. Allerdings erlaubt Clojure durch Einsatz von STM die konsistente Manipulation mehrerer Refs.

Agent

Agents arbeiten asynchron und seriell. Dadurch wird die Fehlerbehandlung aufwendiger. Auch bei ihnen erfolgt der Zugriff durch Dereferenzieren.

Var

Vars unterscheiden sich von den drei anderen Referenztypen wesentlich. Der Zugriff auf ihren Inhalt erfolgt implizit, es ist kein Dereferenzieren notwendig. Änderungen gelten nur lokal pro Thread, es findet keine Kommunikation mit anderen Threads statt. Ihr Einsatzzweck ist primär ein Container für benannte Objekte wie Funktionen, Makros oder Werte. Durch die Eigenschaft der dynamischen Variablenbindung erlauben sie Einflussnahme auf die Arbeitsweise einer Funktion neben der Parameterübergabe.

3.5  Threads

Die Referenztypen spielen die zentrale Rolle bei der Koordination von Zugriffen auf geteilte Informationen. Damit es überhaupt etwas zu koordinieren gibt, muss die Anwendung separate Threads erzeugen und die zu verrichtende Arbeit auf diese verteilen. Dieser Abschnitt befasst sich mit der Erzeugung von Threads und wie sich auf den grundlegenden Mechanismen andere Konzepte entwickeln lassen. Die Methoden zur Erzeugung lassen sich grob nach ihrer Herkunft und ihrer Verwendung gruppieren.

• Direkter Zugriff auf das Portfolio von Java,
• Funktionen aus dem Angebot von Clojure,
• Parallelisierung.

Die beiden erstgenannten zielen dabei eher auf Multithreading zur gleichzeitigen Bearbeitung verschiedener Jobs, während sich die letzte mit der Verteilung einer Aufgabe auf mehrere Prozessoren beschäftigt.

3.5.1  Methoden von Java

Die einfachste Art, einen Thread zu erzeugen, die auch bereits mehrfach Verwendung gefunden hat, ist die Erzeugung einer Instanz von Thread. Typische Java-Anwendungen leiten entweder eine eigene Klasse von Thread ab oder aber implementieren das Interface Runnable und dort die Methode run. Clojures Funktionen gehen den zweiten Weg und können somit an einen Thread übergeben werden. Als Beispiel dient eine Funktion, die aus dem aktuellen Thread einige Parameter liest und ausgibt.

Im Thread der REPL angewendet, zeigt sie dessen Namen, ID und Priorität:

Andere Threads bekommen einen automatischen Namen und eine neue ID:

Auf Wunsch kann dem Thread auch ein dedizierter Name gegeben werden. Das folgende Beispiel verwendet das Makro doto, um Wiederholungen der Instanz-Variable zu vermeiden. Dies wird in Abschnitt 4.1.1 beschrieben.

Da Clojure den direkten Zugriff auf Java-Klassen und -Methoden erlaubt, steht es Clojure-Entwicklern frei, sich für eine dieser Methoden zu entscheiden. Dann gilt es allerdings, alle Nebeneffekte zu beachten, die bei Verwendung solcher Thread-Pools und Services auftauchen können. Die JDK-Dokumentation enthält Hinweise darauf, welche Aktivitäten in welcher Reihenfolge durchgeführt werden. Somit erscheint die direkte Verwendung solcher Pools wenig typisch für Clojure-Programme.

In diesem Beispiel wird explizit ein eigener Thread-Pool mit drei enthaltenen Threads angelegt. Zu Beginn ist dieser, wie der Aufruf von getPoolSize zeigt, noch leer, es ist aber Raum für bis zu drei Threads, was getMaximumPoolSize anzeigt. Im Anschluss wird auf dem aktuellen, dem REPL-Thread, die Funktion print-th-info einmal mit Hilfe von execute ausgeführt. Danach enthält der Pool einen Thread. Um dem Pool etwas Arbeit zu geben, erzeugt repeat eine Sequence, die fünfmal die Funktion print-th-info enthält, und übergibt diese durch den Aufruf von invokeAll an den Pool. Die folgenden Zeilen enthalten die Ausgabe, an der erkenntlich wird, wie weitere Threads für die Arbeit erzeugt werden. Abschließend hat der Pool seine maximale Größe erreicht.

3.5.2  Clojures Future

Vollkommen ohne explizites Thread-Handling kommt die Methode future aus. Mit ihrer Verwendung drückt der Programmierer aus, dass er einen Programmteil irgendwann in einem anderen Thread ausgeführt wissen möchte. Das Resultat kann durch DereferenzierenDereferenzieren der Var zu einem beliebigen späteren Zeitpunkt erfolgen. Sollte das Ergebnis bis dahin noch nicht feststehen, wird der dereferenzierende Ausdruck blockieren, bis das Ergebnis vorliegt.

3.5.3  Parallelisierung

In der Einleitung zu diesem Kapitel wurden die zwei verschiedenen Arten der Concurrency genannt: parallele Verarbeitung unabhängiger Teile eines Jobs und parallele Bearbeitung verschiedener Jobs. Die bisher vorgestellten Methoden zur Erzeugung von Threads fokussieren auf die letztgenannte Variante.

Dieses wenig hintergründige Beispiel verwendet Ad-hoc-Funktionen, um den Aufruf und das Resultat von pcalls zu demonstrieren. In realen Projekten wird man eher die zu lösende Aufgabe in separate Teilaufgaben zerlegen, deren parallel berechnete Ergebnisse abschließend wieder zusammengefügt werden. Dann hilft pcalls bei der parallelen Verarbeitung eines Jobs, wobei der Programmierer – im Gegensatz zum einfachen pmap – explizit die Aufteilung vornimmt.

3.6  Transiente Datenstrukturen

Clojures Datentypen sind – wie in Abschnitt 3.2.1 beschrieben – im Allgemeinen unveränderlich. Operationen wie zum Beispiel das Hinzufügen eines Elements zu einem Vektor erzeugen eine neue Vektorinstanz, die viele ihrer internen Datenstrukturen mit dem ursprünglichen Vektor teilt.

Der Startwert einer Transienten kann eine beliebige Datenstruktur sein, auch eine bereits gefüllte. Dann werden die ursprünglichen Inhalte weiterverwendet und manipuliert, wobei das Original selbstverständlich unverändert bleibt.

Die Implementation von Clojure garantiert, dass die Umwandlung einer transienten in eine persistente Datenstruktur in konstanter Laufzeit erfolgt, also nicht mit der Elementanzahl steigt.

Allerdings ist der Overhead der Transienten bei wenigen Manipulationen an der Datenstruktur auch zu erkennen:

3.7  Hintergrund: Clojures STM

In diesem Abschnitt geben wir in Kürze einige Hintergrundinformationen über Clojures Implementation von Software Transactional Memory wieder. Die grundlegenden Funktionen sind im Java-Code von Clojures Implementation in der Datei LockingTransaction.java zu finden, aber die Funktionen, die für STM notwendig sind, reichen bis in die Implementationen von etwa Refs oder Agents hinein. Daran ist ersichtlich, dass STM nicht – oder zumindest nicht leicht – als eine modulare Funktion, als eine Bibliothek, betrachtet werden kann. Sie ist in Clojure tief integriert.

3.7.1  Wissenswertes

Eigentlich sollten die Hintergründe für den Anwender von Clojure nicht relevant sein. Wie an anderer Stelle, etwa in Abschnitt 7.1, beschrieben wird, ist dieser Zustand noch nicht erreicht. Die derzeit beste Quelle, neben dem Quelltext, ist der Artikel „Software Transactional Memory“ von Mark Volkmann [73].

Der Aufruf von commute stellt sicher, dass es keine Deadlocks geben kann, indem vor dem Commit der Werte auf alle Refs in der Reihenfolge ihrer Definition ein Lock geholt wird. Somit gehen alle Transaktionen in der gleichen Reihenfolge vor, und es kann nicht geschehen, dass eine Transaktion auf eine andere wartet und umgekehrt.

3.7.2  Fallstricke

Die Entwicklung hochgradig paralleler Anwendungen führt zu neuen Problemen. Nur die Erfahrung, die jeder Entwickler selbst macht, wird helfen können, dieser Probleme Herr zu werden. Sowohl im Diskussionsforum von Clojure als auch im IRC-Channel werden gelegentlich solche Fälle besprochen. So fiel einem Anwender auf, dass seine Applikation, die viele Zufallszahlen erzeugt, nicht gut skalierte. Der Grund dafür ist, dass die Funktion rand-intrand-int einen Flaschenhals darstellt. Es wird ein einziger Zufallszahlengenerator von allen Threads verwendet. Dies lässt sich durch einen dedizierten Generator, der zum Thread gehört, umgehen. Nur muss man da erst mal drauf kommen. Garbage CollectorÄhnlich verhält es sich mit Javas Garbage Collector. In der Standardeinstellung arbeitet dieser nicht parallel und ist somit ebenfalls ein Nadelöhr, das die Skalierung über Prozessoren negativ beeinflussen kann [65].

Ein kurzer Demo-Code von Chris Houser [36], der einer Diskussion am 28. Juni 2010 entsprungen ist, zeigt anhand zweier Threads, von denen einer eine langsame Transaktion mit einem Reader ausführt und der andere schnell die Werte erhöht, zu welchen Fällen es hier kommen kann:

Clojure vereinfacht die Handhabung von Multithreaded-Programmen, sie enthebt den Entwickler jedoch nicht von seiner Verantwortung, die Mechanismen seines Programms zu durchschauen.

3.8  Beispiel: Genetischer Algorithmus

Ein Beispiel, an dem sich die grundlegende Veränderung eines Programms durch die Einführung von Concurrency anschaulich studieren lässt, ist die Implementation eines einfachen genetischen Algorithmus. Die klassische Vorgehensweise beschreibt der folgende Pseudocode:

Dabei werden Populationen sukzessive in Form von Generationen erzeugt, und pro Generation gibt es ein oder mehrere beste Individuen in der Population. Ein offensichlicher Einstiegspunkt für parallele Verarbeitung ist die Bewertung der Nachkommen. Diese ist in der Regel vom Rest der Population vollkommen unabhängig und kann somit leicht über mehrere Prozessoren verteilt werden.

Die Fitness-Funktion fitness-bewerten hat dazu zwei Teile:

• die Bewertung der Längendifferenz mit zweifacher Wertung
• und die Anzahl der unterschiedlichen Zeichen.

Dabei machen wir uns zwei Eigenschaften von map zunutze: einerseits, dass über mehr als eine Sequence iteriert werden kann, und andererseits, dass die Iteration abbricht, sobald das Ende einer Sequence erreicht wurde. Bei Ungleichheit von zwei zu vergleichenden Zeichen wird eine 1 an die Funktion reduce weitergerreicht, die somit die Addition der entdeckten Unterschiede übernimmt. Erwähnenswert ist auch, dass die Java-Methode length für Strings nicht verwendet wird, da sie (N) ist, während count auf Datenstrukturen (1) garantiert.