C, C++ hilos no sincronizados que devuelven un resultado extraño

Question

Bien, tengo esta pregunta en uno con respecto a los hilos.

hay dos hilos de la falta de sincronización se ejecutan simultáneamente y utilizando un recurso global "int num" primero:

void Thread() 
{ 
    int i; 
    for (i=0 ; i < 100000000; i++) 
    { 
     num++; 
     num--; 
    } 
} 

segundo:

void Thread2() 
{ 
    int j; 
    for (j=0 ; j < 100000000; j++) 
    { 
     num++; 
     num--;  
    } 
} 

Los estados pregunta: ¿cuáles son los posibles valores de la variable "num" al final del programa. ahora yo diría que 0 será el valor de num al final del programa pero, intente ejecutar este código y verá que el resultado es bastante aleatorio, y no puedo entender por qué?

El código completo:

#include <windows.h> 
    #include <process.h> 
    #include <stdio.h> 

    int static num=0; 

    void Thread() 
    { 
     int i; 
     for (i=0 ; i < 100000000; i++) 
     { 
      num++; 
      num--; 
     } 
    } 

    void Thread2() 
    { 
     int j; 
     for (j=0 ; j < 100000000; j++) 
     { 
      num++; 
      num--;  
     } 
    } 

    int main() 
    { 
     long handle,handle2,code,code2; 
     handle=_beginthread(Thread, 0, NULL); 
     handle2=_beginthread(Thread2, 0, NULL); 

     while((GetExitCodeThread(handle,&code)||GetExitCodeThread(handle2,&code2))!=0); 

     TerminateThread(handle, code); 
     TerminateThread(handle2, code2); 

     printf("%d ",num); 
     system("pause"); 
    } 

Answer 1

num++ y num-- no tienen que ser las operaciones atómicas. Para tomar num++ como un ejemplo, esto es, probablemente, implementado como:

int tmp = num; 
tmp = tmp + 1; 
num = tmp; 

donde tmp se mantiene en un registro de la CPU.

Ahora vamos a decir que num == 0, ambos hilos intenta ejecutar num++, y las operaciones se intercalan los siguientes:

Thread A  Thread B 
int tmp = num; 
tmp = tmp + 1; 
       int tmp = num; 
       tmp = tmp + 1; 
num = tmp; 
       num = tmp; 

El resultado al final habrá num == 1 a pesar de que debería haber sido incrementado dos veces. Aquí, se pierde un incremento; de la misma manera, una disminución también podría perderse.

En casos patológicos, todos los incrementos de un hilo pueden perderse, lo que resulta en num == -100000000, o pueden perderse todos los decrementos de un hilo, lo que resulta en num == +100000000. Incluso puede haber escenarios más extremos acechando por ahí.

Luego también están en curso otros asuntos, porque num no está declarado como volátil. Ambos hilos supondrán, por lo tanto, que el valor de num no cambia, a menos que sean los que lo cambian. Esto permite que el compilador optimice todo el circuito for, ¡si así lo desea!

Answer 2

Los valores posibles para num incluyen todos los posibles valores de int, además de valores de punto flotante, cadenas y jpegs de demonios nasales. Una vez que invoca comportamiento indefinido, todas las apuestas están desactivadas.

Más específicamente, la modificación del mismo objeto de varios hilos sin sincronización da como resultado un comportamiento indefinido. En la mayoría de los sistemas del mundo real, los peores efectos que se ven probablemente estarán ausentes o incrementos o decrementos dobles, pero podría ser mucho peor (corrupción de memoria, estrellarse, corrupción de archivos, etc.). Entonces no lo hagas.

Los próximos estándares C y C++ próximos incluirán tipos atómicos que pueden tener acceso seguro desde múltiples hilos sin ninguna API de sincronización.

Answer 3

Como dijo Thomas, los resultados son impredecibles porque su incremento y decremento no son atómicos. Puede usar InterlockedIncrement y InterlockedDecrement, que son atómicos, para ver un resultado predecible.

• Interlocked Variable Access (MSDN)

Answer 4

Usted habla de subprocesos que se ejecutan al mismo tiempo que en realidad podría no ser el caso si sólo tiene un núcleo en su sistema. Supongamos que tienes más de uno.

En el caso de que varios dispositivos tengan acceso a la memoria principal en forma de CPU o bus-mastering o DMA, deben estar sincronizados. Esto es manejado por el prefijo de bloqueo (implícito para la instrucción xchg). Accede a un cable físico en el bus del sistema que básicamente señala a todos los dispositivos presentes que se mantengan alejados. Es, por ejemplo, parte de la función Win32 EnterCriticalSection.

Entonces, en el caso de dos núcleos en el mismo chip que acceden a la misma posición, el resultado no se definiría, lo que puede parecer extraño teniendo en cuenta que debe haber sincronización ya que comparten el mismo caché L3 (si hay uno). Parece lógico, pero no funciona de esa manera. ¿Por qué? Porque ocurre un caso similar cuando tiene los dos núcleos en chips diferentes (no tengo un caché L3 compartido). No puede esperar que estén sincronizados. Bueno, puedes considerar todos los otros dispositivos que tienen acceso a la memoria principal. Si planea sincronizar entre dos chips de CPU, no puede detenerse ahí: debe realizar una sincronización completa que bloquee todos los dispositivos con acceso y para asegurar una sincronización exitosa, todos los demás dispositivos necesitan tiempo para reconocer que una sincronización ha se ha solicitado y eso lleva mucho tiempo, especialmente si se le ha otorgado acceso a un dispositivo y está realizando una operación de masterización de bus que debe permitirse completar. El bus PCI realizará una operación cada 0.125 us (8 MHz) y considerando que sus CPU funcionan a 400 veces, usted está viendo MUCHOS estados de espera. Luego considere que pueden ser necesarios varios ciclos de reloj PCI.

Se podría argumentar que debería existir un bloqueo de tipo medio (solo bus de memoria), pero esto significa un pin adicional en cada procesador y lógica adicional en cada chipset solo para manejar un caso que es realmente un malentendido por parte del programador. Entonces no está implementado.

Para resumir: una sincronización genérica que manejaría su situación dejaría inutilizada su PC debido a que siempre tenía que esperar al último dispositivo para verificar y aprobar la sincronización. Es una mejor solución para que sea opcional y solo inserte estados de espera cuando el desarrollador haya determinado que es absolutamente necesario.

---

Esto fue tan divertido que he jugado un poco con el código de ejemplo y añadió spinlocks para ver lo que sucedería. Los componentes spinlock eran

// prototypes 

char spinlock_failed (spinlock *); 
void spinlock_leave (spinlock *); 

// application code 

while (spinlock_failed (&sl)) ++n; 
++num; 
spinlock_leave (&sl); 

while (spinlock_failed (&sl)) ++n; 
--num; 
spinlock_leave (&sl); 

spinlock_failed fue construido alrededor de la "xchg mem, eax" instrucción. Una vez que falló (al no configurar el spinlock < => se logró establecerlo) spinlock_leave simplemente le asignaría "mov mem, 0". El "++ n" cuenta el número total de reintentos.

Cambié el bucle a 2.5 millones (porque con dos subprocesos y dos spinlocks por loop obtengo 10 millones de spinlocks, agradables y fáciles de redondear) y sincronicé las secuencias con el conteo "rdtsc" en un Athlon II M300 a doble núcleo a 2 GHz y esto es lo que encontraron

• Ejecución de un hilo sin temporización (excepto para el bucle principal) y cerraduras (como en el ejemplo el original) 33748884 < => 16,9 ms => 13,5 ciclos/bucle.
• Ejecución de un hilo i E Ningún otro núcleo tratando tomó 210917969 ciclos < => 105,5 ms => 84,4 ciclos/bucle < => nos 0.042/bucle. Los spinlocks requieren 112581340 ciclos < => 22.5 ciclos por secuencia de spinlocked. Aún así, el spinlock más lento requiere 1334208 ciclos: eso es 667 us o solo 1500 por segundo.

Por lo tanto, la adición de spinlocks no afectados por otra CPU agrega varios cientos por ciento al tiempo total de ejecución. El valor final en num era 0.

• Ejecución de dos hilos sin spinlocks tomó 171157957 ciclos < => 85,6 ms => 68,5 ciclos/bucle. Num contenía 10176.
• Dos hilos con spinlocks tomaron => 2049 ms => 1640 ciclos/bucle < => nos 0.82/bucle. Los spinlocks requieren 3930091465 ciclos => 786 ciclos por secuencia de spinlocked. El spinlock más lento requiere 27038623 ciclos: eso es 13.52 ms o solo 74 por segundo. Num contenía 0.

Incidentalmente los 171157957 ciclos para dos hilos sin spinlocks compara muy favorablemente con dos roscas con spinlocks donde se ha eliminado el tiempo spinlock: 4099370103-3930091465 = 169 278 638 ciclos.

Para mi secuencia, la competencia de spinlock provocó 21-29 millones de reintentos por subproceso, que sale a 4.2-5.8 reintentos por spinlock o 5.2-6.8 tries por spinlock. La adición de spinlocks causó una penalización de tiempo de ejecución de 1927% (1500/74-1). El spinlock más lento requirió 5-8% de todos los intentos.