将EBR算法中seq_cst改为acq_rel的RMW操作，能否保证等价正确性？

使用seq_cst内存序的程序，其可观测行为是否等价于将对应操作改为写入相同值的acq_rel内存序RMW（读-改-写）操作？

示例1：seq_cst版本 #

#include <atomic>
#include <thread>

int main(){
  std::atomic<int> epoch = {0};
  std::atomic<int> 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，这由seq_cst的单一全局全序保证，有效全序为 #1 < #2 < #3 < #4。
• 其他情况下，#4可读取初始值0或#1写入的1，对应有效全序包括#3 < #4 < #1 < #2、#3 < #1 < #2 < #4或#3 < #1 < #4 < #2。

示例2：acq_rel RMW版本 #

将原seq_cst的load/store替换为acq_rel的RMW操作（如fetch_add(0)，仅读取不修改值），代码如下：

#include <atomic>
#include <thread>

int main(){
  std::atomic<int> epoch = {0};
  std::atomic<int> 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，根据C++标准[atomics.order]第10条：

Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

#3在value的修改顺序中必须排在#2之后。由于二者均为acq_rel内存序，#2 happens-before #3，因此#1对#4的可见性由happens-before关系保证。

• 其他情况下，#4同样可读取0或1。

二者的可观测行为在功能上完全等价。

EBR算法的核心逻辑适配 #

第一段代码简化自EBR（基于纪元的内存回收）算法：

• #3模拟指针更新操作，核心思路是：若读者的#2读取到旧指针值，则在seq_cst的单一全序中#2必须排在#3之前，因此读者的#1也必然排在写者的#4之前，写者的#4必须看到读者的#1写入的纪元值，以此确认读者的纪元是否为当前值。

若仅考虑核心逻辑的正确性，完全可以将原seq_cst操作替换为acq_rel的RMW操作：

• 原版本通过seq_cst的单一全局全序保证#1的可见性；
• 修改版本通过acq_rel带来的happens-before关系保证相同的可见性，二者正确性一致。

更新：多读者单写者场景下的EBR伪实现 #

#include <atomic>
#include <vector>
#include <iostream>

struct ThreadState {
    std::atomic<bool> active{false};
    std::atomic<uint64_t> local_epoch{0};
};

class EBRManager {
    std::atomic<uint64_t> global_epoch{0};
    ThreadState thread_states[8]; 
    
    // 三个垃圾回收袋：Bag[0], Bag[1], Bag[2]
    std::vector<void*> 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<Data*> 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（value.fetch_add(0, std::memory_order::acq_rel)）读取到指针值Px，则Px仅会在被写者换出后才可能被回收。

假设存在写者执行exchange操作，写入新指针并换出Px：

• 由于RMW操作的特性，所有读取到Px的读者的#2，在value的修改顺序中必然排在写者的#3之前；
• 结合acq_rel的内存序，读者的#2与写者的#3之间形成synchronizes-with关系，进而推导出读者的#1 happens-before 写者的#4，因此#1的纪元值对#4可见。

进一步延伸：
若所有读取Px的读者存储的纪元值等于G，写者随后回收garbage[G-1]中的指针时，纪元最多仅能推进一次；Px会被保存在garbage[G]中，直到所有读取过Px的读者将active设为false，纪元才能继续推进。此逻辑适用于任意读者。

内容的提问来源于stack exchange，提问作者xmh0511