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

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.

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.

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.

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.

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:

• http://dl.acm.org/citation.cfm?id=1454466
• http://dl.acm.org/citation.cfm?id=1924440

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

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.