Gesynchroniseerde verzameling
Gesynchroniseerde verzamelingen zijn er in verschillende klassen, met name:
- Vector
- Hashtable
- Collections.synchronizedXXX
Al deze klassen gebruiken het `synchronized` trefwoord in hun publiekelijk gedeclareerde methoden om ervoor te zorgen dat er maar één thread tegelijk toegang heeft tot de interne waarden en zo gelijktijdigheid garanderen.
Vector
```javascript
public class Vector
Als we kijken naar de `add()` methode van de Vector-klasse, die elementen toevoegt, zien we het `synchronized` trefwoord. Dit betekent dat de invoeging van elementen in Vector intern gesynchroniseerd wordt.
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(); }
}
De `contains()` methode van de Hashtable-klasse, die controleert of een waarde bestaat, gebruikt, net zoals de Vector-klasse, het `synchronized` trefwoord.
Collections.synchronizedXXX
Laten we eens kijken naar de SynchronizedList-klasse die gemaakt wordt met de `Collections.synchronizedList()` methode.
```javascript
static class SynchronizedList
}
Als we kijken naar de methoden van de SynchronizedList-klasse zien we dat ze allemaal het `synchronized` trefwoord gebruiken. De synchronisatie wordt echter bereikt met een mutex via een synchronized blok. Alle methoden delen het mutex-object, dus als één thread in een synchronized blok zit, zijn de synchronized blokken van alle andere methoden vergrendeld.
Problemen met gesynchroniseerde collecties
In een multi-thread omgeving moet je soms gesynchroniseerde collecties gebruiken, maar in de meeste gevallen is het beter om andere synchronisatiemethoden te gebruiken. Er zijn twee belangrijke redenen hiervoor.
Het combineren van meerdere bewerkingen tot één bewerking
Gesynchroniseerde collectie klassen garanderen gelijktijdigheid in een multi-thread omgeving. Als je echter meerdere bewerkingen wilt combineren tot één bewerking kan er een probleem ontstaan. Met deze gesynchroniseerde collecties kan het zijn dat de bewerking niet correct uitgevoerd wordt.
```javascript
final List
for (int i = 0; i < nThreads; i++) { es.execute(new Runnable() {
}
Als je deze code uitvoert en Thread A `remove(0)` uitvoert terwijl Thread B `clear()` uitvoert, zal er een fout optreden. Je moet dus de code als volgt in een synchronized blok plaatsen.
```javascript synchronized (list) { list.clear(); list.add("888"); list.remove(0); }
Prestatieverlies
Als je alle methoden die toegang hebben tot het gedeelde object als `synchronized` methoden definieert, of als je binnen de methoden hetzelfde `synchronized` blok definieert, zal een thread, zodra deze de lock heeft verkregen, alle andere threads in een blocking-status brengen en ze geen enkele synchronized methode meer kunnen gebruiken. Dit herhaalde patroon kan leiden tot prestatieverlies.
Concurrent collectie
Het `java.util.concurrent` pakket bevat verschillende parallele collecties. In deze blogpost bespreken we slechts een aantal van deze collecties.
- CopyOnWriteArrayList
- Een subklasse van de List-klasse, die de prestaties van het itereren door en opvragen van objecten in een lijst prioriteert.
- ConcurrentMap
- Een parallelle collectie. De interface definieert bewerkingen zoals `put-if-absent`, `replace` en `conditional remove`, die een element alleen toevoegen als het nog niet bestaat.
- ConcurrentHashMap
- Een subklasse van ConcurrentMap die parallellisme toevoegt aan HashMap.
- ConcurrentLinkedQueue
- Een FIFO-queue (First In, First Out) met parallellisme. Als de queue leeg is, wordt direct een waarde teruggegeven en kan de thread verder met andere taken.
- LinkedBlockingQueue
- Vergelijkbaar met ConcurrentLinkedQueue. Het verschil is dat, als de queue leeg is, de bewerking die een item uit de queue probeert te halen wacht tot er een item wordt toegevoegd. Omgekeerd, als de queue een bepaalde maximale grootte heeft, wacht de bewerking die een item aan de queue wil toevoegen tot er ruimte vrijkomt.
- ConcurrentSkipListMap, ConcurrentSkipListSet
- Verbeterde versies van SortedMap en SortedSet die parallellisme toevoegen.
Het vervangen van traditionele gesynchroniseerde collectieklassen door parallele collecties kan zonder extra risico's leiden tot een aanzienlijke prestatieverbetering.
Laten we eens kijken naar de parallele collecties in vergelijking met de gesynchroniseerde collecties.
CopyOnWriteArrayList
Er zijn twee manieren om een gesynchroniseerde ArrayList te creëren:
- Collections.synchronizedList()
- CopyOnWriteArrayList
`Collections.synchronizedList()` werd toegevoegd in JDK 1.2. Deze collectie synchroniseert alle lees- en schrijfbewerkingen, wat een inflexibele aanpak is. Om dit te corrigeren werd de CopyOnWriteArrayList geïntroduceerd.
Leesbewerkingen
Bij SynchronizedList worden zowel lees- als schrijfbewerkingen vergrendeld op de instantie zelf. CopyOnWriteArrayList daarentegen maakt bij schrijfbewerkingen een kopie van de elementen in de originele array en maakt een nieuwe tijdelijke array. De schrijfbewerking wordt uitgevoerd op deze tijdelijke array en vervolgens wordt de originele array bijgewerkt. Dit maakt het mogelijk dat leesbewerkingen niet worden vergrendeld, waardoor CopyOnWriteArrayList beter presteert dan SynchronizedList.
```javascript
public class CopyOnWriteArrayList
}
De `get()` methode is hierboven weergegeven. Omdat er geen `synchronized` trefwoord is, is deze niet vergrendeld.
Schrijfbewerkingen
CopyOnWriteArrayList gebruikt bij schrijfbewerkingen een expliciete lock. Uiteindelijk worden beide soorten collecties vergrendeld tijdens deze bewerkingen. CopyOnWriteArrayList voert echter een array-kopieerbewerking uit, wat relatief duur is, waardoor er prestatieproblemen kunnen optreden als er veel schrijfbewerkingen plaatsvinden.
```javascript
public class CopyOnWriteArrayList
}
Hierboven is de `add()` methode getoond. Deze wordt vergrendeld via een synchronized blok en er wordt een array-kopieerbewerking uitgevoerd.
Iterator
De `iterator` die wordt geëxtraheerd uit CopyOnWriteArrayList, itereert over de collectiegegevens op het moment dat de `iterator` wordt opgehaald. Tijdens het itereren worden toevoegingen of verwijderingen van gegevens in de collectie toegepast op een kopie die onafhankelijk is van de iteratie. Dit betekent dat er geen problemen zijn met gelijktijdig gebruik.
CopyOnWriteArraySet
Er zijn twee manieren om een gesynchroniseerde Set te creëren:
- Collections.synchronizedSet()
- CopyOnWriteArraySet
Zoals de naam al doet vermoeden, is de werking van CopyOnWriteArraySet, behalve de gegevensstructuur, bijna identiek aan die van CopyOnWriteArrayList.
Leesbewerkingen
```javascript
public class CopyOnWriteArraySet
}
De `contains()` methode is hierboven getoond. CopyOnWriteArraySet definieert intern een CopyOnWriteArrayList en gebruikt de methoden van CopyOnWriteArrayList.
```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); }
}
De `contains()` methode van CopyOnWriteArrayList is hierboven getoond. We zien dat deze niet is vergrendeld.
Schrijfbewerkingen
```javascript
public class CopyOnWriteArraySet
}
De `add()` methode maakt ook gebruik van de methoden van 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; } }
De `addIfAbsent()` methode is hierboven getoond. We zien dat bij schrijfbewerkingen de methode vergrendeld wordt en er een array-kopieerbewerking wordt uitgevoerd. Daarom is het, net als bij CopyOnWriteArrayList, ook voor CopyOnWriteArraySet beter om niet te veel schrijfbewerkingen uit te voeren.
ConcurrentHashMap
Er zijn twee manieren om een gesynchroniseerde HashMap te creëren:
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap is, net als HashMap, een Hash-gebaseerde Map. Het biedt een efficiëntere manier om gelijktijdigheid te garanderen dan synchronizedMap.
Voordat Java 8 werd uitgebracht, werd een Segment gebruikt, dat ReentrantLock erfde, om gelijktijdigheid te garanderen door de gebieden te verdelen en per gebied een lock te gebruiken.
Vanaf Java 8 wordt een andere methode gebruikt, waarbij elke tabel-bucket onafhankelijk wordt vergrendeld. Als er een nieuw element wordt toegevoegd aan een lege bucket, wordt in plaats van een lock de CAS-algoritme gebruikt. Voor andere wijzigingen wordt een gedeeltelijke lock verkregen op de eerste node van elke bucket (met een synchronized block), waardoor de contention tussen threads wordt geminimaliseerd en gelijktijdigheid wordt gegarandeerd.
Laten we eens kijken naar de code van de `putVal()` methode van ConcurrentHashMap, die een nieuw element toevoegt. Hiermee kunnen we zien hoe gelijktijdigheid wordt gegarandeerd. De volgende code is gebaseerd op Java 11.
De `putVal()` methode kan grofweg in twee gevallen (met in totaal vier vertakkingen) worden verdeeld.
- Een nieuwe node toevoegen aan een lege hash-bucket.
- Een nieuwe node toevoegen aan een hash-bucket die al nodes bevat.
```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"); } } ... } } ... }
Een nieuwe node toevoegen aan een lege hash-bucket.
(1) Om een nieuwe node toe te voegen wordt gecontroleerd of de bucket leeg is door de waarde van de betreffende bucket (`tabAt()`) op te halen.
```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) Er wordt toegang gekregen tot de volatile variabele die in de node is opgeslagen. De huidige waarde (null) wordt vergeleken met de nieuwe waarde. Als deze gelijk zijn, wordt de nieuwe node opgeslagen. Als deze niet gelijk zijn, wordt de for-loop opnieuw uitgevoerd. Dit is de CAS-algoritme.
```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); }
Het CAS-algoritme wordt gebruikt om atomische bewerkingen en zichtbaarheidsproblemen op te lossen en gelijktijdigheid te garanderen.
Een nieuwe node toevoegen aan een hash-bucket die al nodes bevat.
(3) Als er al nodes in de bucket zitten, wordt een synchronized block gebruikt om te voorkomen dat meerdere threads tegelijkertijd toegang hebben. Omdat de lock wordt verkregen op de niet-lege hash-bucket van het type Node<K, V>, worden threads die toegang proberen te krijgen tot dezelfde bucket in een blocking-status geplaatst.
(4) Vervang de node door een nieuwe node.
(5) Als er een hash-conflict is, wordt het element toegevoegd aan de `Separate Chaing`.
(6) Als er een hash-conflict is, wordt het element toegevoegd aan de `Tree`.
Referenties
Verwachte interviewvragen en antwoorden
Wat zijn de problemen met Vector, HashTable en Collections.SynchronziedXXX?
De klassen Vector, HashTable en SynchronziedXxx gebruiken `synchronized` methoden of blokken en delen één lock-object. Als één thread de lock heeft verkregen, kunnen andere threads geen enkele methode gebruiken en komen ze in een blocking-status. Dit kan leiden tot prestatieverlies in de applicatie.
Wat is het verschil tussen SynchronizedList en CopyOnArrayList?
SynchronizedList vergrendelt zowel lees- als schrijfbewerkingen op de instantie zelf. CopyOnArrayList daarentegen vergrendelt bij schrijfbewerkingen het betreffende blok, maakt een kopie van de elementen in de originele array en maakt een nieuwe tijdelijke array. De schrijfbewerking wordt uitgevoerd op deze tijdelijke array en vervolgens wordt de originele array bijgewerkt. Dit maakt het mogelijk dat leesbewerkingen niet worden vergrendeld, waardoor CopyOnWriteArrayList beter presteert dan SynchronizedList tijdens het lezen. De schrijfbewerkingen zijn echter duurder vanwege de array-kopieerbewerking, waardoor CopyOnWriteArrayList minder goed presteert dan SynchronizedList tijdens het schrijven.
Als er meer leesbewerkingen zijn dan schrijfbewerkingen, is het dus efficiënter om CopyOnArrayList te gebruiken.
Wat is het verschil tussen SynchronziedMap en ConcurrentHashMap?
SynchronziedMap vergrendelt zowel lees- als schrijfbewerkingen op de instantie zelf. ConcurrentHashMap daarentegen vergrendelt elke tabel-bucket onafhankelijk. Als er een nieuw element wordt toegevoegd aan een lege bucket, wordt in plaats van een lock de CAS-algoritme gebruikt. Voor andere wijzigingen wordt een gedeeltelijke lock verkregen op de eerste node van elke bucket (met een synchronized block), waardoor de contention tussen threads wordt geminimaliseerd en gelijktijdigheid wordt gegarandeerd.
Reacties0