algorithm multithreading theory correctness proof

algorithm - Demostrando la corrección de los algoritmos de subprocesos múltiples



multithreading theory (6)

@Just in case: I is. Pero por lo que aprendí, hacerlo para un algoritmo no trivial es un gran dolor. Dejo ese tipo de cosas para las personas más inteligentes. Aprendí lo que sé de Parallel Program Design: A Foundation (1988) de KM Chandy, J Misra

Los algoritmos de subprocesos múltiples son notablemente difíciles de diseñar / depurar / probar. El algoritmo de Dekker es un excelente ejemplo de lo difícil que puede ser diseñar un algoritmo sincronizado correcto. Los sistemas operativos modernos de Tanenbaum están llenos de ejemplos en su sección de IPC. ¿Alguien tiene una buena referencia (libros, artículos) para esto? ¡Gracias!

Respuesta corta: es difícil.

Hubo un trabajo realmente bueno en DEC SRC Modula-3 y alerce de finales de los 80.

p.ej

Algunas de las buenas ideas de Modula-3 lo están convirtiendo en el mundo de Java, por ejemplo, JML, aunque "JML está actualmente limitado a la especificación secuencial", dice la introducción .

No tengo ninguna referencia concreta, pero es posible que desee examinar la teoría de Owicki-Gries (si le gusta la demostración de teoremas) o la teoría / álgebra de procesos (para la cual también hay varias herramientas de verificación de modelos disponibles).

Es imposible probar nada sin basarse en garantías, por lo que lo primero que debe hacer es familiarizarse con el modelo de memoria de su plataforma objetivo; Java y x86 tienen modelos de memoria sólidos y estandarizados: no estoy tan seguro de CLR, pero si todo lo demás falla, se basará en el modelo de memoria de la arquitectura de CPU de destino. La excepción a esta regla es si tiene la intención de utilizar un idioma que no permite ningún estado mutable compartido: he oído que Erlang es así.

El primer problema de concurrencia es el estado mutable compartido.

Eso puede ser arreglado por:

  • Haciendo el estado inmutable
  • No compartiendo estado
  • Protección del estado mutable compartido mediante el mismo bloqueo (dos bloqueos diferentes no pueden proteger el mismo estado, a menos que siempre use exactamente estos dos bloqueos)

El segundo problema de la concurrencia es la publicación segura. ¿Cómo haces que los datos estén disponibles para otros hilos? ¿Cómo se realiza una transferencia? Tendrás la solución a este problema en el modelo de memoria y (con suerte) en la API. Java, por ejemplo, tiene muchas formas de publicar estado y el paquete java.util.concurrent contiene herramientas específicamente diseñadas para manejar la comunicación entre hilos.

El tercer (y más difícil) problema de concurrencia es el bloqueo. El orden de bloqueo mal administrado es la fuente de bloqueos muertos. Puede probar analíticamente, basándose en las garantías del modelo de memoria, si los bloqueos son posibles o no en su código. Sin embargo, debe diseñar y escribir su código teniendo esto en cuenta, de lo contrario, la complejidad del código puede hacer que dicho análisis sea imposible de realizar en la práctica.

Entonces, una vez que tenga, o antes de hacerlo, demuestre el uso correcto de concurrencia, tendrá que demostrar la corrección de un solo subproceso. El conjunto de errores que pueden ocurrir en una base de código concurrente es igual al conjunto de errores de programa de subproceso único, más todos los posibles errores de concurrencia.