Jak osiągnąć barierę StoreLoad w C ++ 11?

Chcę napisać przenośny kod (Intel, ARM, PowerPC ...), który rozwiązuje wariant klasycznego problemu:

Initially: X=Y=0

Thread A:
  X=1
  if(!Y){ do something }
Thread B:
  Y=1
  if(!X){ do something }

w którym celem jest uniknięcie sytuacji, w której robią oba wątkisomething . (W porządku, jeśli żadna rzecz nie działa; nie jest to mechanizm jednokrotnego uruchomienia.) Popraw mnie, jeśli zauważysz jakieś błędy w moim rozumowaniu poniżej.

Zdaję sobie sprawę, że mogę osiągnąć cel z memory_order_seq_cstatomowych stores oraz loads, co następuje:

std::atomic<int> x{0},y{0};
void thread_a(){
  x.store(1);
  if(!y.load()) foo();
}
void thread_b(){
  y.store(1);
  if(!x.load()) bar();
}

który osiąga cel, ponieważ musi istnieć jakaś pojedyncza całkowita kolejność
{x.store(1), y.store(1), y.load(), x.load()}zdarzeń, która musi zgadzać się z kolejnością programu „zbocza”:

• x.store(1) „w TO jest przed” y.load()
• y.store(1) „w TO jest przed” x.load()

a jeśli foo()został wywołany, mamy dodatkową przewagę:

• y.load() „czyta wartość przed” y.store(1)

a jeśli bar()został wywołany, mamy dodatkową przewagę:

• x.load() „czyta wartość przed” x.store(1)

a wszystkie te krawędzie połączone razem utworzyłyby cykl:

x.store(1)„w TO jest przed” y.load()„odczytuje wartość przed” y.store(1)”w TO jest przed” x.load()„czyta wartość przed”x.store(true)

co narusza fakt, że zamówienia nie mają cykli.

Celowo używam niestandardowych terminów „w TO jest przed” i „odczytuje wartość przed” w przeciwieństwie do standardowych terminów, takich jak happens-before, ponieważ chcę prosić o opinię na temat poprawności mojego założenia, że ​​te krawędzie rzeczywiście sugerują happens-beforerelację, można łączyć razem w jedno wykres, a cykl na takim połączonym wykresie jest zabroniony. Nie jestem tego pewny. Wiem, że ten kod tworzy prawidłowe bariery dla Intel gcc & clang i ARM gcc

Teraz mój prawdziwy problem jest nieco bardziej skomplikowany, ponieważ nie mam kontroli nad „X” - jest ukryty za niektórymi makrami, szablonami itp. I może być słabszy niż seq_cst

Nie wiem nawet, czy „X” jest pojedynczą zmienną, czy jakimś innym pojęciem (np. Lekki semafor lub muteks). Wiem tylko, że mam dwa makra set()i check()tak, że check()wraca true„po” inny wątek nazwał set(). (To jest znany również, że seti checksą thread-safe i nie można utworzyć danych wyścigu UB).

Tak koncepcyjnie set()jest trochę jak „X = 1” i check()jest jak „X”, ale nie mam bezpośredniego dostępu do atomów, jeśli w ogóle.

void thread_a(){
  set();
  if(!y.load()) foo();
}
void thread_b(){
  y.store(1);
  if(!check()) bar();
}

Martwię się, że set()może to być wewnętrznie zaimplementowane x.store(1,std::memory_order_release)i / lub check()być x.load(std::memory_order_acquire). Lub hipotetycznie: std::mutexjeden wątek się odblokowuje, a drugi zaczyna try_lock; w standardzie ISO std::mutexgwarantuje się tylko uzyskanie i wydanie zamówienia, a nie seq_cst.

Jeśli tak jest, to check()czy ciało można wcześniej „zmienić” y.store(true)( patrz odpowiedź Alexa, gdzie pokazują, że dzieje się tak na PowerPC ).
Byłoby to naprawdę złe, ponieważ teraz możliwa jest następująca sekwencja zdarzeń:

• thread_b()najpierw ładuje starą wartość x( 0)
• thread_a() wykonuje wszystko, w tym foo()
• thread_b() wykonuje wszystko, w tym bar()

Tak więc, zarówno foo()i bar()został sprawdzony, co miałem do uniknięcia. Jakie są moje opcje, aby temu zapobiec?

Opcja A

Spróbuj wymusić barierę Store-Load. W praktyce można to osiągnąć poprzez std::atomic_thread_fence(std::memory_order_seq_cst);- jak wyjaśnił Alex w innej odpowiedzi - wszystkie testowane kompilatory emitowały pełne ogrodzenie:

• x86_64: MFENCE
• PowerPC: hwsync
• Itanuim: mf
• ARMv7 / ARMv8: dmb ish
• MIPS64: synchronizacja

Problem z tym podejściem polega na tym, że nie mogłem znaleźć żadnej gwarancji w regułach C ++, która std::atomic_thread_fence(std::memory_order_seq_cst)musi przełożyć się na pełną barierę pamięci. W rzeczywistości koncepcja atomic_thread_fences w C ++ wydaje się być na innym poziomie abstrakcji niż koncepcja asemblacji barier pamięci i zajmuje się bardziej takimi rzeczami, jak „co atomowa synchronizuje z czym”. Czy jest jakiś teoretyczny dowód, że poniższe wdrożenie osiąga cel?

void thread_a(){
  set();
  std::atomic_thread_fence(std::memory_order_seq_cst)
  if(!y.load()) foo();
}
void thread_b(){
  y.store(true);
  std::atomic_thread_fence(std::memory_order_seq_cst)
  if(!check()) bar();
}

Opcja B

Użyj kontroli, jaką mamy nad Y, aby osiągnąć synchronizację, używając operacji odczytu-modyfikacji-zapisu memory_order_acq_rel na Y:

void thread_a(){
  set();
  if(!y.fetch_add(0,std::memory_order_acq_rel)) foo();
}
void thread_b(){
  y.exchange(1,std::memory_order_acq_rel);
  if(!check()) bar();
}

Chodzi tutaj o to, że dostęp do pojedynczego atomu ( y) musi być utworzony w jednym porządku, w którym zgadzają się wszyscy obserwatorzy, więc albo fetch_addjest przed, exchangealbo na odwrót.

Jeśli fetch_addjest wcześniej, exchangeto część „release” fetch_addsynchronizuje się z częścią „acquire”, exchangea zatem wszystkie efekty uboczne set()muszą być widoczne podczas wykonywania kodu check(), więc bar()nie zostaną wywołane.

W przeciwnym razie exchangejest wcześniej fetch_add, wtedy fetch_addzobaczy 1i nie zadzwoni foo(). Nie można więc zadzwonić zarówno do, jak foo()i do bar(). Czy to rozumowanie jest prawidłowe?

Opcja C

Użyj atrapy atomów, aby wprowadzić „krawędzie”, które zapobiegną katastrofie. Rozważ następujące podejście:

void thread_a(){
  std::atomic<int> dummy1{};
  set();
  dummy1.store(13);
  if(!y.load()) foo();
}
void thread_b(){
  std::atomic<int> dummy2{};
  y.store(1);
  dummy2.load();
  if(!check()) bar();
}

Jeśli uważasz, że problem jest atomiclokalny, wyobraź sobie przeniesienie ich do zakresu globalnego, w następującym rozumowaniu nie wydaje mi się to mieć znaczenia, a ja celowo napisałem kod w taki sposób, aby ujawnić, jak zabawny jest ten manekin1 i dummy2 są całkowicie oddzielne.

Dlaczego na ziemi to może działać? Cóż, musi istnieć jakaś pojedyncza całkowita kolejność, {dummy1.store(13), y.load(), y.store(1), dummy2.load()}która musi być spójna z „krawędziami” programu:

• dummy1.store(13) „w TO jest przed” y.load()
• y.store(1) „w TO jest przed” dummy2.load()

(Mam nadzieję, że seq_cst store + load tworzy odpowiednik C ++ pełnej bariery pamięci, w tym StoreLoad, tak jak robią one w asm na prawdziwych ISA, w tym nawet AArch64, gdzie nie są wymagane oddzielne instrukcje barier).

Teraz mamy do rozważenia dwa przypadki: albo y.store(1)jest przed, y.load()albo w kolejności całkowitej.

Jeśli y.store(1)jest przed y.load()czym foo()nie będzie się nazywać i jesteśmy bezpieczni.

Jeśli y.load()jest wcześniej y.store(1), to łącząc go z dwoma krawędziami, które już mamy w kolejności programowej, wywnioskujemy, że:

• dummy1.store(13) „w TO jest przed” dummy2.load()

Teraz dummy1.store(13)jest to operacja zwolnienia, która uwalnia efekty set()i dummy2.load()jest operacją pozyskiwania, więc check()powinieneś zobaczyć efekty set()i dlatego bar()nie będziemy wywoływani, a my jesteśmy bezpieczni.

Czy można tutaj myśleć, że check()zobaczą wyniki set()? Czy mogę łączyć w ten sposób „krawędzie” różnego rodzaju („kolejność programu”, czyli Sequenced Before, „total order”, „before release”, „after nabyć”)? Mam co do tego poważne wątpliwości: wydaje się, że reguły C ++ mówią o „synchronizacji z” relacjami między sklepem a ładowaniem w tej samej lokalizacji - tutaj nie ma takiej sytuacji.

Należy pamiętać, że jesteśmy tylko martwi przypadku gdy dumm1.storejest znany (za pośrednictwem innego rozumowania), aby być wcześniej dummy2.loadw kolejności ogólnej seq_cst. Gdyby mieli dostęp do tej samej zmiennej, ładunek zobaczyłby zapisaną wartość i zsynchronizował się z nią.

(Wyjaśnienie dotyczące bariery pamięci / ponownego zamawiania dla implementacji, w których ładunki atomowe i magazyny kompilują się z co najmniej 1-stronnymi barierami pamięci (a operacje seq_cst nie mogą zmienić kolejności: np. Sklep seq_cst nie może przekazać obciążenia seq_cst) jest taki, że jakiekolwiek obciążenia / sklepy po dummy2.loadzdecydowanie stają się widoczne dla innych wątków po y.store . I podobnie dla innych wątków ... wcześniej y.load.)

Możesz zagrać z moją implementacją Opcji A, B, C na https://godbolt.org/z/u3dTa8

Opcje A i B są poprawnymi rozwiązaniami.

• Opcja A: tak naprawdę nie ma znaczenia, na co tłumaczy się ogrodzenie sekwencyjne, standard C ++ wyraźnie określa, jakie gwarancje zapewnia. Przedstawiłem je w tym poście: Kiedy przydatne jest ogrodzenie memory_order_seq_cst?
• Opcja B: tak, twoje rozumowanie jest prawidłowe. Wszystkie modyfikacje niektórych obiektów mają jedną całkowitą kolejność (kolejność modyfikacji), więc możesz użyć tego do synchronizacji wątków i zapewnienia widoczności wszystkich efektów ubocznych.

Jednak opcja C nie jest ważna! Relację synchronizacji z można ustanowić tylko poprzez operacje pozyskiwania / zwalniania tego samego obiektu . W twoim przypadku masz dwa zupełnie różne i niezależne przedmioty dummy1oraz dummy2. Nie można ich jednak użyć do ustalenia relacji „zdarza się przed”. W rzeczywistości, ponieważ zmienne atomowe są czysto lokalne (tj. Zawsze są dotykane tylko przez jeden wątek), kompilator może je usunąć w oparciu o zasadę as-if .

Aktualizacja

Opcja A:
zakładam set()i check()działam na pewnej wartości atomowej. Następnie mamy następującą sytuację (-> oznacza sekwencję przed ):

• set()-> fence1(seq_cst)->y.load()
• y.store(true)-> fence2(seq_cst)->check()

Możemy więc zastosować następującą zasadę:

W przypadku operacji atomowych A i B na obiekcie atomowym M , gdzie A modyfikuje M, a B przyjmuje swoją wartość, jeśli istnieją memory_order_seq_cstogrodzenia X i Y takie, że A jest sekwencjonowane przed X , Y jest sekwencjonowane przed B , a X poprzedza Y w S , następnie B obserwuje albo wpływ A, albo późniejszą modyfikację M w kolejności modyfikacji.

Tzn. Albo check()widzi zapisaną wartość set, albo y.load()zapisaną wartość y.store()(operacje na ymożna nawet wykorzystać memory_order_relaxed).

Wariant C: C ++ 17 standardowych stany [32.4.3, p1347]

Powinna istnieć jedna całkowita kolejność S dla wszystkich memory_order_seq_cstoperacji, zgodna z kolejnością i modyfikacją „wydarzy się przed” dla wszystkich dotkniętych lokalizacji [...]

Ważnym słowem jest tutaj „konsekwentny”. Oznacza to, że jeśli operacja dzieje, przed operacją na B , a następnie musi poprzedzać B w S . Jednak logiczną implikacją jest jednokierunkowa uliczka, więc nie możemy wywnioskować odwrotnego: właśnie dlatego, że niektóre operacje C poprzedza działanie D w S nie oznacza, że C dzieje się przed D .

W szczególności dwie operacje sekwencyjne na dwóch osobnych obiektach nie mogą być użyte do ustalenia relacji przed zdarzeniem, nawet jeśli operacje są całkowicie uporządkowane w S. Jeśli chcesz zamówić operacje na osobnych obiektach, musisz odwołać się do sekw. - ogrodzenia (patrz Opcja A).

W pierwszym przykładzie y.load()odczyt 0 nie oznacza, że y.load()zdarzyło się to wcześniej y.store(1).

Oznacza to jednak, że jest wcześniej w pojedynczej kolejności całkowitej dzięki regule, że ładowanie seq_cst zwraca albo wartość ostatniego magazynu seq_cst w całkowitej kolejności, albo wartość jakiegoś sklepu innego niż seq_cst, który nie występuje wcześniej to (które w tym przypadku nie istnieje). Więc jeśli y.store(1)był wcześniej niż y.load()w całkowitej kolejności, y.load()zwróciłbym 1.

Dowód jest nadal poprawny, ponieważ pojedyncze zamówienie całkowite nie ma cyklu.

Co powiesz na to rozwiązanie?

std::atomic<int> x2{0},y{0};

void thread_a(){
  set();
  x2.store(1);
  if(!y.load()) foo();
}

void thread_b(){
  y.store(1);
  if(!x2.load()) bar();
}

@mpoeter wyjaśnił, dlaczego opcje A i B są bezpieczne.

W praktyce przy rzeczywistych implementacjach, myślę, że Opcja A potrzebuje tylko std::atomic_thread_fence(std::memory_order_seq_cst)w wątku A, a nie B.

Sklepy seq-cst w praktyce zawierają pełną barierę pamięci, lub na AArch64 przynajmniej nie można zmienić kolejności z późniejszymi ładowaniami lub seq_cst ( stlrsekwencyjne uwalnianie musi opróżnić bufor pamięci, zanim będzie ldarmogło odczytać z pamięci podręcznej).

Odwzorowania C ++ -> asm mają do wyboru koszt opróżnienia bufora magazynu na zapasach atomowych lub ładunkach atomowych. Rozsądnym wyborem dla rzeczywistych implementacji jest tanie ładunki atomowe, więc sklepy seq_cst zawierają pełną barierę (w tym StoreLoad). Podczas gdy obciążenia seq_cst są takie same, jak w większości przypadków.

(Ale nie POWER; nawet obciążenia wymagają dużej synchronizacji = pełna bariera, aby zatrzymać przekazywanie do sklepu z innych wątków SMT na tym samym rdzeniu, co może prowadzić do zmiany kolejności IRIW, ponieważ seq_cst wymaga, aby wszystkie wątki mogły uzgodnić kolejność wszystkie operacje seq_cst. Czy dwa zapisy atomowe w różnych lokalizacjach w różnych wątkach zawsze będą widziane w tej samej kolejności przez inne wątki? )

(Oczywiście, aby uzyskać formalną gwarancję bezpieczeństwa, potrzebujemy ogrodzenia w obu przypadkach, aby promować nabywanie / zwalnianie set () -> check () w seq_cst synchronizuje się z. Myślę, że działałoby to również w przypadku zrelaksowanego zestawu, ale luźna kontrola może zmienić kolejność z paskiem z POV innych wątków.)

Myślę, że prawdziwy problem z Opcją C polega na tym, że zależy to od jakiegoś hipotetycznego obserwatora, który mógłby zsynchronizować z yoperacjami pozorowanymi. Dlatego oczekujemy, że kompilator zachowa tę kolejność podczas tworzenia asm dla ISA opartego na barierach.

Tak będzie w praktyce na prawdziwych ISA; oba wątki zawierają pełną barierę lub równoważny, a kompilatory nie optymalizują (jeszcze) atomiki. Ale oczywiście „kompilacja do opartego na barierach ISA” nie jest częścią standardu ISO C ++. Spójna współdzielona pamięć podręczna to hipotetyczny obserwator, który istnieje dla rozumowania asm, ale nie dla rozumowania ISO C ++.

Aby opcja C działała, potrzebujemy zamówienia takiego jak dummy1.store(13);/ y.load()/ set(); (jak widać w wątku B), aby złamać jakąś zasadę ISO C ++ .

Wątek, w którym działają te instrukcje, musi zachowywać się tak, jakby set() wykonywany jako pierwszy (ze względu na sekwencję przed). To dobrze, porządkowanie pamięci środowiska wykonawczego i / lub zmiana kolejności operacji w czasie kompilacji mogą nadal to robić.

Dwa seq_cst ops d1=13i ysą zgodne z sekwencją przed (kolejność programu). set()nie uczestniczy w wymaganym globalnym zamówieniu dla operacji seq_cst, ponieważ nie jest to seq_cst.

Wątek B nie synchronizuje się z dummy1.store, więc nie dzieje się przed wymaganiem setwzględemd1=13 zastosowanie , mimo że zadanie jest operacja uwolnienia.

Nie widzę żadnych innych możliwych naruszeń zasad; Nie mogę tu znaleźć niczego, co wymagałoby zachowania zgodności z setsekwencją-przedtemd1=13 .

Argumentacja „dummy1.store releases set ()” jest wadą. Ta kolejność dotyczy tylko prawdziwego obserwatora, który synchronizuje się z nią lub w asm. Jak odpowiedział @mpoeter, istnienie całkowitego zamówienia seq_cst nie tworzy ani nie sugeruje, że wydarzy się relacja przedtem, a to jedyna rzecz, która formalnie gwarantuje zamówienie poza seq_cst.

Jakikolwiek rodzaj „normalnego” procesora ze spójną współdzieloną pamięcią podręczną, w którym zmiana kolejności mogłaby się zdarzyć w czasie wykonywania, nie wydaje się prawdopodobna. (Ale jeśli kompilator mógłby usunąć dummy1idummy2 następnie najwyraźniej mielibyśmy problem, i myślę, że jest to dozwolone przez standard).

Ale ponieważ model pamięci C ++ nie jest zdefiniowany w kategoriach bufora sklepu, współdzielonej spójnej pamięci podręcznej lub testów lakmusowych dozwolonego ponownego zamawiania, rzeczy wymagane przez rozsądek nie są formalnie wymagane przez reguły C ++. Jest to być może celowe, aby umożliwić optymalizację nawet zmiennych seq_cst, które okazują się być wątkami prywatnymi. (Obecne kompilatory nie robią tego oczywiście ani żadnej innej optymalizacji obiektów atomowych.)

Implementacja, w której jeden wątek naprawdę widział set()ostatni, podczas gdy inny widział set()pierwsze dźwięki niewiarygodne. Nawet MOC nie mogła tego zrobić; zarówno seq_cst load, jak i store zawierają pełne bariery dla POWER. (Zasugerowałem w komentarzach, że zmiana kolejności IRIW może być tutaj istotna; reguły acq / rel w C ++ są wystarczająco słabe, aby to uwzględnić, ale całkowity brak gwarancji poza synchronizacją - lub innymi zdarzeniami - zanim sytuacja stanie się znacznie słabsza niż jakikolwiek sprzęt. )

C ++ nie gwarantuje niczego dla non-seq_cst, chyba że faktycznie jest obserwator, a potem tylko dla tego obserwatora. Bez niego jesteśmy na terytorium kota Schroedingera. Lub, jeśli dwa drzewa spadną do lasu, czy jedno spadło przed drugim? (Jeśli jest to duży las, ogólna teoria względności mówi, że zależy to od obserwatora i że nie ma uniwersalnej koncepcji jednoczesności.)

@mpoeter zasugerował, że kompilator może nawet usunąć fikcyjne ładowanie i przechowywać operacje, nawet na obiektach seq_cst.

Myślę, że może to być poprawne, gdy mogą udowodnić, że nic nie może zsynchronizować się z operacją. np. kompilator, który widzi, że dummy2nie ucieka z funkcji, może prawdopodobnie usunąć to obciążenie seq_cst.

Ma to co najmniej jedną konsekwencję w świecie rzeczywistym: w przypadku kompilacji dla AArch64 pozwoliłoby to wcześniejszemu sklepowi seq_cst zmienić kolejność w praktyce z późniejszymi zrelaksowanymi operacjami, co nie byłoby możliwe przy sklepie seq_cst + obciążeniu bufora sklepu przed jakimkolwiek innym później mogą być wykonywane obciążenia.

Oczywiście obecne kompilatory wcale nie optymalizują atomów, nawet jeśli ISO C ++ tego nie zabrania; to nierozwiązany problem dla komitetu normalizacyjnego.

Myślę, że jest to dozwolone, ponieważ model pamięci C ++ nie ma niejawnego obserwatora ani wymogu, aby wszystkie wątki zgadzały się na zamówienie. Zapewnia pewne gwarancje oparte na spójnych pamięciach podręcznych, ale nie wymaga widoczności dla wszystkich wątków, aby były jednoczesne.

w standardzie ISO std :: mutex ma tylko gwarancję nabycia i wydania, a nie seq_cst.

Ale nic nie gwarantuje „seq_cst ordering”, ponieważ seq_cstnie jest własnością żadnej operacji.

seq_cstjest gwarancją wszystkich operacji danej implementacji std::atomiclub alternatywnej klasy atomowej. W związku z tym twoje pytanie jest nieuzasadnione.