Synchronisierte Sammlung
Synchronisierte Sammlungen sind in der Regel Klassen wie die folgenden:
- Vektor
- Hashtable
- Collections.synchronizedXXX
Alle diese Klassen verwenden das Schlüsselwort synchronized in öffentlich deklarierten Methoden, um sicherzustellen, dass nur ein Thread gleichzeitig auf die Werte zugreifen kann und gleichzeitig die Gleichzeitigkeit gewährleistet.
Vektor
```javascript
public class Vector
Betrachten wir die add()-Methode, die Elemente in der Vector-Klasse hinzufügt, sehen wir das Schlüsselwort synchronized. D. h. innerhalb von Vector wird der Einfügevorgang von Elementen synchronisiert.
Hashtable
```javascript public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { ... public synchronized boolean contains(Object value) { if (value == null) { throw new NullPointerException(); }
}
Wenn wir uns die contains()-Methode in der Hashtable-Klasse ansehen, um zu überprüfen, ob der gleiche Wert vorhanden ist, stellen wir fest, dass das Schlüsselwort synchronized verwendet wird, genau wie in der Vector-Klasse.
Collections.synchronizedXXX
Schauen wir uns nun die SynchronizedList-Klasse an, die mit der Methode Collections.synchronizedList() erzeugt wird.
```javascript
static class SynchronizedList
}
Wenn wir uns die Methoden der SynchronizedList-Klasse ansehen, stellen wir fest, dass alle das Schlüsselwort synchronized verwenden. Allerdings wurde die Synchronisation mithilfe eines Mutex über einen synchronisierten Block implementiert. Da alle Methoden das Mutex-Objekt gemeinsam nutzen, werden alle synchronisierten Blöcke anderer Methoden gesperrt, sobald ein Thread in den synchronisierten Block eingetreten ist.
Probleme mit synchronisierten Sammlungen
In einer Multithread-Umgebung kann es notwendig sein, synchronisierte Sammlungen zu verwenden. Es ist jedoch ratsam, andere Synchronisationsmethoden zu verwenden, wenn möglich. Es gibt dafür zwei Hauptgründe:
Mehrere Operationen als eine einzelne Operation zusammenfassen
Synchronisierte Sammlungsklassen gewährleisten die Gleichzeitigkeit in einer Multithread-Umgebung. Wenn jedoch mehrere Operationen zu einer einzigen Operation zusammengefasst werden müssen, können Probleme auftreten. Die Verwendung dieser synchronisierten Sammlungen kann zu Fehlfunktionen führen.
```javascript
final List
for (int i = 0; i < nThreads; i++) { es.execute(new Runnable() {
}
Wenn der obige Code ausgeführt wird, tritt ein Fehler auf, wenn Thread A remove(0) ausführt und Thread B gleichzeitig clear() ausführt. Daher muss dies mit einem synchronisierten Block wie folgt umschlossen werden.
```javascript synchronized (list) { list.clear(); list.add("888"); list.remove(0); }
Leistungseinbußen
Wenn alle Methoden, die auf ein gemeinsam genutztes Objekt zugreifen möchten, zu synchronisierten Methoden gemacht werden oder innerhalb der Methoden der gleiche synchronisierte Block definiert wird, kann kein anderer Thread alle synchronisierten Methoden verwenden, wenn ein Thread die Sperre erlangt hat. Dieser Thread befindet sich dann in einem Sperrzustand. Diese wiederholten Vorgänge können zu Leistungseinbußen führen.
Gleichzeitige Sammlung
Das Paket java.util.concurrent bietet verschiedene Arten von parallelen Sammlungen. In diesem Artikel werden nur einige davon behandelt.
- CopyOnWriteArrayList
- Eine Unterklasse der List-Klasse, die eine parallele Sammlung ist, die die Leistung von Operationen priorisiert, die die Objekt-Liste durchlaufen und abrufen.
- ConcurrentMap
- Eine parallele Sammlung, deren Schnittstelle Operationen wie put-if-absent, replace und bedingtes Entfernen definiert, die einen neuen Eintrag nur dann hinzufügen, wenn der hinzuzufügende Eintrag noch nicht vorhanden ist.
- ConcurrentHashMap
- Eine Unterklasse von ConcurrentMap, eine parallele Sammlung, die HashMap ersetzt und gleichzeitig die Parallelität gewährleistet.
- ConcurrentLinkedQueue
- Eine parallele Sammlung, die eine Queue im FIFO-Modus (First In First Out) ist. Wenn kein Element aus der Queue entnommen werden kann, wird sofort eine Rückgabe durchgeführt und eine andere Aufgabe ausgeführt.
- LinkedBlockingQueue
- Ähnlich wie ConcurrentLinkedQueue. Der Unterschied besteht darin, dass Operationen zum Entfernen von Elementen aus der Queue warten, bis ein neues Element hinzugefügt wird, wenn die Queue leer ist. Umgekehrt wird das Hinzufügen eines neuen Elements in die Queue warten, bis Platz frei wird, wenn die Queue eine bestimmte Größe hat und vollständig gefüllt ist.
- ConcurrentSkipListMap, ConcurrentSkipListSet
- Fortschrittliche Versionen der Klassen SortedMap bzw. SortedSet, die die Parallelität verbessern.
Der Austausch bestehender synchronisierter Sammlungsklassen durch parallele Sammlungen kann die Gesamtperformance ohne zusätzliche Risiken deutlich verbessern.
Lassen Sie uns die synchronisierten Sammlungen im Vergleich zu parallelen Sammlungen genauer betrachten.
CopyOnWriteArrayList
Es gibt zwei Möglichkeiten, eine synchronisierte ArrayList zu erstellen:
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList() wurde in JDK 1.2 hinzugefügt. Diese Sammlung ist für alle Lese- und Schreibvorgänge synchronisiert. Dies kann als ein nicht flexibles Design angesehen werden. Daher wurde CopyOnWriteArrayList als Ergänzung eingeführt.
Lesevorgänge
SynchronizedList sperrt die Instanz selbst beim Lesen und Schreiben. CopyOnWriteArrayList hingegen kopiert bei jedem Schreibvorgang die Elemente aus dem ursprünglichen Array in ein neues temporäres Array und führt dann den Schreibvorgang in diesem temporären Array durch, bevor das ursprüngliche Array aktualisiert wird. Dadurch sind Lesevorgänge nicht gesperrt, was CopyOnWriteArrayList schneller macht als SynchronizedList.
```javascript
public class CopyOnWriteArrayList
}
Dies ist die get()-Methode, die keine Synchronisierung enthält und daher nicht gesperrt ist.
Schreibvorgänge
CopyOnWriteArrayList verwendet beim Ausführen von Schreibvorgängen eine explizite Sperre. Letztendlich werden beide Sammlungstypen beim Ausführen dieses Vorgangs gesperrt. Da CopyOnWriteArrayList einen relativ teuren Kopiervorgang für das Array verwendet, kann es zu Leistungsproblemen kommen, wenn viele Schreibvorgänge ausgeführt werden.
```javascript
public class CopyOnWriteArrayList
}
Dies ist die add()-Methode, die einen synchronisierten Block verwendet, um eine Sperre zu setzen und das Array zu kopieren.
Iterator
In CopyOnWriteArrayList werden die Daten der Sammlung zum Zeitpunkt des Abrufens des Iterators iteriert. Da Änderungen an der Sammlung während der Iteration auf die Kopie angewendet werden, die unabhängig vom Iterator ist, gibt es keine Probleme mit der gleichzeitigen Verwendung.
CopyOnWriteArraySet
Es gibt zwei Möglichkeiten, eine synchronisierte Set zu erstellen:
- Collections.synchronizedSet()
- CopyOnWriteArraySet
Wie der Methodennamen andeutet, ist die Funktionsweise mit CopyOnWriteArrayList bis auf die Datenstruktur fast identisch.
Lesevorgänge
```javascript
public class CopyOnWriteArraySet
}
Dies ist die contains()-Methode, die zeigt, dass CopyOnWriteArraySet intern CopyOnWriteArrayList definiert und die Methoden von CopyOnWriteArrayList verwendet.
```javascript public boolean contains(Object o) { return indexOf(o) >= 0; }
public int indexOf(Object o) { Object[] es = getArray(); return indexOfRange(o, es, 0, es.length); }
}
Wenn wir uns die contains()-Methode von CopyOnWriteArrayList ansehen, stellen wir fest, dass sie nicht gesperrt ist.
Schreibvorgänge
```javascript
public class CopyOnWriteArraySet
}
Die add()-Methode verwendet ebenfalls die Methode von CopyOnWriteArrayList.
```javascript public boolean addIfAbsent(E e) { Object[] snapshot = getArray(); return indexOfRange(e, snapshot, 0, snapshot.length) < 0 && addIfAbsent(e, snapshot); }
private boolean addIfAbsent(E e, Object[] snapshot) { synchronized (lock) { Object[] current = getArray(); int len = current.length; if (snapshot != current) { // Optimize for lost race to another addXXX operation int common = Math.min(snapshot.length, len); for (int i = 0; i < common; i++) if (current[i] != snapshot[i] && Objects.equals(e, current[i])) return false; if (indexOfRange(e, current, common, len) >= 0) return false; } Object[] newElements = Arrays.copyOf(current, len + 1); newElements[len] = e; setArray(newElements); return true; } }
Wenn wir uns die addIfAbsent()-Methode ansehen, stellen wir fest, dass sie beim Ausführen eines Schreibvorgangs eine Sperre setzt und das Array kopiert. Daher ist es auch bei CopyOnWriteArraySet, genau wie bei CopyOnWriteArrayList, empfehlenswert, nicht zu viele Schreibvorgänge durchzuführen.
ConcurrentHashMap
Es gibt zwei Möglichkeiten, eine synchronisierte HashMap zu erstellen:
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap ist wie HashMap eine auf Hash basierende Map. Im Vergleich zu synchronizedMap bietet es eine effizientere Möglichkeit, die Gleichzeitigkeit zu gewährleisten.
Vor Java 8 wurde ReentrantLock von Segment geerbt, um die Sperre durch Aufteilung in Bereiche zu gewährleisten.
Ab Java 8 werden die einzelnen Tabellen-Buckets unabhängig voneinander gesperrt. Wenn ein neuer Knoten in einen leeren Bucket eingefügt wird, wird anstelle einer Sperre der CAS-Algorithmus verwendet. Alle anderen Änderungen werden unter Verwendung einer teilweisen Sperre (synchronized block) auf Basis des ersten Knotens des jeweiligen Buckets ausgeführt, um Thread-Konflikte zu minimieren und gleichzeitig die Parallelität zu gewährleisten.
Schauen wir uns den Code der putVal()-Methode an, die einen neuen Knoten in ConcurrentHashMap einfügt, um zu verstehen, wie die Parallelität gewährleistet wird. Dieser Code bezieht sich auf Java 11.
Die putVal()-Methode kann grob in zwei Fälle (insgesamt vier Verzweigungen) unterteilt werden:
- Ein Knoten wird in einen leeren Hash-Bucket eingefügt
- Es ist bereits ein Knoten im Hash-Bucket vorhanden
```javascript final V putVal(K key, V value, boolean onlyIfAbsent) { if (key null || value null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; K fk; V fv; if (tab null || (n = tab.length) 0) tab = initTable(); // (1) else if ((f = tabAt(tab, i = (n - 1) & hash)) null) { // (2) if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) break; } else if ((fh = f.hash) MOVED) tab = helpTransfer(tab, f); else if (onlyIfAbsent // check first node without acquiring lock && fh hash && ((fk = f.key) key || (fk != null && key.equals(fk))) && (fv = f.val) != null) return fv; // (3) else { V oldVal = null; synchronized (f) { if (tabAt(tab, i) f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; // (4) if (e.hash hash && ((ek = e.key) key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; // (5) if ((e = e.next) null) { pred.next = new Node<K,V>(hash, key, value); break; } } } // (6) else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } else if (f instanceof ReservationNode) throw new IllegalStateException("Recursive update"); } } ... } } ... }
Ein Knoten wird in einen leeren Hash-Bucket eingefügt
(1) Um einen neuen Knoten einzufügen, wird der Wert des entsprechenden Buckets (tabAt()) abgerufen und geprüft, ob er leer ist.
```javascript static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); }
(2) Der volatile Variablen im Knoten wird zugegriffen und mit dem alten Wert (null) verglichen. Wenn sie gleich sind, wird der neue Knoten gespeichert. Wenn sie nicht gleich sind, wird die Schleife for erneut durchlaufen. Dieses Verfahren ist der CAS-Algorithmus.
```javascript static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) { return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); }
Mithilfe des CAS-Algorithmus werden Atomaartigkeit und Sichtbarkeitsprobleme gelöst, um die Gleichzeitigkeit zu gewährleisten.
Es ist bereits ein Knoten im Hash-Bucket vorhanden
(3) Wenn bereits ein Knoten vorhanden ist, wird mit einem synchronisierten Block sichergestellt, dass nur ein Thread zugreifen kann. In diesem Fall wird die Sperre auf den nicht leeren Hash-Bucket vom Typ Node<K, V> gesetzt, so dass Threads, die auf denselben Bucket zugreifen, in den Sperrzustand versetzt werden.
(4) Der neue Knoten wird ersetzt.
(5) Wenn eine Hash-Kollision auftritt, wird sie der separaten Verkettung hinzugefügt.
(6) Wenn eine Hash-Kollision auftritt, wird sie dem Baum hinzugefügt.
Referenz
Erwartete Interviewfragen und Antworten
Was sind die Probleme von Vector, HashTable und Collections.SynchronziedXXX?
Die Klassen Vector, HashTable und SynchronziedXxx verwenden synchronisierte Methoden oder Blöcke und teilen sich ein einziges Sperrobjekt. Daher kann, wenn ein Thread die Sperre für die Sammlung erwirbt, kein anderer Thread alle Methoden verwenden und befindet sich im Sperrzustand. Dies kann zu Leistungseinbußen in der Anwendung führen.
Was ist der Unterschied zwischen SynchronizedList und CopyOnArrayList?
SynchronizedList sperrt die Instanz selbst beim Lesen und Schreiben. CopyOnArrayList hingegen sperrt den entsprechenden Block beim Schreiben und kopiert die Elemente aus dem ursprünglichen Array in ein neues temporäres Array. Anschließend führt es den Schreibvorgang in diesem temporären Array aus, bevor das ursprüngliche Array aktualisiert wird. Dadurch sind Lesevorgänge nicht gesperrt, wodurch CopyOnArrayList eine bessere Leseleistung als SynchronizedList erzielt. Da jedoch ein relativ teurer Kopiervorgang für das Array durchgeführt wird, ist die Schreibgeschwindigkeit von CopyOnArrayList geringer als die von SynchronizedList.
Daher ist es effektiver, CopyOnArrayList zu verwenden, wenn mehr gelesen als geschrieben wird.
Was ist der Unterschied zwischen SynchronizedMap und ConcurrentHashMap?
SynchronziedMap sperrt die Instanz selbst beim Lesen und Schreiben. ConcurrentHashMap hingegen verwendet eine Methode, bei der jeder Tabellen-Bucket unabhängig voneinander gesperrt wird. Wenn ein neuer Knoten in einen leeren Bucket eingefügt wird, wird anstelle einer Sperre (Lock) der CAS-Algorithmus verwendet. Alle anderen Änderungen werden unter Verwendung einer teilweisen Sperre (synchronized block) auf Basis des ersten Knotens des jeweiligen Buckets ausgeführt, um Thread-Konflikte zu minimieren und gleichzeitig die Parallelität zu gewährleisten.
Kommentare0