Равно ли наблюдаемое поведение программы, гарантированное seq_cst, изменению ее на операции RMW с acq_rel, которые запис ⇐ C++

[Anonymous]

Рассмотрим этот пример:

Код: Выделить всё

#include 
#include 

int main(){
std::atomic epoch = {0};
std::atomic value = {1};
std::thread t1([&](){
epoch.store(1,std::memory_order::seq_cst);  // #1
value.load(std::memory_order::seq_cst);  // #2
});

std::thread t2([&](){
value.exchange(2,std::memory_order::seq_cst); // #3
epoch.load(std::memory_order::seq_cst); // #4
});
}

В этом примере, если #2 читается как 1, то #4 должен читаться как #1, поскольку это гарантируется одним общим порядком #1 < #2 < #3 < #4. В других случаях #4 может либо читать начальное значение, либо #1, они соответствуют допустимому единому общему порядку #3 < #4 < #1 < #2 или #3 < #1 < #2 < #4 (или #3 < #1 < #4 < #2) соответственно.
Если изменить пример на следующий:

Код: Выделить всё

#include 
#include 

int main(){
std::atomic epoch = {0};
std::atomic value = {1};
std::thread t1([&](){
epoch.store(1,std::memory_order::relaxed);  // #1
value.fetch_add(0,std::memory_order::acq_rel);  // #2
});

std::thread t2([&](){
value.exchange(2,std::memory_order::acq_rel); // #3
epoch.load(std::memory_order::relaxed); // #4
});
}

В этом примере, если #2 читает 1, согласно [atomics.order] p10

Атомарные операции чтения-изменения-записи всегда должны считывать последнее значение (в порядке модификации), записанное перед записью, связанной с операцией чтения-изменения-записи.

Код: Выделить всё

#3

должен следовать за номером 2 в порядке изменения значения. Поскольку их порядок памяти — acq_rel, #2 должен happens-before #3, поэтому видимость #1 по #4 теперь гарантируется happens-before. Аналогично, в других случаях #4 может читаться либо как 0, либо как #1. IIUC, эти две программы функционально эквивалентны в наблюдаемом поведении.
Этот первый фрагмент кода упрощен из алгоритма EBR (т. е. восстановления на основе эпох). #3 эмулирует операцию обновления указателя. Основная идея заключается в том, что если #2 считывает старое значение указателя, оно должно предшествовать #3 в едином общем порядке, поэтому #1 также предшествует #4 в единственном общем порядке; следовательно, #4 должен видеть #1, чтобы проверить, является ли эпоха читателя текущей.
Если мы рассматриваем только правильность реализации основной идеи, могу ли я изменить порядок памяти seq_cst на acq_rel, изменив соответствующие операции на те, что во втором примере? IIUC, они должны иметь одинаковую корректность; просто видимость #1 гарантируется единым общим порядком в первом способе и гарантируется happens-before во втором способе.
Обновление:
Псевдо-реализация EBR для нескольких читателей и одного записывающего устройства выглядит следующим образом:

Код: Выделить всё

#include 
#include 
#include 

struct ThreadState {
std::atomic active{false};
std::atomic local_epoch{0};
};

class EBRManager {
std::atomic global_epoch{0};
ThreadState thread_states[8];

// Bag[0], Bag[1], Bag[2]
std::vector garbage_bags[3];

public:

void reader_enter(int tid) {
thread_states[tid].active.store(true, std::memory_order_seq_cst);
uint64_t g = global_epoch.load(std::memory_order_seq_cst);
thread_states[tid].local_epoch.store(g, std::memory_order_seq_cst);
}

void reader_exit(int tid) {
thread_states[tid].active.store(false, std::memory_order_seq_cst);
}

void retire(void* old_ptr) {
uint64_t g = global_epoch.load(std::memory_order_relaxed);
garbage_bags[g].push_back(old_ptr);
try_collect();
}

void try_collect() {
uint64_t curr_g = global_epoch.load(std::memory_order_seq_cst);

for (int i = 0; i < 8; ++i) {
if (thread_states[i].active.load(std::memory_order_seq_cst)) {
if (thread_states[i].local_epoch.load(std::memory_order_seq_cst) != curr_g) {
return;
}
}
}

uint64_t next_g = (curr_g + 1) % 3;

uint64_t safe_g = (next_g + 1) % 3;
clear_bag(safe_g);

global_epoch.store(next_g, std::memory_order_seq_cst);
}

void clear_bag(int index) {
for (void* ptr : garbage_bags[index]) {
free(ptr);
}
garbage_bags[index].clear();
}
};

struct Data {
int value;
};

std::atomic global_ptr{new Data{100}};
EBRManager ebr;

void writer_thread_update(int new_value) {
Data* newData = new Data{new_value};
Data* oldData = global_ptr.exchange(newData, std::memory_order_seq_cst);
if (oldData != nullptr) {
ebr.retire(oldData);
}
}

void reader_thread(int tid) {
ebr.reader_enter(tid);
Data* p = global_ptr.load(std::memory_order_seq_cst);
ebr.reader_exit(tid);
}

Как доказать:

Как показано на графике, нам не нужно заботиться о том, какое значение показывает эпоха №1; мы можем предположить, что значение равно C. Предполагая, что #2 считывает значение указателя Px, нам также не нужно заботиться о том, что перед этим делает записывающий элемент, поскольку значение указателя Px может быть потенциально возвращено только после его выгрузки. Итак, мы предполагаем, что средство записи выполняет операцию обмена, которая записывает new_pointer и заменяет Px, поскольку последовательность освобождения, что означает #2, должна синхронизироваться с таким #3; следовательно, #1 должен быть виден #4. Как показано на рисунке, эпоху можно продвинуть максимум один раз, при этом восстанавливается значение указателя, сохраненное в мусоре[G-1]; в любом случае Px был сохранен в мусоре[G], эпоха не может быть продвинута до тех пор, пока читатель не запишет false в active. Это доказательство применимо к любому читателю.