Java Memory Model Atomic References Java Magazin, Oktober 2009 Klaus Kreft & Angelika Langer

Dies ist das Manuskript eines Artikels, der im Rahmen einer Kolumne mit dem Titel "Effective Java" im Java Magazin erschienen ist.  Die übrigen Artikel dieser Serie sind ebenfalls verfügbar ( click here ).   Die ganze Serie zum  "Java Memory Modell" als PDF (985 KB).

Wir haben im letzten der Beiträge dieser Kolumne [ JMM10 ] über atomare skalare Variablen gesprochen.   In diesem Beitrag sehen wir uns die atomaren Referenzvariablen an.

Wir haben im letzten Beitrag gezeigt, wie man atomare Skalare aus dem Package java.util.concurrent.atomic als bessere volatile Variablen für die Optimierung von konkurrierenden Zugriffen auf skalare Variablen einsetzen kann. Erläutert haben wir es am Beispiel einer Counter-Abstraktion, in der ein Integer konkurrierend inkrementiert und dekrementiert werden kann.  Da Inkrement und Dekrement keine atomaren Operationen sind, sind sie unterbrechbar.  Eine Möglichkeit, die Counter-Abstraktion thread-safe zu machen, besteht nun darin, den konkurrierenden Zugriff auf diese Operationen mit Hilfe von Locks zu synchronisieren .  Als Alternative zur Synchronisation kann man statt eines normalen int einen AtomicInteger verwenden.  Er hat nämlich atomare Inkrement- und Dekrement-Operationen, deren Verwendung dann den Verzicht auf Synchronisation ermöglicht.

Ganz allgemein ist die Idee hinter einem atomaren Inkrement und Dekrement die sogenannte Compare-and-Swap-Sequenz, auch CAS genannt.  Solch ein atomarer CAS-Befehl wird üblicherweise von dem jeweiligen Prozessor bereits unterstützt und die atomaren Variablen in Java nutzen die Möglichkeiten der Hardware, um ununterbrechbare Read-Modify-Write-Sequenzen auf Java-Objekten zu unterstützen.  Solche Unterstützung bieten die atomaren, skalaren Variablen AtomicInteger, AtomicLong und AtomicBoolean. Nun beschränkt sich das Bedürfnis nach atomaren Read-Modify-Write-Sequenzen nicht nur auf skalare Typen.  Deshalb gibt es neben den atomaren Skalaren auch noch atomare Referenzen wie AtomicReference<V>, AtomicMarkableReference<V> und AtomicStampedReference<V>.
 

Fallstudie zu atomaren Referenzen

public final class StringUpdater { // Vorsicht: falsch !!!
    private String theString;
    private boolean changed = false;

    public void setText(String txt)  {
        theString = txt;
        changed = true;
    }
    public boolean displayText() {
        if (changed) {
            String currentText = theString;
            ... display currentText ...
            changed = false;
        }
        return true;
    }
}

Sichtbarkeitsprobleme

Das Sichtbarkeitsproblem könnte man lösen, indem die beiden Felder der Klasse StringUpdater als volatile deklariert werden.  Das sähe dann so aus:

public final class StringUpdater { // Vorsicht: immer noch falsch !!!

    private volatile String theString;
    private volatile boolean changed = false;

    public void setText(String txt)  {
        theString = txt;
        changed = true;
    }
    public void displayText() {
        if (changed) {
            String currentText = theString;
            ... display currentText ...
            changed = false;
        }
    }
}

Der zweite Mangel ist damit aber nicht behoben:  in der Methode displayText() wird das Boolesche Feld gelesen, ausgewertet und anschließend geändert.  Diese Sequenz von Operationen ist unterbrechbar.  Es könnte passieren (siehe Diagramm), dass ein Anzeige-Thread das Boolesche Feld changed liest, den Wert true vorfindet, deshalb den Text anzeigen will, aber vorher unterbrochen wird.  Ein anderer Anzeige-Thread liest ebenfalls das Boolesche Feld und findet ebenfalls den Wert true.  Dieser zweite Anzeige-Thread wird nicht unterbrochen und zeigt den Wert an.  Wenn der erste Anzeige-Thread wieder arbeiten darf, wird er den bereits nicht mehr aktuellen Wert trotzdem anzeigen.  Wir bekämen dann die redundante Mehrfach-Anzeige, die eigentlich vermieden werden sollte.

Das Problem ist, dass die Sequenz von Lesen-Auswerten-Verändern des Booleschen Feldes changed ununterbrechbar sein müsste.  Wir brauchen also Synchronisation, um die Mehrfach-Anzeige zu verhindern.  Das sähe dann so aus:

public final class StringUpdater {  // korrekt, aber nicht optimal

    private String theString;
    private boolean changed = false;

    public synchronized void setText(String txt) {
        theString = txt;
        changed = true;
    }

    public synchronized void displayText() {
        if (changed) {
            String currentText = theString;
            ... display currentText ...
            changed = false;
        }
    }
}

Optimierung mit Atomaren Referenzen

public class StringUpdater {  // Vorsicht: falsch !!!

    private AtomicReference<String> theString = new AtomicReference<String>(null);
    private AtomicBoolean           changed   = new AtomicBoolean(false);

    public void setText(String txt) {
        theString.set(txt);
        changed.set(true);
    }
    public void displayText() {
        boolean chg = changed.get();
        if (chg) {
            if (changed.compareAndSet(true, false)) {
                String currentText = theString.get();
                ... display currentText ...
                return;
            } else  {
                displayText();
                return;
            }
        }
    }
}

Es könnte nämlich auch sein, dass nach dem Ändern des Booleschen Feld changed im ersten Anzeige-Thread ein Sensor-Thread den Text und das Boolesche Feld ändert (siehe Diagramm).  Dann würde der eine Anzeige-Thread den neuen Text anzeigen.  Der alte Text wäre verloren gegangen, aber das ist im gegebenen Anwendungsfall kein Prblem. Danach würde aber im anderen Anzeige-Thread das Modifzieren des Booleschen Feldes erfolgreich verlaufen, weil sich der Boolesche Wert zwar in der Zwischenzeit geändert hat, aber schon wieder den erwarteten Wert true hat.  Der neue Text würde also noch einmal angezeigt - und wir hätte dann doch eine unerwünschte Mehrfach-Anzeige.

Das Problem hier ist, dass wir das Boolesche Feld changed nur ändern dürfen, wenn sich der Inhalt des Textfeldes nicht geändert hat.  Es genügt nicht, wenn wir das Boolesche Feld in Isolation betrachten, sondern wir müssen hier die Kombination von String und Boolean gemeinsam verarbeiten.

Für diese Kombination von einem Objekt und einem Booleschen Wert gibt es im Package java.util.concurrent.atomic eine Abstraktion, nämlich die AtomicMarkableReference<V>.  Die korrekte Lösung für unser Problem sieht also so aus:

public final class StringUpdater {  // endlich korrekt und effizient

    private AtomicMarkableReference<String> amr = new AtomicMarkableReference<String>(null, false);

    public void setText(String txt) {
        amr.set(txt, true);
    }
      public void displayText() {
        boolean[] changed = new boolean[1];
        String currentText = amr.get(changed);
        if (changed[0]) {
            if (amr.compareAndSet(currentText,currentText,true,false)) {
                ... display currentText ...
                return;
            } else {
                displayText();
                return;
            }
        }
    }
}

Jetzt kann es nicht mehr passieren, dass derselbe Text redundant mehrfach angezeigt wird.  Die Compare-And-Set-Operation klappt nun nicht mehr, wenn sich der Text in der Zwischenzeit geändert hat, weil die AtomicMarkableReference<V>  sowohl für die Referenz als auch für den Booleschen Wert prüft, ob sie die erwarteten Werte haben.  In unserem Beispiel würde die  CAS-Operation scheitern (siehe Diagramm) und der zweite Anzeige-Thread würde den gesamten Vorgang von "Werte lesen, vergleichen und ändern" erneut versuchen.

Wir haben anhand der Fallstudie illustriert, dass die Verwendung von atomaren Referenzen zur Verweidung von Synchronisation verwendet werden kann.  Die atomaren Referenzen haben diesselben Speichereffekte wie volatile Referenzen und haben zusätzlich ununterbrechbare CAS-Operationen.  In diesem Sinne sind die atomaren Referenzen eine logische Verallgemeinerung von volatile Referenzen.  Wie das Beispiel aber auch gezeigt hat, kann man bei Verwendung von atomaren Referenzen natürlich Fehler machen.  Die Verwendung von atomaren Variablen funktioniert nur dann als Ersatz für Synchronisation, wenn sich die kritischen Zugriffe auf eine einzige Variable beziehen.  Wir haben in der Fallstudie den Fehler gemacht, dass wir zunächst zwei atomare Variablen verwendet haben.  Auch das kann in Spezialfällen mal korrekt sein, nämlich wenn die beiden Variablen voneinander unabhängig sind.  Sobald jedoch die beiden Variablen in einer Beziehung zueinander stehen und konsistent zueinander sein müssen, dann ist die Verwendung von zwei atomaren Variablen falsch.  Wichtig ist beim Programmieren mit atomaren Variablen, dass man sich wirklich auf eine einzige (dann atomare) Variable beschränken kann.  In unserem Beispiel war die AtomicMarkableReference<V>, also die Kombination von Referenz und Boolschem Wert, das richtige Instrument.

Atomare Referenzen - Übersicht

Alle atomaren Referenzen haben dieselben Speichereffekte wir volatile, damit es keine Sichtbarkeitsprobleme gibt.  Die wesentlichen Methoden und deren Speichereffekte sind:
 

get()	entspricht dem Lesen einer volatile-Variablen
set()	entspricht dem schreibenden Zugriff auf eine volatile-Variable
compareAndSet()	entspricht dem lesenden und schreibenden Zugriff auf eine volatile-Variable
weakCompareAndSet()	ist lediglich ununterbrechbar, hat aber keine Speichereffekte, entspricht also dem Zugriff auf eine non-volatile-Variable (dient zur Optimierung, wenn man zum Beispiel weiss, dass die relevanten Speichereffekte aufgrund anderer Operationen ausgeführt werden)

Neben den oben genannten Abstraktionen gibt es noch die schon im letzten Beitrag erwähnten atomaren Skalare AtomicBoolean, AtomicInteger, und AtomicLong. Sie haben zusätzliche Inkrement- und Dekrement-Methoden.

Außerdem gibt es atomare Arrays: AtomicIntegerArray, AtomicLongArray und AtomicReferenceArray.  Sie bieten atomare Zugriffe auf die Elemente des Arrays - eine Funktionalität, die es für normale Arrays nicht gibt, weil man mit den Java-Sprachmitteln gar nicht deklarieren kann, dass man ein Array von volatile-Elementen haben möchte.

Daneben gibt es noch die sogenannten atomaren Updater: AtomicReferenceFieldUpdater<T,V>, AtomicIntegerFieldUpdater<T> und AtomicLongFieldUpdater<T>.  Das sind Abstraktionen, die atomare CAS-Zugriffe auf volatile-Felder von Objekten anbieten. Während die atomaren Variablen jeweils ein Objekt (oder skalaren Wert, Array, Objekt + Boolean, Objekt + Version) kapseln und für das Objekt atomare CAS-Zugriffe ermöglichen,  bieten die Updater atomare CAS-Zugriffe für volatile-Felder von Objekten.  Dabei kann man einen einzigen Updater verwenden, um auf ein bestimmtes Feld in verschiedenen Objekten zuzugreifen.  Man hat also zum Beispiel nur einen Updater für das next-Feld einer Klasse Node und kann mit diesem einen Updater auf das next-Feld aller Objekte vom Typ Node zugreifen. Das spart Resourcen, weil nicht jedes einzelne next-Feld in jedem einzelen Node-Objekt in eine AtomicReference<Node> eingepackt werden muss.  Dafür sind die Garantien schwächer, weil neben den sicheren Zugriffen über den Updater immer noch direkt Zugriffe auf die volatile-Fehler gemacht werden können, die dann nicht atomar und ohne Speichereffekte sind.

Praxis-Relevanz

Beispiele für den Einsatz atomarer Variablen findet man im JDK:  die Klasse ConcurrentLinkedQueue wie auch die SkipList-Implementierungen sind Beispiele für Abstraktionen, die thread-sicher sind und die Thread-Sicherheit ohne die Verwendung von Synchronisation erreicht.  Die Implementierung der ConcurrentLinkedQueue zum Beispiel verwendet atomare Updater, um den Link auf den jeweils nächsten Knoten in der Liste zu verwalten.  Die Algorithmen, die für diese Art von Programmierung benötigt werden, sind in der Regeln nicht trivial und typischerweise das Ergebnis jahrelanger Forschung.  Es gibt einige Standardalgorithmen für Stacks und Listen.  Wer sich für Details interessiert, der muss sich mit der entsprechenden Fachliteratur beschäftigen.  Eine gute (wenn auch sehr, sehr knappe) Einführung in die Prinzipien des Lockfree-Programming findet man in Kapitel 15.4. "Nonblocking Algorithms" in "Java Concurrency in Practice" von Brian Goetz (siehe [ JCP ]).

Insgesamt ist die Verwendung von atomaren Variablen kein Instrument, mit dem man in beliebigen Situationen optimieren kann, indem synchronisierte Zugriffe durch atomare Zugriffe ersetzt werden.

Zusammenfassung

Literaturverweise

Die gesamte Serie über das Java Memory Model:

If you are interested to hear more about this and related topics you might want to check out the following seminar:

Seminar   Concurrent Java - An in-depth seminar covering all that is worth knowing about concurrent programming in Java, from basics such as synchronization over the Java 5.0 concurrency utilities to the intricacies of the Java Memory Model (JMM). 4 day seminar ( open enrollment and on-site)