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 tymfoo()thread_b()wykonuje wszystko, w tymbar()
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
foo()i bar()być wywoływanym jednocześnie.
compare_exchange_*do wykonania operacji RMW na atomie bool bez zmiany jego wartości (po prostu ustaw oczekiwany i nowy na tę samą wartość).
atomic<bool>has exchangeand compare_exchange_weak. Ten ostatni może być użyty do wykonania manekina RMW poprzez (próbę) CAS (prawda, prawda) lub fałsz, fałsz. Albo zawiedzie, albo atomowo zamieni wartość na siebie. (W architekturze x86-64 asm ta sztuczka lock cmpxchg16bpolega na tym, jak wykonywać gwarantowane 16-bajtowe obciążenia; niewydajne, ale mniej złe niż oddzielne blokowanie.)
foo()nie bar()zostaniemy wezwani. Nie chciałem przenosić do wielu elementów „prawdziwego świata” kodu, aby uniknąć odpowiedzi typu „myślisz, że masz problem X, ale problem Y”. Ale jeśli naprawdę trzeba wiedzieć, co to jest kondygnacja w tle: set()to naprawdę some_mutex_exit(), check()to try_enter_some_mutex(), yjest „są kelnerzy”, foo()to „wyjście bez budzenia nikogo”, bar()to „czekanie na budzenie” ... Ale odmawiam przedyskutuj ten projekt tutaj - nie mogę go naprawdę zmienić.
std::atomic_thread_fence(std::memory_order_seq_cst)kompiluje się do pełnej bariery, ale ponieważ cała koncepcja jest szczegółem implementacji, którego nie znajdziesz wszelkie wzmianki o tym w normie. (Modele pamięci procesora są zwykle definiowane w kategoriach dozwolonych ponownych powtórzeń w odniesieniu do spójności sekwencyjnej. Np. X86 to seq-cst + bufor sklepu z przekazywaniem)