Java Memory Model CopyOnWriteArrayList Java Magazin, Dezember 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).

In diesem Beitrag wollen wir die CopyOnWriteArrayList aus dem JDK hernehmen und an ihrem Beispiel das Zusammenspiel der Speichereffekte von Synchronisation, volatile, und atomaren Referenzen noch einmal abschließend erläutern.

In unserer Serie über das Java Memory Modells haben wir eine Reihe von Aspekten angeschaut, mit denen sich die Verwendung von Synchronisation reduzieren läßt.  Dabei soll mit der Vermeidung der Synchronisation in der Regel die Performance der betroffenen Abstraktion verbessert und der Durchsatz erhöht werden, weil ohne Synchronisation mehrere Threads ungehindert parallel arbeiten können, ohne aufeinander warten zu müssen.  Wir haben die Effekte von final-, volatile- und atomaren Variablen betrachtet und an kleineren Beispielen demonstriert.  Dieses Mal wollen wir zeigen, wie diese Sprachmittel in einer realistischen Abstraktion in der Praxis genutzt werden.  Dazu wollen wir uns die Implementierung der CopyOnWriteArrayList aus dem JDK-Package java.util.concurrent genauer ansehen, weil sie ein geschicktes Zusammenspiel von volatile und Synchronisation zeigt.

Was ist eine CopyOnWriteArrayList?

Wie funktioniert eine CopyOnWriteArrayList?

public class CopyOnWriteArrayList<E> implements List<E> {

    private volatile transient Object[] array;

    private final Object[] getArray() {
        return array;
    }

    public E get(int index) {
        return (E)(getArray()[index]);
    }
}

Das Fehlen jeglicher Synchronisation bedeutet, dass wir in der get()-Methode einen unsynchronisierten Zugriff auf die Array-Referenz haben.  Bei unsynchronisierten Zugriffen stellt sich stets die Frage nach der Sichtbarkeit von Modifikationen, die ein anderer Thread gemacht hat.  Kann die get()-Methode alle Modifikationen am Array sehen, die beispielsweise eine set()-Methode zuvor in einem anderen Thread ausgelöst hat?

Die Referenz auf das Array der CopyOnWriteArrayList ist als volatile deklariert und die get()-Methode greift lesend auf die Referenz zu (über die Hilfs-Methode getArray()).  Weil die Array-Referenz volatile ist, ist garantiert, dass die get()-Methode alle Modifikationen sehen kann, die ein anderer Thread vor einem schreibenden Zugriff auf die Array-Referenz gemacht hat.  Sehen wir uns also eine modifizierende Methode näher an.  Hier ist ein größerer Ausschnitt aus der Implementierung, der zusätzlich zur get()-Methode auch die set()-Methode zeigt:

public class CopyOnWriteArrayList<E> implements List<E> {

    /** The lock protecting all mutators */
    transient final ReentrantLock lock = new ReentrantLock();

    /** The array, accessed only via getArray/setArray. */
    private volatile transient Object[] array;

    private final Object[] getArray() {
        return array;
    }

    private final void setArray(Object[] a) {
        array = a;
    }

    public E get(int index) {
        return (E)(getArray()[index]);
    }

    public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            Object oldValue = elements[index];

            if (oldValue != element) {
               int len = elements.length;
               Object[] newElements = Arrays.copyOf (elements, len); // 1
               newElements[index] = element;                        // 2
             setArray(newElements);                                // 3
            } else {
               // Not quite a no-op; ensures volatile write semantics
             setArray(elements);                                   // 3
            }
            return (E)oldValue;
       } finally {
            lock.unlock();
       }
    }
}

Man kann nun auch sehen, warum der konkurriende unsynchronisierte Ablauf von set()- und get()-Methode keine Race Condition ist.  Das Array, das die get()-Methode liest, wird von der set()-Methode nicht verändert, denn sie verändert nur eine lokale Kopie des Arrays.  Die einzige Modifikation, die die set()-Methode an den Feldern der CopyOnWriteArrayList vornimmt, ist die Zuweisung der Adresse des neu erstellten Arrays an die Referenzvariable array (siehe //3).  Diese Adresszuweisung ist atomar, also unkritisch, weil sie ununterbrechbar ist.  Die get()-Methode erwischt also die Adresse des unveränderten Arrays vor dem Aufruf von setArray() oder die Adresse der modifizierten Kopie nach dem Aufruf von setArray(). Auf irgendwelche inkonsistenten Zwischenzustände des Arrays hat die get()-Methode keinen Zugriff.

Der konkurrierende Ablauf von zwei set()-Methode wäre hingegen sehr wohl eine Race Condition.  Wenn sich beide set()-Methoden die Adresse des Arrays holen, beide eine lokale Kopie anlegen und ihre jeweilige Modifikation an der lokalen Kopie machen, dann wird die eine set()-Methode die Modifikation der anderen set()-Methode überschreiben, wenn sie die Referenzvariable array überschreibt.  Nach einem unsynchronisierten Ablauf beider set()-Methoden bliebe nur eine der beiden Modifikationen übrig; wir hätte also ein Lost-Update-Problem.  Die modifizierenden Methoden der CopyOnWriteArrayList sind deshalb alle gegeneinander synchronisiert.  Dazu wird ein explizites Lock verwendet.

Die übrigen lesenden und modifizierenden Methoden der CopyOnWriteArrayList sehen analog aus.  Interessant ist noch der Iterator.  Die Beschreibung sagt, der Iterator iteriert über die Liste, so wie im Augenblick der Konstruktion des Iterators ausgesehen hat.  Deshalb ist von einem Snapshot die Rede.  Was hat es mit dem Snapshot auf sich?

Wie funktioniert der Iterator der CopyOnWriteArrayList

Hier ist ein Auszug aus der Implementierung des Iterators der CopyOnWriteArrayList:

public class CopyOnWriteArrayList<E>

    private volatile transient Object[] array;

    private final Object[] getArray() {
        return array;
    }
    public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }

    private static class COWIterator<E> implements ListIterator<E> {
        /* Snapshot of the array **/
        private final Object[] snapshot;
        /* Index of element to be returned by subsequent call to next.*/
        private int cursor;

        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }

        public boolean hasNext() {
            return cursor < snapshot.length;
        }

        public E next() {
            if (! hasNext())
                throw new NoSuchElementException();
            return (E) snapshot[cursor++];
        }

        /* Not supported. Always throws UnsupportedOperationException. */
        public void remove() {
            throw new UnsupportedOperationException();
        }
       ...
   }
   ...
}

Wie wir schon gesehen haben, legt die set()-Methode eine Kopie des Arrays an, modifiziert die Kopie und überschreibt dann die Array-Referenz in der CopyOnWriteArrayList mit der Adresse der Kopie.  Der Iterator bekommt davon nichts mit.  Er wird weiterhin auf dem alten Array iterieren.  In diesem Sinne arbeitet der Iterator der CopyOnWriteArrayList auf einem Snapshot und dieser Snapshot ist, nachdem eine Änderung an der Liste vorgenommen wurde, eine "alte" Kopie der Liste.

Weil das Array der CopyOnWriteArrayList nie verändert wird, wird im Iterator keine Synchronisation gebraucht.  Auch der konkurrierende Ablauf einer Iteration und einer Modifikation der Liste ist kein Problem.  Auf diese Weise hat die CopyOnWriteArrayList einen höchst effizienten Iterator, der ein Maximum an konkurrierenden Zugriffen auf die Liste zuläßt.

Allerdings hat der Iterator der CopyOnWriteArrayList eine andere Semantik als der Fast-Fail-Iterator einer synchronisierten Liste.  Er zeigt unter Umständen einen alten Stand (stale value) der Liste - eine Situation, die beim Iterieren über eine synchronisierte Liste nicht auftreten kann.  Bei der synchronisierten Liste ist die konkurrierende Modifikation ein Fehler, der sich in der ConcurrentModificationException des Iterators ausdrückt.  Bei der CopyOnWriteArrayList ist die konkurrierende Modifikation hingegen ein Feature.

Eine andere Anwendung desselben Prinzips

public class Interval {  // Vorsicht: nicht thread-safe !!!
  // INVARIANT: lower <= upper
  private volatile int lower = 0
  private volatile int upper = 0;

  public void setLower(int i) {
        if (i > upper.)
            throw new IllegalArgumentException(
                    "can't set lower to " + i + " > upper");
        lower = i;
  }

    public int getLower() {
        return lower;
    }

  public boolean isInRange(int i) {
        return (i >= lower && i <= upper);
  }
  …
}

Um diese Interval-Klasse thread-safe zu machen, kann man dasselbe Prinzip anwenden, das auch in der CopyOnWriteArrayList verwendet wird: man sorgt dafür, dass die eigentlichen Daten des Intervals (also das Paar von Unter- und Obergrenze) unveränderlich sind und lediglich bei Bedarf neue Daten erzeugt und gegen die alten ausgetauscht werden.

Hier ist eine korrigierte Fassung:

@ThreadSafe
public class Interval {

    @Immutable
    private static class IntPair {
        private final int lower;
        private final int upper;
        public IntPair(int l, int u) {
            lower =l;
            upper =u;
        }
    }

    private final AtomicReference<IntPair> values =
        new AtomicReference<IntPair>(new IntPair(0, 0));
 

    public void setLower(int i) {
        while (true) {
            IntPair oldv = values.get();
            if (i > oldv.upper)
                throw new IllegalArgumentException(
                   "Can't set lower to " + i + " > upper");
            IntPair newv = new IntPair(i, oldv.upper);
            if (values.compareAndSet(oldv, newv))
                return;
        }
    }

    public int getLower() {
        return values.get().lower;
    }

    public boolean isInRange(int i) {
        IntPair v = values.get();
        return (i >= v.lower && i <= v.upper);
    }

    …
}

Das Verhalten ist bei dieser Lösung ähnlich wie bei der CopyOnWriteArrayList: konkurreirende Lesezugriffe sind sowieso kein Problem; Modifikationen, die konkurrierend zu lesenden Zugriffen passieren, sind auch kein Problem.  Der Leser sieht stets ein gültiges Interval, das zu irgendeinem Zeitpunkt einmal existiert hat (und niemals ein fehlerhaftes, bei dem die Untergrenze größer als die Obergrenze ist); schlimmstenfalls sieht er einen älteren Zustand des Intervals (vor der letzten aktuellen Änderung).  Sogar konkurrierende Schreibzugriffe kommen wegen der AtomicReference ohne Synchronisation aus; schlimmstenfalls muss ein Thread seinen Modifikationsversuch mehrmals wiederholen.
 

Zusammenfassung

• Die Implementierung der Abstraktion hält lediglich eine Referenz auf alle Daten der Abstraktion und diese Daten sind unveränderlich; lediglich die Referenz kann sich ändern.  Die Referenz ist wegen der Sichtbarkeitsanforderungen entweder volatile oder atomar.
• Alle Modifikationen werden auf einer Kopie der aktuellen Daten gemacht und am Ende wird die Referenz auf die alten Daten gegen eine Referenz auf die neuen Daten ausgetauscht.  Weil die eigentlichen Daten der Abstraktion unveränderlich sind, können lesende Zugriffe miteinander und mit den modifizierenden Zugriffen zusammen parallel ohne Synchronisation ablaufen.  Diesen  Gewinn an Parallelität bezahlt man mit den Kosten für das Kopieren.  Das Idiom lohnt sich also in erster Linie bei Abstraktionen, die wesentlich häufiger gelesen als modifiziert werden.
• Für die Modifikationen ist es erforderlich, dass eine Sequenz von "Lesen der aktuellen Daten" - "Bewerten der gelesenen Daten (Vergleich, Berechnung, etc.) - "Verändern der Daten" ununterbrechbar abläuft.  Die Atomarität kann entweder per Synchronisation erreicht werden, wie bei der CopyOnWriteArrayList, oder mit Hilfe einer atomaren Referenz, wie im Interval-Beispiel.

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)