Concurrencia componible en Java o cualquier otro lenguaje de programación

8

Mientras leía un artículo de investigación sobre concurrencia llamado Software and the Concurrency Revolution ( versión html ). Encontré las siguientes líneas:

Desafortunadamente, aunque los bloqueos funcionan, plantean serios problemas para el desarrollo de software moderno. Un problema fundamental con las cerraduras es que no son componibles . No puede tomar dos piezas de código correctas basadas en bloqueo, combinarlas y saber que el resultado sigue siendo correcto. El desarrollo de software moderno se basa en la capacidad de componer bibliotecas en programas más grandes, por lo que es una gran dificultad que no podamos construir sobre componentes basados ​​en bloqueos sin examinar sus implementaciones.

  1. Estaba pensando, cómo Java garantiza la concurrencia composable o incluso si hay una manera de producir estos escenarios.

  2. ¿Y cómo podemos sincronizar datos en una o más bibliotecas? ¿Puede un programador hacerlo desde su programa o depende de la biblioteca sincronizar las cosas?

  3. Si no es Java, ¿hay algún otro idioma que use concurrencia basada en bloqueo y garantice concurrencia componible?

Lo siguiente también se toma del mismo documento:

Existen al menos tres problemas principales con los métodos sincronizados. Primero, no son apropiados para tipos cuyos métodos invocan funciones virtuales en otros objetos (por ejemplo, Vector de Java y SyncHashTable de .NET), porque llamar a un código de terceros mientras se mantiene un bloqueo abre la posibilidad de un punto muerto . En segundo lugar, los métodos sincronizados pueden realizar demasiados bloqueos, mediante la adquisición y liberación de bloqueos en todas las instancias de objetos, incluso aquellos que nunca se comparten entre subprocesos (generalmente la mayoría). Tercero, los métodos sincronizados también pueden realizar muy poco bloqueo, al no preservar la atomicidad cuando un programa llama a múltiples métodos en un objeto o en diferentes objetos. Como un ejemplo simple de esto último, considere una transferencia bancaria: cuenta1.Crédito (monto); cuenta 2. Débito (cantidad) ...

Nota: El artículo se publicó en septiembre de 2005.

mosquito
fuente
El documento de @ErikEidt tiene 94 citas
3
No es una respuesta a la pregunta, pero obtienes una simultaneidad mucho mejor cuando restringes las interacciones a la transmisión de mensajes: procesos (procesos completos, no solo hilos) que se comunican a través de colas de mensajes asincrónicas. Es cierto que no es tan eficaz como el modelo basado en amenazas, pero si el envío de un mensaje no puede bloquearse, no puede bloquearse a menos que tenga una dependencia de datos circular real codificada en sus mensajes. Lo más importante, cualquier mensaje es trivialmente compuesto / interpretado como una operación atómica, por lo que todos los dolores de cabeza del estado constante desaparecen.
cmaster - reinstalar a monica el
1
La memoria transaccional de software es una construcción de concurrencia que se puede componer. Haskell tiene una biblioteca STM.
tormenta el
1
@penguin: concurrencia! = paralelismo. Javascript (node.js) es un buen ejemplo de un lenguaje con muy alta concurrencia (de hecho, todas las E / S son concurrentes) pero tiene un solo subproceso. Java tiene un marco bastante bueno para esto en forma de Futuros (CompletionStage). Por supuesto, cuán libre de bloqueo esté su código depende de la implementación, pero las herramientas están ahí para que pueda desarrollarlas.
slebetman

Respuestas:

7

No es el lenguaje Java. Es la naturaleza de las cerraduras (mutexes).

Hay mejores formas de mejorar la simultaneidad sin dejar de garantizar la corrección, formas que son independientes del idioma:

  1. Usando objetos inmutables, para que no necesite bloqueos.
  2. Uso de promesas y estilo de paso continuo.
  3. Uso de estructuras de datos sin bloqueo.
  4. Uso de la memoria transaccional de software para compartir el estado de forma segura.

Todas estas técnicas permiten mejorar la concurrencia sin usar bloqueos. Ninguno de ellos depende del lenguaje Java específicamente.

Robert Harvey
fuente
3

Estaba pensando, cómo Java garantiza la concurrencia componible o incluso si hay una manera de producir estos escenarios.

Como dice el artículo, no es posible garantizar la componibilidad al usar bloqueos junto con métodos virtuales (u otro mecanismo similar, como pasar funciones como parámetros). Si un fragmento de código tiene acceso a métodos virtuales que provienen de otro fragmento de código y ambos potencialmente usan bloqueos, entonces para componer los dos fragmentos de código de manera segura (es decir, sin el riesgo de un punto muerto), debe inspeccionar el código fuente de ambos.

¿Y cómo podemos sincronizar datos en una o más bibliotecas? ¿Puede un programador hacerlo desde su programa o depende de la biblioteca sincronizar las cosas?

En general, depende del programador usar las bibliotecas para realizar la sincronización. De esa manera, el programador sabe dónde están todos los bloqueos y puede asegurarse de que no se bloqueen.

Si no es Java, ¿hay algún otro idioma que use concurrencia basada en bloqueo y garantice concurrencia componible?

Una vez más, el punto del artículo es que esto no es posible.

svick
fuente
El documento fue publicado en 2005. Su respuesta se basa en el mismo documento. Los idiomas han evolucionado mucho desde 2005. ¿Puede dar alguna referencia más reciente o puede confirmar su respuesta?
2
Ese documento no habla de nada que sea específico para 2005. Todavía será cierto en 2105 que las bibliotecas basadas en bloqueo no son componibles.
svick
Java actualiza constantemente sus construcciones de bloqueo, puede comparar el paquete de concurrencia de Java en Java5 hasta Java8.
No importa. Java 8 ciertamente no eliminó la posibilidad de un punto muerto cuando se usan bloqueos, por lo que nada cambió al respecto.
svick
2
@penguin: es imposible hacer que un lenguaje sea completamente componible una vez que tiene características no componibles, porque no puede garantizar que los módulos cerrados no los usen de manera peligrosa. Puede hacer que su código sea componible, incluso si está usando bloqueos (aunque debe tener cuidado con la forma en que los usa en este caso), pero no puede estar seguro de que las bibliotecas arbitrarias y / o los componentes del sistema no lo sean.
Julio
1

Los mecanismos de bloqueo de bajo nivel no son inherentemente compostables. Esto se debe principalmente a que las cerraduras alcanzan debajo del mundo para afectar la máquina que ejecuta las instrucciones.

Las bibliotecas posteriores de Java han agregado mecanismos cada vez más altos para garantizar el funcionamiento correcto de subprocesos múltiples. Lo hacen al restringir el uso de lock()y volatilepara ciertos conocido, y controlables circunstancias. Por ejemplo, una implementación de cola simultánea tiene un comportamiento muy localizado y permite razonar sobre los estados antes y después. El uso de mecanismos de nivel superior significa que necesita leer menos de la especificación o el código para hacerlo bien. Pero, y esto es un gran pero, aún necesita comprender el modelo de bloqueo de cualquier subsistema y cómo interactúan entre sí. Además, los cambios en Java para la concurrencia después de Java 5 están casi exclusivamente relacionados con las bibliotecas y no con el lenguaje.

El principal problema con cualquier mecanismo de bloqueo es que afecta el estado y opera en el dominio del tiempo. Ni los humanos ni las computadoras razonan bien sobre el estado o el tiempo. Es la capacidad de razonar sobre el valor y la estructura lo que permitió a los científicos de la computación encontrar mónadas, lo primero que se me ocurre con respecto a la componibilidad en un lenguaje.

Lo más cerca que hemos llegado es de comunicar procesos secuenciales . Esto todavía requiere un mecanismo de alto nivel, como los buzones y el paso de mensajes. En mi humilde opinión, CSP todavía no trata adecuadamente con sistemas grandes (el objetivo final del software composable) o el razonamiento basado en el tiempo.

BobDalgleish
fuente
1
Esto no responde mi pregunta. Quería saber si Java es componible o hay algún otro idioma que lo sea. Según las dos respuestas que obtuve, Java no es componible, pero ambas respuestas no proporcionan ninguna evidencia concreta.
¿Querías una prueba de que Java usando solo bloqueos no es composable? Además, si lee el artículo de CSP anterior, verá un montón de idiomas mencionados que son componibles. Mis comentarios se refieren a cualquier idioma donde lock()y volatileson la granularidad del hilo o la sincronización de procesos.
BobDalgleish
De acuerdo, hay algo que me interesa. En tu respuesta dijiste "Lo más cerca que hemos llegado ...", ¿qué quieres decir con eso? ¿Cómo descubriste que CSP es el más cercano?
1

En primer lugar, agradezco a todos los miembros que respondieron esta pregunta, especialmente a Robert Harvey, cuya respuesta parece muy similar a la mía.

He estado investigando sobre conceptos de concurrencia durante dos años y, según mis hallazgos, ningún lenguaje garantiza que sus construcciones de concurrencia sean componibles. El código de ejecución perfectamente bueno que usa estructuras de datos inmutables y STM también puede producir resultados inesperados porque, bajo el capó, STM usa bloqueos. STM es muy bueno para las operaciones atómicas, pero si hablamos de la posibilidad de componer los contrastes de concurrencia entre los módulos, existe una posibilidad (muy leve) de que STM no funcione como se esperaba.

Pero aún así, podemos minimizar la incertidumbre usando lo siguiente (técnicas / métodos / construcciones):

  1. Evitar bloqueos y sincronización
  2. Usando STM
  3. Usar estructuras de datos persistentes (inmutables)
  4. Evitar compartir estado
  5. Funciones puras
  6. Estilo de programación asincrónica
  7. Evitar el cambio frecuente de contexto
  8. El paradigma de subprocesos múltiples y la naturaleza de su entorno juegan un papel importante

Quizás la objeción más fundamental [...] es que los programas basados ​​en bloqueo no se componen: los fragmentos correctos pueden fallar cuando se combinan. —Tim Harris et al., "Transacciones de memoria componible", Sección 2: Antecedentes, pág.

Actualizar

Gracias a Jules, estoy corregido. STM usa varias implementaciones y la mayoría de ellas no tienen bloqueo. Pero todavía creo que STM es una buena solución aquí, pero no la perfecta, y tiene inconvenientes:

Cada lectura (o escritura) de una ubicación de memoria desde el interior de una transacción se realiza mediante una llamada a una rutina STM para leer (o escribir) datos. Con código secuencial, estos accesos se realizan mediante una sola instrucción de CPU. Las rutinas de lectura y escritura STM son significativamente más caras que las instrucciones correspondientes de la CPU, ya que, por lo general, tienen que mantener datos de contabilidad sobre cada acceso. La mayoría de los STM verifican conflictos con otras transacciones concurrentes, registran el acceso y, en caso de escritura, registran el valor actual (o antiguo) de los datos, además de leer o escribir la ubicación de la memoria accedida. Algunas de estas operaciones utilizan costosas instrucciones de sincronización y acceden a metadatos compartidos, lo que aumenta aún más sus costos. Todo esto reduce el rendimiento de un solo subproceso en comparación con el código secuencial. - Por qué STM puede ser más que un juguete de investigación - página 1

Vea también estos documentos:

Estos documentos tienen algunos años. Las cosas pueden haber cambiado / mejorado pero no todas.

CanProgram
fuente
"Un código de ejecución perfectamente bueno que utiliza estructuras de datos inmutables y STM también puede producir resultados inesperados porque, bajo el capó, STM usa bloqueos". ¿Puedes dar un ejemplo de un resultado tan inesperado? Hasta donde yo sé, STM se considera confiable y composable, pero ¿tal vez conoces algo que no soy ...?
Julio
Además, usted afirma que STM "usa bloqueos", pero eso es solo un detalle de implementación de algunas versiones del mismo. STM puede implementarse en un sistema completamente libre de bloqueos mediante el uso de actualizaciones atómicas; ver dl.acm.org/citation.cfm?id=1941579
Julio
1

Escuché decir por investigadores respetados que cualquier mecanismo útil de sincronización puede usarse para construir un punto muerto. La memoria transaccional (ya sea hardware o software) no es diferente. Por ejemplo, considere este enfoque para escribir una barrera de hilos:

transaction {
    counter++;
}

while (true) {
    transaction {
        if (counter == num_threads)
            break;
    }
}

(Nota: el ejemplo está tomado de un artículo de Yannis Smaragdakis en PACT 2009)

Si ignoramos el hecho de que esta no es una buena manera de sincronizar una gran cantidad de subprocesos, parece ser correcto. Pero no es composable. La decisión de poner la lógica en dos transacciones es esencial. Si tuviéramos que llamar a esto desde otra transacción, de modo que todo se aplaste en una transacción, entonces probablemente nunca completaríamos.

Lo mismo ocurre con los canales que pasan mensajes: los ciclos de comunicación pueden causar puntos muertos. La sincronización ad-hoc con atómicas de C ++ puede conducir a puntos muertos. RCU, bloqueos de secuencia, bloqueos de lectores / escritores, variables de condición y semáforos se pueden usar para crear puntos muertos.

Eso no quiere decir que las transacciones o canales (o bloqueos o RCU) sean malos. Más bien, es decir que algunas cosas simplemente no parecen posibles. Los mecanismos de control de concurrencia escalables, componibles y libres de patología probablemente no sean posibles.

La mejor manera de evitar problemas es no buscar un mecanismo de bala de plata, sino utilizar rigurosamente buenos patrones. En el mundo de la computación paralela, un buen punto de partida es la Programación paralela estructurada: patrones para la computación eficiente , por Arch Robison, James Reinders y Michael McCool. Para la programación concurrente, hay algunos buenos patrones (vea el comentario de @ gardenhead), pero no es probable que los programadores de C ++ y Java los usen. Un patrón que más personas podrían comenzar a usar de la manera correcta es reemplazar las sincronizaciones ad-hoc en los programas con una cola de múltiples productores y múltiples consumidores. Y TM es definitivamente mejor que las cerraduras, ya que eleva el nivel de abstracción, por lo que los programadores se centran en lo que debe ser atómico , nocómo implementar un protocolo de bloqueo inteligente para garantizar la atomicidad . Con suerte, a medida que el hardware TM mejore y los idiomas agreguen más soporte TM, llegaremos a un punto en el que TM suplante los bloqueos en el caso común.

Mike Spear
fuente
1
"Para la programación concurrente, los patrones no están tan bien desarrollados". Esto es evidentemente falso. Los modelos concurrentes de computación se remontan a décadas. El modelo de actor fue inventado a principios de los años 70, y desde entonces también se han inventado y estudiado varias formas de cálculo de procesos. El problema no radica en los buenos modelos de computación; recae en los programadores que no están dispuestos a usar esos modelos y posibles ineficiencias en su implementación.
cabeza de jardín
Excelente punto, @gardenhead. Los modelos han sido desarrollados, es solo que nadie los usa. Editaré mi respuesta.
Mike Spear