제이온

[Java] Colección Sincronizada vs Colección Concurrente

Creado: 2024-04-25

Creado: 2024-04-25 22:31

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

```javascript 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

```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(); }

}


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().


```javascript static class SynchronizedList extends SynchronizedCollection implements List {

}


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.


```javascript 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() {

}


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.


```javascript 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.


```javascript public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {

}


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.


```javascript public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {

}


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

```javascript public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {

}


El código anterior es el método contains(), que muestra que CopyOnWriteArraySet define internamente CopyOnWriteArrayList y usa sus métodos.


```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); }

}


Al observar el método contains() de CopyOnWriteArrayList, vemos que no está bloqueado.


Operación de escritura

```javascript public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {

}


El método add() también toma prestado el método de 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; } }


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


```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"); } } ... } } ... }


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.


```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) 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.


```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); }


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<K, V>, por lo que los hilos que acceden al mismo bucket quedan en estado de bloqueo.

(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.

Comentarios0