Esta es una publicación traducida por IA.
[Java] Colección sincronizada vs Colección concurrente
- Idioma de escritura: Coreano
- •
-
País de referencia: Todos los países
- •
- Tecnología de la información
0000-00-00 00:00:00
Seleccionar idioma
Texto resumido por la IA durumis
- Las colecciones sincronizadas como Vector, Hashtable y Collections.synchronizedXXX utilizan internamente la palabra clave synchronized para garantizar la concurrencia, pero pueden surgir problemas como la agrupación de varias operaciones o el deterioro del rendimiento.
- El paquete java.util.concurrent proporciona diversas clases como CopyOnWriteArrayList, ConcurrentMap, ConcurrentHashMap, etc. para colecciones paralelas, que ofrecen un rendimiento superior al de las colecciones sincronizadas.
- Las colecciones paralelas como CopyOnWriteArrayList, ConcurrentHashMap, etc. ofrecen un rendimiento de lectura superior al de las colecciones sincronizadas y son efectivas cuando se realizan operaciones de escritura relativamente pocas.
Colección sincronizada
Las colecciones sincronizadas tienen las siguientes clases representativas.
- Vector
- Hashtable
- Collections.synchronizedXXX
Todos estos métodos, declarados públicamente en la clase, usan la palabra clave synchronized para controlar que solo un hilo pueda acceder al valor interno, garantizando la simultaneidad.
Vector
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;
}
... Si observamos el método add() para agregar un elemento a la clase Vector, veremos la palabra clave synchronized. Esto significa que internamente, en Vector, se garantiza la sincronización al insertar un elemento.
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;
}
... Si revisamos el método contains() de la clase Hashtable, que verifica si existe un valor idéntico, veremos que la palabra clave synchronized se utiliza de la misma manera que en la clase Vector.
Collections.synchronizedXXX
Veamos la clase SynchronizedList que se crea usando el método 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);}
}
... Si observamos los métodos de la clase SynchronizedList, veremos que todos usan la palabra clave synchronized. Sin embargo, la sincronización se implementa a través de un mutex usando un bloque synchronized. Todos los métodos comparten el objeto mutex, por lo que cuando un hilo ingresa al bloque synchronized, todos los demás bloques synchronized de otros métodos se bloquean.
Problemas con la colección sincronizada
En un entorno de múltiples hilos, a veces es necesario usar una colección sincronizada, pero en la mayoría de los casos, es mejor usar otras formas de sincronización. Hay dos razones principales para esto.
Usar varias operaciones como una sola operación
Las clases de colecciones sincronizadas garantizan la simultaneidad en un entorno de múltiples hilos. Sin embargo, si necesita agrupar varias operaciones para usarlas como una sola, puede haber problemas. Incluso con estas colecciones sincronizadas, puede que no funcione correctamente.
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();
}
}
}
}); Si ejecutamos este código, si el Hilo A ejecuta remove(0) y al mismo tiempo el Hilo B ejecuta clear(), se producirá un error. Por lo tanto, debemos agruparlo en un bloque synchronized como se muestra a continuación.
synchronized (list) {
list.clear();
list.add("888");
list.remove(0);Rendimiento reducido
Convertir todos los métodos que quieren usar el objeto compartido en métodos synchronized o definir un bloque synchronized dentro del método, hará que cuando un hilo adquiera el bloqueo, todos los demás hilos no puedan usar ningún método sincronizado y quedarán en estado de bloqueo. Esta repetición puede conducir a una disminución del rendimiento.
Colección concurrente
El paquete java.util.concurrent ofrece varios tipos de colecciones paralelas. En este artículo, solo trataremos algunos de ellos.
- CopyOnWriteArrayList
- Es una subclase de la clase List y es una colección paralela que prioriza el rendimiento de las operaciones de consulta al iterar a través de la lista de objetos.
- ConcurrentMap
- Es una colección paralela que define operaciones como put-if-absent, replace, remove condicional, etc., en la interfaz, que solo agregan nuevos elementos si no existen en la colección.
- ConcurrentHashMap
- Es una subclase de ConcurrentMap y es una colección paralela que proporciona simultaneidad como sustituto de HashMap.
- ConcurrentLinkedQueue
- Es una cola FIFO que proporciona simultaneidad. Si no hay elementos para sacar de la cola, regresa inmediatamente y ejecuta otra tarea.
- LinkedBlockingQueue
- Es similar a ConcurrentLinkedQueue. Sin embargo, si la cola está vacía, la operación de sacar elementos de la cola espera hasta que se agregue un nuevo elemento, y si la cola tiene un tamaño especificado, si la cola está llena hasta el tamaño especificado, la operación de agregar nuevos elementos a la cola espera hasta que se libere un espacio en la cola.
- ConcurrentSkipListMap, ConcurrentSkipListSet
- Son las versiones mejoradas de las clases SortedMap y SortedSet, respectivamente, para mejorar la simultaneidad.
Solo con cambiar las clases de colección sincronizada que usabas antes por las colecciones paralelas, puedes mejorar el rendimiento general sin ningún riesgo.
Veamos en detalle las colecciones sincronizadas en comparación con las colecciones paralelas.
CopyOnWriteArrayList
Hay dos formas de crear una ArrayList sincronizada.
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList() se agregó en la versión 1.2 de JDK. Esta colección está sincronizada para todas las operaciones de lectura y escritura, lo que se puede considerar un diseño inflexible. Por lo tanto, apareció CopyOnWriteArrayList como una mejora.
Operación de lectura
SynchronizedList bloquea la instancia misma durante las operaciones de lectura y escritura. Sin embargo, CopyOnWriteArrayList crea un nuevo arreglo temporal al copiar los elementos del arreglo original en cada operación de escritura, realiza la operación de escritura en este arreglo temporal y luego actualiza el arreglo original. Gracias a esto, la operación de lectura no se bloquea, por lo que el rendimiento es mejor que 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);
}
... El código anterior es el método get(), que no tiene synchronized, por lo que no se bloquea.
Operación de escritura
CopyOnWriteArrayList usa un bloqueo explícito al realizar una operación de escritura. Finalmente, ambos tipos de colecciones se bloquean en esta operación. Sin embargo, CopyOnWriteArrayList realiza una operación de copia de arreglo, que es relativamente costosa, por lo que si se realizan muchas operaciones de escritura, puede haber problemas de rendimiento.
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);
}
...
}
} El código anterior es el método add(), que bloquea a través del bloque synchronized y realiza la operación de copia del arreglo.
Iterator
CopyOnWriteArrayList itera en base a los datos de la colección en el momento en que se saca el iterador, y durante la iteración, los cambios en la colección, como agregar o eliminar datos, se reflejan en la copia, que es independiente del bucle de iteración, por lo que no hay problemas con el uso simultáneo.
CopyOnWriteArraySet
Hay dos formas de crear un Set sincronizado.
- Collections.synchronizedSet()
- CopyOnWriteArraySet
Como sugiere el nombre del método, el funcionamiento es casi idéntico a CopyOnWriteArrayList, excepto por las características de la estructura de datos.
Operación de lectura
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean contains(Object o) {
return al.contains(o);
} El código anterior es el método contains(), que muestra que CopyOnWriteArraySet define internamente CopyOnWriteArrayList y usa sus métodos.
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;Al observar el método contains() de CopyOnWriteArrayList, vemos que no está bloqueado.
Operación de escritura
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean add(E e) {
return al.addIfAbsent(e);
} El método add() también toma prestado el método de 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;
}Si observamos el método addIfAbsent(), vemos que bloquea al realizar la operación de escritura y realiza la copia del arreglo. Por lo tanto, como CopyOnWriteArrayList, CopyOnWriteArraySet también debe evitar realizar muchas operaciones de escritura.
ConcurrentHashMap
Hay dos formas de crear un HashMap sincronizado.
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap es un Map basado en Hash, al igual que HashMap. Proporciona una forma más eficiente de garantizar la simultaneidad en comparación con synchronizedMap.
Antes de Java 8, usaba Segment, que heredaba ReentrantLock, para dividir el espacio y bloquearlo por área.
Desde Java 8, se usa un enfoque en el que cada bucket de la tabla se bloquea de forma independiente. Si se inserta un nodo en un bucket vacío, se usa el algoritmo CAS en lugar de un bloqueo, y para otros cambios, se adquiere un bloqueo parcial (bloque synchronized) basado en el primer nodo del bucket para minimizar la competencia entre hilos y garantizar la simultaneidad.
Veamos el código del método putVal(), que inserta un nuevo nodo en ConcurrentHashMap, para comprobar cómo se garantiza la simultaneidad. El código de ejemplo que se muestra a continuación se basa en Java 11.
El método putVal() se puede dividir en dos casos (las ramificaciones son un total de cuatro partes).
- Si se inserta un nodo en un bucket de hash vacío
- Si ya existe un nodo en el bucket de hash
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");
}
}
...
}
}
... Si se inserta un nodo en un bucket de hash vacío
(1) Para insertar un nuevo nodo, se obtiene el valor de ese bucket (tabAt()) y se comprueba si está vacío.
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); (2) Se accede a la variable volátil contenida en el nodo, se compara con el valor existente (null) y si es igual, se almacena un nuevo nodo. Si no es igual, se vuelve al bucle for. Este enfoque es el algoritmo CAS.
static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); El algoritmo CAS se utiliza para resolver los problemas de atomicidad y visibilidad y garantizar la simultaneidad.
Si ya existe un nodo en el bucket de hash
(3) Si ya existe un nodo, se usa el bloque synchronized para controlar que solo un hilo acceda. En este caso, se bloquea el bucket de hash no vacío de tipo Node
(4) Se sustituye por un nuevo nodo.
(5) Si se produce una colisión de hash, se agrega a Separate Chaing.
(6) Si se produce una colisión de hash, se agrega al árbol.
Referencias
Preguntas y respuestas de la entrevista esperadas
¿Cuáles son los problemas de Vector, HashTable y Collections.SynchronziedXXX?
Las clases Vector, HashTable y SynchronziedXxx usan métodos o bloques synchronized y comparten un solo objeto de bloqueo. Por lo tanto, si un hilo adquiere el bloqueo en la colección, los otros hilos no pueden usar ningún método y quedan en estado de bloqueo. Esto puede provocar una disminución del rendimiento de la aplicación.
¿Cuál es la diferencia entre SynchronizedList y CopyOnArrayList?
SynchronizedList bloquea la instancia misma durante las operaciones de lectura y escritura. Sin embargo, CopyOnArrayList bloquea el bloque correspondiente durante la operación de escritura, copia los elementos del arreglo original en un nuevo arreglo temporal, realiza la operación de escritura en este arreglo temporal y luego actualiza el arreglo original. Gracias a esto, la operación de lectura no se bloquea, por lo que el rendimiento de lectura es mejor que SynchronizedList. Sin embargo, la operación de escritura realiza una operación de copia de arreglo, que es costosa, por lo que el rendimiento de escritura es peor que SynchronizedList.
Por lo tanto, si hay más operaciones de lectura que de cambios, es más eficaz usar CopyOnArrayList.
¿Cuál es la diferencia entre SynchronizedMap y ConcurrentHashMap?
SynchronziedMap bloquea la instancia misma durante las operaciones de lectura y escritura. Sin embargo, ConcurrentHashMap usa un enfoque en el que cada bucket de la tabla se bloquea de forma independiente. Si se inserta un nodo en un bucket vacío, se usa el algoritmo CAS en lugar de un bloqueo, y para otros cambios, se adquiere un bloqueo parcial (bloque synchronized) basado en el primer nodo del bucket para minimizar la competencia entre hilos y garantizar la simultaneidad.
