Problemas de ejemplo para el cómputo concurrente

Question

Hay una plétora de paradigmas y métodos para la programación simultánea en uso en la actualidad. Memoria transaccional de software, actores, concurrencia de estado compartido, espacios de tupla y muchos, muchos más.

Lo que encuentro que falta, sin embargo, es una biblioteca de problemas de prueba interesantes para concurrencia. Un ejemplo bien conocido es el "Problema de los filósofos del comedor", que no es lo suficientemente complejo ni motivador ni realista. Luego hay muchos algoritmos paralelos (multiplicación de matrices, renderizado, paralelismo de datos anidados generales) que solo requieren la distribución del trabajo, pero no concurrencia real con la comunicación entre hilos de ejecución.

Entonces, ¿alguien me puede señalar algunos conjuntos interesantes de problemas que requieren concurrencia real en un entorno interactivo, tal vez incluso distribuido, que son lo suficientemente simples como ejemplos para los paradigmas de simultaneidad? Idealmente, quiero encontrar un conjunto de problemas para servir como una "prueba de ausencia" para los paradigmas de concurrencia (o para resaltar sus diferencias, ya que cada paradigma tiene sus fortalezas y debilidades).

Cualquier ayuda es muy apreciada :)

Answer 1

he considerado previamente esta cuestión exacta, habiéndose propuesto anteriormente algunos paradigmas de programación concurrente a mí mismo: p

La conclusión a la que llegué es, entonces, que un conjunto de estas pruebas doesn Parece que realmente existe de una manera independiente del lenguaje. Si bien puede ser útil que exista, parece haber algunas razones bastante buenas que no lo hace (a mi leal saber y entender).

La mayor parte del enfoque dentro de la programación simultánea tiende a ser paralelidad de datos, de modo que la misma operación se aplica en paralelo a diferentes piezas del mismo conjunto de datos. Los tipos de paralelismo a nivel de tarea (es decir, diferentes tareas que se realizan en paralelo, posiblemente compartiendo datos) de los que creo que se está hablando en realidad no se hacen mucho. Creo que esto es porque es un poco difícil. Pero creo que también es un poco difícil porque la mayoría de los problemas no se prestan particularmente bien a este tipo de concurrencia. La descripción de un sistema distribuido en términos de primitivas de concurrencia puede ser útil, pero estos sistemas tienden a desacoplarse de forma tal que existe un protocolo (escrito o implícito) que modera su comunicación. Las personas tienden a no pensar en este tipo de sistemas como situaciones de programación obviamente "concurrentes", aunque son vistas en el marco correcto (es decir, considerando el "cliente" y el "servidor" como agentes que funcionan en paralelo con la sincronización en algunos puntos) .

Los únicos lugares donde creo que podría encontrar algunas fuentes de inspiración serían las implementaciones individuales. Erlang, Occam (y Occam-pi), Alice, CML, Concurrent Haskell, etc. probablemente tengan pequeños corpus de prueba, pero tanto los problemas como sus implementaciones van a estar sesgados para ser implementables dentro de un lenguaje específico (porque obviamente son implementable dentro de ese lenguaje!). Quizás también pueda consultar las comunidades que trabajan en multi-party session types y varios process calculi, como pi-calculus, CCS y CSP, para ver qué tipos de sistemas están utilizando como modelos de ejemplo. La idea de un conjunto estándar de problemas agnósticos para describir sistemas de comunicación concurrentes es atractiva, pero algo elusiva en este punto, creo.