Parallelprogrammierung mit Clojure
Seite 3: Software Transactional Memory
STM: Von Datenbanken gelernt
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 das Verfahren erprobt, und der Gedanke liegt nahe, diese Technik auf Daten im Speicherbereich eines Programms anzuwenden.
Von den bekannten ACID-Eigenschaften (Atomic, Consistent, Isolated, Durable) solcher Transaktionen lassen sich die ersten drei auch auf Manipulationen flüchtigen Speichers übertragen, lediglich die Sicherung auf nichtflüchtige Medien entfällt. Von der (patentierten) Idee aus den 1980er-Jahren ausgehend, transaktionalen Speicher zu bauen, konzentrieren sich Forschung und Entwicklung seitdem auf reine Softwarelösungen: Software Transactional Memory.
Clojures wohl prominentestes Concurrent-Programming-Feature dürfte die Implementierung von STM sein, einer Technik, deren Umsetzung selbst ein großer Konzern wie Microsoft für .NET (zumindest vorläufig) eingestellt hat, wie Joe Duffy schreibt.
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. Den abschließenden Schritt, der die Manipulation der Daten einer Transaktion auch für andere Programmteile manifestiert, nennt man Commit. Den Abschluss kann von gleichzeitigen Transaktionen nur eine durchführen, und zwar die, die zuerst ihren Commit versucht. Alle anderen müssen in der Regel ihre Arbeit erneut beginnen. Diese Wiederholungen stellen eine wichtige Anforderung an die in einer Transaktion durchgeführten Funktionen: 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.
STM hat zwei Vorteile. Erstens ist es, im Gegensatz zum Locking, das gemeinhin als Standardverfahren gilt, ein optimistischer Ansatz. Es blockiert nicht lesende Zugriffe, auch führt es alle schreibenden Zugriffe, wenn das Transaktionssystem nicht vorher Konflikte erkennen kann, bis zur Commit-Phase durch. Das erlaubt einen höheren Grad an Parallelisierung. Der zweite Vorteil ist, dass dieses Modell einfach zu verstehen und handzuhaben ist. Der Programmierer muss nur darauf achten, dass die in einer Transaktion verwendeten Funktionen keine Nebeneffekte haben, und den Rest erledigt das Transaktionssystem. Die konkrete Implementierung des Systems kann mit Locking erfolgen. In dem Fall müssen aber nur seine Entwickler das Locking in den Griff bekommen, alle weiteren Anwender sind davon befreit.
Nachteilig an STM sind die höheren Anforderungen an Speicher und CPU. Jede Transaktion braucht genau genommen eine komplette Kopie der zu verändernden Daten, und die Wiederholungen verbrauchen mehr Rechenleistung. Bei n gleichzeitigen Transaktionen kann es im schlimmsten Falle zum n-fachen Bedarf an Speicher und Rechenleistung kommen. Zudem leidet die Vorhersagbarkeit, da der Ablauf der Transaktionen vom Laufzeitverhalten abhängt.
An der Stelle kommt der Implementierung der persistenten Datenstrukturen bei Clojure eine tragende Rolle zu. Durch sie ist es möglich, jeder Transaktion effizient eine eigene Kopie der Daten zur Verfügung zu stellen sowie die Historie dieser Datenstruktur bei zwischenzeitlich in anderen Threads erfolgten Änderungen.
Ein Befehl, große Wirkung
In Anbetracht der Komplexität, die mit STM einhergeht, ist es umso beachtlicher, dass sich die Komplexität für den Anwender hinter nur einem Befehl verbirgt: dosync.
Refs werden mit der Funktion ref angelegt, die den zu referenzierenden Wert übergeben bekommt:
#+begin_src clojure
(def ref1 (ref 1))
(def ref2 (ref 1))
#+end_Src
Für die Manipulation von Refs existieren drei Funktionen. Einen neuen Wert setzt die Funktion ref-set, es werden hingegen die Funktionen alter und commute bevorzugt, die keinen neuen Wert übernehmen, sondern eine Funktion erwarten, die den neuen Wert liefert.
Das folgende Beispiel verwendet die oben erzeugten Refs und demonstriert mit je einem lesenden und einem schreibenden Thread, wie die neuen Werte koordiniert für den lesenden Thread sichtbar werden.
#+begin_src clojure
(defn lesethread []
(println "Thread 1: lese")
(dotimes [i 6]
(Thread/sleep 100)
(dosync
(println "T1, ref1: " @ref1 " ref2: " @ref2))))
(defn schreibthread []
(println "Thread 2: schreibe")
(dosync
(alter ref1 inc)
(Thread/sleep 300)
(alter ref2 inc)))
user> (do (.start (Thread. lesethread))
(.start (Thread. schreibthread)))
Thread 1: lese
Thread 2: schreibe
T1, ref1: 1 ref2: 1
T1, ref1: 1 ref2: 1
T1, ref1: 1 ref2: 1
T1, ref1: 2 ref2: 2
T1, ref1: 2 ref2: 2
T1, ref1: 2 ref2: 2
#+end_src
Nach drei Lesevorgängen wechseln beide Refs ihren Wert vom ersten Thread aus betrachtet gleichzeitig von 1 zu 2. Das Verhalten ist sicher, und beliebig viele Ausführungen werden nie einen inkonsistenten Zustand lesen.
An einem etwas ausführlicheren Beispiel sei die Verwendung von alter gezeigt und auch hier ein separater, immer wieder lesender Thread gestartet. Zunächst die Anlage der Refs:
#+begin_src clojure
(def ref1 (ref "Original 1"))
(def ref2 (ref "Original 2"))
user> [@ref1 @ref2]
["Original 1" "Original 2"]
#+end_src
Des Weiteren definiert man drei Hilfsfunktionen, die Lesen, Schreiben und das Erzeugen eines neuen Werts erledigen. Dabei ist die letztgenannte (namenator) mit einem Nebeneffekt – einer Ausgabe mit println – versehen. Das ist im Normalfall nicht ratsam, da diese Funktion als Update-Funktion für die Refs verwendet wird, und Update-Funktionen sich durch die STM-Maschinerie wiederholt aufrufen lassen. Update-Funktionen sollten demnach frei von Nebeneffekten sein.
#+begin_src clojure
(defn leserich
"Liest die aktuellen Werte"
[] (dotimes [i 10]
(dosync
(println "LESERICH" @ref1 @ref2)
(flush))
(Thread/sleep 20)))
(defn namenator
"Liefert einen Namen. Mit unklugem Nebeneffekt"
[num nam] (let [result (str "NEU" num ": " nam)]
(println "NAMENATOR" result)
result))
(defn schreiberling
"Schreibt NAM in ref1 und ref2"
[nam] (dosync
(alter ref1
(fn [_] (namenator 1 nam)))
(Thread/sleep 88)
(alter ref2
(fn [_] (namenator 2 nam)))))
#+end_src
Abschließend sorgt ein Aufruf von do am REPL-Prompt dafür, dass sich die Hilfsfunktionen mit verschiedenen Werten in eigenen Threads aufrufen lassen. Die Sleep-Zeiten der Threads sind so aufeinander abgestimmt, dass die Ausgabe möglichst lesbar bleibt und die Effekte der STM-Maschinerie sichtbar werden.
#+begin_src clojure
user> (do (.start (Thread. leserich))
(dotimes [i 3]
(.start (Thread.
(fn []
(schreiberling (+ i 10))))))
(Thread/sleep 2000))
LESERICH Original 1 Original 2
NAMENATOR NEU1: 10
NAMENATOR NEU1: 11
NAMENATOR NEU1: 12
LESERICH Original 1 Original 2
LESERICH Original 1 Original 2
NAMENATOR NEU2: 10
NAMENATOR NEU1: 11
NAMENATOR NEU1: 12
LESERICH NEU1: 10 NEU2: 10
LESERICH NEU1: 10 NEU2: 10
LESERICH NEU1: 10 NEU2: 10
NAMENATOR NEU2: 11
NAMENATOR NEU1: 12
LESERICH NEU1: 11 NEU2: 11
LESERICH NEU1: 11 NEU2: 11
NAMENATOR NEU2: 12
LESERICH NEU1: 12 NEU2: 12
LESERICH NEU1: 12 NEU2: 12
nil
#+end_src
Ein Studium der Ausgabe, die durch das Multithreading bei jedem Durchlauf anders aussehen kann, zeigt, wie der STM-Mechanismus Update-Funktionen wiederholt, da eine Ref in der Zwischenzeit verändert wurde. Zunächst wird die Update-Funktion dreimal für die erste Ref aufgerufen, dann einmal für die zweite, und der Schreibzugriff, der diesen Aufruf initiiert hat, kann seine Transaktion erfolgreich beenden. Danach haben beide Refs den Wert "NEUx:10". Die Transaktionen, die die Zahlen 11 und 12 verwenden wollten, müssen von vorne beginnen und rufen die Update-Funktion erneut für die erste Ref auf. Dieses Mal bekommt der Thread mit der 11 den Zuschlag, weil er als Erster bis zum Ende seiner Transaktion kam, und die noch verbleibende Transaktion ("12") muss von vorne beginnen.
