Я запускал кучу алгоритмов через Relacy , чтобы проверить их правильность, и наткнулся на что-то, чего я действительно не понял. Вот его упрощенная версия:
#include <thread>
#include <atomic>
#include <iostream>
#include <cassert>
struct RMW_Ordering
{
std::atomic<bool> flag {false};
std::atomic<unsigned> done {0}, counter {0};
unsigned race_cancel {0}, race_success {0}, sum {0};
void thread1() // fail
{
race_cancel = 1; // data produced
if (counter.fetch_add(1, std::memory_order_release) == 1 &&
!flag.exchange(true, std::memory_order_relaxed))
{
counter.store(0, std::memory_order_relaxed);
done.store(1, std::memory_order_relaxed);
}
}
void thread2() // success
{
race_success = 1; // data produced
if (counter.fetch_add(1, std::memory_order_release) == 1 &&
!flag.exchange(true, std::memory_order_relaxed))
{
done.store(2, std::memory_order_relaxed);
}
}
void thread3()
{
while (!done.load(std::memory_order_relaxed)); // livelock test
counter.exchange(0, std::memory_order_acquire);
sum = race_cancel + race_success;
}
};
int main()
{
for (unsigned i = 0; i < 1000; ++i)
{
RMW_Ordering test;
std::thread t1([&]() { test.thread1(); });
std::thread t2([&]() { test.thread2(); });
std::thread t3([&]() { test.thread3(); });
t1.join();
t2.join();
t3.join();
assert(test.counter == 0);
}
std::cout << "Done!" << std::endl;
}
Два потока стремятся войти в защищенную область, а последний изменяет done , освобождая третий поток от бесконечного l oop. Пример немного надуманный, но исходный код должен запросить эту область через флаг , чтобы сигнализировать «готово».
Изначально fetch_add имел acq_rel упорядочение, потому что я был обеспокоен тем, что обмен может быть переупорядочен раньше, что может привести к тому, что один поток потребует флаг, сначала попытается проверить fetch_add , и предотвратить другой поток (который проходит проверку приращения). ) от успешного изменения графика. Во время тестирования с Relacy я решил, что произойдет ли ожидаемая мной живая блокировка, если я переключусь с acq_rel на release , и, к моему удивлению, это не произошло , Затем я использовал relaxed для всего, и опять же, без livelock.
Я пытался найти какие-либо правила, относящиеся к этому, в стандарте C ++, но мне удалось выкопать только эти:
1.10.7 Кроме того, существуют расслабленные операции атома c, которые не являются операциями синхронизации, и операции атома c чтения-изменения-записи, которые имеют специальные характеристики.
29.3.11 Atomi c Операции чтения-изменения-записи должны всегда читать последнее значение (в порядке изменения), записанное перед записью, связанной с операцией чтения-изменения-записи.
Могу ли я всегда полагаться на то, что операции RMW не переупорядочиваются - даже если они влияют на различные области памяти - и есть ли в стандарте что-либо, гарантирующее такое поведение?
РЕДАКТИРОВАТЬ :
Я придумал более простую настройку, которая должна немного лучше проиллюстрировать мой вопрос. Вот сценарий CppMem для него:
int main()
{
atomic_int x = 0; atomic_int y = 0;
{{{
{
if (cas_strong_explicit(&x, 0, 1, relaxed, relaxed))
{
cas_strong_explicit(&y, 0, 1, relaxed, relaxed);
}
}
|||
{
if (cas_strong_explicit(&x, 0, 2, relaxed, relaxed))
{
cas_strong_explicit(&y, 0, 2, relaxed, relaxed);
}
}
|||
{
// Is it possible for x and y to read 2 and 1, or 1 and 2?
x.load(relaxed).readsvalue(2);
y.load(relaxed).readsvalue(1);
}
}}}
return 0;
}
Я не думаю, что инструмент достаточно сложен, чтобы оценить этот сценарий, хотя, похоже, он показывает, что это возможно. Вот почти эквивалентная установка Relacy:
#include "relacy/relacy_std.hpp"
struct rmw_experiment : rl::test_suite<rmw_experiment, 3>
{
rl::atomic<unsigned> x, y;
void before()
{
x($) = y($) = 0;
}
void thread(unsigned tid)
{
if (tid == 0)
{
unsigned exp1 = 0;
if (x($).compare_exchange_strong(exp1, 1, rl::mo_relaxed))
{
unsigned exp2 = 0;
y($).compare_exchange_strong(exp2, 1, rl::mo_relaxed);
}
}
else if (tid == 1)
{
unsigned exp1 = 0;
if (x($).compare_exchange_strong(exp1, 2, rl::mo_relaxed))
{
unsigned exp2 = 0;
y($).compare_exchange_strong(exp2, 2, rl::mo_relaxed);
}
}
else
{
while (!(x($).load(rl::mo_relaxed) && y($).load(rl::mo_relaxed)));
RL_ASSERT(x($) == y($));
}
}
};
int main()
{
rl::simulate<rmw_experiment>();
}
Утверждение никогда не нарушается, поэтому 1 и 2 (или наоборот) невозможны в соответствии с Relacy.