Я хочу написать переносимый код (Intel, ARM, PowerP C ...), который решает вариант задачи classi c:
Initially: X=Y=0
Thread A:
X=1
if(!Y){ do something }
Thread B:
Y=1
if(!X){ do something }
, в котором цель чтобы избежать ситуации, в которой оба потока делают something. (Хорошо, если ни одна из них не запускается; это не механизм, запускаемый ровно один раз.) Пожалуйста, исправьте меня, если вы увидите некоторое fl aws в моих рассуждениях ниже.
Я знаю, что могу достигните цели с memory_order_seq_cst atomi c store s и load s следующим образом:
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();
}
, которая достигает цели, потому что на
должен быть какой-то один общий заказ {x.store(1), y.store(1), y.load(), x.load()} события, которые должны согласовываться с «гранями» программного порядка:
x.store(1) «в TO до» y.load()y.store(1) »в TO до «x.load()
и если был вызван foo(), то у нас есть дополнительное ребро:
y.load()» читает значение перед «y.store(1)
и если был вызван bar(), то у нас есть дополнительное ребро:
x.load() "читает значение перед" x.store(1)
и все эти ребра, объединенные вместе, образовали бы цикл:
x.store(1) "в TO до" y.load() "считывает значение до" y.store(1) "в TO до" x.load() "читает значение до" x.store(true)
, что нарушает тот факт, что у заказов нет циклов.
Я намеренно использую нестандартные термины «в ТО есть раньше» и «читает значение раньше» в отличие от стандартных терминов, таких как happens-before, потому что я хочу потребовать Обратная связь о правильности моего предположения о том, что эти ребра действительно подразумевают отношение happens-before, может быть объединена в один граф, и цикл в таком объединенном графе запрещен. Я не уверен в этом. Я знаю, что этот код создает правильные барьеры на Intel g cc & clang и на ARM g cc
Теперь моя настоящая проблема немного сложнее, потому что я не контролирую "X" - он скрыт за некоторыми макросами, шаблонами и т. д. c. и может быть слабее, чем seq_cst
Я даже не знаю, является ли «X» единственной переменной или какой-то другой концепцией (например, легкий семафор или мьютекс). Все, что я знаю, это то, что у меня есть два макроса set() и check(), так что check() возвращает true "после" другого потока с именем set(). (Известно, что также известно, что set и check являются поточно-ориентированными и не могут создавать UB для гонки данных.)
Так что концептуально set() чем-то похоже на "X" = 1 "и check() похоже на" X ", но у меня нет прямого доступа к атомам, если таковые имеются.
void thread_a(){
set();
if(!y.load()) foo();
}
void thread_b(){
y.store(1);
if(!check()) bar();
}
Я беспокоюсь, что set() может быть реализовано внутри как x.store(1,std::memory_order_release) и / или check() может быть x.load(std::memory_order_acquire). Или гипотетически std::mutex, что один поток разблокируется, а другой try_lock ing; в стандарте ISO std::mutex гарантируется только порядок получения и выпуска, но не seq_cst.
Если это так, то check(), если тело можно «переупорядочить» до y.store(true) ( См. Ответ Алекса , где они демонстрируют, что это происходит на PowerP C).
Это было бы очень плохо, так как теперь такая последовательность событий возможна:
thread_b() сначала загружает старое значение x (0) thread_a() выполняет все, включая foo()thread_b() выполняет все, включая bar()
Итак, оба foo() и bar() были вызваны, чего я должен был избежать. Какие у меня есть варианты, чтобы предотвратить это?
Опция A
Попытаться форсировать барьер Store-Load. На практике это может быть достигнуто с помощью std::atomic_thread_fence(std::memory_order_seq_cst); - как объяснил Алекс в другом ответе все протестированные компиляторы выдавали полный забор:
- x86_64: MFENCE
- PowerP C: hwsyn c
- Итануим: mf
- ARMv7 / ARMv8: dmb i sh
- MIPS64: syn c
Проблема этого подхода заключается в том, что я не смог найти никакой гарантии в правилах C ++, что std::atomic_thread_fence(std::memory_order_seq_cst) должен переводиться в полный барьер памяти. На самом деле, концепция atomic_thread_fence s в C ++, кажется, находится на другом уровне абстракции, чем концепция ассемблирования барьеров памяти, и имеет дело с такими вещами, как «то, что операция atomi c синхронизирует с чем». Есть ли какие-либо теоретические доказательства того, что приведенная ниже реализация достигает цели?
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();
}
Опция B
Используйте контроль над Y, чтобы добиться синхронизации, используя read-modify -write memory_order_acq_rel Операции с 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();
}
Идея заключается в том, что доступ к одному атому c (y) должен формировать единый порядок, с которым согласны все наблюдатели, поэтому либо fetch_add предшествует exchange или наоборот.
Если fetch_add предшествует exchange, то часть «release» fetch_add синхронизируется с частью «acqu» в exchange и, таким образом, все побочные эффекты set() должны быть видимы для кода, выполняющего check(), поэтому bar() не будет вызываться.
В противном случае exchange предшествует fetch_add, тогда fetch_add увидит 1 и не звоните foo(). Таким образом, невозможно назвать и foo(), и bar(). Правильно ли это рассуждение?
Опция C
Использовать фиктивную атомарность, чтобы ввести «ребра», которые предотвращают катастрофу. Рассмотрим следующий подход:
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();
}
Если вы думаете, что проблема здесь в том, что atomic s являются локальными, то представьте, что вы перемещаете их в глобальную область, в следующих рассуждениях это не кажется мне важным и я намеренно написал код таким образом, чтобы показать, как забавно, что dummy1 и dummy2 полностью отделены друг от друга.
Почему, черт возьми, это может сработать? Ну, должен быть какой-то один общий порядок {dummy1.store(13), y.load(), y.store(1), dummy2.load()}, который должен соответствовать программному порядку "ребер":
dummy1.store(13) "в TO перед" y.load()y.store(1) "в ТО есть раньше" dummy2.load()
(хранилище seq_cst + загрузка, мы надеемся, образуют эквивалент C ++ полного барьера памяти, включая StoreLoad, как они делают в asm на реальных ISA включая даже AArch64, где не требуются отдельные инструкции по барьеру.)
Теперь у нас есть два случая, чтобы рассмотреть: либо y.store(1) до y.load(), либо после в общем порядке.
Если y.store(1) до y.load(), тогда foo() не будет вызван, и мы в безопасности.
Если y.load() до y.store(1), то объединяем его с двумя ребрами, которые у нас уже есть в программном порядке , мы выводим, что:
dummy1.store(13) "в TO до" dummy2.load()
Теперь dummy1.store(13) - это операция освобождения, которая освобождает эффекты set(), а dummy2.load() является операцией получения, поэтому check() должен видеть эффекты set() и, следовательно, bar() wi Меня не вызовут, и мы в безопасности.
Правильно ли здесь думать, что check() увидит результаты set()? Могу ли я так комбинировать "ребра" разных видов ("программный порядок" или "Последовательный до", "общий порядок", "до выпуска", "после приобретения")? У меня есть серьезные сомнения по этому поводу: Кажется, правила C ++ говорят об отношениях «синхронизирует с» между хранилищем и загрузкой в одном и том же месте - здесь такой ситуации нет.
Обратите внимание, что нас беспокоит только случай, когда dumm1.store равен известно (по другим причинам) до dummy2.load в общем порядке seq_cst. Поэтому, если бы они обращались к одной и той же переменной, загрузка увидела бы сохраненное значение и синхронизировалась бы с ним.
(Рассуждение о барьере памяти / переупорядочении для реализаций, где atomi c загружается и хранится, компилируется в Минимальные односторонние барьеры памяти (и операции seq_cst не могут переупорядочиваться: например, хранилище seq_cst не может передать нагрузку seq_cst) состоит в том, что любые загрузки / сохранения после dummy2.load определенно становятся видимыми для других потоков после y.store. И аналогично для другого потока, ... до y.load.)
Вы можете поиграть с моей реализацией опций A, B, C на https://godbolt.org/z/u3dTa8