Licznik atomów w gcc

Question

Muszę po prostu mieć chwilę, bo to powinno być łatwe, ale nie mogę sprawić, żeby działało prawidłowo.

Jaki jest poprawny sposób na wprowadzenie licznika atomowego w GCC?

tj. Chcę mieć licznik, który działa od zera do 4 i jest bezpieczny dla wątków.

robiłem to (co jest dodatkowo owinięte w klasie, ale nie tutaj)

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; 
} 

Ale to działa od 1 do od 1 - 4 włącznie następnie wokół zera.
Powinno to trwać od 0 do 3. Normalnie chciałbym zrobić licznik z operatorem mod, ale nie wiedzieć, jak to zrobić bezpiecznie.

Być może ta wersja jest lepsza. Czy widzisz jakieś problemy z tym, lub oferują lepsze rozwiązanie.

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; 
} 

Właściwie, powinienem zaznaczyć, że nie jest absolutnie krytyczne, że każda nić ma inną wartość. Jeśli dwa wątki odczytałyby tę samą wartość w tym samym czasie, to nie byłoby problemu. Ale w żadnym momencie nie mogą przekroczyć limitu.

Answer 1

Twój kod nie jest atomowy (a twoja druga get_count nawet nie zwiększa wartości licznika)!

Powiedzmy, że ma 3 na początku i dwa wątki jednocześnie wywołują get_count. Jeden z nich pobierze najpierw swój ładunek atomowy i zwiększy count do 4. Jeśli drugi wątek będzie wystarczająco szybki, może go zwiększyć do 5, zanim pierwszy wątek zresetuje go do zera.

Ponadto w ramach przetwarzania obejścia zresetowano count na 0, ale nie na save_count. To wyraźnie nie jest zgodne z zamierzeniem.

Jest to najprostszy jeśli limit jest potęgą 2. Nie kiedykolwiek zrobić redukcję samemu, wystarczy użyć

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

lub alternatywnie

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

to robi tylko jedną operację atomową za wezwaniem , jest bezpieczny i bardzo tani. W przypadku limitów ogólnych nadal można użyć wartości %, ale spowoduje to przerwanie sekwencji, jeśli licznik kiedykolwiek przepełni się. Możesz spróbować użyć wartości 64-bitowej (jeśli twoja platforma obsługuje 64-bitową atomikę) i po prostu mieć nadzieję, że nigdy się nie przepełni; to jednak zły pomysł. Właściwym sposobem na to jest użycie operacji wymiany atomowej. Zrobisz to:

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)); 

To podejście uogólnia także na bardziej skomplikowane sekwencje i operacje aktualizacji.

To powiedziawszy, ten rodzaj operacji bez blokady jest trudny do uzyskania, w pewnym stopniu polega na nieokreślonym zachowaniu (wszystkie obecne kompilatory uzyskują to poprawnie, ale nie ma standardu C/C++ zanim C++ 0x rzeczywiście ma dobrze zdefiniowane model pamięci) i łatwo go złamać. Zalecam użycie prostego muteksu/blokady, chyba że profilujesz go i uznasz, że jest to wąskie gardło.

Answer 2

Niemożliwe jest stworzenie czegokolwiek atomowego w czystym C, nawet z volatile. Potrzebujesz asm. C1x będzie miał specjalne typy atomowe, ale do tego czasu utkniesz z asmem.

Answer 3

Masz dwa problemy.

__sync_fetch_and_add zwróci poprzedniego (wartość, to znaczy przed dodaniem jeden). Tak więc na etapie, gdzie _count staje się 3, twoja lokalna zmienna save_count powraca 2. Musisz więc zwiększyć wartość _count aż do 4, zanim powróci jako 3.

Przede wszystkim jednak poszukujesz go jako >= 4, zanim zresetujesz go z powrotem do 0. To tylko kwestia użycia złego limitu, jeśli szukasz go tylko po to, aby uzyskać jak najwyższy poziom jak trzy.

Answer 4

Masz szczęście, ponieważ zakres, który chcesz, pasuje do dokładnie 2 bitów.

Łatwe rozwiązanie: pozwól zmiennej lotniczej zliczyć na zawsze. Ale po przeczytaniu użyj tylko dwóch najniższych bitów (val & 3). Presto, licznik atomowy od 0-3.