Co oznacza „zdecydowanie wcześniej”?

9

Wyrażenie „zdecydowanie zdarza się wcześniej” jest używane kilkakrotnie w standardowym projekcie C ++.

Na przykład: Zakończenie [basic.start.term] / 5

Jeśli zakończenie inicjalizacji obiektu o czasie przechowywania statycznym nastąpi zdecydowanie przed wywołaniem std :: atexit (patrz [support.start.term]), wywołanie funkcji przekazane do std :: atexit jest sekwencjonowany przed wywołaniem obiektu destruktora dla obiektu. Jeśli wywołanie std :: atexit wystąpi zdecydowanie przed zakończeniem inicjalizacji obiektu o statycznym czasie przechowywania, wywołanie obiektu destruktora dla obiektu jest sekwencjonowane przed wywołaniem funkcji std :: atexit . Jeśli wywołanie std :: atexit wystąpi zdecydowanie przed kolejnym wywołaniem std :: atexit, wywołanie funkcji przekazanej do drugiego wywołania std :: atexit jest sekwencjonowane przed wywołaniem funkcji pierwsze wywołanie std :: atexit.

I zdefiniowane w Wyścigi danych [intro.races] / 12

Ocena Zdecydowanie występuje przed oceną D, jeśli również

(12.1) A jest sekwencjonowane przed D, lub

(12.2) A synchronizuje się z D, a oba A i D są sekwencyjnie spójnymi operacjami atomowymi ([atomics.order]) lub

(12.3) istnieją oceny B i C takie, że A jest sekwencjonowane przed B, B po prostu dzieje się przed C, a C jest sekwencjonowane przed D, lub

(12.4) istnieje ocena B taka, że ​​A dzieje się zdecydowanie przed B, a B występuje zdecydowanie przed D.

[Uwaga: Nieoficjalnie, jeśli A zdarza się zdecydowanie przed B, to A wydaje się być oceniane przed B we wszystkich kontekstach. Zdecydowanie dzieje się przed wykluczeniem operacji konsumpcji. - uwaga końcowa]

Dlaczego wprowadzono „zdecydowanie wcześniej”? Intuicyjnie, jaka jest jego różnica i związek z „dzieje się wcześniej”?

Co oznacza „A wydaje się być oceniane przed B we wszystkich kontekstach” w notatce?

(Uwaga: motywem tego pytania są komentarze Petera Cordesa pod tą odpowiedzią ).

Dodatkowy projekt standardowej wyceny (dzięki Peter Cordes)

Porządek i spójność [atomics.order] / 4

Istnieje jedna suma S dla wszystkich operacji memory_order :: seq_cst, w tym ogrodzeń, która spełnia następujące ograniczenia. Po pierwsze, jeśli A i B są operacjami memory_order :: seq_cst, a A zdarza się silnie przed B, to A poprzedza B w S. Po drugie, dla każdej pary operacji atomowych A i B na obiekcie M, gdzie A jest uporządkowaną spójnością przed B S musi spełnić następujące cztery warunki:

(4.1) jeśli A i B są operacjami memory_order :: seq_cst, to A poprzedza B w S; i

(4.2) jeśli A jest operacją memory_order :: seq_cst, a B dzieje się przed ogrodzeniem Y kolejki memory_order :: seq_cst, to A poprzedza Y w S; i

(4.3) jeśli ogrodzenie memory_order :: seq_cst X nastąpi przed A, a B jest operacją memory_order :: seq_cst, to X poprzedza B w S; i

(4.4) jeśli X_pamięci :: seq_cst ogrodzenie X nastąpi przed A, a B ma miejsce przed X_pamięci :: seq_cst ogrodzenie Y, to X poprzedza Y w S.

ciekawy
źródło
1
Obecny projekt standardu odwołuje się również do „A zdecydowanie dzieje się przed B” jako warunku obowiązującej reguły seq_cstw Atomics 31.4. Porządek i spójność: 4 . Nie ma tego w standardzie C ++ 17 n4659 , w którym 32.4 - 3 definiuje istnienie pojedynczej całkowitej kolejności operacji seq_cst zgodnej z kolejnością „zamówień sprzed” i zleceniami modyfikacji dla wszystkich dotkniętych lokalizacji ; „zdecydowanie” dodano w późniejszym szkicu.
Peter Cordes
2
@PeterCordes Myślę, że komentarz z wyłączeniem konsumpcji, stwierdzający, że jest to HB „we wszystkich kontekstach” / „silny” i mówienie o wywołaniach wskaźników funkcji jest czymś martwym. Jeśli program wielowątkowy wywołuje atexit()w jednym wątku, a exit()w drugim, inicjalizatory nie mogą przenosić tylko zależności zależnej od zużycia tylko dlatego, że wyniki różnią się od tego, czy exit()wywołano go przez ten sam wątek. Moja starsza odpowiedź dotyczyła tej różnicy.
Nie będę istniał Idonotexist
@IwillnotexistIdonotexist Czy możesz nawet wyjść z programu MT? Czy to nie jest zasadniczo zepsuty pomysł?
ciekawy
1
@curiousguy Taki jest cel exit(). Dowolny wątek może zabić cały program, wychodząc lub główny wątek może wyjść przez return-ing. Powoduje to przywołanie przewodników atexit()i śmierć wszystkich wątków, bez względu na to, co robią.
Nie będę istniał Idonotexist

Odpowiedzi:

5

Dlaczego wprowadzono „zdecydowanie wcześniej”? Intuicyjnie, jaka jest jego różnica i związek z „dzieje się wcześniej”?

Przygotuj się również na „po prostu zdarza się wcześniej”! Spójrz na tę bieżącą migawkę cppref https://en.cppreference.com/w/cpp/atomic/memory_order

wprowadź opis zdjęcia tutaj

Wydaje się, że w C ++ 20 dodano „po prostu zdarza się wcześniej”.

Po prostu dzieje się wcześniej

Niezależnie od wątków, ocena A po prostu dzieje się przed oceną B, jeśli spełniony jest jeden z poniższych warunków:

1) A jest sekwencjonowane przed B

2) A synchronizuje się z B

3) Po prostu dzieje się przed X, a X po prostu dzieje się przed B.

Uwaga: bez operacji konsumpcji relacje po prostu zdarzają się wcześniej i zdarzają się zanim relacje będą takie same.

Zatem Simply-HB i HB są takie same, z wyjątkiem tego, jak radzą sobie z operacjami konsumpcji. Zobacz HB

Zdarza się wcześniej

Niezależnie od wątków ocena A ma miejsce przed oceną B, jeśli spełniony jest jeden z poniższych warunków:

1) A jest sekwencjonowane przed B

2) Wątek występuje przed B.

Wdrożenie jest wymagane w celu zapewnienia, że ​​relacja „zdarza się przed” jest acykliczna, poprzez wprowadzenie dodatkowej synchronizacji, jeśli to konieczne (może to być konieczne tylko w przypadku operacji konsumpcji, patrz Batty i in.)

Czym różnią się pod względem konsumpcji? Patrz Inter-Thread-HB

Inter-thread dzieje się wcześniej

Pomiędzy wątkami, ocena A Wątek występuje przed oceną B, jeśli spełniony jest jeden z poniższych warunków

1) A synchronizuje się z B

2) A jest uporządkowane według zależności przed B.

3) ...

...

Operacja, która jest uporządkowana zależnie (tj. Używa wydania / konsumpcji) to HB, ale niekoniecznie Simply-HB.

Spożywanie jest bardziej relaksujące niż nabywanie, więc jeśli dobrze rozumiem, HB jest bardziej zrelaksowany niż Simply-HB.

Zdecydowanie zdarza się wcześniej

Niezależnie od wątków, ocena A dzieje się zdecydowanie przed oceną B, jeśli spełniony jest jeden z poniższych warunków:

1) A jest sekwencjonowane przed B

2) A synchronizuje się z B, a zarówno A, jak i B są sekwencyjnie spójnymi operacjami atomowymi

3) A jest sekwencjonowane przed X, X po prostu dzieje się przed Y, a Y jest sekwencjonowane przed B

4) Zdecydowanie dzieje się - przed X, a X zdecydowanie dzieje się - przed B.

Uwaga: nieformalnie, jeśli A zdarza się zdecydowanie przed B, to A wydaje się być oceniane przed B we wszystkich kontekstach.

Uwaga: zdecydowanie zdarza się przed wykluczeniem operacji konsumpcji.

Tak więc operacja wydania / konsumpcji nie może być silnie HB.

Zwolnienie / przejęcie może być HB i Simply-HB (ponieważ zwolnienie / przejęcie synchronizuje się z), ale niekoniecznie jest silnie HB. Ponieważ Strong-HB wyraźnie mówi, że A musi zsynchronizować się z B AND być operacją sekwencyjnie spójną.

                            Is happens-before guaranteed?

                        HB             Simply-HB          Strongly-HB

relaxed                 no                 no                 no
release/consume        yes                 no                 no      
release/acquire        yes                yes                 no
S.C.                   yes                yes                yes

Co oznacza „A wydaje się być oceniane przed B we wszystkich kontekstach” w notatce?

Wszystkie konteksty: wszystkie wątki / wszystkie procesory widzą (lub „w końcu się zgodzą”) w tej samej kolejności. Jest to gwarancja spójności sekwencyjnej - globalnej kolejności modyfikacji wszystkich zmiennych. Łańcuchy pobierania / zwalniania gwarantują jedynie postrzeganą kolejność modyfikacji dla wątków uczestniczących w łańcuchu. Wątki poza łańcuchem teoretycznie mogą widzieć inną kolejność.

Nie wiem, dlaczego wprowadzono Strong-HB i Simply-HB. Może pomóc wyjaśnić, jak działać wokół konsumpcji? Silnie-HB ma ładne właściwości - jeśli jeden wątek obserwuje Zdecydowanie dzieje się przed B, wie, że wszystkie wątki będą obserwować to samo.

Historia konsumpcji:

Paul E. McKenney jest odpowiedzialny za konsumpcję w standardach C i C ++. Consume gwarantuje uporządkowanie między przypisaniem wskaźnika a pamięcią, na którą wskazuje. Został wynaleziony z powodu DEC Alpha. DEC Alpha mógł spekulacyjnie wyłuskać wskaźnik, dlatego też miał ogrodzenie pamięci, aby temu zapobiec. DEC Alpha nie jest już produkowany i żaden procesor nie ma dzisiaj takiego zachowania. Spożywać ma być bardzo zrelaksowany.

Humphrey Winnebago
źródło
1
O jeny. Prawie żałuję, że zadałem to pytanie. Chcę wrócić do rozwiązywania prostych problemów z C ++, takich jak reguły unieważniania iteratora, wyszukiwanie nazw zależne od argumentów, operatory konwersji zdefiniowane przez użytkownika w szablonie, odejmowanie argumentów szablonu, kiedy wyszukiwanie nazw wygląda na klasę podstawową w elemencie szablonu i kiedy może przekształcić się w wirtualną bazę na początku budowy obiektu.
ciekawy,
Re: konsumować. Czy twierdzisz, że los zamawiania konsumpcji jest powiązany z losem DEC Alpha i nie ma żadnej wartości poza tym konkretnym łukiem?
ciekawy,
1
To dobre pytanie. Patrząc teraz bardziej na to, wygląda na to, że konsumpcja teoretycznie może zwiększyć wydajność słabo uporządkowanych łuków, takich jak ARM i PowerPC. Daj mi trochę więcej czasu, żeby się temu przyjrzeć.
Humphrey Winnebago,
1
Powiedziałbym, że konsumpcja istnieje z powodu wszystkich słabo uporządkowanych ISA innych niż Alpha. W Alpha asm jedyne opcje są zrelaksowane i nabywają (i sekw.-Cst), a nie porządkowanie zależności. mo_consumema na celu skorzystanie z porządkowania zależności danych na rzeczywistych procesorach i sformalizowanie, że kompilator nie może przerwać zależności danych za pomocą przewidywania gałęzi. np. int *p = load(); tmp = *p;mógłby zostać zepsuty przez wprowadzenie kompilatora, if(p==known_address) tmp = *known_address; else tmp=*p;gdyby miał jakiś powód, aby oczekiwać, że pewna wartość wskaźnika będzie wspólna. Jest to legalne dla zrelaksowanego, ale nie konsumpcyjnego.
Peter Cordes,
@PeterCordes ma rację ... łuki o słabym uporządkowaniu muszą emitować barierę pamięci dla akwizycji, ale (teoretycznie) nie do konsumpcji. Wygląda na to, że uważasz, że gdyby Alfa nigdy nie istniał, nadal byśmy konsumowali? Mówisz też, że konsumpcja to fantazyjna (lub „standardowa”) bariera kompilatora.
Humphrey Winnebago,