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 current
do true
i 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;
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;
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.