¿Son las "carreras de datos" y la "condición de carrera" realmente lo mismo en el contexto de la programación concurrente?

Respuestas:

142

No, no son lo mismo. No son un subconjunto entre sí. Tampoco son la condición necesaria ni suficiente el uno para el otro.

La definición de una carrera de datos es bastante clara y, por lo tanto, su descubrimiento puede automatizarse. Se produce una carrera de datos cuando 2 instrucciones de diferentes subprocesos acceden a la misma ubicación de memoria, al menos uno de estos accesos es una escritura y no hay sincronización que imponga un orden particular entre estos accesos.

Una condición de carrera es un error semántico. Es una falla que ocurre en la sincronización o el orden de los eventos que conduce a un comportamiento erróneo del programa. Muchas condiciones de carrera pueden deberse a carreras de datos, pero esto no es necesario.

Considere el siguiente ejemplo simple donde x es una variable compartida:

Thread 1    Thread 2

 lock(l)     lock(l)
 x=1         x=2
 unlock(l)   unlock(l)

En este ejemplo, las escrituras ax del subproceso 1 y 2 están protegidas por bloqueos, por lo tanto, siempre están sucediendo en algún orden impuesto por el orden con el que se adquieren los bloqueos en tiempo de ejecución. Es decir, la atomicidad de las escrituras no se puede romper; siempre hay una relación suceda antes entre las dos escrituras en cualquier ejecución. Simplemente no podemos saber qué escritura ocurre antes que la otra a priori.

No hay un orden fijo entre las escrituras, porque los bloqueos no pueden proporcionar esto. Si la corrección de los programas se ve comprometida, digamos que cuando la escritura en x por el hilo 2 es seguida por la escritura en x en el hilo 1, decimos que hay una condición de carrera, aunque técnicamente no hay carrera de datos.

Es mucho más útil detectar condiciones de carrera que carreras de datos; sin embargo, esto también es muy difícil de lograr.

Construir el ejemplo inverso también es trivial. Esta publicación de blog también explica muy bien la diferencia, con un ejemplo de transacción bancaria simple.

Baris Kasikci
fuente
1
"carrera de datos (...) no hay sincronización que obligue a algún orden particular entre estos accesos". Estoy un poco confundido. En su ejemplo, las operaciones pueden ocurrir en ambos órdenes (ya sea = 1 luego = 2, o al revés). ¿Por qué no es una carrera de datos?
josinalvo
6
@josinalvo: es un artefacto de la definición técnica de una carrera de datos, el punto clave es que entre los dos accesos habrá un abrepuertas y una adquisición de cerradura (para cualquiera de los posibles pedidos). Por definición, un desbloqueo y una adquisición de candado establecen un orden entre los dos accesos y, por lo tanto, no hay carrera de datos.
Baris Kasikci
La sincronización nunca exige ningún orden en particular entre operaciones, por lo que esta no es una forma muy afortunada de expresarlo. Por otro lado, el JMM especifica que para cada operación de lectura debe haber una operación de escritura definida que observe, incluso en una carrera de datos. Es difícil evitar mencionar explícitamente ocurre-antes y sincronizar el orden, sin embargo, incluso la definición de JLS se equivoca al mencionar solo sucede-antes : por su definición, dos escrituras volátiles concurrentes constituyen una carrera de datos.
Marko Topolnik
@BarisKasikci "establece un orden" no tiene ningún significado real, en lo que a mí respecta. Son solo palabras de comadreja. Honestamente, no creo que la "carrera de datos" sea un concepto remotamente útil, ya que, literalmente, cada ubicación de la memoria a la que acceden varios subprocesos se puede considerar como una "carrera de datos"
Noldorin
Los pares de liberación y adquisición siempre establecen un orden. Una explicación general es extensa, pero un ejemplo trivial es un par señal-espera. @Noldorin "Establece un orden" se refiere a un orden de suceder antes, que es un concepto clave de la teoría de la concurrencia (consulte el artículo fundamental de Lamport sobre la relación sucedió antes) y los sistemas distribuidos. Las carreras de datos son un concepto útil, ya que su presencia plantea muchos problemas (por ejemplo, semántica indefinida según el modelo de memoria C ++, semántica muy compleja en Java, etc.). Su detección y eliminación constituyen una vasta literatura en investigación y práctica.
Baris Kasikci
20

Según Wikipedia, el término "condición de carrera" se ha utilizado desde los días de las primeras puertas lógicas electrónicas. En el contexto de Java, una condición de carrera puede pertenecer a cualquier recurso, como un archivo, una conexión de red, un hilo de un grupo de hilos, etc.

Es mejor reservar el término "carrera de datos" por su significado específico definido por la JLS .

El caso más interesante es una condición de carrera que es muy similar a una carrera de datos, pero aún no lo es, como en este simple ejemplo:

class Race {
  static volatile int i;
  static int uniqueInt() { return i++; }
}

Dado que ies volátil, no hay carrera de datos; sin embargo, desde el punto de vista de la corrección del programa, existe una condición de carrera debido a la no atomicidad de las dos operaciones: leer i, escribir i+1. Varios subprocesos pueden recibir el mismo valor de uniqueInt.

Marko Topolnik
fuente
1
¿Puede colocar una línea en su respuesta que describa lo que data racerealmente significa en JLS?
Geek
@geek La palabra "JLS" es un hipervínculo a la sección relevante de JLS.
Marko Topolnik
@MarkoTopolnik Estoy un poco confundido por el ejemplo. ¿Podría explicarme: "Dado que soy volátil, no hay carrera de datos"? Voltility solo aseguró que sea visible, pero aún así: 1) no está sincronizado y varios subprocesos pueden leer / escribir al mismo y 2) es un campo compartido no final Entonces, de acuerdo con Java Concurrency in Practice (citado a continuación también) , es carrera de datos y no condición de carrera, ¿no?
aniliitb10
@ aniliitb10 En lugar de confiar en citas de segunda mano sacadas de su contexto, debe revisar la sección 17.4 de JLS a la que me vinculé en mi respuesta. El acceso a una variable volátil es una acción de sincronización como se define en §17.4.2.
Marko Topolnik
@ aniliitb10 Los Votaltiles no provocan carrera de datos, porque sus accesos se pueden ordenar. Es decir, puede razonar su orden de esta o aquella manera, lo que lleva a resultados diferentes. Con la carrera de datos, no tiene forma de razonar el pedido. Por ejemplo, la operación i ++ de cada subproceso puede ocurrir en su respectivo valor i almacenado localmente en caché. Globalmente, no tiene forma de ordenar esas operaciones (desde el punto de vista del programador), a menos que tenga un determinado modelo de memoria de lenguaje en su lugar.
Xiao-Feng Li
3

No, son diferentes y ninguno de ellos es un subconjunto de uno o viceversa.

El término condición de carrera a menudo se confunde con el término relacionado carrera de datos, que surge cuando la sincronización no se usa para coordinar todo el acceso a un campo compartido no final. Corre el riesgo de una carrera de datos cada vez que un hilo escribe una variable que podría ser leída por otro hilo o lee una variable que podría haber sido escrita por última vez por otro hilo si ambos hilos no usan sincronización; El código con carreras de datos no tiene una semántica definida útil en el modelo de memoria de Java. No todas las condiciones de carrera son carreras de datos, y no todas las carreras de datos son condiciones de carrera, pero ambas pueden hacer que los programas simultáneos fallen de formas impredecibles.

Tomado del excelente libro - Java Concurrency in Practice de Joshua Bloch & Co.

Shirgill Farhan
fuente
Tenga en cuenta que la pregunta tiene una etiqueta independiente del idioma.
martinkunev
1

TL; DR: La distinción entre raza de datos y condición de carrera depende de la naturaleza de la formulación del problema y de dónde trazar el límite entre el comportamiento indefinido y el comportamiento bien definido pero indeterminado. La distinción actual es convencional y refleja mejor la interfaz entre el arquitecto del procesador y el lenguaje de programación.

1. Semántica

La carrera de datos se refiere específicamente a los "accesos de memoria" en conflicto no sincronizados (o acciones u operaciones) a la misma ubicación de memoria. Si no hay conflicto en los accesos a la memoria, mientras todavía hay un comportamiento indeterminado causado por el orden de las operaciones, esa es una condición de carrera.

Tenga en cuenta que aquí los "accesos a la memoria" tienen un significado específico. Se refieren a las acciones de almacenamiento o carga de memoria "pura", sin ninguna semántica adicional aplicada. Por ejemplo, un almacén de memoria de un subproceso no sabe (necesariamente) cuánto tiempo tardan los datos en escribirse en la memoria y finalmente se propaga a otro subproceso. Para otro ejemplo, un almacenamiento de memoria en una ubicación antes de otro almacenamiento en otra ubicación por el mismo hilo no garantiza (necesariamente) que los primeros datos escritos en la memoria estén por delante del segundo. Como resultado, el orden de esos accesos a la memoria pura no puede (necesariamente) ser "razonado" , y cualquier cosa podría suceder, a menos que esté bien definido.

Cuando los "accesos a la memoria" están bien definidos en términos de ordenación a través de la sincronización, la semántica adicional puede asegurar que, incluso si el tiempo de los accesos a la memoria es indeterminado, su orden se puede "razonar" a través de las sincronizaciones. Tenga en cuenta que, aunque se puede razonar el orden entre los accesos a la memoria, no están necesariamente determinados, de ahí la condición de carrera.

2. ¿Por qué la diferencia?

Pero si el orden sigue siendo indeterminado en la condición de carrera, ¿por qué molestarse en distinguirlo de la carrera de datos? La razón es más práctica que teórica. Es porque la distinción existe en la interfaz entre el lenguaje de programación y la arquitectura del procesador.

Una instrucción de carga / almacenamiento de memoria en la arquitectura moderna generalmente se implementa como acceso a la memoria "pura", debido a la naturaleza de la canalización fuera de orden, la especulación, el caché de varios niveles, la interconexión cpu-ram, especialmente el de varios núcleos, etc. Hay muchos factores que conducen a tiempos y pedidos indeterminados. Hacer cumplir el pedido de cada instrucción de memoria conlleva una gran penalización, especialmente en un diseño de procesador que admite varios núcleos. Entonces, la semántica de ordenamiento se proporciona con instrucciones adicionales como varias barreras (o vallas).

La carrera de datos es la situación en la que se ejecuta la instrucción del procesador sin barreras adicionales para ayudar a razonar el orden de los accesos a la memoria en conflicto. El resultado no solo es indeterminado, sino también posiblemente muy extraño, por ejemplo, dos escrituras en la misma ubicación de palabra por diferentes subprocesos pueden resultar con cada mitad de la palabra escrita, o solo pueden operar sobre sus valores en caché local. - Estos son comportamientos indefinidos, desde el punto de vista del programador. Pero (normalmente) están bien definidos desde el punto de vista del arquitecto del procesador.

Los programadores deben tener una forma de razonar la ejecución de su código. La carrera de datos es algo que no pueden tener sentido, por lo que siempre deben evitarlo (normalmente). Es por eso que las especificaciones de lenguaje que son de nivel suficientemente bajo suelen definir la carrera de datos como un comportamiento indefinido, diferente del comportamiento de memoria bien definido de la condición de carrera.

3. Modelos de memoria lingüística

Los diferentes procesadores pueden tener un comportamiento de acceso a la memoria diferente, es decir, el modelo de memoria del procesador. Es incómodo para los programadores estudiar el modelo de memoria de cada procesador moderno y luego desarrollar programas que puedan beneficiarse de ellos. Es deseable que el lenguaje pueda definir un modelo de memoria para que los programas de ese lenguaje siempre se comporten como se espera como lo define el modelo de memoria. Es por eso que Java y C ++ tienen definidos sus modelos de memoria. Es responsabilidad de los desarrolladores del compilador / tiempo de ejecución garantizar que los modelos de memoria del lenguaje se apliquen en las diferentes arquitecturas de procesador.

Dicho esto, si un lenguaje no quiere exponer el comportamiento de bajo nivel del procesador (y está dispuesto a sacrificar ciertos beneficios de rendimiento de las arquitecturas modernas), puede optar por definir un modelo de memoria que oculte por completo los detalles de "puro". accesos a la memoria, pero aplican la semántica de ordenamiento para todas sus operaciones de memoria. Entonces, los desarrolladores del compilador / tiempo de ejecución pueden optar por tratar cada variable de memoria como volátil en todas las arquitecturas de procesador. Para estos lenguajes (que admiten memoria compartida entre subprocesos), no hay carreras de datos, pero aún pueden existir condiciones de carrera, incluso con un lenguaje de consistencia secuencial completa.

Por otro lado, el modelo de memoria del procesador puede ser más estricto (o menos relajado, o en un nivel más alto), por ejemplo, implementando consistencia secuencial como lo hacía el procesador de los primeros días. Luego, se ordenan todas las operaciones de memoria y no existe una carrera de datos para los idiomas que se ejecutan en el procesador.

4. Conclusión

Volviendo a la pregunta original, en mi humilde opinión, está bien definir la carrera de datos como un caso especial de condición de carrera, y la condición de carrera en un nivel puede convertirse en carrera de datos en un nivel superior. Depende de la naturaleza de la formulación del problema y de dónde trazar el límite entre el comportamiento indefinido y el comportamiento bien definido pero indeterminado. Solo la convención actual define el límite en la interfaz de procesador de lenguaje, no necesariamente significa que siempre sea y deba ser así; pero la convención actual probablemente refleja mejor la interfaz (y la sabiduría) de vanguardia entre el arquitecto del procesador y el lenguaje de programación.

Xiao-Feng Li
fuente