La versión 1.5 y posteriores de Java Collections Framework del lenguaje de programación Java define e implementa los mapas originales de un solo subproceso y también los nuevos mapas seguros para subprocesos que implementan la java.util.concurrent.ConcurrentMap
interfaz entre otras interfaces concurrentes. En Java 1.6, la java.util.NavigableMap
interfaz se agregó, se extendió java.util.SortedMap
y la java.util.concurrent.ConcurrentNavigableMap
interfaz se agregó como una combinación de subinterfaces.
Interfaces de mapas de Java
El diagrama de la interfaz del mapa de la versión 1.8 tiene la siguiente forma. Los conjuntos se pueden considerar sub-casos de los mapas correspondientes en los que los valores son siempre una constante particular que se puede ignorar, aunque la API de conjuntos utiliza métodos correspondientes pero con nombres diferentes. En la parte inferior está java.util.concurrent.ConcurrentNavigableMap, que es una herencia múltiple.
Implementaciones
ConcurrentHashMap
Para el acceso no ordenado como se define en la interfaz java.util.Map, java.util.concurrent.ConcurrentHashMap implementa java.util.concurrent.ConcurrentMap. El mecanismo es un acceso hash a una tabla hash con listas de entradas, cada entrada contiene una clave, un valor, el hash y una siguiente referencia. Antes de Java 8, había varios bloqueos, cada uno de los cuales serializaba el acceso a un 'segmento' de la tabla. En Java 8, la sincronización nativa se usa en las cabezas de las propias listas, y las listas pueden mutar en árboles pequeños cuando amenazan con crecer demasiado debido a desafortunadas colisiones hash. Además, Java 8 usa la primitiva comparar y establecer de manera optimista para colocar las cabezas iniciales en la tabla, lo cual es muy rápido. El rendimiento es O (n), pero ocasionalmente hay retrasos cuando es necesario repetir el proceso. Una vez que la tabla hash se expande, nunca se encoge, lo que posiblemente provoque una "pérdida" de memoria después de eliminar las entradas.
ConcurrentSkipListMap
Para el acceso ordenado según lo definido por la interfaz java.util.NavigableMap, se agregó java.util.concurrent.ConcurrentSkipListMap en Java 1.6 e implementa java.util.concurrent.ConcurrentMap y también java.util.concurrent.ConcurrentNavigableMap. Es una lista de omisión que utiliza técnicas sin bloqueo para hacer un árbol. El rendimiento es O (log (n)).
Ctrie
- Ctrie Un árbol sin bloqueo basado en trie.
Problema de modificación concurrente
Un problema resuelto por el paquete Java 1.5 java.util.concurrent es el de la modificación concurrente. Las clases de colección que proporciona pueden ser utilizadas de forma fiable por varios subprocesos.
Todos los mapas no concurrentes de subprocesos compartidos y otras colecciones deben utilizar alguna forma de bloqueo explícito, como la sincronización nativa, para evitar modificaciones simultáneas, o de lo contrario debe haber una forma de demostrar a partir de la lógica del programa que la modificación simultánea no puede ocurrir. La modificación simultánea de un mapa por varios subprocesos a veces destruye la consistencia interna de las estructuras de datos dentro del mapa, lo que lleva a errores que se manifiestan raras veces o de manera impredecible y que son difíciles de detectar y corregir. Además, la modificación simultánea de un subproceso con acceso de lectura de otro subproceso o subprocesos a veces dará resultados impredecibles al lector, aunque la consistencia interna del mapa no se destruirá. El uso de la lógica del programa externo para evitar modificaciones simultáneas aumenta la complejidad del código y crea un riesgo impredecible de errores en el código existente y futuro, aunque permite utilizar colecciones no simultáneas. Sin embargo, ni los bloqueos ni la lógica del programa pueden coordinar los hilos externos que pueden entrar en contacto con la Colección.
Contadores de modificaciones
Para ayudar con el problema de modificación concurrente, las implementaciones de mapas no concurrentes y otras colecciones utilizan contadores de modificación internos que se consultan antes y después de una lectura para observar los cambios: los escritores incrementan los contadores de modificación. Se supone que este mecanismo detecta una modificación simultánea, lo que genera una excepción java.util.ConcurrentModificationException, pero no se garantiza que ocurra en todos los casos y no se debe confiar en ella. El mantenimiento del mostrador también reduce el rendimiento. Por motivos de rendimiento, los contadores no son volátiles, por lo que no se garantiza que los cambios en ellos se propaguen entre los subprocesos.
Colecciones.synchronizedMap ()
Una solución al problema de la modificación concurrente es utilizar una clase contenedora particular proporcionada por una fábrica en Colecciones: public static
que envuelve un mapa no seguro para subprocesos existente con métodos que se sincronizan en un mutex interno. También hay envoltorios para los otros tipos de colecciones. Esta es una solución parcial, porque aún es posible que los subprocesos que mantengan u obtengan referencias no envueltas puedan acceder al mapa subyacente de forma inadvertida. Además, todas las colecciones implementan los java.lang.Iterable
mapas, pero los mapas empaquetados sincronizados y otras colecciones empaquetadas no proporcionan iteradores sincronizados, por lo que la sincronización se deja al código del cliente, que es lento y propenso a errores y no es posible esperar que otros consumidores de el Mapa sincronizado. También se debe proteger toda la duración de la iteración. Además, un mapa que se envuelve dos veces en diferentes lugares tendrá diferentes objetos mutex internos en los que operan las sincronizaciones, lo que permite la superposición. La delegación es un reductor del rendimiento, pero los compiladores Just-in-Time modernos a menudo están muy integrados, lo que limita la reducción del rendimiento. Así es como funciona el envoltorio dentro del envoltorio: el mutex es solo un Objeto final y m es el Mapa envuelto final:
public V put ( clave K , valor V ) { sincronizado ( mutex ) { return m . poner ( clave , valor );} }
La sincronización de la iteración se recomienda de la siguiente manera, sin embargo, esto se sincroniza en el contenedor en lugar de en el mutex interno, lo que permite la superposición: [1]
Map < String , String > wrapMap = Colecciones . SynchronizedMap ( mapa ); ... synchronized ( wrapMap ) { for ( String s : wrapMap . keySet ()) { // alguna operación posiblemente larga ejecutada posiblemente // muchas veces, retrasando todos los demás accesos } }
Sincronización nativa
Cualquier mapa se puede utilizar de forma segura en un sistema de subprocesos múltiples al garantizar que todos los accesos sean manejados por el mecanismo de sincronización de Java:
Map < String , String > map = new HashMap < String , String > (); ... // Thread A // Usa el mapa en sí como bloqueo. En su lugar, se puede utilizar cualquier objeto acordado. sincronizado ( mapa ) { mapa . poner ( "clave" , "valor" ); } .. // Subproceso B sincronizado ( mapa ) { Resultado de cadena = mapa . obtener ( "clave" ); ... } ... // Subproceso C sincronizado ( mapa ) { para ( Entrada < Cadena , Cadena > s : mapa . EntrySet ()) { / * * Alguna operación posiblemente lenta, retrasando todas las demás operaciones supuestamente rápidas. * No es posible la sincronización en iteraciones individuales. * / ... } }
ReentrantReadWriteLock
El código que utiliza java.util.concurrent.ReentrantReadWriteLock es similar al de la sincronización nativa. Sin embargo, por seguridad, las cerraduras deben usarse en un bloqueo de intento / final de modo que la salida anticipada, como el lanzamiento de excepción o la interrupción / continuación, se asegure de pasar por el desbloqueo. Esta técnica es mejor que usar la sincronización porque las lecturas pueden superponerse entre sí, hay un nuevo problema al decidir cómo priorizar las escrituras con respecto a las lecturas. Por simplicidad, se puede usar java.util.concurrent.ReentrantLock en su lugar, que no hace distinciones entre lectura y escritura. Son posibles más operaciones en las cerraduras que con la sincronización, como tryLock()
y tryLock(long timeout, TimeUnit unit)
.
bloqueo ReentrantReadWriteLock final = nuevo ReentrantReadWriteLock (); última ReadLock readLock = cerradura . readLock (); última WriteLock WriteLock = cerradura . writeLock (); .. // Thread A try { writeLock . bloquear (); mapear . poner ( "clave" , "valor" ); ... } finalmente { writeLock . desbloquear (); } ... // Thread B try { readLock . bloquear (); Cadena s = mapa . obtener ( "clave" ); .. } finalmente { readLock . desbloquear (); } // Thread C try { readLock . bloquear (); for ( Entry < String , String > s : map . entrySet ()) { / * * Alguna operación posiblemente lenta, retrasando todas las demás operaciones supuestamente rápidas. * No es posible la sincronización en iteraciones individuales. * / ... } } finalmente { readLock . desbloquear (); }
Convoyes
La exclusión mutua tiene un problema de convoy de bloqueo , en el que los subprocesos pueden acumularse en un bloqueo, lo que hace que la JVM necesite mantener costosas colas de camareros y "estacionar" los subprocesos en espera. Es costoso estacionar y anular el estacionamiento de un hilo, y puede ocurrir un cambio de contexto lento. Los cambios de contexto requieren de microsegundos a milisegundos, mientras que las propias operaciones básicas del mapa normalmente toman nanosegundos. El rendimiento puede reducirse a una pequeña fracción del rendimiento de un solo hilo a medida que aumenta la contención. Sin embargo, cuando hay poca o ninguna contención por la cerradura, hay poco impacto en el rendimiento, a excepción de la prueba de contención de la cerradura. Las JVM modernas integrarán la mayor parte del código de bloqueo, reduciéndolo a solo unas pocas instrucciones, manteniendo el caso de no disputa muy rápido. Sin embargo, las técnicas de reentrada como la sincronización nativa o java.util.concurrent.ReentrantReadWriteLock tienen un bagaje adicional que reduce el rendimiento en el mantenimiento de la profundidad de reentrada, lo que también afecta el caso de no disputa. El problema de Convoy parece estar aliviando con JVMS moderno, pero se puede ocultar mediante un cambio de contexto lento: en este caso, la latencia aumentará, pero el rendimiento seguirá siendo aceptable. Con cientos de hilos, un tiempo de cambio de contexto de 10 ms produce una latencia en segundos.
Varios núcleos
Las soluciones de exclusión mutua no aprovechan toda la potencia informática de un sistema de múltiples núcleos, porque solo se permite un subproceso dentro del código de mapa a la vez. Las implementaciones de los mapas concurrentes particulares proporcionados por Java Collections Framework y otros a veces aprovechan múltiples núcleos utilizando técnicas de programación sin bloqueo . Las técnicas sin bloqueo utilizan operaciones como el método intrínseco compareAndSet () disponible en muchas de las clases de Java, como AtomicReference, para realizar actualizaciones condicionales de algunas estructuras internas de Map de forma atómica. La primitiva compareAndSet () es aumentada en las clases JCF por código nativo que puede hacer compareAndSet en partes internas especiales de algunos Objetos para algunos algoritmos (usando acceso 'inseguro'). Las técnicas son complejas, y se basan a menudo en las reglas de comunicación entre subprocesos proporcionadas por variables volátiles, la relación sucede antes, tipos especiales de 'bucles de reintento' sin bloqueos (que no son como bloqueos de giro en el sentido de que siempre producen progreso) . CompareAndSet () se basa en instrucciones especiales específicas del procesador. Es posible que cualquier código Java utilice para otros fines el método compareAndSet () en varias clases concurrentes para lograr una concurrencia sin bloqueo o incluso sin espera, que proporciona una latencia finita. Las técnicas sin bloqueo son simples en muchos casos comunes y con algunas colecciones simples como pilas.
El diagrama indica cómo la sincronización con Collections.synchronizedMap () que envuelve un HashMap normal (violeta) puede no escalar tan bien como ConcurrentHashMap (rojo). Los otros son ConcurrentNavigableMaps AirConcurrentMap (azul) y ConcurrentSkipListMap (CSLM verde) ordenados. (Los puntos planos pueden ser repeticiones que producen tablas que son más grandes que Nursery, y ConcurrentHashMap ocupa más espacio. Tenga en cuenta que el eje y debe decir 'pone K'. El sistema es i7 de 8 núcleos a 2,5 GHz, con -Xms5000m para evitar GC). La expansión de procesos de GC y JVM cambian las curvas considerablemente, y algunas técnicas internas Lock-Free generan basura en la contención.
Latencia predecible
Otro problema más con los enfoques de exclusión mutua es que la suposición de atomicidad completa hecha por algún código de un solo subproceso crea retrasos esporádicos inaceptablemente largos entre subprocesos en un entorno concurrente. En particular, los iteradores y las operaciones masivas como putAll () y otras pueden tomar un período de tiempo proporcional al tamaño del mapa, lo que retrasa otros subprocesos que esperan una latencia predeciblemente baja para operaciones no masivas. Por ejemplo, un servidor web de subprocesos múltiples no puede permitir que algunas respuestas se retrasen por iteraciones de larga ejecución de otros subprocesos que ejecutan otras solicitudes que buscan un valor en particular. Relacionado con esto está el hecho de que los subprocesos que bloquean el mapa en realidad no tienen ningún requisito para renunciar al bloqueo, y un bucle infinito en el subproceso propietario puede propagar el bloqueo permanente a otros subprocesos. Los subprocesos lentos del propietario a veces pueden interrumpirse. Los mapas basados en hash también están sujetos a retrasos espontáneos durante la repetición.
Consistencia débil
La solución de los paquetes java.util.concurrency para el problema de modificación concurrente, el problema del convoy, el problema de latencia predecible y el problema de múltiples núcleos incluye una elección de arquitectura llamada consistencia débil. Esta elección significa que las lecturas como get () no se bloquearán incluso cuando las actualizaciones estén en progreso, y es posible que incluso las actualizaciones se superpongan consigo mismas y con las lecturas. La consistencia débil permite, por ejemplo, que el contenido de un ConcurrentMap cambie durante una iteración del mismo por un solo hilo. Los iteradores están diseñados para ser utilizados por un hilo a la vez. Entonces, por ejemplo, un mapa que contiene dos entradas que son interdependientes puede ser visto de manera inconsistente por un hilo lector durante la modificación por otro hilo. Una actualización que se supone que debe cambiar la clave de una Entrada ( k1, v ) a una Entrada ( k2, v ) atómicamente necesitaría hacer una eliminación ( k1 ) y luego una colocación ( k2, v ), mientras que una iteración podría fallar la entrada o verla en dos lugares. Las recuperaciones devuelven el valor de una clave determinada que refleja la última actualización completada anterior para esa clave. Por tanto, hay una relación de "ocurre antes".
No hay forma de que ConcurrentMaps bloquee toda la tabla. No hay posibilidad de ConcurrentModificationException ya que existe con la modificación simultánea inadvertida de Maps no simultáneos. El método size () puede llevar mucho tiempo, a diferencia de los mapas no concurrentes correspondientes y otras colecciones que generalmente incluyen un campo de tamaño para un acceso rápido, porque es posible que necesiten escanear todo el mapa de alguna manera. Cuando se producen modificaciones simultáneas, los resultados reflejan el estado del mapa en algún momento, pero no necesariamente un estado coherente único, por lo que size (), isEmpty () y containsValue () se pueden usar mejor solo para el monitoreo.
Métodos ConcurrentMap 1.5
Hay algunas operaciones proporcionadas por ConcurrentMap que no están en Map, que extiende, para permitir la atomicidad de las modificaciones. El reemplazo ( K, v1, v2 ) probará la existencia de v1 en la Entrada identificada por K y solo si se encuentra, entonces v1 se reemplaza por v2 atómicamente. El nuevo reemplazo ( k, v ) hará un put ( k, v ) solo si k ya está en el mapa. Además, putIfAbsent ( k, v ) hará una put ( k, v ) solo si k aún no está en el mapa, y remove (k, v) eliminará la entrada para v solo si v está presente. Esta atomicidad puede ser importante para algunos casos de uso de subprocesos múltiples, pero no está relacionada con la restricción de consistencia débil.
Para ConcurrentMaps, los siguientes son atómicos.
m.putIfAbsent (k, v) es atómico pero equivalente a:
si ( k == nulo || v == nulo ) lanza una nueva NullPointerException (); if ( ! m . containsKey ( k )) { return m . poner ( k , v ); } else { return m . obtener ( k ); }
m replace (k, v) es atómico pero equivalente a:
si ( k == nulo || v == nulo ) lanza una nueva NullPointerException (); if ( m . containsKey ( k )) { devolver m . poner ( k , v ); } else { devolver nulo ; }
m.replace (k, v1, v2) es atómico pero equivalente a:
if ( k == nulo || v1 == nulo || v2 == nulo ) lanzar nueva NullPointerException (); if ( m . containsKey ( k ) && Objects . equals ( m . get ( k ), v1 )) { m . poner ( k , v2 ); devuelve verdadero ; } si no devuelve falso ; }
m.remove (k, v) es atómico pero equivalente a:
// si Map no admite claves o valores nulos (aparentemente de forma independiente) if ( k == null || v == null ) throw new NullPointerException (); if ( m . containsKey ( k ) && Objects . equals ( m . get ( k ), v )) { m . eliminar ( k ); devuelve verdadero ; } si no devuelve falso ; }
Métodos ConcurrentMap 1.8
Debido a que Map y ConcurrentMap son interfaces, no se les pueden agregar nuevos métodos sin interrumpir las implementaciones. Sin embargo, Java 1.8 agregó la capacidad para implementaciones de interfaz predeterminadas y agregó a la interfaz de mapa implementaciones predeterminadas de algunos métodos nuevos getOrDefault (Object, V), forEach (BiConsumer), replaceAll (BiFunction), computeIfAbsent (K, Function), computeIfPresent ( K, BiFunction), calcular (K, BiFunction) y fusionar (K, V, BiFunction). Las implementaciones predeterminadas en Map no garantizan la atomicidad, pero en las configuraciones predeterminadas de ConcurrentMap, estas utilizan técnicas sin bloqueo para lograr la atomicidad, y las implementaciones existentes de ConcurrentMap serán automáticamente atómicas. Las técnicas sin bloqueo pueden ser más lentas que las anulaciones en las clases concretas, por lo que las clases concretas pueden optar por implementarlas de forma atómica o no y documentar las propiedades de concurrencia.
Atomicidad sin bloqueo
Es posible utilizar técnicas sin bloqueo con ConcurrentMaps porque incluyen métodos de un número de consenso suficientemente alto, es decir, infinito, lo que significa que se puede coordinar cualquier número de subprocesos. Este ejemplo podría implementarse con Java 8 merge () pero muestra el patrón general sin bloqueo, que es más general. Este ejemplo no está relacionado con los aspectos internos de ConcurrentMap, sino con el uso del código de cliente de ConcurrentMap. Por ejemplo, si queremos multiplicar un valor en el Mapa por una constante C atómicamente:
estática final larga C = 10 ; void atomicMultiply ( ConcurrentMap < Long , Long > map , Long key ) { para (;;) { Long oldValue = map . obtener ( clave ); // Suponiendo que oldValue no es nulo. Esta es la operación de 'carga útil' y no debería tener efectos secundarios debido a un posible recálculo del conflicto Long newValue = oldValue * C ; if ( map . replace ( key , oldValue , newValue )) break ; } }
PutIfAbsent ( k, v ) también es útil cuando se permite que la entrada para la clave esté ausente. Este ejemplo podría implementarse con Java 8 compute () pero muestra el patrón general sin bloqueo, que es más general. El reemplazo ( k, v1, v2 ) no acepta parámetros nulos, por lo que a veces es necesaria una combinación de ellos. En otras palabras, si v1 es nulo, se invoca putIfAbsent ( k, v2 ); de lo contrario, se invoca replace ( k, v1, v2 ).
void atomicMultiplyNullable ( ConcurrentMap < Long , Long > map , Long key ) { for (;;) { Long oldValue = map . obtener ( clave ); // Esta es la operación de 'carga útil' y no debería tener efectos secundarios debido a un posible recálculo del conflicto Long newValue = oldValue == null ? INITIAL_VALUE : oldValue * C ; if ( replaceNullable ( map , key , oldValue , newValue )) break ; } } ... static boolean replaceNullable ( ConcurrentMap < Long , Long > map , Long key , Long v1 , Long v2 ) { return v1 == null ? mapear . putIfAbsent ( clave , v2 ) == null : map . reemplazar ( clave , v1 , v2 ); }
Historia
El marco de las colecciones de Java fue diseñado y desarrollado principalmente por Joshua Bloch , y se introdujo en JDK 1.2 . [2] Las clases de concurrencia originales vinieron de Doug Lea 's [3] paquete de colección.
Ver también
Referencias
- ^ "java.util.Collections.synchronizedMap" . Java / Java SE / 11 / API / java.base. Centro de ayuda de Oracle . 19 de septiembre de 2018 . Consultado el 17 de julio de 2020 .
- ^ Vanhelsuwé, Laurence (1 de enero de 1999). "La batalla de los frameworks de contenedores: ¿cuál debería utilizar?" . JavaWorld . Consultado el 17 de julio de 2020 .
- ^ Lea, Doug . "Descripción general del paquete util.concurrent Release 1.3.4" . Consultado el 1 de enero de 2011 .
- Goetz, Brian; Joshua Bloch; Joseph Bowbeer; Doug Lea; David Holmes; Tim Peierls (2006). Concurrencia de Java en la práctica . Addison Wesley. ISBN 0-321-34960-1. OL 25208908M .
- Lea, Doug (1999). Programación concurrente en Java: principios y patrones de diseño . Addison Wesley. ISBN 0-201-31009-0. OL 55044M .
enlaces externos
- Lecciones de colecciones
- Tutorial de la colección Java 6 - Por Jakob Jenkov, Kadafi Kamphulusa
- Taming Tiger: El marco de las colecciones
- 'The Collections Framework' (documentación de Oracle Java SE 8)
- 'Los tutoriales de Java - Colecciones' por Josh Bloch
- ¿Qué colección de Java debo usar? - Un práctico diagrama de flujo para simplificar la selección de colecciones.
- '¿Qué colección de Java usar?' - por Janeve George