Estructura de datos concurrentes

En informática , una estructura de datos concurrente es una forma particular de almacenar y organizar datos para que puedan ser accedidos por múltiples subprocesos (o procesos ) informáticos en una computadora.

Históricamente, estas estructuras de datos se utilizaban en máquinas monoprocesador con sistemas operativos que admitían múltiples subprocesos (o procesos ) de computación. El término concurrencia capturaba la multiplexación /entrelazado de las operaciones de los subprocesos sobre los datos por parte del sistema operativo, aunque los procesadores nunca emitieran dos operaciones que accedieran a los datos simultáneamente.

En la actualidad, a medida que las arquitecturas informáticas multiprocesador que proporcionan paralelismo se convierten en la plataforma informática dominante (a través de la proliferación de procesadores multinúcleo ), el término ha llegado a referirse principalmente a estructuras de datos a las que pueden acceder varios subprocesos que, en realidad, pueden acceder a los datos simultáneamente porque se ejecutan en diferentes procesadores que se comunican entre sí. Se considera que la estructura de datos concurrente (a veces también denominada estructura de datos compartida ) reside habitualmente en un entorno de almacenamiento abstracto denominado memoria compartida , aunque esta memoria puede implementarse físicamente como una colección de módulos de almacenamiento "estrechamente acoplados" o distribuidos.

Las estructuras de datos concurrentes, pensadas para su uso en entornos informáticos paralelos o distribuidos, difieren de las estructuras de datos "secuenciales", pensadas para su uso en una máquina monoprocesador, en varios aspectos. ^[1] En particular, en un entorno secuencial se especifican las propiedades de la estructura de datos y se comprueba que se implementan correctamente, proporcionando propiedades de seguridad . En un entorno concurrente, la especificación también debe describir las propiedades de vitalidad que debe proporcionar una implementación. Las propiedades de seguridad suelen indicar que nunca ocurre algo malo, mientras que las propiedades de vitalidad indican que siempre ocurre algo bueno. Estas propiedades se pueden expresar, por ejemplo, utilizando la lógica temporal lineal .

El tipo de requisitos de vitalidad tiende a definir la estructura de datos. Las llamadas a métodos pueden ser bloqueantes o no bloqueantes . Las estructuras de datos no están restringidas a un tipo u otro, y pueden permitir combinaciones donde algunas llamadas a métodos son bloqueantes y otras no (se pueden encontrar ejemplos en la biblioteca de software de concurrencia de Java ).

Las propiedades de seguridad de las estructuras de datos concurrentes deben capturar su comportamiento dadas las muchas interrelaciones posibles de los métodos llamados por diferentes subprocesos. Es bastante intuitivo especificar cómo se comportan las estructuras de datos abstractas en un entorno secuencial en el que no hay interrelaciones. Por lo tanto, muchos enfoques convencionales para argumentar las propiedades de seguridad de una estructura de datos concurrente (como serializabilidad , linealizabilidad , consistencia secuencial y consistencia quiescente ^[1] ) especifican las propiedades de las estructuras de manera secuencial y asignan sus ejecuciones concurrentes a una colección de ejecuciones secuenciales.

Para garantizar las propiedades de seguridad y actividad, las estructuras de datos concurrentes deben permitir típicamente (aunque no siempre) que los subprocesos alcancen un consenso sobre los resultados de sus solicitudes simultáneas de acceso y modificación de datos. Para respaldar dicho acuerdo, las estructuras de datos concurrentes se implementan utilizando operaciones de sincronización primitivas especiales (consulte primitivas de sincronización ) disponibles en las máquinas multiprocesador modernas que permiten que varios subprocesos alcancen un consenso. Este consenso se puede lograr de manera bloqueante mediante el uso de bloqueos , o sin bloqueos, en cuyo caso es no bloqueante . Existe un amplio cuerpo de teoría sobre el diseño de estructuras de datos concurrentes (consulte las referencias bibliográficas).

Las estructuras de datos concurrentes son significativamente más difíciles de diseñar y verificar como correctas que sus contrapartes secuenciales.

La fuente principal de esta dificultad adicional es la concurrencia, agravada por el hecho de que los hilos deben considerarse completamente asincrónicos: están sujetos a la preemisión del sistema operativo, fallos de página, interrupciones, etc.

En las máquinas actuales, la disposición de los procesadores y la memoria, la disposición de los datos en la memoria y la carga de comunicación en los distintos elementos de la arquitectura multiprocesador influyen en el rendimiento. Además, existe una tensión entre la corrección y el rendimiento: las mejoras algorítmicas que buscan mejorar el rendimiento a menudo dificultan el diseño y la verificación de una implementación correcta de la estructura de datos. ^[2]

Una medida clave para el rendimiento es la escalabilidad, capturada por la aceleración de la implementación. La aceleración es una medida de la eficacia con la que la aplicación utiliza la máquina en la que se ejecuta. En una máquina con P procesadores, la aceleración es la relación entre el tiempo de ejecución de las estructuras en un solo procesador y su tiempo de ejecución en P procesadores. Idealmente, queremos una aceleración lineal: nos gustaría lograr una aceleración de P cuando usamos P procesadores. Las estructuras de datos cuya aceleración crece con P se denominan escalables . El grado en el que se puede escalar el rendimiento de una estructura de datos concurrente se captura mediante una fórmula conocida como la ley de Amdahl y versiones más refinadas de la misma, como la ley de Gustafson .

Un problema clave con el rendimiento de las estructuras de datos concurrentes es el nivel de contención de memoria: la sobrecarga en el tráfico hacia y desde la memoria como resultado de múltiples subprocesos que intentan acceder simultáneamente a las mismas ubicaciones en la memoria. Este problema es más agudo con las implementaciones de bloqueo en las que los bloqueos controlan el acceso a la memoria. Para adquirir un bloqueo, un subproceso debe intentar repetidamente modificar esa ubicación. En un multiprocesador coherente con la caché (uno en el que los procesadores tienen cachés locales que se actualizan por hardware para mantenerlas consistentes con los últimos valores almacenados), esto da como resultado largos tiempos de espera para cada intento de modificar la ubicación, y se ve exacerbado por el tráfico de memoria adicional asociado con los intentos fallidos de adquirir el bloqueo.

• Concurrencia en Java (JSR 166)
• Mapa concurrente de Java

• Nancy Lynch "Computación distribuida"
• Hagit Attiya y Jennifer Welch "Computación distribuida: fundamentos, simulaciones y temas avanzados, 2.ª edición"
• Doug Lea , "Programación concurrente en Java: principios y patrones de diseño"
• Maurice Herlihy y Nir Shavit , "El arte de la programación multiprocesador"
• Mattson, Sanders y Massingil "Patrones para programación paralela"

• Estructuras de datos multiproceso para computación paralela, parte 1 (diseño de estructuras de datos concurrentes) por Arpan Sen
• Estructuras de datos multiproceso para computación paralela: Parte 2 (Diseño de estructuras de datos concurrentes sin mutex) por Arpan Sen
• libcds: biblioteca C++ de contenedores sin bloqueos y esquema de recuperación de memoria segura
• Synchrobench: bibliotecas y puntos de referencia de C/C++ y Java para estructuras de datos sin bloqueos, basadas en bloqueos, basadas en TM y basadas en RCU/COW.