12.11 Synchronisation der Datenstrukturen 
Ein großer Unterschied zwischen den klassischen Datenstrukturen wie Vector oder Hashtable und denen aus der Collection-API besteht darin, dass alle Methoden durch synchronisierte Blöcke vor parallelen Änderungen geschützt waren. Bei den neuen Klassen wie ArrayList und HashMap sind Einfüge- und Löschoperationen nicht mehr automatisch synchronized. Sollen allerdings Listen, Mengen oder Assoziativspeicher vor nebenläufigen Änderungen sicher sein, gibt es zwei Möglichkeiten: einmal über spezielle so genannte Lock-free-(bzw. Wait-free-)Algorithmen, die tatsächlich parallele Zugriffe – wenn möglich – erlauben, und einmal über synchronisierende Wrapper.
12.11.1 Lock-free-Algorithmen aus java.util.concurrent 
Wenn zum Beispiel bei einer verketteten Liste ein Thread vorn etwas anhängt und der andere hinten etwas entfernt, ist das tatsächlich nebenläufig möglich, und es muss nicht die ganze Datenstruktur gelockt werden. Die Schnittstelle ConcurrentMap deklariert vier Operationen für Implementierungen, die atomar ausgeführt werden müssen:
- V putIfAbsent( K key, V value )
- boolean remove( Object key, Object value )
- V replace( K key, V value )
- boolean replace( K key, V oldValue, V newValue )
Die Implementierungen der Schnittstelle sind ConcurrentHashMap, eine sehr schnelle Datenstruktur für gleichzeitig operierende Threads, und ConcurrentSkipListMap seit Java 6. Bei beiden lösen Veränderungen durch den Iterator keine ConcurrentModificationException aus.
Obwohl es keine Schnittstellen ConcurrentSet und ConcurrentList gibt, existiert zumindest eine Klasse ConcurrentLinkedQueue, die eine Thread-sichere und Lock-freie Liste (genauer: Queue) ist. Wie der Name schon andeutet, beruht die Realisierung auf verketteten Listen und nicht auf Arrays. Ein eigenes ConcurrentSet könnte auf der Basis von ConcurrentHashMap implementiert werden, so wie auch HashSet intern mit einer HashMap realisiert ist. In Java 6 ist die Klasse ConcurrentSkipListSet hinzugekommen.
12.11.2 Wrapper zur Synchronisation
Können zur Absicherung nebenläufiger Operationen die oben aufgeführten Datenstrukturen aus java.util.concurrent nicht verwendet werden, etwa bei Java 1.4 oder bei eigenen nicht-nebenläufig implementierten Versionen von Set, Map, List, Queue, lassen sich Zugriffe auf die Datenstrukturen extern synchronisieren. Dazu fordern statische Methoden wie synchronizedXXX() einen Wrapper an, der sich um die existierende Datenstruktur legt. Die Wrapper arbeiten nicht lock-free, und Parallelität in den Datenstrukturen ist nicht gegeben.
|
Beispiel Eine synchronisierte Liste: List<Byte> syncList = Collections.synchronizedList( new LinkedList<Byte>() );Der generische Typ der Datenstruktur geht auch weiter an den Wrapper. |
Die synchronizedXXX()-Funktionen liefern eine neue Sammlung, die sich wie eine Hülle um die existierende Datenstruktur legt und alle Funktionsaufrufe synchronisiert. Paralleler Zugriff darf natürlich dann nur noch über den Wrapper laufen, wobei nicht-paralleler Zugriff weiterhin über die Original-Datenstruktur möglich ist.
|
class java.util.Collections |
- static <T> Collection<T> synchronizedCollection( Collection<T> c )
- static <T> List<T> synchronizedList( List<T> list )
- static <K,V> Map<K,V> synchronizedMap( Map<K,V> m )
- static <T> Set<T> synchronizedSet( Set<T> s )
- static <K,V> SortedMap<K,V> synchronizedSortedMap( SortedMap<K,V> m )
- static <T> SortedSet<T> synchronizedSortedSet( SortedSet<T> s )
Liefert synchronisierte, also Thread-sichere Datenstrukturen.
Iteratoren von synchronisierten Wrappern
Mit dem Wrapper ist der nebenläufige Zugriff über die Funktionen gesichert, aber nicht der Zugriff über den Iterator. Ist syncList eine synchronisierte Datenstruktur, die ein Iterator ablaufen möchte, und während des Ablaufens soll jeder andere Zugriff gesperrt sein, ist zu schreiben:
List<Byte> syncList = Collections.synchronizedList( new LinkedList<Byte>() ); synchronized ( syncList ) { Iterator iter = syncList.iterator(); }
Die Synchronisation ist immer auf dem Wrapper und nicht auf dem »Gewrappten«.
12.11.3 CopyOnWriteArrayList und CopyOnWriteArraySet
Ist die Anzahl der Leseoperationen hoch, kann es sich lohnen, bei jedem Schreibzugriff erst die Daten zu kopieren und dann das Element hinzuzufügen, damit im Hintergrund andere Threads ohne einen Lock, der fürs Schreiben nötig ist, lesen können. Zwei dieser Datenstrukturen bietet Java an: CopyOnWriteArrayList für Listen und CopyOnWriteArraySet für Mengen. Die Klassen sind genau dann optimal, wenn wenig verändert – das ist teuer – und fast ausschließlich gelesen wird.
