practice - threads java




¿Qué es la concurrencia "sin bloqueo" y cómo es diferente de la concurrencia normal? (6)

¿Qué es la simultaneidad sin bloqueo y cómo es diferente de la concurrencia normal utilizando subprocesos?

La concurrencia sin bloqueo es una forma diferente de coordinar el acceso entre los hilos de la concurrencia de bloqueo. Existe una gran cantidad de material de fondo (teórico), pero la explicación más simple (ya que parece que está buscando una respuesta práctica simple) es que la concurrencia sin bloqueo no utiliza bloqueos.

¿Por qué no utilizamos la concurrencia "sin bloqueo" en todos los escenarios donde se requiere concurrencia?

Hacemos. Te mostraré en un momento. Pero es verdad que no siempre existen algoritmos eficientes de bloqueo para cada problema de concurrencia.

¿hay gastos generales para "no bloqueo"

Bueno, hay una sobrecarga para cualquier tipo de información compartida entre subprocesos que llegue hasta la estructura de la CPU, especialmente cuando obtienes lo que llamamos "contención", es decir, sincronizando más de un subproceso que intenta escribir en el mismo ubicación de la memoria al mismo tiempo. Pero, en general, el no bloqueo es más rápido que la concurrencia de bloqueo (basado en bloqueos) en muchos casos, especialmente en todos los casos donde hay una implementación bien conocida, simple y sin bloqueos de un algoritmo / estructura de datos dados. Son estas buenas soluciones las que se proporcionan con Java.

He escuchado que esto está disponible en Java.

Absolutamente. Para empezar, todas las clases en java.util.concurrent.atomic proporcionan un mantenimiento sin bloqueo de las variables compartidas. Además, todas las clases en java.util.concurrent cuyos nombres comienzan con ConcurrentLinked o ConcurrentSkipList, proporcionan una implementación sin bloqueos de listas, mapas y conjuntos.

¿Hay algún escenario particular que deberíamos usar esta característica?

Debería utilizar la cola y deque sin bloqueo en todos los casos en los que, de lo contrario, (antes de JDK 1.5) utilizará Collections.synchronizedlist, ya que proporcionan un mejor rendimiento en la mayoría de las condiciones. es decir, los usaría cada vez que más de un hilo esté modificando al mismo tiempo la colección, o cuando un hilo esté modificando el conjunto y otros hilos intenten leerlo. Tenga en cuenta que el popular ConcurrentHashMap realmente usa bloqueos internamente, pero es más popular que ConcurrentSkipListMap porque creo que proporciona un mejor rendimiento en la mayoría de los escenarios. Sin embargo, creo que Java 8 incluiría una implementación sin bloqueo de ConcurrentHashMap.

¿Hay alguna diferencia / ventaja de usar uno de estos métodos para una colección? ¿Cuáles son las compensaciones?

Bueno, en este breve ejemplo, son exactamente lo mismo. Sin embargo, tenga en cuenta que cuando tiene lectores y escritores concurrentes, debe sincronizar tanto las lecturas como las escrituras, y Collections.synchronizedList () lo hace. Es posible que desee probar ConcurrentLinkedQueue sin bloqueo como alternativa. Podría darle un mejor rendimiento en algunos escenarios.

Nota general

Si bien la concurrencia es un tema muy importante para aprender, tenga en cuenta que también es un tema muy complicado, donde incluso los desarrolladores con mucha experiencia a menudo se equivocan. Lo que es peor, es posible que descubra errores de concurrencia solo cuando su sistema tiene una carga pesada. Por lo tanto, siempre recomendaría usar tantas bibliotecas y clases concurrentes ya preparadas como sea posible en lugar de desplegar la suya propia.

  1. ¿Qué es la concurrencia "no bloqueante" y cómo es diferente de la concurrencia normal utilizando subprocesos? ¿Por qué no utilizamos la concurrencia sin bloqueo en todos los escenarios donde se requiere concurrencia? ¿Hay gastos generales para usar la concurrencia sin bloqueo?
  2. He oído que la concurrencia sin bloqueo está disponible en Java. ¿Hay algún escenario particular donde deberíamos usar esta característica?
  3. ¿Hay alguna diferencia o ventaja al usar uno de estos métodos con una colección? ¿Cuáles son las compensaciones?

Ejemplo para Q3:

class List   
{  
    private final ArrayList<String> list = new ArrayList<String>();

    void add(String newValue) 
    {
        synchronized (list)
        {
            list.add(newValue);
        }
    }
}  

vs.

private final ArrayList<String> list = Collections.synchronizedList(); 

Las preguntas son más desde un punto de vista de aprendizaje / comprensión. Gracias por la atención.


¿Qué es la simultaneidad sin bloqueo y cómo es diferente?

Formal:

En informática, la sincronización sin bloqueo garantiza que los hilos que compiten por un recurso compartido no se pospongan indefinidamente por exclusión mutua. Un algoritmo sin bloqueo no tiene bloqueos si se garantiza un progreso en todo el sistema; esperar libre si también hay un progreso garantizado por hilo. (wikipedia)

Informal: una de las características más ventajosas de no bloquear versus bloquear es que, los hilos no tienen que ser suspendidos / reactivados por el sistema operativo. Tal sobrecarga puede ascender a 1ms a unos 10ms, por lo que eliminar esto puede ser una gran ganancia de rendimiento. En Java, también significa que puede optar por utilizar el bloqueo no justo, que puede tener un rendimiento mucho mayor del sistema que el bloqueo justo.

He escuchado que esto está disponible en Java. ¿Hay algún escenario particular que deberíamos utilizar esta función?

Sí, desde Java5. De hecho, en Java básicamente debes tratar de satisfacer tus necesidades con java.util.concurrent tanto como sea posible (lo que sucede es que usa mucha concurrencia sin bloquear, pero no tienes que preocuparte explícitamente en la mayoría de los casos). Solo si no tiene otra opción, debe usar los contenedores sincronizados (.synchronizedList () etc.) o la palabra clave de synchronize manual. De esta forma, terminas la mayor parte del tiempo con aplicaciones más fáciles de mantener y de mejor rendimiento.

La concurrencia sin bloqueo es particularmente ventajosa cuando hay mucha contención. No puede usarlo cuando necesite bloqueo (bloqueo equitativo, cosas controladas por eventos, cola con longitud máxima, etc.), pero si no lo necesita, la concurrencia sin bloqueo tiende a funcionar mejor en la mayoría de las condiciones.

¿Hay alguna diferencia / ventaja de usar uno de estos métodos para una colección? ¿Cuáles son las compensaciones?

Ambos tienen el mismo comportamiento (el código de bytes debe ser igual). Pero sugiero usar Collections.synchronized porque es más corto = ¡habitación más pequeña para arruinar!


1] ¿Qué es la simultaneidad sin bloqueo y cómo es diferente?

Como han mencionado otros, el no bloqueo es una forma de decir punto muerto (es decir, no deberíamos tener una condición donde el progreso se detiene por completo mientras los hilos están bloqueados, esperando el acceso).

Lo que se entiende por 'concurrencia' es simplemente que múltiples cálculos ocurren al mismo tiempo (concurrentemente).

2] He escuchado que esto está disponible en Java. ¿Hay algún escenario particular que deberíamos utilizar esta función?

Desea utilizar algoritmos no bloqueantes cuando es importante que varios hilos puedan acceder a los mismos recursos al mismo tiempo, pero no estamos tan preocupados con el orden de acceso o las posibles ramificaciones de la acción de entrelazado (más sobre esto a continuación).

3] ¿Hay alguna diferencia / ventaja de usar uno de estos métodos para una colección? ¿Cuáles son las compensaciones?

.

Usar el bloque sincronizado (lista) asegura que todas las acciones realizadas dentro del bloque se vean como atómicas. Es decir, siempre que solo accedamos a la lista desde bloques sincronizados (lista), todas las actualizaciones de la lista aparecerán como si ocurrieran al mismo tiempo dentro del bloque.

Un objeto synchronizedList (o synchronizedMap) solo garantiza que las operaciones individuales son seguras para subprocesos. Esto significa que dos inserciones no ocurrirán al mismo tiempo. Considera el siguiente ciclo:

for(int i=0; i < 4; i++){
    list.add(Integer.toString(i));
}

Si la lista en uso era synchronizedList y este bucle se ejecutó en dos subprocesos diferentes, entonces podemos terminar con {0,0,1,2,1,3,2,3} en nuestra lista, o alguna otra permutación.

¿Por qué? Bien, estamos seguros de que el hilo 1 agregará 0-3 en ese orden y se nos garantiza lo mismo que el del hilo 2, sin embargo, no tenemos garantía de cómo se intercalarán.

Sin embargo, si envolvemos esta lista en un bloque sincronizado (lista):

synchronized(list){
    for(int i=0; i < 4; i++){
        list.add(Integer.toString(i));
    }
}

Estamos seguros de que las inserciones del hilo 1 y el hilo 2 no se entrelazarán, pero se producirán todas a la vez. Nuestra lista contendrá {0,1,2,3,0,1,2,3}. El otro hilo se bloqueará, esperando en la lista, hasta que se complete el primer hilo. No tenemos garantía de qué hilo será el primero, pero se nos garantiza que terminará antes de que comience el otro.

Entonces, algunas concesiones son:

  • Con syncrhonizedList, puede insertar sin utilizar explícitamente un bloque sincronizado.
  • Una Lista sincrónica puede darle una falsa sensación de seguridad, ya que puede ingenuamente creer que sucesivas operaciones en un hilo son atómicas, cuando solo las operaciones individuales son atómicas.
  • El uso de un bloque sincrónico (lista) debe realizarse con cuidado, porque estamos en condiciones de crear un interbloqueo (más abajo).

Podemos crear un interbloqueo cuando dos (o más) subprocesos están esperando cada uno un subconjunto de recursos. Si, por ejemplo, tiene dos listas: userList y movieList.

Si el hilo 1 adquiere primero el bloqueo a lista de usuario, entonces movieList, pero el segundo hilo realiza estos pasos en reversa (adquiere el bloqueo a movieList antes de UserList), entonces nos hemos abierto al punto muerto. Considere el siguiente curso de eventos:

  1. El subproceso 1 obtiene el bloqueo de la lista de usuario
  2. El subproceso 2 se bloquea en la Lista de películas
  3. El subproceso 1 intenta bloquearlo en MovieList, espera en el subproceso 2 para lanzar
  4. El subproceso 2 intenta obtener el bloqueo en userList, espera en el subproceso 1 para liberar

Ambos hilos esperan el otro y ninguno puede avanzar. Este es un escenario de bloqueo, y dado que ninguno renunciará a su recurso, estamos en un punto muerto.


  1. Wikipedia es un gran recurso para cualquier estudiante de informática. Aquí hay un artículo sobre Sincronización sin bloqueo: en.wikipedia.org/wiki/Non-blocking_synchronization

  2. La sincronización sin bloqueo está disponible en cualquier idioma, es la forma en que el programador define su aplicación multiproceso.

  3. Solo debe usar el bloqueo (es decir, sincronizado (lista)) cuando sea necesario debido al tiempo que lleva adquirir el bloqueo. En Java, el Vector es una estructura de datos segura para hilos que es muy similar a ArrayList de Java.


La sincronización sin bloqueo es la misma sincronización de bloqueo, ambas son tipo de sincronización, la única diferencia es que la sincronización sin bloqueo es más rápida en general.

Para los principiantes, usted quiere usar la sincronización solo cuando varios hilos acceden al mismo recurso en la RAM. No puede usar la sincronización cuando intenta acceder a cosas en el disco, o mejor dicho, necesita usar bloqueos en el disco.

Dicho esto, ¿cómo se puede sincronizar si ningún hilo bloquea?

La respuesta es bloqueo optimista. Esta idea ha existido por al menos 20 años. Quizás más.

Quizás hayas oído hablar del lenguaje Lisp. Como resulta que los lenguajes funcionales nunca modifican sus parámetros, solo devuelven nuevos valores, por lo que nunca necesitan sincronizarse.

En Lisp puede haber estado compartido, pero se vuelve complicado. Entonces, la mayoría de los programas pueden ejecutarse en paralelo y nunca preocuparse por la sincronización.

La idea del bloqueo optimista es que todos los subprocesos modifiquen los valores compartidos voluntariamente, pero tienen un área local para modificar los valores, y solo aplican la modificación al final, con una instrucción, atómicamente, usando CAS. Cas significa Compare And Swap, funciona en un solo ciclo de CPU y se ha implementado en CPU durante al menos 20 años.

Una excelente explicación de lo que es CAS: https://www.cs.umd.edu/class/fall2010/cmsc433/lectures/nonBlocking.pdf

Entonces, si hay un conflicto en la modificación, solo afectará a uno de los escritores, el resto se hará con él.

Además, si no existe ninguna contención, los algoritmos no bloqueantes funcionan mucho más rápido que sus contrapartes de bloqueo.

Tutorial sobre algoritmos sin bloqueo en Java con ejemplos de código que puede usar en la vida real: http://tutorials.jenkov.com/java-concurrency/non-blocking-algorithms.html


1: ¿Qué es la concurrencia "no bloqueante" y cómo es diferente de la concurrencia normal utilizando subprocesos? ¿Por qué no utilizamos la concurrencia sin bloqueo en todos los escenarios donde se requiere concurrencia? ¿Hay gastos generales para usar la concurrencia sin bloqueo?

Los algoritmos que no bloquean no utilizan esquemas específicos de bloqueo de objetos para controlar el acceso simultáneo a la memoria (los bloqueos de objetos sincronizados y estándar son ejemplos que usan bloqueos de nivel de objeto / función para reducir los problemas de acceso simultáneo en Java, sino que utilizan algún tipo de instrucción de bajo nivel para (en algún nivel) una comparación simulanea e intercambiar en una ubicación de memoria; si esto falla, simplemente devuelve falso y no produce errores, si funciona, entonces fue exitoso y usted continúa. En general, esto se intenta en un ciclo hasta que funciona, ya que solo habrá pequeños periodos de tiempo (con suerte) en los que esto fallará, simplemente se repite un par de veces más hasta que pueda configurar la memoria que necesita.

Esto no siempre se usa porque es mucho más complejo desde la perspectiva del código incluso para casos de uso relativamente triviales que la sincronización Java estándar. Además, para la mayoría de los usos, el impacto en el rendimiento del bloqueo es trivial en comparación con otras fuentes en el sistema. En la mayoría de los casos, los requisitos de rendimiento no son lo suficientemente altos como para justificar siquiera mirar esto.

Finalmente, a medida que el JDK / JRE evoluciona, los diseñadores principales están mejorando las implementaciones del lenguaje interno para intentar incorporar los medios más eficientes para lograr estos fines en los constructos centrales. A medida que se aleja de las construcciones centrales, pierde la implementación automática de esas mejoras ya que está utilizando implementaciones menos estándar (por ejemplo, jaxb / jibx; jaxb solía rendir mucho menos que jibx, pero ahora es igual si no más rápido en la mayoría de los casos que probado a partir de java 7) cuando topas tu versión java.

Si observa el siguiente ejemplo de código, puede ver las ubicaciones de 'sobrecarga'. En realidad, no se trata de una carga general, pero el código debe ser extremadamente eficiente para funcionar sin bloqueo y, en realidad, funciona mejor que una versión sincronizada estándar debido al bucle. Incluso pequeñas modificaciones pueden llevar a un código que pasará de ser varias veces mejor que el estándar a un código que es varias veces peor (por ejemplo, instancias de objetos que no necesitan estar allí o incluso comprobaciones condicionales rápidas; estamos hablando de ciclos de ahorro) aquí, entonces la diferencia entre el éxito y el fracaso es muy pequeña).

2: He oído que la concurrencia sin bloqueo está disponible en Java. ¿Hay algún escenario particular donde deberíamos usar esta característica?

En mi opinión, solo debería usar esto si A) tiene un problema de rendimiento comprobado en su sistema en ejecución en producción, en su hardware de producción; y B) si puede probar que la única ineficiencia que queda en la sección crítica está relacionada con el bloqueo; C) tiene una aceptación firme de sus partes interesadas de que están dispuestos a tener un código no estándar menos sostenible a cambio de la mejora del rendimiento que usted debe D) probar numéricamente en su hardware de producción para estar seguro de que incluso ayudará en absoluto.

3: ¿Hay alguna diferencia o ventaja al usar uno de estos métodos con una colección? ¿Cuáles son las compensaciones?

La ventaja es el rendimiento, la compensación es primero que es un código más especializado (por lo que muchos desarrolladores no saben qué hacer con él, lo que hace más difícil que un nuevo equipo o una nueva contratación se pongan al día, recuerde que la mayoría de el costo del software es mano de obra, por lo que debe observar el costo total de propiedad que usted impone a través de las decisiones de diseño), y que cualquier modificación debe probarse nuevamente para garantizar que el constructo aún sea más rápido. Por lo general, en un sistema que requeriría esto, se requeriría algún rendimiento o carga y se requerirían pruebas de rendimiento para cualquier cambio. Si no estás haciendo estas pruebas, diría que casi seguro no necesitas pensar en estos enfoques, y casi definitivamente no verías ningún valor por la complejidad incrementada (si lograste que todo funcione bien).

De nuevo, solo tengo que repetir todas las advertencias estándar en contra de la optimización en general, ya que muchos de estos argumentos son los mismos que usaría contra esto como diseño. Muchos de los inconvenientes de esto son los mismos que cualquier optimización, por ejemplo, cada vez que cambie el código, debe asegurarse de que su "corrección" no introduzca ineficiencia en algún constructo que solo se ubique allí para mejorar el rendimiento, y trate con eso (es decir, hasta la refactorización de toda la sección para eliminar potencialmente las optimizaciones) si la solución es crítica y reduce el rendimiento.

Es realmente, realmente fácil estropear esto en formas que son muy difíciles de depurar, así que si no tienes que hacerlo (que solo he encontrado algunos escenarios donde alguna vez lo harías, y para mí esos eran bastante cuestionables y hubiera preferido no hacerlo) no lo hagas. usa lo estándar y todos estarán más felices!

Discusión / Código

La concurrencia sin bloqueo o sin bloqueo evita el uso de bloqueos de objetos específicos para controlar el acceso a la memoria compartida (como bloques sincronizados o bloqueos específicos). Hay una ventaja de rendimiento cuando la sección de código no es de bloqueo; sin embargo, el código en el bucle CAS (si es así, hay otros métodos en Java) debe ser muy, muy eficiente o esto le costará más rendimiento de lo que gana.

Como todas las optimizaciones de rendimiento, la complejidad adicional no vale la pena en la mayoría de los casos de uso. La creación limpia de Java utilizando construcciones estándar funcionará igual o mejor que la mayoría de las optimizaciones (y de hecho le permitirá a su organización mantener el software más fácilmente una vez que se haya ido). En mi opinión, esto solo tiene sentido en las secciones de muy alto rendimiento con problemas de rendimiento probados donde el bloqueo es la única fuente de ineficiencia. Si definitivamente no tiene un problema de rendimiento conocido y cuantificado, evitaría el uso de cualquier técnica como esta hasta que haya probado que el problema está realmente allí debido al bloqueo y no a otros problemas con la eficiencia del código. Una vez que tenga un problema comprobado de rendimiento basado en el bloqueo, me aseguraré de que tenga algún tipo de métrica en su lugar para garantizar que este tipo de configuración realmente se ejecutará más rápido para usted que simplemente utilizando la concurrencia estándar de Java.

La implementación que he hecho para esto usa operaciones CAS y la familia de variables Atomic. Este código básico nunca me ha bloqueado ni me ha planteado ningún error en este caso de uso (entrada y salida de muestreo aleatorio para pruebas fuera de línea de un sistema de traducción de alto rendimiento). Básicamente funciona así:

Tiene un objeto que se comparte entre subprocesos, y se declara como AtomicXXX o AtomicReference (para la mayoría de los casos de uso no triviales se ejecutará con la versión de AtomicReference).

cuando se hace referencia al valor / objeto dado, lo recupera del contenedor Atomic, esto le proporciona una copia local en la que realiza alguna modificación. Desde aquí, utiliza un compareAndSwap como condición de un ciclo while para intentar establecer este Atomic a partir de su hilo, si esto falla, devuelve falso en lugar de bloquearlo. Esto se repetirá hasta que funcione (el código en este ciclo debe ser muy eficiente y simple).

Puede buscar operaciones CAS para ver cómo funcionan, básicamente se pretende implementar como un único conjunto de instrucciones con una comparación al final para ver si el valor es el que intentó establecer.

Si el compareAndSwap falla, obtienes tu objeto nuevamente del contenedor Atomic, realizas cualquier modificación de nuevo, y luego intentas comparar e intercambiar de nuevo hasta que funcione. No hay un bloqueo específico, solo intenta volver a establecer el objeto en la memoria y, si falla, simplemente intente de nuevo cada vez que el hilo vuelva a tener el control.

El código para esto está a continuación para un caso simple con una lista:

/* field declaration*/
//Note that I have an initialization block which ensures that the object in this
//reference is never null, this was required to remove null checks and ensure the CAS
//loop was efficient enough to improve performance in my use case
private AtomicReference<List<SampleRuleMessage>> specialSamplingRulesAtomic = new AtomicReference<List<SampleRuleMessage>>();


/*start of interesting code section*/

    List<SampleRuleMessage> list = specialSamplingRulesAtomic.get();
    list.add(message);
    while(!specialSamplingRulesAtomic.compareAndSet(specialSamplingRulesAtomic.get(), list)){
        list = specialSamplingRulesAtomic.get();
        list.add(message);
    };
 /* end of interesting code section*/






concurrency