Необходим ли `AcqRel` в атомарной операции чтения-изменения-записи, чтобы избежать гонки данных в однопользовательской о ⇐ C++

[Anonymous]

Рассмотрите этот фрагмент кода реализации незаблокированной очереди с несколькими производителями и одним потребителем в Rust

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

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

impl Queue {
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 {
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 = Box::from_raw(tail);
return Data(ret);
}

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

Эквивалентная реализация C++:

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

template
struct Node{
std::atomic next;
T value;
Node(T v):value(v),next(){}
};
template
struct Queue {
std::atomic head;
Node* tail;
Queue(){
auto h = new Node{};
head.store(h);
tail = h;
}
void push(T t){
auto node = new Node{};
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 next;
return ret;
}
if this->head == tail{
throw "empty";
}
}
}

Поскольку атомарная объектная модель Rust такая же, как и в C++, я буду ссылаться на стандарты C++ об атомарных операциях.
Сначала посмотрите # 2, поскольку [atomics.order] p10 говорит:

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

Эта операция чтения-изменения-записи гарантирует, что вызов push изменит self.head по порядку, и только один поток изменит следующее поле этого объекта, возвращаемого функцией swap.

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

#3

— это операция освобождения хранилища, а #4 — операция получения загрузки, следовательно, как только #4 прочитает указатель, записанный в #3, они синхронизируются, так что модификация, произошедшая в #1, произойдет до тех операций, которые читают/записывают объект после #4.
Если я правильно понимаю, то, что происходит до между #1 и часть после #4 устанавливаются синхронизацией #3 и #4. Операция чтения-изменения-записи в #2 просто гарантирует, что каждый поток, выполняющий push, имеет свой индивидуальный «pre», и они происходят в порядке модификации.
Итак, мне интересно, можно ли заменить Ordering::AcqRel в #2 на Relaxed?

Подробнее здесь: https://stackoverflow.com/questions/787 ... id-data-ra