Questo è un post tradotto da IA.
[Java] Synchronized Collection vs Concurrent Collection
- Lingua di scrittura: Coreana
- •
-
Paese di riferimento: Tutti i paesi
- •
- Tecnologia dell'informazione
0000-00-00 00:00:00
Seleziona la lingua
Testo riassunto dall'intelligenza artificiale durumis
- Synchronized collections like Vector, Hashtable, Collections.synchronizedXXX internally use the synchronized keyword to ensure concurrency, but they may have problems with performance degradation or when using multiple operations together.
- The concurrent collections provided in the java.util.concurrent package offer various classes like CopyOnWriteArrayList, ConcurrentMap, ConcurrentHashMap, and are more performant than synchronized collections.
- Concurrent collections like CopyOnWriteArrayList, ConcurrentHashMap have better read performance than synchronized collections, and it's more effective to use them when write operations are relatively infrequent.
Collezione sincronizzata
Le collezioni sincronizzate hanno tipicamente le seguenti classi:
- Vettore
- Hashtable
- Collections.synchronizedXXX
Tutte queste classi garantiscono la concorrenza usando la parola chiave synchronized nei metodi dichiarati pubblicamente, impedendo così che più thread contemporaneamente accedano ai valori interni.
Vettore
public class Vector extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable {
...
public synchronized boolean add(E e) {
modCount++;
add(e, elementData, elementCount);
return true;
}
... Se si osserva il metodo add() della classe Vector, che si occupa di aggiungere un elemento, si nota la parola chiave synchronized. Ciò significa che all'interno di Vector, l'operazione di inserimento di un elemento è garantita concorrenza.
Hashtable
public class Hashtable extends Dictionary
implements Map, Cloneable, java.io.Serializable {
...
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
... Nel metodo contains() della classe Hashtable, che verifica se esiste un valore identico, si può osservare, come nella classe Vector, l'utilizzo della parola chiave synchronized.
Collections.synchronizedXXX
Diamo un'occhiata alla classe SynchronizedList, creata usando il metodo Collections.synchronizedList().
static class SynchronizedList extends SynchronizedCollection
implements List {
final Object mutex;
...
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
... Osservando i metodi della classe SynchronizedList, si nota che tutti usano la parola chiave synchronized. Tuttavia, la concorrenza è implementata usando un mutex tramite un blocco synchronized. Tutti i metodi condividono l'oggetto mutex, quindi quando un thread entra nel blocco synchronized di un metodo, tutti gli altri blocchi synchronized degli altri metodi vengono bloccati.
Problemi della collezione sincronizzata
In un ambiente multi-thread, può essere necessario usare collezioni sincronizzate, ma è meglio usare altri metodi di concorrenza, se possibile. Ci sono due motivi principali per questo.
Combinazione di più operazioni come un'unica operazione
Le classi di collezioni sincronizzate garantiscono la concorrenza in un ambiente multi-thread. Tuttavia, se è necessario combinare più operazioni in un'unica operazione, potrebbero sorgere problemi. L'uso di queste collezioni sincronizzate potrebbe non garantire un corretto funzionamento.
final List list = Collections.synchronizedList(new ArrayList());
final int nThreads = 2;
ExecutorService es = Executors.newFixedThreadPool(nThreads);
for (int i = 0; i < nThreads; i++) {
es.execute(new Runnable() {
public void run() {
while(true) {
try {
list.clear();
list.add("888");
list.remove(0);
} catch(IndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}
}); Se si esegue il codice sopra, se il Thread A esegue remove(0) mentre il Thread B esegue clear(), si verifica un errore. Pertanto, è necessario raggruppare le operazioni in un blocco synchronized come mostrato di seguito.
synchronized (list) {
list.clear();
list.add("888");
list.remove(0);Riduzione delle prestazioni
Se si trasformano tutti i metodi che tentano di accedere all'oggetto condiviso in metodi synchronized o se si definiscono blocchi synchronized identici all'interno dei metodi, quando un thread acquisisce il lock, tutti gli altri thread non possono utilizzare alcun metodo sincronizzato e finiscono in stato di blocco. Questo fenomeno ripetuto può portare a una riduzione delle prestazioni.
Collezione concorrente
Il pacchetto java.util.concurrent fornisce diversi tipi di collezioni parallele, di cui alcune saranno trattate in questo articolo.
- CopyOnWriteArrayList
- È una sottoclasse della classe List e una collezione parallela che privilegia le prestazioni delle operazioni di lettura e iterazione sugli elementi dell'elenco.
- ConcurrentMap
- È una collezione parallela. L'interfaccia include operazioni come put-if-absent, replace e rimuovi-condizionale, che consentono di aggiungere elementi solo se non esistono già.
- ConcurrentHashMap
- È una sottoclasse di ConcurrentMap e una collezione parallela che sostituisce HashMap garantendo la concorrenza.
- ConcurrentLinkedQueue
- È una coda FIFO che garantisce la concorrenza. Se non ci sono elementi da estrarre dalla coda, restituisce immediatamente un valore e continua a eseguire altre operazioni.
- LinkedBlockingQueue
- È simile a ConcurrentLinkedQueue, ma se la coda è vuota, l'operazione di estrazione di un elemento dalla coda attende che venga aggiunto un nuovo elemento. Al contrario, se la coda ha una dimensione definita, l'operazione di aggiunta di un nuovo elemento alla coda attende che si liberi uno spazio nella coda.
- ConcurrentSkipListMap, ConcurrentSkipListSet
- Sono forme avanzate di SortedMap e SortedSet che migliorano la concorrenza.
Sostituire le tradizionali classi di collezioni sincronizzate con le collezioni parallele può aumentare notevolmente le prestazioni generali senza introdurre rischi aggiuntivi.
Analizziamo più in dettaglio le collezioni sincronizzate e le collezioni parallele, evidenziandone le differenze.
CopyOnWriteArrayList
Esistono due metodi per creare un ArrayList sincronizzato:
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList() è stato aggiunto in JDK 1.2. Questa collezione sincronizza tutte le operazioni di lettura e scrittura, il che la rende un design poco flessibile. Per ovviare a questo problema, è stato introdotto CopyOnWriteArrayList.
Operazioni di lettura
SynchronizedList blocca l'istanza stessa sia per le operazioni di lettura che di scrittura. Tuttavia, CopyOnWriteArrayList crea un nuovo array temporaneo copiando gli elementi dall'array originale per ogni operazione di scrittura, esegue l'operazione di scrittura sull'array temporaneo e quindi aggiorna l'array originale. Grazie a questo, le operazioni di lettura non sono bloccate, quindi le prestazioni sono migliori rispetto a SynchronizedList.
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
...
public E get(int index) {
return elementAt(getArray(), index);
}
... Il codice sopra mostra il metodo get(), che non è sincronizzato, quindi non è bloccato.
Operazioni di scrittura
CopyOnWriteArrayList utilizza un lock esplicito durante l'esecuzione delle operazioni di scrittura. In definitiva, entrambe le collezioni vengono bloccate durante questa operazione. Tuttavia, CopyOnWriteArrayList esegue un'operazione di copia dell'array, che è relativamente costosa, quindi se vengono eseguite molte operazioni di scrittura, potrebbero verificarsi problemi di prestazioni.
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
public void add(int index, E element) {
synchronized (lock) {
...
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(es, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index, newElements, index + 1,
numMoved);
}
...
}
} Il codice sopra mostra il metodo add(), che utilizza un blocco synchronized per bloccare l'operazione e eseguire la copia dell'array.
Iteratore
In CopyOnWriteArrayList, l'iteratore viene estratto in base ai dati della collezione al momento dell'estrazione e l'iterazione viene eseguita usando una copia. Pertanto, non ci sono problemi di concorrenza, anche se vengono aggiunti o eliminati dati dalla collezione durante l'iterazione.
CopyOnWriteArraySet
Esistono due metodi per creare un Set sincronizzato:
- Collections.synchronizedSet()
- CopyOnWriteArraySet
Come suggerisce il nome del metodo, il funzionamento di CopyOnWriteArraySet è quasi identico a quello di CopyOnWriteArrayList, ad eccezione delle caratteristiche della struttura dei dati.
Operazioni di lettura
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean contains(Object o) {
return al.contains(o);
} Il codice sopra mostra il metodo contains(). Si può vedere che CopyOnWriteArraySet definisce internamente CopyOnWriteArrayList e utilizza i suoi metodi.
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
Object[] es = getArray();
return indexOfRange(o, es, 0, es.length);
}
private static int indexOfRange(Object o, Object[] es, int from, int to) {
if (o == null) {
for (int i = from; i < to; i++)
if (es[i] == null)
return i;
} else {
for (int i = from; i < to; i++)
if (o.equals(es[i]))
return i;
}
return -1;Il metodo contains() di CopyOnWriteArrayList non è bloccato.
Operazioni di scrittura
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean add(E e) {
return al.addIfAbsent(e);
} Il metodo add() utilizza i metodi di CopyOnWriteArrayList.
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;
}Il metodo addIfAbsent() mostra che l'operazione di scrittura blocca l'operazione e copia l'array. Pertanto, come CopyOnWriteArrayList, è meglio evitare di eseguire troppe operazioni di scrittura su CopyOnWriteArraySet.
ConcurrentHashMap
Esistono due metodi per creare un HashMap sincronizzato:
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap è una mappa basata su hash, come HashMap. È più efficiente di synchronizedMap nel garantire la concorrenza.
Prima di Java 8, veniva utilizzato Segment, che eredita da ReentrantLock, per separare le aree e applicare il lock a ciascuna di esse.
Da Java 8 in poi, viene utilizzato un metodo che blocca ogni bucket della tabella in modo indipendente. Se viene inserito un nodo in un bucket vuoto, viene utilizzato l'algoritmo CAS invece del lock. Per le altre modifiche, viene acquisito un lock parziale (blocco synchronized) dal primo nodo del bucket per ridurre al minimo la concorrenza tra i thread e garantire la concorrenza.
Diamo un'occhiata al codice del metodo putVal() di ConcurrentHashMap, che inserisce un nuovo nodo, per capire come garantisce la concorrenza. Il codice di esempio seguente si basa su Java 11.
Il metodo putVal() può essere suddiviso in due casi principali (con un totale di quattro rami):
- Inserimento di un nodo in un bucket hash vuoto
- Se il bucket hash contiene già un nodo
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[] tab = table;;) {
Node 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(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 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 pred = e;
// (5)
if ((e = e.next) == null) {
pred.next = new Node(hash, key, value);
break;
}
}
}
// (6)
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
...
}
}
... Inserimento di un nodo in un bucket hash vuoto
(1) Per inserire un nuovo nodo, viene controllato se il valore del bucket corrispondente (tabAt()) è vuoto.
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); (2) Viene controllato se il valore della variabile volatile presente nel nodo è uguale al valore esistente (null) e, in caso affermativo, viene memorizzato un nuovo nodo. Se non è uguale, il ciclo for viene ripetuto. Questo metodo si chiama algoritmo CAS.
static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); L'algoritmo CAS risolve i problemi di atomicità e visibilità, garantendo la concorrenza.
Se il bucket hash contiene già un nodo
(3) Se esiste già un nodo, viene utilizzato un blocco synchronized per consentire l'accesso a un solo thread. In questo caso, viene applicato un lock al bucket hash non vuoto di tipo Node
(4) Il nodo viene sostituito con un nuovo nodo.
(5) Se si verifica una collisione di hash, viene aggiunto a Separate Chaing.
(6) Se si verifica una collisione di hash, viene aggiunto a un albero.
Riferimenti
Domande e risposte del colloquio
Quali sono i problemi di Vector, HashTable e Collections.SynchronziedXXX?
Le classi Vector, HashTable e SynchronziedXxx usano metodi o blocchi synchronized e condividono uno stesso lock. Quindi, quando un thread acquisisce il lock sulla collezione, tutti gli altri thread non possono usare alcun metodo e finiscono in stato di blocco. Questo può portare a una riduzione delle prestazioni dell'applicazione.
Qual è la differenza tra SynchronizedList e CopyOnArrayList?
SynchronizedList blocca l'istanza stessa sia per le operazioni di lettura che di scrittura. Tuttavia, CopyOnArrayList blocca il blocco durante l'operazione di scrittura, copia gli elementi dall'array originale per creare un nuovo array temporaneo, esegue l'operazione di scrittura sull'array temporaneo e quindi aggiorna l'array originale. Grazie a questo, le operazioni di lettura non sono bloccate, quindi le prestazioni di lettura sono migliori rispetto a SynchronizedList. Tuttavia, l'operazione di scrittura comporta un'operazione di copia dell'array, che è costosa, quindi le prestazioni di scrittura sono inferiori a quelle di SynchronizedList.
Pertanto, è più efficiente usare CopyOnArrayList se si hanno più operazioni di lettura che di modifica.
Qual è la differenza tra SynchronizedMap e ConcurrentHashMap?
SynchronziedMap blocca l'istanza stessa sia per le operazioni di lettura che di scrittura. Tuttavia, ConcurrentHashMap utilizza un metodo che blocca ogni bucket della tabella in modo indipendente. Se viene inserito un nodo in un bucket vuoto, viene utilizzato l'algoritmo CAS invece del lock. Per le altre modifiche, viene acquisito un lock parziale (blocco synchronized) dal primo nodo del bucket per ridurre al minimo la concorrenza tra i thread e garantire la concorrenza.
