Zrozumienie std :: atomic :: compare_exchange_weak () w C ++ 11

bool compare_exchange_weak (T& expected, T val, ..);

compare_exchange_weak()jest jednym z prymitywów wymiany porównawczej udostępnionych w C ++ 11. Jest słaba w tym sensie, że zwraca fałsz, nawet jeśli wartość obiektu jest równa expected. Wynika to z fałszywej awarii na niektórych platformach, na których do zaimplementowania jest używana sekwencja instrukcji (zamiast jednej, jak na x86). Na takich platformach przełączanie kontekstu, przeładowanie tego samego adresu (lub linii pamięci podręcznej) przez inny wątek itp. Może zakończyć się niepowodzeniem. To spuriousjak to nie jest wartość przedmiotu (nie równy expected), który nie przejdzie operację. Zamiast tego jest to rodzaj problemów z synchronizacją.

Zastanawiające mnie jednak jest to, co zostało powiedziane w standardzie C ++ 11 (ISO / IEC 14882),

29.6.5 .. Konsekwencją fałszywej awarii jest to, że prawie wszystkie zastosowania słabego porównania i wymiany będą się zapętlać.

Dlaczego w prawie każdym zastosowaniu musi być w pętli ? Czy to oznacza, że ​​będziemy pętli, gdy zawiedzie z powodu fałszywych awarii? Jeśli tak jest, dlaczego sami zawracamy sobie głowę używaniem compare_exchange_weak()i pisaniem pętli? Możemy po prostu użyć tego, compare_exchange_strong()co moim zdaniem powinno pozbyć się za nas fałszywych błędów. Jakie są typowe przypadki użycia compare_exchange_weak()?

Inne pytanie związane. W swojej książce „C ++ Concurrency In Action” Anthony mówi:

//Because compare_exchange_weak() can fail spuriously, it must typically
//be used in a loop:

bool expected=false;
extern atomic<bool> b; // set somewhere else
while(!b.compare_exchange_weak(expected,true) && !expected);

//In this case, you keep looping as long as expected is still false,
//indicating that the compare_exchange_weak() call failed spuriously.

Dlaczego !expectedwystępuje stan pętli? Czy ma to na celu zapobieżenie, że wszystkie wątki mogą umrzeć z głodu i przez jakiś czas nie robić postępów?

Edytuj: (ostatnie pytanie)

Na platformach, na których nie ma jednej instrukcji sprzętowej CAS, zarówno słaba, jak i mocna wersja są implementowane przy użyciu LL / SC (jak ARM, PowerPC itp.). Czy jest więc jakaś różnica między następującymi dwiema pętlami? Dlaczego, jeśli w ogóle? (Według mnie powinny mieć podobną wydajność).

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_weak(..))
{ .. }

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_strong(..)) 
{ .. }

Podchodzę do tego ostatniego pytania, o którym wszyscy wspominacie, że w pętli może być różnica w wydajności. Wspomina o tym również norma C ++ 11 (ISO / IEC 14882):

Gdy funkcja porównania i wymiany jest zapętlona, ​​słaba wersja zapewni lepszą wydajność na niektórych platformach.

Jednak jak przeanalizowano powyżej, dwie wersje w pętli powinny dawać taką samą / podobną wydajność. Za czym tęsknię?

Dlaczego warto robić wymianę w pętli?

Zwykle chcesz, aby Twoja praca została wykonana, zanim przejdziesz dalej, dlatego wprowadzasz compare_exchange_weakpętlę, aby próbowała się wymieniać, dopóki się nie powiedzie (tj. Nie zwróci true).

Zauważ, że compare_exchange_strongjest również często używany w pętli. Nie zawodzi z powodu fałszywej awarii, ale zawodzi z powodu współbieżnych zapisów.

Dlaczego używać weakzamiast strong?

Całkiem proste: pozorna awaria nie zdarza się często, więc nie jest to duży hit wydajnościowy. Z drugiej strony tolerowanie takiej awarii pozwala na znacznie wydajniejszą implementację weakwersji (w porównaniu do strong) na niektórych platformach: strongnależy zawsze sprawdzać fałszywą awarię i ją maskować. To jest drogie.

Dlatego weakjest używany, ponieważ jest znacznie szybszy niż strongna niektórych platformach

Kiedy stosować weaki kiedy strong?

Odniesienia stanowi podpowiedzi kiedy używać weaki kiedy użyć strong:

Gdy funkcja porównania i wymiany jest zapętlona, ​​słaba wersja zapewni lepszą wydajność na niektórych platformach. Gdy słabe porównanie i wymiana wymagałoby pętli, a mocna nie, preferowana jest mocna.

Zatem odpowiedź wydaje się być dość prosta do zapamiętania: jeśli musiałbyś wprowadzić pętlę tylko z powodu fałszywej awarii, nie rób tego; używać strong. Jeśli i tak masz pętlę, użyj weak.

Dlaczego !expectedw przykładzie

Zależy to od sytuacji i pożądanej semantyki, ale zwykle nie jest to potrzebne do poprawności. Pominięcie go dałoby bardzo podobną semantykę. Tylko w przypadku, gdy inny wątek mógłby zresetować wartość do false, semantyka może się nieco zmienić (ale nie mogę znaleźć sensownego przykładu, w którym byś tego chciał). Zobacz komentarz Tony'ego D. po szczegółowe wyjaśnienie.

Jest to po prostu szybka ścieżka, gdy inny wątek pisze true: Następnie przerywamy zamiast próbować pisać trueponownie.

O twoim ostatnim pytaniu

Jednak jak przeanalizowano powyżej, dwie wersje w pętli powinny dawać taką samą / podobną wydajność. Za czym tęsknię?

Z Wikipedii :

Prawdziwe implementacje LL / SC nie zawsze kończą się powodzeniem, jeśli nie ma równoległych aktualizacji w danej lokalizacji pamięci. Wszelkie wyjątkowe zdarzenia między tymi dwiema operacjami, takie jak przełączanie kontekstu, inne łącze ładowania lub nawet (na wielu platformach) inna operacja ładowania lub przechowywania, spowodują fałszywe niepowodzenie warunku magazynu. Starsze implementacje zakończą się niepowodzeniem, jeśli są jakieś aktualizacje rozgłaszane przez magistralę pamięci.

Tak więc, na przykład, LL / SC zawiedzie fałszywie przy przełączaniu kontekstu. Teraz, silna wersja przyniosłaby swoją „własną małą pętlę”, aby wykryć tę fałszywą awarię i maskować ją, próbując ponownie. Należy zauważyć, że ta własna pętla jest również bardziej skomplikowana niż zwykła pętla CAS, ponieważ musi odróżniać fałszywe niepowodzenie (i maskować je) od niepowodzenia wynikającego z równoczesnego dostępu (co powoduje zwrot z wartością false). Słaba wersja nie ma takiej własnej pętli.

Ponieważ w obu przykładach podajesz jawną pętlę, po prostu nie jest konieczne posiadanie małej pętli dla silnej wersji. W konsekwencji, w przykładzie z strongwersją, sprawdzenie awarii jest wykonywane dwukrotnie; raz przez compare_exchange_strong(co jest bardziej skomplikowane, ponieważ musi rozróżniać fałszywe awarie i równoczesne dostępy) i raz przez pętlę. Ten kosztowny czek jest niepotrzebny i powód, dla którego weakbędzie tutaj szybszy.

Zauważ również, że twój argument (LL / SC) to tylko jedna możliwość zaimplementowania tego. Jest więcej platform, które mają nawet różne zestawy instrukcji. Ponadto (i co ważniejsze) pamiętaj, że std::atomicmusi obsługiwać wszystkie operacje dla wszystkich możliwych typów danych , więc nawet jeśli zadeklarujesz strukturę dziesięciomilionową, możesz użyć compare_exchangena tym. Nawet w przypadku procesora, który ma CAS, nie można CAS dziesięciu milionów bajtów, więc kompilator wygeneruje inne instrukcje (prawdopodobnie przejęcie blokady, po którym nastąpi nieatomowe porównanie i zamiana, a następnie zwolnienie blokady). Pomyśl teraz, ile rzeczy może się wydarzyć podczas wymiany dziesięciu milionów bajtów. Więc chociaż fałszywy błąd może być bardzo rzadki przy wymianie 8-bajtowej, może być bardziej powszechny w tym przypadku.

Krótko mówiąc, C ++ oferuje dwie semantyki, jedną ( weak) z „najlepszym wysiłkiem” i „Zrobię to na pewno, bez względu na to, ile złych rzeczy może się wydarzyć pomiędzy” one ( strong). Sposób ich implementacji na różnych typach danych i platformach to zupełnie inny temat. Nie wiąż swojego modelu mentalnego z implementacją na konkretnej platformie; Biblioteka standardowa została zaprojektowana do pracy z większą liczbą architektur, niż możesz być świadomy. Jedyny ogólny wniosek, jaki możemy wyciągnąć, jest taki, że zagwarantowanie sukcesu jest zwykle trudniejsze (i dlatego może wymagać dodatkowej pracy) niż tylko próba i pozostawienie miejsca na ewentualną porażkę.

Dlaczego w prawie każdym zastosowaniu musi być w pętli ?

Ponieważ jeśli nie zapętlisz i nie powiedzie się to fałszywie, twój program nie zrobił nic użytecznego - nie zaktualizowałeś obiektu atomowego i nie wiesz, jaka jest jego aktualna wartość (korekta: patrz komentarz poniżej Camerona). Jeśli połączenie nie przyniesie nic pożytecznego, jaki jest sens tego robić?

Czy to oznacza, że ​​będziemy pętli, gdy zawiedzie z powodu fałszywych awarii?

Tak.

Jeśli tak jest, dlaczego sami zawracamy sobie głowę używaniem compare_exchange_weak()i pisaniem pętli? Możemy po prostu użyć funkcji compare_exchange_strong (), która moim zdaniem powinna pozbyć się za nas fałszywych błędów. Jakie są typowe przypadki użycia compare_exchange_weak ()?

Na niektórych architekturach compare_exchange_weakjest bardziej wydajne, a fałszywe awarie powinny być dość rzadkie, więc może być możliwe napisanie bardziej wydajnych algorytmów przy użyciu słabej formy i pętli.

Ogólnie rzecz biorąc, prawdopodobnie lepiej jest użyć silnej wersji, jeśli twój algorytm nie musi się zapętlać, ponieważ nie musisz się martwić o fałszywe awarie. Jeśli i tak musi zapętlić się nawet dla silnej wersji (a wiele algorytmów i tak musi zapętlić), to użycie słabej formy może być bardziej wydajne na niektórych platformach.

Dlaczego !expectedwystępuje stan pętli?

Wartość mogła zostać ustawiona trueprzez inny wątek, więc nie chcesz kontynuować próby ustawienia w pętli.

Edytować:

Jednak jak przeanalizowano powyżej, dwie wersje w pętli powinny dawać taką samą / podobną wydajność. Za czym tęsknię?

Z pewnością jest oczywiste, że na platformach, na których możliwa jest fałszywa awaria, implementacja compare_exchange_strongmusi być bardziej skomplikowana, aby sprawdzić fałszywą awarię i spróbować ponownie.

Słaba forma po prostu powraca w przypadku fałszywej awarii, nie próbuje ponownie.

Próbuję sobie na to odpowiedzieć, po przejrzeniu różnych zasobów online (np. Tego i tego ), standardu C ++ 11, a także udzielonych tutaj odpowiedzi.

Powiązane pytania są łączone (np. „ Dlaczego! Oczekiwano? ” Jest łączone z „dlaczego umieścić w pętli porównaj_exchange_weak ()? ”) I udzielane są odpowiednio odpowiedzi.

Dlaczego funkcja compare_exchange_weak () musi być zapętlona w prawie wszystkich zastosowaniach?

Typowy wzór A

Musisz uzyskać atomową aktualizację na podstawie wartości zmiennej atomowej. Niepowodzenie wskazuje, że zmienna nie została zaktualizowana naszą żądaną wartością i chcemy spróbować ponownie. Zauważ, że tak naprawdę nie obchodzi nas, czy nie powiedzie się z powodu współbieżnego zapisu lub fałszywej awarii. Ale obchodzi nas, że to my dokonujemy tej zmiany.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

Przykładem w świecie rzeczywistym jest jednoczesne dodawanie elementu do listy pojedynczo połączonej przez kilka wątków. Każdy wątek najpierw ładuje wskaźnik nagłówka, przydziela nowy węzeł i dołącza nagłówek do tego nowego węzła. Wreszcie próbuje zamienić nowy węzeł z głową.

Innym przykładem jest implementacja muteksu przy użyciu std::atomic<bool>. Co najwyżej jednej nici można wprowadzić krytyczny punkt w czasie, w zależności od ustawienia nitki pierwszej currentdo truei zamknięcia pętli.

Typowy wzór B.

To jest właściwie wzór wspomniany w książce Anthony'ego. W przeciwieństwie do wzorca A, chcesz, aby zmienna atomowa została zaktualizowana raz, ale nie obchodzi Cię, kto to robi. Dopóki nie jest zaktualizowany, spróbuj ponownie. Jest to zwykle używane w przypadku zmiennych boolowskich. Np. Musisz zaimplementować wyzwalacz, aby maszyna stanu mogła się poruszać. Która nić pociąga za spust, jest niezależna.

expected = false;
// !expected: if expected is set to true by another thread, it's done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Zauważ, że generalnie nie możemy użyć tego wzorca do implementacji muteksu. W przeciwnym razie w sekcji krytycznej może znajdować się jednocześnie wiele wątków.

To powiedziawszy, powinno być rzadkie używanie compare_exchange_weak()poza pętlą. Wręcz przeciwnie, zdarzają się przypadki, że używana jest silna wersja. Na przykład,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak nie jest tutaj właściwe, ponieważ gdy powraca z powodu fałszywej awarii, prawdopodobnie nikt jeszcze nie zajmuje krytycznej sekcji.

Głodująca nić?

Warto wspomnieć o tym, że co się stanie, jeśli fałszywe awarie będą nadal występować, powodując głodzenie nici? Teoretycznie może się to zdarzyć na platformach, gdy compare_exchange_XXX()jest zaimplementowane jako sekwencja instrukcji (np. LL / SC). Częsty dostęp do tej samej linii pamięci podręcznej między LL i SC spowoduje ciągłe fałszywe awarie. Bardziej realistycznym przykładem jest głupie planowanie, w którym wszystkie współbieżne wątki są przeplatane w następujący sposób.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

Czy to się może stać?

Na szczęście nie stanie się to wiecznie dzięki temu, czego wymaga C ++ 11:

Implementacje powinny zapewnić, że słabe operacje porównania i wymiany nie będą konsekwentnie zwracać fałszu, chyba że obiekt atomowy ma wartość inną niż oczekiwana lub istnieją równoległe modyfikacje obiektu atomowego.

Dlaczego zawracamy sobie głowę użyciem compare_exchange_weak () i sami piszemy pętlę? Możemy po prostu użyć compare_exchange_strong ().

To zależy.

Przypadek 1: Gdy oba muszą być użyte wewnątrz pętli. C ++ 11 mówi:

Gdy funkcja porównania i wymiany jest zapętlona, ​​słaba wersja zapewni lepszą wydajność na niektórych platformach.

Na x86 (przynajmniej obecnie. Może pewnego dnia skorzysta z podobnego schematu jak LL / SC, aby uzyskać wydajność, gdy zostanie wprowadzonych więcej rdzeni), słaba i mocna wersja są zasadniczo takie same, ponieważ obie sprowadzają się do jednej instrukcji cmpxchg. Na niektórych innych platformach, na których compare_exchange_XXX()nie jest zaimplementowana atomowo (co oznacza, że ​​nie istnieje żaden pojedynczy prymityw sprzętowy), słaba wersja wewnątrz pętli może wygrać bitwę, ponieważ silniejsza będzie musiała poradzić sobie z fałszywymi awariami i odpowiednio spróbować ponownie.

Ale,

rzadko, może wolimy compare_exchange_strong()się compare_exchange_weak()nawet w pętli. Np., Gdy jest dużo rzeczy do zrobienia pomiędzy ładowaniem zmiennej atomowej, a obliczona nowa wartość jest wymieniana (patrz function()wyżej). Jeśli sama zmienna atomowa nie zmienia się często, nie musimy powtarzać kosztownych obliczeń dla każdej fałszywej awarii. Zamiast tego możemy mieć nadzieję, że compare_exchange_strong()„pochłoną” takie awarie i powtarzamy obliczenia tylko wtedy, gdy zawiodą one z powodu rzeczywistej zmiany wartości.

Przypadek 2: Kiedy compare_exchange_weak() trzeba używać tylko wewnątrz pętli. C ++ 11 mówi również:

Gdy słabe porównanie i wymiana wymagałoby pętli, a mocna nie, preferowana jest mocna.

Dzieje się tak zazwyczaj, gdy wykonujesz pętlę tylko po to, aby wyeliminować fałszywe błędy ze słabej wersji. Ponawiasz próbę, aż wymiana zakończy się powodzeniem lub niepowodzeniem z powodu współbieżnego zapisu.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

W najlepszym przypadku jest to wymyślenie na nowo kół i działanie tak samo, jak compare_exchange_strong(). Gorzej? Takie podejście nie pozwala w pełni wykorzystać maszyn, które zapewniają niefałszywe porównywanie i wymianę sprzętu .

Na koniec, jeśli zapętlisz inne rzeczy (np. Zobacz „Typowy wzorzec A” powyżej), to jest duża szansa, że compare_exchange_strong()zostanie ona również zapętlona, ​​co przeniesie nas z powrotem do poprzedniego przypadku.

W porządku, więc potrzebuję funkcji, która wykonuje atomowe przesunięcie w lewo. Mój procesor nie ma do tego natywnej operacji, a standardowa biblioteka nie ma do tego funkcji, więc wygląda na to, że piszę własną. Tutaj idzie:

void atomicLeftShift(std::atomic<int>* var, int shiftBy)
{
    do {
        int oldVal = std::atomic_load(var);
        int newVal = oldVal << shiftBy;
    } while(!std::compare_exchange_weak(oldVal, newVal));
}

Istnieją dwa powody, dla których pętla może być wykonywana więcej niż raz.

1. Ktoś inny zmienił zmienną, kiedy robiłem lewą zmianę. Wyniki moich obliczeń nie powinny być stosowane do zmiennej atomowej, ponieważ skutecznie wymazałoby to czyjeś zapis.
2. Mój procesor pękł, a słaby CAS fałszywie zawiódł.

Szczerze nie obchodzi mnie, który. Zmiana biegów w lewo jest na tyle szybka, że ​​równie dobrze mogę po prostu zrobić to ponownie, nawet jeśli błąd był pozorny.

Co znajduje się mniej szybko, choć jest dodatkowy kod, że silne potrzeby CAS owinąć wokół słaby CAS aby być silny. Ten kod nie robi wiele, gdy słaby CAS się powiedzie ... ale kiedy zawiedzie, silny CAS musi wykonać jakąś pracę detektywistyczną, aby ustalić, czy był to przypadek 1, czy przypadek 2. Ta praca detektywa przyjmuje formę drugiej pętli, efektywnie wewnątrz własnej pętli. Dwie zagnieżdżone pętle. Wyobraź sobie, że twój nauczyciel algorytmów patrzy na ciebie teraz.

I jak już wspomniałem, nie obchodzi mnie wynik tej pracy detektywa! Tak czy inaczej zamierzam przerobić CAS. Tak więc używanie silnego CAS nie daje mi nic, a traci małą, ale wymierną ilość wydajności.

Innymi słowy, słaby CAS jest używany do implementacji niepodzielnych operacji aktualizacji. Silny CAS jest używany, gdy zależy Ci na wyniku CAS.

Myślę, że większość powyższych odpowiedzi traktuje „pozorną awarię” jako pewnego rodzaju problem, kompromis między wydajnością a poprawnością.

Można to zauważyć, ponieważ słaba wersja jest przez większość czasu szybsza, ale w przypadku fałszywej awarii staje się wolniejsza. A mocna wersja to wersja, która nie ma możliwości fałszywej awarii, ale prawie zawsze jest wolniejsza.

Dla mnie główna różnica polega na tym, jak te dwie wersje radzą sobie z problemem ABA:

słaba wersja odniesie sukces tylko wtedy, gdy nikt nie dotknął linii pamięci podręcznej między ładowaniem a przechowywaniem, więc w 100% wykryje problem ABA.

silna wersja zawiedzie tylko w przypadku niepowodzenia porównania, więc nie wykryje problemu ABA bez dodatkowych środków.

Tak więc teoretycznie, jeśli używasz słabej wersji na słabo uporządkowanej architekturze, nie potrzebujesz mechanizmu detekcji ABA, a implementacja będzie znacznie prostsza, dając lepszą wydajność.

Ale na x86 (architektura z silnym uporządkowaniem) słaba wersja i silna wersja są takie same i oba cierpią na problem ABA.

Więc jeśli piszesz algorytm całkowicie wieloplatformowy, i tak musisz rozwiązać problem ABA, więc użycie słabej wersji nie przynosi korzyści w zakresie wydajności, ale istnieje spadek wydajności w przypadku obsługi fałszywych awarii.

Podsumowując - ze względu na przenośność i wydajność, mocna wersja jest zawsze lepszą lub równą opcją.

Słaba wersja może być lepszą opcją tylko wtedy, gdy pozwala całkowicie pominąć środki zaradcze ABA lub twój algorytm nie dba o ABA.