¿Por qué el código que muta una variable compartida a través de subprocesos aparentemente NO sufre una condición de carrera?

107

Estoy usando Cygwin GCC y ejecuto este código:

#include <iostream>
#include <thread>
#include <vector>
using namespace std;

unsigned u = 0;

void foo()
{
    u++;
}

int main()
{
    vector<thread> threads;
    for(int i = 0; i < 1000; i++) {
        threads.push_back (thread (foo));
    }
    for (auto& t : threads) t.join();

    cout << u << endl;
    return 0;
}

Compilado con la línea: g++ -Wall -fexceptions -g -std=c++14 -c main.cpp -o main.o.

Imprime 1000, que es correcto. Sin embargo, esperaba un número menor debido a que los subprocesos sobrescribían un valor incrementado previamente. ¿Por qué este código no sufre de acceso mutuo?

Mi máquina de prueba tiene 4 núcleos y no pongo restricciones al programa que conozco.

El problema persiste al reemplazar el contenido del compartido foopor algo más complejo, p. Ej.

if (u % 3 == 0) {
    u += 4;
} else {
    u -= 1;
}
mafu
fuente
66
Las CPU Intel tienen una increíble lógica interna de "derribo" para preservar la compatibilidad con las primeras CPU x86 utilizadas en los sistemas SMP (como las máquinas Pentium Pro duales). Muchas de las condiciones de falla que nos enseñan son posibles, casi nunca ocurren en máquinas x86. Entonces, digamos que un núcleo va a uvolver a escribir en la memoria. La CPU realmente hará cosas asombrosas como notar que la línea de memoria para uno está en el caché de la CPU y reiniciará la operación de incremento. ¡Es por eso que pasar de x86 a otras arquitecturas puede ser una experiencia reveladora!
David Schwartz
1
Quizás todavía demasiado rápido. Debe agregar código para asegurarse de que el subproceso cede antes de que haga algo para asegurarse de que se inicien otros subprocesos antes de que se complete.
Rob K
1
Como se ha señalado en otra parte, el código del hilo es tan corto que bien puede ejecutarse antes de que el siguiente hilo esté en cola. ¿Qué tal 10 hilos que colocan a u ++ en un ciclo de 100 conteos? Y un breve retraso antes del inicio del ciclo (o una bandera global de "ir" para iniciarlos todos al mismo tiempo)
RufusVS
5
En realidad, generar el programa repetidamente en un bucle eventualmente muestra que se rompe: algo como while true; do res=$(./a.out); if [[ $res != 1000 ]]; then echo $res; break; fi; done;imprime 999 o 998 en mi sistema.
Daniel Kamil Kozar

Respuestas:

266

foo()es tan corto que cada hilo probablemente termina antes de que se genere el siguiente. Si agrega un sueño por un tiempo aleatorio foo()antes del u++, puede comenzar a ver lo que espera.

Rob K
fuente
51
De hecho, esto cambió la salida de la manera esperada.
mafu
49
Me gustaría señalar que, en general, esta es una estrategia bastante buena para exhibir condiciones de carrera. Debería poder inyectar una pausa entre dos operaciones cualesquiera; si no, hay una condición de carrera.
Matthieu M.
Recientemente, tuvimos este problema con C #. El código casi nunca falla por lo general, pero la reciente adición de una llamada a la API en el medio introdujo suficiente retraso para que cambie constantemente.
Obsidian Phoenix
@MatthieuM. ¿Microsoft no tiene una herramienta automatizada que hace exactamente eso, como un método tanto para detectar condiciones de carrera como para hacerlas reproducibles de manera confiable?
Mason Wheeler
1
@MasonWheeler: Trabajo casi exclusivamente en Linux, así que ... no sé :(
Matthieu M.
59

Es importante comprender que una condición de carrera no garantiza que el código se ejecute incorrectamente, simplemente que podría hacer cualquier cosa, ya que es un comportamiento indefinido. Incluyendo correr como se esperaba.

Particularmente en las máquinas X86 y AMD64, las condiciones de carrera en algunos casos rara vez causan problemas, ya que muchas de las instrucciones son atómicas y las garantías de coherencia son muy altas. Estas garantías se reducen algo en los sistemas multiprocesador donde se necesita el prefijo de bloqueo para que muchas instrucciones sean atómicas.

Si en su máquina, el incremento es una operación atómica, es probable que se ejecute correctamente aunque de acuerdo con el estándar del lenguaje sea Comportamiento indefinido.

Específicamente, espero que en este caso el código se esté compilando en un Fetch and Add atómico instrucción (ADD o XADD en el ensamblaje X86) que de hecho es atómico en sistemas de un solo procesador, sin embargo, en sistemas multiprocesador no se garantiza que sea atómico y un bloqueo sería necesario para hacerlo así. Si está ejecutando en un sistema multiprocesador, habrá una ventana donde los subprocesos podrían interferir y producir resultados incorrectos.

Específicamente, compilé su código para ensamblar usando https://godbolt.org/ y lo foo()compila para:

foo():
        add     DWORD PTR u[rip], 1
        ret

Esto significa que solo está realizando una instrucción de adición que para un solo procesador será atómica (aunque como se mencionó anteriormente no es así para un sistema multiprocesador).

Vality
fuente
41
Es importante recordar que "ejecutar según lo previsto" es un resultado permisible de un comportamiento indefinido.
Mark
3
Como indicó, esta instrucción no es atómica en una máquina SMP (como lo son todos los sistemas modernos). Incluso inc [u]no es atómico. El LOCKprefijo es necesario para que una instrucción sea verdaderamente atómica. El OP simplemente está teniendo suerte. Recuerde que aunque le está diciendo a la CPU "agregue 1 a la palabra en esta dirección", la CPU todavía tiene que buscar, incrementar, almacenar ese valor y otra CPU puede hacer lo mismo simultáneamente, causando que el resultado sea incorrecto.
Jonathon Reinhart
2
Voté en contra, pero luego volví a leer su pregunta y me di cuenta de que sus declaraciones de atomicidad estaban asumiendo una sola CPU. Si edita su pregunta para que esto sea más claro (cuando diga "atómico", tenga claro que este es solo el caso en una sola CPU), entonces podré eliminar mi voto negativo.
Jonathon Reinhart
3
Con una votación negativa, encuentro esta afirmación un poco meh "Particularmente en las máquinas X86 y AMD64, las condiciones de carrera en algunos casos rara vez causan problemas, ya que muchas de las instrucciones son atómicas y las garantías de coherencia son muy altas". El párrafo debe comenzar con la suposición explícita de que se está enfocando en un solo núcleo. Aun así, las arquitecturas de múltiples núcleos son un estándar de facto hoy en día en los dispositivos de consumo que yo consideraría un caso de esquina para explicar en último lugar, en lugar de primero.
Patrick Trentin
3
Oh, definitivamente. x86 tiene toneladas de compatibilidad con versiones anteriores ... cosas para asegurarse de que el código escrito incorrectamente funcione en la medida de lo posible. Fue realmente importante cuando el Pentium Pro introdujo la ejecución fuera de orden. Intel quería asegurarse de que la base de código instalada funcionara sin necesidad de volver a compilarla específicamente para su nuevo chip. x86 comenzó como un núcleo CISC, pero ha evolucionado internamente hasta convertirse en un núcleo RISC, aunque todavía se presenta y se comporta de muchas maneras como CISC desde la perspectiva de un programador. Para obtener más información, consulte la respuesta de Peter Cordes aquí .
Cody Gray
20

Creo que no es tanto la cosa si pones un sueño antes o después del u++. Se trata más bien de que la operación se u++traduce en un código que, en comparación con la sobrecarga de los subprocesos de generación que llaman foo, se realiza muy rápidamente, de modo que es poco probable que sea interceptado. Sin embargo, si "prolonga" la operación u++, la condición de carrera será mucho más probable:

void foo()
{
    unsigned i = u;
    for (int s=0;s<10000;s++);
    u = i+1;
}

resultado: 694


Por cierto: también lo intenté

if (u % 2) {
    u += 2;
} else {
    u -= 1;
}

y me dio la mayoría de las veces 1997, pero a veces 1995.

Stephan Lechner
fuente
1
Esperaría en cualquier compilador vagamente cuerdo que toda la función se optimice para lo mismo. Me sorprende que no fuera así. Gracias por el interesante resultado.
Vality
Esto es exactamente correcto. Se deben ejecutar muchos miles de instrucciones antes de que el siguiente hilo comience a ejecutar la pequeña función en cuestión. Cuando acerca el tiempo de ejecución en la función a la sobrecarga de creación de subprocesos, ve el impacto de la condición de carrera.
Jonathon Reinhart
@Vality: También esperaba que eliminara el bucle for falso en la optimización O3. ¿No es así?
user21820
¿Cómo podría else u -= 1ser ejecutado? Incluso en un entorno paralelo, el valor nunca debería no encajar %2, ¿no es así?
mafu
2
de la salida, parece que else u -= 1se ejecuta una vez, la primera vez que se llama a foo (), cuando u == 0. Las 999 veces restantes u es impar y u += 2se ejecuta dando como resultado u = -1 + 999 * 2 = 1997; es decir, la salida correcta. Una condición de carrera a veces hace que uno de los + = 2 sea sobrescrito por un hilo paralelo y obtienes 1995.
Lucas
7

Sufre de una condición de carrera. Ponga usleep(1000);antes u++;en fooy veo diferente de salida (<1,000) cada vez.

juf
fuente
6
  1. La respuesta probable que la razón por la condición de carrera no se manifestó para usted, a pesar de que hace existir, es que foo()es tan rápido, en comparación con el tiempo que se necesita para iniciar un hilo, que cada hilo acabados antes de la próxima puede incluso comenzar. Pero...

  2. Incluso con su versión original, el resultado varía según el sistema: lo probé a su manera en una Macbook (de cuatro núcleos) y, en diez ejecuciones, obtuve 1000 tres veces, 999 seis veces y 998 una vez. Entonces la carrera es algo rara, pero claramente presente.

  3. Compilaste con '-g', que tiene una forma de hacer desaparecer los errores. Volví a compilar su código, todavía sin cambios pero sin el '-g', y la carrera se volvió mucho más pronunciada: obtuve 1000 una vez, 999 tres veces, 998 dos veces, 997 dos veces, 996 una vez y 992 una vez.

  4. Re. la sugerencia de agregar un sueño - eso ayuda, pero (a) un tiempo de sueño fijo deja los hilos todavía sesgados por la hora de inicio (sujeto a la resolución del temporizador), y (b) un sueño aleatorio los distribuye cuando lo que queremos es acercarlos más juntos. En su lugar, los codificaría para esperar una señal de inicio, de modo que pueda crearlos todos antes de dejarlos trabajar. Con esta versión (con o sin '-g'), obtengo resultados en todas partes, tan bajos como 974 y no más altos que 998:

    #include <iostream>
    #include <thread>
    #include <vector>
    using namespace std;
    
    unsigned u = 0;
    bool start = false;
    
    void foo()
    {
        while (!start) {
            std::this_thread::yield();
        }
        u++;
    }
    
    int main()
    {
        vector<thread> threads;
        for(int i = 0; i < 1000; i++) {
            threads.push_back (thread (foo));
        }
        start = true;
        for (auto& t : threads) t.join();
    
        cout << u << endl;
        return 0;
    }
dgould
fuente
Solo una nota. La -gbandera no "hace desaparecer los errores" de ninguna manera. La -gbandera en los compiladores GNU y Clang simplemente agrega símbolos de depuración al binario compilado. Esto le permite ejecutar herramientas de diagnóstico como GDB y Memcheck en sus programas con algunos resultados legibles por humanos. Por ejemplo, cuando Memcheck se ejecuta sobre un programa con una pérdida de memoria, no le dirá el número de línea a menos que el programa se haya creado con la -gbandera.
MS-DDOS
Por supuesto, los errores que se esconden del depurador suelen ser más una cuestión de optimización del compilador; Debería haberlo intentado y haber dicho "usar en -O2 lugar de -g". Pero dicho esto, si nunca ha tenido el placer de buscar un error que se manifestaría solo cuando se compila sin él -g , considérese afortunado. Se puede suceder, con algunos de los muy desagradable de errores de aliasing sutiles. Lo he visto, aunque no recientemente, y podría creer que tal vez era una peculiaridad de un compilador propietario antiguo, así que te creeré, provisionalmente, acerca de las versiones modernas de GNU y Clang.
dgould
-gno le impide utilizar optimizaciones. por ejemplo, gcc -O3 -ghace el mismo asm que gcc -O3, pero con metadatos de depuración. gdb dirá "optimizado" si intenta imprimir algunas variables. -gtal vez podría cambiar las ubicaciones relativas de algunas cosas en la memoria, si alguna de las cosas que agrega es parte de la .textsección. Definitivamente ocupa espacio en el archivo de objeto, pero creo que después de vincularlo todo termina en un extremo del segmento de texto (no en la sección), o no forma parte de un segmento en absoluto. Quizás podría afectar dónde se asignan las cosas para las bibliotecas dinámicas.
Peter Cordes