Una condición de carrera o peligro de carrera es la condición de un sistema electrónico , software u otro sistema donde el comportamiento sustancial del sistema depende de la secuencia o el momento de otros eventos incontrolables, lo que lleva a resultados inesperados o inconsistentes. Se convierte en un error cuando uno o más de los posibles comportamientos no son deseables.
El término condición de carrera ya se utilizaba en 1954, por ejemplo en la tesis doctoral de David A. Huffman "La síntesis de circuitos de conmutación secuencial". [1]
Las condiciones de carrera pueden ocurrir especialmente en circuitos lógicos , programas de software distribuidos o multiproceso .
Un ejemplo típico de condición de carrera puede ocurrir cuando una puerta lógica combina señales que han viajado por diferentes caminos desde la misma fuente. Las entradas a la puerta pueden cambiar en momentos ligeramente diferentes en respuesta a un cambio en la señal fuente. La salida puede, durante un breve período, cambiar a un estado no deseado antes de volver al estado diseñado. Ciertos sistemas pueden tolerar tales fallas , pero si esta salida funciona como una señal de reloj para otros sistemas que contienen memoria, por ejemplo, el sistema puede apartarse rápidamente de su comportamiento diseñado (de hecho, la falla temporal se convierte en una falla permanente).
Considere, por ejemplo, una puerta AND de dos entradas alimentada con la siguiente lógica:
Un ejemplo práctico de una condición de carrera puede ocurrir cuando se utilizan circuitos lógicos para detectar ciertas salidas de un contador. Si todos los bits del contador no cambian exactamente al mismo tiempo, habrá patrones intermedios que pueden provocar coincidencias falsas.
Una condición de carrera crítica ocurre cuando el orden en que se cambian las variables internas determina el estado final en el que terminará la máquina de estados .
Una condición de carrera no crítica ocurre cuando el orden en el que se cambian las variables internas no determina el estado final en el que terminará la máquina de estados.
Una condición de carrera estática ocurre cuando se combinan una señal y su complemento.
Una condición de carrera dinámica ocurre cuando da como resultado múltiples transiciones cuando solo se pretende una. Se deben a la interacción entre puertas. Puede eliminarse utilizando no más de dos niveles de compuerta.
Una condición de carrera esencial ocurre cuando una entrada tiene dos transiciones en menos del tiempo total de propagación de la retroalimentación. A veces se solucionan utilizando elementos de línea de retardo inductivo para aumentar efectivamente la duración de una señal de entrada.
Técnicas de diseño como los mapas de Karnaugh alientan a los diseñadores a reconocer y eliminar las condiciones de carrera antes de que causen problemas. A menudo se puede agregar redundancia lógica para eliminar algunos tipos de carreras.
Además de estos problemas, algunos elementos lógicos pueden entrar en estados metaestables , lo que crea más problemas para los diseñadores de circuitos.
Puede surgir una condición de carrera en el software cuando un programa de computadora tiene múltiples rutas de código que se ejecutan al mismo tiempo. Si las múltiples rutas de código toman una cantidad de tiempo diferente a la esperada, pueden finalizar en un orden diferente al esperado, lo que puede causar errores de software debido a un comportamiento imprevisto. También puede ocurrir una carrera entre dos programas, lo que resulta en problemas de seguridad (ver más abajo).
Las condiciones críticas de carrera provocan ejecuciones no válidas y errores de software . Las condiciones de carrera críticas suelen ocurrir cuando los procesos o subprocesos dependen de algún estado compartido. Las operaciones en estados compartidos se realizan en secciones críticas que deben ser mutuamente excluyentes . El incumplimiento de esta regla puede corromper el estado compartido.
Una carrera de datos es un tipo de condición de carrera. Las carreras de datos son partes importantes de varios modelos de memoria formal . El modelo de memoria definido en los estándares C11 y C++11 especifica que un programa C o C++ que contiene una carrera de datos tiene un comportamiento indefinido . [3] [4]
Una condición de carrera puede ser difícil de reproducir y depurar porque el resultado final no es determinista y depende de la sincronización relativa entre los subprocesos que interfieren. Por lo tanto, los problemas de esta naturaleza pueden desaparecer cuando se ejecuta en modo de depuración, se agregan registros adicionales o se adjunta un depurador. Un error que desaparece de esta manera durante los intentos de depuración a menudo se denomina " Heisenbug ". Por lo tanto, es mejor evitar las condiciones de carrera mediante un diseño de software cuidadoso.
Supongamos que dos subprocesos incrementan cada uno el valor de una variable entera global en 1. Idealmente, se llevaría a cabo la siguiente secuencia de operaciones:
En el caso que se muestra arriba, el valor final es 2, como se esperaba. Sin embargo, si los dos subprocesos se ejecutan simultáneamente sin bloqueo ni sincronización (mediante semáforos ), el resultado de la operación podría ser incorrecto. La secuencia alternativa de operaciones a continuación demuestra este escenario:
En este caso, el valor final es 1 en lugar del resultado esperado de 2. Esto ocurre porque aquí las operaciones de incremento no son mutuamente excluyentes. Las operaciones mutuamente excluyentes son aquellas que no se pueden interrumpir al acceder a algún recurso, como una ubicación de memoria.
No todos consideran las carreras de datos como un subconjunto de condiciones de carrera. [5] La definición precisa de carrera de datos es específica del modelo de concurrencia formal que se utiliza, pero normalmente se refiere a una situación en la que una operación de memoria en un subproceso podría potencialmente intentar acceder a una ubicación de memoria al mismo tiempo que una operación de memoria en otro hilo está escribiendo en esa ubicación de memoria, en un contexto donde esto es peligroso. Esto implica que una carrera de datos es diferente de una condición de carrera, ya que es posible tener no determinismo debido a la sincronización incluso en un programa sin carreras de datos, por ejemplo, en un programa en el que todos los accesos a la memoria utilizan solo operaciones atómicas .
Esto puede ser peligroso porque en muchas plataformas, si dos subprocesos escriben en una ubicación de memoria al mismo tiempo, es posible que la ubicación de memoria termine manteniendo un valor que sea una combinación arbitraria y sin sentido de los bits que representan los valores que cada hilo intentaba escribir; esto podría provocar daños en la memoria si el valor resultante es uno que ningún subproceso intentó escribir (a veces esto se denomina "escritura rota"). De manera similar, si un hilo lee desde una ubicación mientras otro hilo escribe en él, es posible que la lectura devuelva un valor que sea una combinación arbitraria y sin sentido de los bits que representan el valor que la ubicación de memoria tenía antes de la escritura. y de los bits que representan el valor que se está escribiendo.
En muchas plataformas, se proporcionan operaciones de memoria especiales para el acceso simultáneo; En tales casos, normalmente el acceso simultáneo mediante estas operaciones especiales es seguro, pero el acceso simultáneo mediante otras operaciones de memoria es peligroso. A veces, estas operaciones especiales (que son seguras para el acceso simultáneo) se denominan operaciones atómicas o de sincronización , mientras que las operaciones ordinarias (que no son seguras para el acceso simultáneo) se denominan operaciones de datos . Probablemente por eso se utiliza el término carrera de datos ; en muchas plataformas, donde existe una condición de carrera que involucra únicamente operaciones de sincronización , dicha carrera puede ser no determinista pero, por lo demás, segura; pero una carrera de datos podría provocar daños en la memoria o un comportamiento indefinido.
La definición precisa de carrera de datos difiere entre los modelos formales de concurrencia. Esto es importante porque el comportamiento concurrente a menudo no es intuitivo y, por lo tanto, a veces se aplica un razonamiento formal.
El estándar C++ , en el borrador N4296 (2014-11-19), define la carrera de datos de la siguiente manera en la sección 1.10.23 (página 14) [6]
Dos acciones son potencialmente concurrentes si
- están realizados por diferentes hilos, o
- no están secuenciados y al menos uno lo realiza un manejador de señales.
La ejecución de un programa contiene una carrera de datos si contiene dos acciones conflictivas potencialmente concurrentes, al menos una de las cuales no es atómica y ninguna ocurre antes que la otra, excepto en el caso especial de los manejadores de señales que se describe a continuación [omitido]. Cualquier carrera de datos de este tipo da como resultado un comportamiento indefinido.
Las partes de esta definición relacionadas con los manejadores de señales son idiosincrásicas de C++ y no son típicas de las definiciones de carrera de datos .
El artículo Detecting Data Races on Weak Memory Systems [7] proporciona una definición diferente:
"dos operaciones de memoria entran en conflicto si acceden a la misma ubicación y al menos una de ellas es una operación de escritura... "Dos operaciones de memoria, x e y, en una ejecución secuencialmente consistente forman una carrera 〈x,y〉, si x y y entran en conflicto, y no están ordenados por la relación hb1 de la ejecución. La carrera 〈x,y〉 es una carrera de datos si al menos uno de x o y es una operación de datos.
Aquí tenemos dos operaciones de memoria que acceden a la misma ubicación, una de las cuales es una escritura.
La relación hb1 se define en otra parte del artículo y es un ejemplo de una relación típica de " sucede antes "; Intuitivamente, si podemos demostrar que estamos en una situación en la que se garantiza que una operación de memoria X se ejecutará hasta su finalización antes de que comience otra operación de memoria Y, entonces decimos que "X sucede antes de Y". Si ni "X sucede antes de Y" ni "Y sucede antes de X", entonces decimos que X e Y "no están ordenados por la relación hb1". Entonces, la cláusula "...y no están ordenados por la relación hb1 de la ejecución" puede traducirse intuitivamente como "...y X e Y son potencialmente concurrentes".
El artículo considera peligrosas sólo aquellas situaciones en las que al menos una de las operaciones de memoria es una "operación de datos"; En otras partes de este documento, el documento también define una clase de "operaciones de sincronización" que son seguras para un uso potencialmente simultáneo, en contraste con las "operaciones de datos".
La Especificación del lenguaje Java [8] proporciona una definición diferente:
Se dice que dos accesos (lecturas o escrituras) a la misma variable están en conflicto si al menos uno de los accesos es de escritura... Cuando un programa contiene dos accesos en conflicto (§17.4.1) que no están ordenados por un relación sucede antes, se dice que contiene una carrera de datos... una carrera de datos no puede causar un comportamiento incorrecto, como devolver una longitud incorrecta para una matriz.
Una diferencia fundamental entre el enfoque de C++ y el de Java es que en C++, una carrera de datos es un comportamiento indefinido, mientras que en Java, una carrera de datos simplemente afecta a las "acciones entre subprocesos". [8] Esto significa que en C++, un intento de ejecutar un programa que contenga una carrera de datos podría (aunque siga cumpliendo con la especificación) fallar o podría exhibir un comportamiento inseguro o extraño, mientras que en Java, un intento de ejecutar un programa que contenga una carrera de datos race puede producir un comportamiento de concurrencia no deseado pero, por lo demás, es seguro (suponiendo que la implementación cumpla con las especificaciones).
Una faceta importante de las carreras de datos es que, en algunos contextos, se garantiza que un programa que está libre de carreras de datos se ejecutará de manera secuencialmente consistente , lo que facilita enormemente el razonamiento sobre el comportamiento concurrente del programa. Se dice que los modelos de memoria formal que brindan dicha garantía exhiben una propiedad "SC para DRF" (consistencia secuencial para la libertad de la carrera de datos). Se ha dicho que este enfoque ha logrado un consenso reciente (presumiblemente en comparación con enfoques que garantizan coherencia secuencial en todos los casos, o enfoques que no la garantizan en absoluto). [9]
Por ejemplo, en Java, esta garantía se especifica directamente: [8]
Un programa está correctamente sincronizado si y sólo si todas las ejecuciones secuencialmente consistentes están libres de carreras de datos.
Si un programa está sincronizado correctamente, todas las ejecuciones del programa parecerán ser secuencialmente consistentes (§17.4.3).
Esta es una garantía extremadamente sólida para los programadores. Los programadores no necesitan razonar sobre reordenamientos para determinar que su código contiene carreras de datos. Por lo tanto, no necesitan razonar sobre reordenamientos al determinar si su código está sincronizado correctamente. Una vez que se determina que el código está sincronizado correctamente, el programador no necesita preocuparse de que los reordenamientos afecten su código.
Un programa debe estar sincronizado correctamente para evitar los tipos de comportamientos contrarios a la intuición que se pueden observar cuando se reordena el código. El uso de una sincronización correcta no garantiza que el comportamiento general de un programa sea correcto. Sin embargo, su uso sí permite a un programador razonar sobre los posibles comportamientos de un programa de forma sencilla; el comportamiento de un programa correctamente sincronizado depende mucho menos de posibles reordenamientos. Sin una sincronización correcta, son posibles comportamientos muy extraños, confusos y contrarios a la intuición.
Por el contrario, un borrador de especificación de C++ no requiere directamente un SC para la propiedad DRF, sino que simplemente observa que existe un teorema que lo proporciona:
[Nota: Se puede demostrar que los programas que usan correctamente mutexes y operaciones Memory_order_seq_cst para evitar todas las carreras de datos y no usan otras operaciones de sincronización se comportan como si las operaciones ejecutadas por sus subprocesos constituyentes estuvieran simplemente entrelazadas, tomando cada cálculo de valor de un objeto. del último efecto secundario sobre ese objeto en ese entrelazado. Esto normalmente se denomina "consistencia secuencial". Sin embargo, esto se aplica sólo a los programas sin carrera de datos, y los programas sin carrera de datos no pueden observar la mayoría de las transformaciones de programas que no cambian la semántica del programa de un solo subproceso. De hecho, la mayoría de las transformaciones de programas de un solo subproceso siguen estando permitidas, ya que cualquier programa que como resultado se comporte de manera diferente debe realizar una operación indefinida.— nota final
Tenga en cuenta que el borrador de la especificación de C++ admite la posibilidad de programas que sean válidos pero utilicen operaciones de sincronización con un orden_memoria distinto de orden_memoria_seq_cst, en cuyo caso el resultado puede ser un programa correcto pero para el cual no se proporciona ninguna garantía de coherencia secuencial. En otras palabras, en C++, algunos programas correctos no son consistentes secuencialmente. Se cree que este enfoque brinda a los programadores de C++ la libertad de elegir una ejecución más rápida del programa a costa de renunciar a la facilidad de razonamiento sobre su programa. [9]
Existen varios teoremas, a menudo proporcionados en forma de modelos de memoria, que proporcionan garantías SC para DRF en diversos contextos. Las premisas de estos teoremas normalmente imponen restricciones tanto al modelo de memoria (y por lo tanto a la implementación) como al programador; es decir, típicamente se da el caso de que hay programas que no cumplen las premisas del teorema y que no se puede garantizar que se ejecuten de manera secuencialmente consistente.
El modelo de memoria DRF1 [10] proporciona SC para DRF y permite las optimizaciones de WO (ordenamiento débil), RCsc ( consistencia de liberación con operaciones especiales secuencialmente consistentes), modelo de memoria VAX y modelos de memoria sin carrera de datos 0. El modelo de memoria PLpc [11] proporciona SC para DRF y permite las optimizaciones de los modelos TSO (Total Store Order), PSO, PC ( Processor Consistency ) y RCpc ( Release Consistency con operaciones especiales de consistencia del procesador). DRFrlx [12] proporciona un bosquejo de un SC para el teorema DRF en presencia de átomos relajados.
Muchas condiciones de carrera de software tienen implicaciones asociadas para la seguridad informática . Una condición de carrera permite que un atacante con acceso a un recurso compartido provoque un mal funcionamiento de otros actores que utilizan ese recurso, lo que produce efectos que incluyen denegación de servicio [13] y escalada de privilegios . [14] [15]
Un tipo específico de condición de carrera implica verificar un predicado (por ejemplo, para autenticación ) y luego actuar sobre el predicado, mientras que el estado puede cambiar entre el momento de la verificación y el momento de uso . Cuando este tipo de error existe en un código sensible a la seguridad, se crea una vulnerabilidad de seguridad llamada error de tiempo de verificación hasta tiempo de uso ( TOCTTOU ).
Las condiciones de carrera también se utilizan intencionalmente para crear generadores de números aleatorios de hardware y funciones físicamente no clonables . [16] [ cita necesaria ] Las PUF se pueden crear diseñando topologías de circuitos con rutas idénticas a un nodo y confiando en variaciones de fabricación para determinar aleatoriamente qué rutas se completarán primero. Al medir el conjunto específico de resultados de las condiciones de carrera de cada circuito fabricado, se puede recopilar un perfil para cada circuito y mantenerlo en secreto para luego verificar la identidad de un circuito.
Dos o más programas pueden chocar en sus intentos de modificar o acceder a un sistema de archivos, lo que puede provocar corrupción de datos o escalada de privilegios. [14] El bloqueo de archivos proporciona una solución comúnmente utilizada. Una solución más engorrosa implica organizar el sistema de tal manera que un proceso único (que ejecuta un demonio o similar) tenga acceso exclusivo al archivo, y todos los demás procesos que necesitan acceder a los datos de ese archivo lo hagan sólo a través de comunicación entre procesos. con ese único proceso. Esto requiere sincronización a nivel de proceso.
Existe una forma diferente de condición de carrera en los sistemas de archivos donde los programas no relacionados pueden afectarse entre sí al consumir repentinamente los recursos disponibles, como espacio en disco, espacio de memoria o ciclos de procesador. El software que no esté cuidadosamente diseñado para anticipar y manejar esta situación de carrera puede volverse impredecible. Este riesgo puede pasarse por alto durante mucho tiempo en un sistema que parece muy fiable. Pero eventualmente se pueden acumular suficientes datos o se puede agregar suficiente software para desestabilizar críticamente muchas partes de un sistema. Un ejemplo de esto ocurrió con la casi pérdida del Mars Rover "Spirit" poco después de aterrizar. Una solución es que el software solicite y reserve todos los recursos que necesitará antes de comenzar una tarea; si esta solicitud falla entonces la tarea se pospone, evitando los muchos puntos donde podría haber ocurrido el fracaso. Alternativamente, cada uno de esos puntos puede equiparse con manejo de errores, o se puede verificar el éxito de toda la tarea después, antes de continuar. Un enfoque más común es simplemente verificar que haya suficientes recursos del sistema disponibles antes de iniciar una tarea; sin embargo, esto puede no ser adecuado porque en sistemas complejos las acciones de otros programas en ejecución pueden ser impredecibles.
En el ámbito de las redes, considere una red de chat distribuida como IRC , donde un usuario que inicia un canal adquiere automáticamente privilegios de operador de canal. Si dos usuarios en diferentes servidores, en diferentes extremos de la misma red, intentan iniciar el canal con el mismo nombre al mismo tiempo, el servidor respectivo de cada usuario otorgará privilegios de operador de canal a cada usuario, ya que ninguno de los servidores habrá recibido todavía el la señal del otro servidor de que ha asignado ese canal. (Este problema se ha resuelto en gran medida mediante varias implementaciones de servidores IRC).
En este caso de condición de carrera, el concepto de " recurso compartido " cubre el estado de la red (qué canales existen, así como qué usuarios los iniciaron y por tanto tienen qué privilegios), que cada servidor puede cambiar libremente siempre que avisa a los demás servidores de la red sobre los cambios para que puedan actualizar su concepción del estado de la red. Sin embargo, la latencia en la red hace posible el tipo de condición de carrera descrita. En este caso, evitar las condiciones de carrera imponiendo una forma de control sobre el acceso al recurso compartido (por ejemplo, designar un servidor para controlar quién tiene qué privilegios) significaría convertir la red distribuida en una red centralizada (al menos para esa parte). del funcionamiento de la red).
Las condiciones de carrera también pueden existir cuando un programa de computadora se escribe con sockets sin bloqueo , en cuyo caso el rendimiento del programa puede depender de la velocidad del enlace de red.
Las fallas de software en sistemas críticos para la vida pueden ser desastrosas. Las condiciones de carrera fueron uno de los fallos de la máquina de radioterapia Therac-25 , que provocaron la muerte de al menos tres pacientes y lesiones a varios más. [17]
Otro ejemplo es el sistema de gestión de energía proporcionado por GE Energy y utilizado por FirstEnergy Corp , con sede en Ohio (entre otras instalaciones eléctricas). Existía una condición de carrera en el subsistema de alarma; Cuando tres líneas eléctricas caídas se activaron simultáneamente, la condición impidió que se enviaran alertas a los técnicos de monitoreo, lo que retrasó su conocimiento del problema. Esta falla de software finalmente provocó el apagón en América del Norte en 2003 . [18] GE Energy desarrolló posteriormente un parche de software para corregir el error no descubierto anteriormente.
Existen muchas herramientas de software para ayudar a detectar condiciones de carrera en el software. Se pueden clasificar en gran medida en dos grupos: herramientas de análisis estático y herramientas de análisis dinámico .
Thread Safety Analysis es una herramienta de análisis estático para análisis estático intraprocedimiento basado en anotaciones, originalmente implementada como una rama de gcc y ahora reimplementada en Clang , compatible con PThreads. [19] [ se necesita fuente no primaria ]
Las herramientas de análisis dinámico incluyen:
Existen varios puntos de referencia diseñados para evaluar la eficacia de las herramientas de detección de carrera de datos.
La neurociencia está demostrando que las condiciones raciales también pueden ocurrir en el cerebro de los mamíferos. [24] [25]
En la señalización ferroviaria del Reino Unido , surgiría una condición de carrera en la aplicación de la Regla 55 . Según esta regla, si un tren se detenía en una línea en marcha debido a una señal, el bombero de la locomotora caminaba hasta la caja de señales para recordarle que el tren estaba presente. Al menos en un caso, en Winwick en 1934, se produjo un accidente porque el señalizador aceptó otro tren antes de que llegara el bombero. La práctica de señalización moderna elimina la condición de carrera al permitir que el conductor se comunique instantáneamente con la caja de señales por radio.
