Condición de carrera
Una condición de carrera o un 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 sincronización de otros eventos incontrolables. 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".
Las condiciones de carrera pueden ocurrir especialmente en circuitos lógicos, programas de software distribuidos o multiproceso.
En electrónica
Un ejemplo típico de una 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.
Formas críticas y no críticas
Una condición de carrera crítica ocurre cuando el orden en el 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.
Formas estáticas, dinámicas y esenciales
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.
Soluciones alternativas
Las 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.
En software
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 de carrera críticas 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.
Una condición de carrera puede ser difícil de reproducir y depurar porque el resultado final no es determinista y depende del tiempo relativo 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.
Ejemplo
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:
| Thread 1 | Thread 2 | Valor entero | |
|---|---|---|---|
| 0 | |||
| Valor de lectura | ← | 0 | |
| valor | 0 | ||
| escribe | → | 1 | |
| Valor de lectura | ← | 1 | |
| valor | 1 | ||
| escribe | → | 2 |
En el caso mostrado 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:
| Thread 1 | Thread 2 | Valor entero | |
|---|---|---|---|
| 0 | |||
| Valor de lectura | ← | 0 | |
| Valor de lectura | ← | 0 | |
| valor | 0 | ||
| valor | 0 | ||
| escribe | → | 1 | |
| escribe | → | 1 |
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.
Carrera de datos
No todos consideran las carreras de datos como un subconjunto de condiciones de carrera. La definición precisa de carrera de datos es específica del modelo de concurrencia formal que se utiliza, pero generalmente 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 se realiza una operación de memoria en otro subproceso. escribir 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 conteniendo 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 ninguno de los subprocesos 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 esta sea la razón por la que el término es datos carrera; en muchas plataformas, donde existe una condición de carrera que involucra solo 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.
Ejemplos de definiciones de carreras de datos en modelos de concurrencia concretos
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).
Dos acciones potencialmente concurrentes si
- son realizados por diferentes hilos, o
- no son secuenciados, y al menos uno es realizado por un manipulador de señal.
La ejecución de un programa contiene un carrera de datos si contiene dos acciones potencialmente concurrentes contradictorias, al menos una de las cuales no es atómica, y tampoco ocurre antes de la otra, excepto el caso especial para los controladores de señal descritos a continuación [omitted]. Cualquier carrera de datos de este tipo resulta en 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 Detección de carreras de datos en sistemas de memoria débiles proporciona una definición diferente:
"dos operaciones de memoria conflicto si acceden a la misma ubicación y al menos uno de ellos es una operación de escritura... "Dos operaciones de memoria, x y y, en una forma de ejecución secuencialmente consistente una raza érix,y〉, iff x y conflicto, y no se ordenan por la relación hb1 de la ejecución. La carrera es una carrera de datos iff 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 tipo "sucede antes". relación; 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 ocurre antes de Y". Si no ocurre ninguna de las dos cosas, 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 ordenadas por la relación hb1 de la ejecución" se puede traducir 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 seguros para un uso potencialmente simultáneo, a diferencia de las "operaciones de datos".
La Especificación del lenguaje Java proporciona una definición diferente:
Dos accesos a (leer o escribir a) se dice que la misma variable es conflictiva si al menos uno de los accesos es un escrito... Cuando un programa contiene dos accesos conflictivos (§17.4.1) que no se ordenan por una relación anterior, se dice que contiene una carrera de datos... una carrera de datos no puede causar un comportamiento incorrecto como devolver la longitud equivocada para un array.
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". 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 exhibir un comportamiento inseguro o extraño, mientras que en Java, un intento de ejecutar un programa que contenga una carrera de datos puede producir comportamiento de concurrencia no deseado, pero por lo demás es seguro (suponiendo que la implementación cumpla con las especificaciones).
Coherencia secuencial para la libertad en la carrera de datos
Una faceta importante de las carreras de datos es que, en algunos contextos, se garantiza que un programa 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 tal garantía exhiben un "SC para DRF" Propiedad (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).
Por ejemplo, en Java, esta garantía se especifica directamente:
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á correctamente sincronizado, entonces todas las ejecuciones del programa parecen ser secuencialmente consistentes (§17.4.3).
Esta es una garantía extremadamente fuerte para los programadores. Los programadores no necesitan razonar sobre reordenaciones para determinar que su código contiene razas de datos. Por lo tanto no necesitan razonar sobre las reordenaciones al determinar si su código está correctamente sincronizado. Una vez hecha la determinación de que el código está correctamente sincronizado, el programador no necesita preocuparse de que las reordenaciones afectarán su código.
Un programa debe ser sincronizado correctamente para evitar los tipos de comportamientos contraintuitivos que se pueden observar cuando se reordena el código. El uso de la sincronización correcta no asegura que el comportamiento general de un programa sea correcto. Sin embargo, su uso permite a un programador razonar sobre los posibles comportamientos de un programa de manera sencilla; el comportamiento de un programa correctamente sincronizado es mucho menos dependiente de posibles reordenaciones. Sin una correcta sincronización, comportamientos muy extraños, confusos y contraintuitivos son posibles.
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 las operaciones de memoria_order_seq_cst para prevenir todas las competiciones de datos y no utilizan otras operaciones de sincronización se comportan como si las operaciones ejecutadas por sus hilos constituyentes fueran simplemente entrelazadas, con cada cálculo de valor de un objeto que se toma del último efecto secundario en ese objeto en ese interleaving. Esto se denomina normalmente " consistencia secuencial ". Sin embargo, esto se aplica sólo a los programas sin límites de datos, y los programas sin límites de datos no pueden observar la mayoría de las transformaciones del programa que no cambian la semántica del programa de un solo programa. De hecho, la mayoría de las transformaciones de programas de un solo hilo siguen permitiéndose, ya que cualquier programa que se comporta de manera diferente como resultado 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.
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 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 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 proporciona un bosquejo de un SC para el teorema DRF en presencia de átomos relajados.
Seguridad informática
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 y escalada de privilegios.
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 utilizar. 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 a 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. 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.
Sistemas de archivos
Dos o más programas pueden chocar en sus intentos de modificar o acceder a un sistema de archivos, lo que puede resultar en corrupción de datos o escalada de privilegios. El bloqueo de archivos proporciona una solución de uso común. 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 del aterrizaje. 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.
Redes
En el ámbito de la creación de 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 lo hará. aún he recibido 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 una 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 lo tanto, tienen qué privilegios), que cada servidor puede cambiar libremente siempre que indique a los demás servidores de la red los cambios para que puedan actualizarlos. 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.
Sistemas críticos para la vida
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.
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 eventualmente condujo al apagón en América del Norte en 2003. Posteriormente, GE Energy desarrolló un parche de software para corregir el error no descubierto anteriormente.
Herramientas
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.
Las herramientas de análisis dinámico incluyen:
- Intel Inspector, una herramienta de control de memoria y depuración de hilos para aumentar la fiabilidad, seguridad y exactitud de las aplicaciones C/C++ y Fortran; Intel Advisor, una herramienta de optimización de la vectorización SIMD y herramienta de asistencia compartida para el procesamiento de memoria para desarrolladores y arquitectos de software C, C++, C# y Fortran;
- ThreadSanitizer, que utiliza binario (basado en Valgrind) o fuente, instrumentación basada en LLVM, y soporta PThreads; y Helgrind, una herramienta Valgrind para detectar errores de sincronización en los programas C, C++ y Fortran que usan los pthreads POSIX que rozan primitivos.
- Data Race Detector está diseñado para encontrar carreras de datos en el lenguaje Go Programming.
Existen varios puntos de referencia diseñados para evaluar la eficacia de las herramientas de detección de carreras de datos.
- DataRaceBench es una suite de referencia diseñada para evaluar sistemáticamente y cuantitativamente las herramientas de detección de razas de datos que analizan aplicaciones multi-teleadas escritas en OpenMP.
En otras áreas
La neurociencia está demostrando que las condiciones raciales también pueden ocurrir en el cerebro de los mamíferos.
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 detuviera en una línea en marcha por una señal, el bombero de la locomotora caminaría hasta la caja de señales para para recordar al señalizador 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.