C, thread non sincronizzati in C++ che restituiscono uno strano risultato

Question

Ok, ho questa domanda in uno riguardante i thread.

ci sono due thread non sincronizzati in esecuzione contemporaneamente e utilizzando una risorsa globale "int num" 1 °:

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

2 °:

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

Gli stati domanda: Quali sono i possibili valori del variabile "num" alla fine del programma. ora direi che 0 sarà il valore di num alla fine del programma ma, prova ad eseguire questo codice e scoprirai che il risultato è abbastanza casuale, e non riesco a capire perché?

Il codice 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++ e num-- non devono essere operazioni atomiche. Per prendere num++ come esempio, questo è probabilmente implementato come:

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

dove tmp si tiene in un registro della CPU.

Ora diciamo che num == 0, entrambi i fili tenta di eseguire num++, e le operazioni sono intercalati come segue:

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

Il risultato alla fine sarà num == 1 anche se avrebbe dovuto essere incrementato due volte. Qui, un incremento è perso; allo stesso modo, si potrebbe perdere anche un decremento.

In casi patologici, tutti gli incrementi di un thread potrebbero essere persi, con conseguente num == -100000000, o tutti i decrementi di un thread potrebbero essere persi, con conseguente num == +100000000. Ci possono anche essere più scenari estremi in agguato là fuori.

Poi ci sono anche altri affari in corso, perché num non è dichiarato come volatile. Entrambi i thread presumono quindi che il valore di num non cambi, a meno che non siano quelli che lo modificano. Ciò consente al compilatore di ottimizzare l'intero ciclo for, se si sente così inclinato!

Answer 2

I valori possibili per num includono tutti i valori possibili int, oltre a valori in virgola mobile, stringhe e jpeg di demoni nasali. Dopo aver invocato il comportamento non definito , tutte le scommesse sono disattivate.

In particolare, la modifica dello stesso oggetto da più thread senza sincronizzazione provoca un comportamento non definito. Sulla maggior parte dei sistemi del mondo reale, gli effetti peggiori che si vedono probabilmente mancheranno o saranno doppi incrementi o decrementi, ma potrebbe essere molto peggiore (corruzione della memoria, arresto anomalo, danneggiamento dei file, ecc.). Quindi non farlo.

I prossimi standard C e C++ includeranno i tipi atomici che possono accedere a in modo sicuro da più thread senza alcuna API di sincronizzazione.

Answer 3

Come ha detto Thomas, i risultati sono imprevedibili perché il vostro incremento e decremento sono non-atomica. È possibile utilizzare InterlockedIncrement e InterlockedDecrement, che sono atomici, per vedere un risultato prevedibile.

• Interlocked Variable Access (MSDN)

Answer 4

si parla di thread in esecuzione contemporaneamente che in realtà potrebbe non essere il caso se si dispone di un solo core nel vostro sistema. Supponiamo che tu ne abbia più di uno.

Nel caso di più dispositivi che hanno accesso alla memoria principale sotto forma di CPU o bus-mastering o DMA, devono essere sincronizzati. Questo è gestito dal prefisso di blocco (implicito per l'istruzione xchg). Accede a un cavo fisico sul bus di sistema che essenzialmente segnala a tutti i dispositivi presenti di stare alla larga. Ad esempio, fa parte della funzione Win32 EnterCriticalSection.

Quindi, nel caso di due core sullo stesso chip che accedono alla stessa posizione, il risultato sarebbe indefinito che potrebbe sembrare strano considerando che dovrebbe verificarsi una sincronizzazione poiché condividono la stessa cache L3 (se ce n'è una). Sembra logico, ma non funziona in questo modo. Perché? Perché un caso simile si verifica quando si hanno i due core su chip diversi (non ho una cache L3 condivisa). Non puoi aspettarti che siano sincronizzati. Bene, ma puoi considerare tutti gli altri dispositivi che hanno accesso alla memoria principale. Se si prevede di sincronizzare tra due chip della CPU, non è possibile fermarsi lì: è necessario eseguire una sincronizzazione completa che blocca tutti i dispositivi con accesso e per garantire una sincronizzazione corretta tutti gli altri dispositivi hanno bisogno di tempo per riconoscere che una sincronizzazione ha è stato richiesto e ciò richiede molto tempo, specialmente se a un dispositivo è stato concesso l'accesso e sta eseguendo un'operazione di masterizzazione del bus che deve essere consentita per completare. Il bus PCI eseguirà un'operazione ogni 0.125 us (8 MHz) e considerando che le tue CPU funzionano a 400 volte stai osservando MOLTI stati di attesa. Quindi considera che potrebbero essere necessari diversi cicli di clock PCI.

Si potrebbe sostenere che un blocco di tipo medio (solo bus di memoria) dovrebbe esistere ma questo significa un pin aggiuntivo su ogni processore e logica aggiuntiva in ogni chipset solo per gestire un caso che è davvero un malinteso da parte del programmatore. Quindi non è implementato.

Per riassumere: una sincronizzazione generica che gestirà la situazione renderebbe il PC inutilizzabile a causa del fatto che deve sempre attendere l'ultimo dispositivo per il check in e ok la sincronizzazione. È una soluzione migliore per renderla facoltativa e inserire solo gli stati di attesa quando lo sviluppatore ha stabilito che è assolutamente necessario.

---

Questo era così divertente che ho giocato un po 'con il codice di esempio e spinlocks aggiunto per vedere cosa sarebbe successo. I componenti di Spinlock erano

// 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 è stato costruito intorno al "xchg mem, eax" istruzioni. Una volta fallito (senza impostare lo spinlock < => riuscito a impostarlo) spinlock_leave gli assegnerebbe semplicemente "mov mem, 0". Il "++ n" conta il numero totale di tentativi.

Ho cambiato il loop a 2.5 milioni (perché con due thread e due spinlock per loop ottengo 10 milioni di spinlock, bello e facile da arrotondare) e cronometrato le sequenze con il conteggio "rdtsc" su un dual-core Athlon II M300 a 2GHz e questo è quello che faccio trovato

• esecuzione un thread senza temporizzazione (tranne per il ciclo principale) e serrature (come nell'esempio originale) 33.748.884 < => 16,9 ms => 13,5 cicli/loop.
• esecuzione un thread i e nessun altro core cercando prese 210917969 cicli < => 105,5 ms => 84,4 cicli/anello < => us 0,042/loop. Gli spinlock richiedevano 112581340 cicli < => 22,5 cicli per sequenza spinlocked . Tuttavia, lo spinlock più lento richiedeva cicli 1334208 : ovvero 667 us o solo 1500 ogni secondo.

Quindi, l'aggiunta di spinlock non interessati da un'altra CPU ha aggiunto diverse centinaia di percento al tempo di esecuzione totale. Il valore finale in num era 0.

• Esecuzione di due thread senza spinlocks preso 171157957 cicli < => 85,6 ms => 68,5 cicli/loop. Num conteneva 10176.
• Due fili con spinlocks preso 4.099.370,103 mila < => 2049 ms => 1640 cicli/anello < => us 0.82/loop. Gli spinotti necessari 3930091465 cicli => 786 cicli per sequenza spinlock. Lo spinlock più lento richiede 27038623 cicli: questo è il 13,52 ms o solo 74 al secondo. Num conteneva 0.

inciso i 171157957 cicli per due fili senza spinlocks confronta molto favorevolmente a due fili con spinlocks cui è stato rimosso il tempo spinlock: 4099370103-3930091465 = 169.278.638 cicli.

Per la mia sequenza, la competizione spinlock ha provocato 21-29 milioni di tentativi per thread, che si traducono in 4.2-5.8 tentativi per spinlock o 5.2-6.8 tentativi per spinlock. L'aggiunta di spinlock ha causato una penalità per il tempo di esecuzione del 1927% (1500/74-1). Lo spinlock più lento ha richiesto il 5-8% di tutti i tentativi.