Anteriormente hice esta pregunta en Programmers.SE , sin éxito.
Estoy buscando recursos de aprendizaje por escrito sobre cómo diseñar estructuras de datos concurrentes. Estoy más interesado en el proceso de diseño (por ejemplo, identificar los invariantes correctos) que en el producto final (una lista completa de códigos).
Para un ejemplo concreto: Realmente disfruté el libro de Chris Okasaki "Estructuras de datos puramente funcionales", porque es más que una referencia: guía al lector a través del diseño de sus estructuras de datos y algoritmos. A menudo, el libro motiva un diseño complicado o no obvio al dar primero una versión más ingenua, y solo luego refinarlo hasta lograr la complejidad de tiempo deseada (ya sea en el peor de los casos o amortizada). Este es el tipo de cosas que estoy buscando.
Entonces:
¿Qué técnicas o heurísticas existen para diseñar estructuras de datos concurrentes?
¿Hay libros, documentos, publicaciones de blog, tutoriales, etc. que expliquen estas técnicas y heurísticas?
La respuesta no es tan simple como la programación funcional. En la programación funcional aquí tenemos un concepto general de lo que es la programación funcional y la especificación de las estructuras de datos en sí no cambia por el hecho de que son funcionales. Sin embargo, ese no es el caso con la concurrencia:
Hay muchos modelos de computación distribuida / paralela / concurrente.
No existe una transformación general que, dada la especificación de una estructura de datos secuencial, le proporcione la especificación de su versión concurrente. Hay varias condiciones (generalmente se clasifican en virtud de la seguridad y LIVENESS condiciones) que podemos requerir de una versión concurrente de una estructura de datos, hay varios nuevos resultados (por ejemplo, operaciones de pausa, operaciones abortan, choques, etc.). Por lo tanto, puede haber muchas especificaciones diferentes para versiones concurrentes de una estructura de datos secuencial.
Algunas preguntas sobre referencias en informática distribuida:
Vea también ¿Por qué no hemos podido desarrollar una teoría de complejidad unificada de la computación distribuida?
fuente
La primera regla de las estructuras de datos concurrentes es: no desea concurrencia.
En el caso ideal, la computación distribuida / paralela / concurrente significa que tiene una serie de procesos secuenciales completamente independientes. Cada proceso tiene sus propios datos y recursos, y el proceso ni siquiera conoce otros procesos.
En el peor de los casos, tiene un sistema de memoria compartida con múltiples hilos que consultan y actualizan las mismas estructuras de datos simultáneamente. Probablemente algo ha salido terriblemente mal, si lo estás considerando seriamente.
Por supuesto, cuando hablamos de estructuras de datos concurrentes, es inevitable cierto grado de concurrencia. Todavía queremos minimizarlo. Cuanto más tiempo pueda funcionar un proceso secuencialmente sin tocar mutexes, realizar operaciones atómicas o pasar mensajes, es más probable que todo funcione correctamente y el rendimiento sea aceptable.
Las estructuras de datos estáticos con actualizaciones por lotes requieren menos sincronización que las estructuras de datos dinámicas. Debe intentar que sus estructuras de datos concurrentes sean estáticas, o al menos lo más cercanas posible a la estática. Si su algoritmo requiere consultas entrelazadas con actualizaciones, intente cambiar el algoritmo antes de recurrir a estructuras dinámicas compartidas.
El mismo principio de diseño también se aplica a la actualización de estructuras de datos estáticos. Cuanto más independiente sea el proceso de actualización de la estructura, mejor funcionará todo.
fuente