Contatore atomico in gcc

Question

Devo stare solo un momento, perché questo dovrebbe essere facile ma non riesco a farlo funzionare correttamente.

Qual è il modo corretto di implementare un contatore atomico in GCC?

Ad esempio, voglio un contatore che va da zero a 4 ed è thread-safe.

stavo facendo questo (che è ulteriormente avvolto in una classe, ma non qui)

static volatile int _count = 0; 
const int limit = 4; 

int get_count(){ 
    // Create a local copy of diskid 
    int save_count = __sync_fetch_and_add(&_count, 1); 
    if (save_count >= limit){ 
     __sync_fetch_and_and(&_count, 0); // Set it back to zero 
    } 
    return save_count; 
} 

Ma è in esecuzione da 1 a 1-4 inclusiva poi intorno a zero.
Dovrebbe andare da 0 a 3. Normalmente farei un contatore con un operatore mod ma non lo so sapere come farlo in modo sicuro.

Forse questa versione è migliore. Riesci a vedere eventuali problemi con esso o offrire una soluzione migliore.

int get_count(){ 
    // Create a local copy of diskid 
    int save_count = _count; 
    if (save_count >= limit){ 
     __sync_fetch_and_and(&_count, 0); // Set it back to zero 
     return 0; 
    } 

    return save_count; 
} 

In realtà, vorrei sottolineare che non è assolutamente fondamentale che ogni thread ottiene un valore diverso. Se due thread hanno letto lo stesso valore nello stesso momento, questo non sarebbe un problema. Ma non possono superare il limite in qualsiasi momento.

Answer 1

Il tuo codice non è atomico (e il tuo secondo get_count non incrementa nemmeno il valore del contatore)!

Dire count è 3 all'inizio e due thread contemporaneamente chiamano get_count. Uno di questi otterrà prima la sua aggiunta atomica e incrementerà count in 4. Se il secondo thread è abbastanza veloce, può incrementarlo a 5 prima che il primo thread lo azzeri.

Inoltre, nell'elaborazione wraparound, è possibile reimpostare count su 0 ma non su save_count. Questo chiaramente non è ciò che è inteso.

Questo è più facile se limit è una potenza di 2. Non farlo mai la riduzione da soli, basta usare

return (unsigned) __sync_fetch_and_add(&count, 1) % (unsigned) limit; 

o in alternativa

return __sync_fetch_and_add(&count, 1) & (limit - 1); 

Questo non fa una sola operazione atomica per ogni invocazione , è sicuro e molto economico. Per i limiti generici, è comunque possibile utilizzare %, ma ciò interromperà la sequenza se il contatore dovesse mai traboccare. Puoi provare a utilizzare un valore a 64 bit (se la tua piattaforma supporta gli atomici a 64 bit) e sperare che non trabocchi mai; questa è una cattiva idea. Il modo corretto per farlo è usare un'operazione di confronto-scambio atomico. Fai questo:

int old_count, new_count; 
do { 
    old_count = count; 
    new_count = old_count + 1; 
    if (new_count >= limit) new_count = 0; // or use % 
} while (!__sync_bool_compare_and_swap(&count, old_count, new_count)); 

Questo approccio generalizza anche a sequenze più complesse e operazioni di aggiornamento.

Detto questo, questo tipo di operazione senza chiave è difficile da ottenere, si affida a un comportamento indefinito in una certa misura (tutti i compilatori correnti lo fanno bene, ma nessuno standard C/C++ prima di C++ 0x ha effettivamente un ben definito modello di memoria) ed è facile da rompere. Raccomando di usare un semplice mutex/lock a meno che non lo abbia profilato e trovato un collo di bottiglia.

Answer 2

È impossibile creare qualcosa di atomico in puro C, anche con volatile. Hai bisogno di asm. C1x avrà tipi atomici speciali, ma fino ad allora sei bloccato con asm.

Answer 3

Hai due problemi.

__sync_fetch_and_add tornerà precedente valore (cioè, prima di aggiungere uno). Pertanto, nel passaggio in cui _count diventa 3, la variabile locale save_count recupera 2. Quindi devi effettivamente incrementare _count fino a 4 prima che torni come 3.

Ma anche in cima a quello, il gioco è specificamente alla ricerca per essere >= 4 prima di reimpostare di nuovo a 0. Questo è solo una questione di utilizzare il limite di male se siete solo alla ricerca di esso per ottenere più in alto come tre.

Answer 4

Sei fortunato, perché l'intervallo che vuoi si adatta perfettamente a 2 bit.

Soluzione semplice: lasciare che la variabile volatile contati per sempre. Ma dopo averlo letto, usa solo i due bit più bassi (val & 3). Presto, contatore atomico da 0-3.