无锁多生产者单消费者队列中原子读写改的AcqRel能否替换为Relaxed？

本文给出了Rust和C实现的无锁多生产者单消费者队列代码，由于Rust原子对象模型与C一致，基于C++标准分析现有代码的内存序逻辑：

• #2处的原子交换操作保证各push调用按序修改self.head，且每个线程能拿到独立的prev节点指针；
• #3的Release存储与#4的Acquire加载建立同步关系，确保#1处的节点初始化操作happens-before#4之后的pop操作。

现提出核心疑问：#2处的Ordering::AcqRel（对应C++的std::memory_order_acq_rel）能否替换为Ordering::Relaxed？

Rust 实现代码 #

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;

enum PopResult<T> {
    Data(T),
    Empty,
    Inconsistent,
}

struct Node<T> {
    next: AtomicPtr<Node<T>>,
    value: Option<T>,
}
impl<T> Node<T> {
    unsafe fn new(v: Option<T>) -> *mut Node<T> {
        Box::into_raw(box Node { next: AtomicPtr::new(ptr::null_mut()), value: v })
    }
}
pub struct Queue<T> {
    head: AtomicPtr<Node<T>>,
    tail: std::cell::UnsafeCell<*mut Node<T>>,
}

impl<T> Queue<T> {
    pub fn push(&self, t: T) {
        unsafe {
            let n = Node::new(Some(t)); // #1
            let prev = self.head.swap(n, Ordering::AcqRel);  // #2
            (*prev).next.store(n, Ordering::Release);  // #3
        }
    }
    pub fn pop(&self) -> PopResult<T> {
        unsafe {
            let tail = *self.tail.get();
            let next = (*tail).next.load(Ordering::Acquire);  // #4

            if !next.is_null() {
                *self.tail.get() = next;
                assert!((*tail).value.is_none());
                assert!((*next).value.is_some());
                let ret = (*next).value.take().unwrap();
                let _: Box<Node<T>> = Box::from_raw(tail);
                return PopResult::Data(ret);
            }

            if self.head.load(Ordering::Acquire) == tail { PopResult::Empty } else { PopResult::Inconsistent }
        }
    }
}

等效C++实现代码 #

#include <atomic>

template<class T>
struct Node{
    std::atomic<Node<T>*> next;
    T value;
    Node() : value(), next(nullptr) {}
    Node(T v):value(v), next(nullptr){}
};
template<class T>
struct Queue {
    std::atomic<Node<T>*> head;
    Node<T>* tail;
    Queue(){
      auto h = new Node<T>{};
      head.store(h);
      tail = h;
    }
    void push(T t){
       auto node = new Node<T>(t);
       auto pre = this->head.exchange(node, std::memory_order_acq_rel);
       pre->next.store(node, std::memory_order_release);
    }
    T pop(){
       auto tail = this->tail;
       auto next = tail->next.load(std::memory_order_acquire);
       if(next){
          this->tail = next;
          auto ret = next->value;
          delete tail;
          return ret;
       }
       if(this->head.load(std::memory_order_acquire) == tail){
          throw "empty";
       }
       throw "inconsistent";
    }
};

解答：不能替换为Relaxed #

核心原因分析： #

1. 跨线程对象可见性的保证
   每个push线程通过swap获取前一个节点的prev指针后，需要确保能看到该节点的完整初始化状态。AcqRel的Acquire语义会强制当前线程刷新缓存，确保读取到的prev指针对应的节点的所有已完成操作（包括前一个push线程的节点初始化、指针关联）对当前线程可见；而Relaxed读取不会触发缓存同步，可能导致当前线程访问prev节点时看到未初始化或部分初始化的状态，引发未定义行为。

2. 维护必要的happens-before关系
   根据C++/Rust内存模型：

   • 前一个push线程的节点初始化（#1）sequenced-before其swap的Release写操作；
   • 当前push线程的swap的Acquire读操作sequenced-before其后续的节点关联操作（#3）；
   • Release写与Acquire读的同步关系，直接确保前一个线程的#1 happens-before当前线程的#3。
     如果换成Relaxed，这种跨线程的happens-before关系会断裂，无法保证节点初始化操作对后续线程可见，进而引发数据竞争。

3. 硬件层面的乱序执行约束
   AcqRel的语义会阻止CPU的乱序执行，确保swap操作完成后才执行后续的prev->next存储操作。虽然编译器因#3依赖于#2的返回值prev不会重排，但硬件层面的乱序执行可能导致逻辑顺序错误，而Relaxed无法约束这种硬件行为。

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