面试题：Rust原子操作在无锁栈中的基础应用

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

struct Node<T> {
    value: T,
    next: *mut Node<T>,
}

struct LockFreeStack<T> {
    head: AtomicPtr<Node<T>>,
}

impl<T> LockFreeStack<T> {
    pub fn new() -> Self {
        LockFreeStack {
            head: AtomicPtr::new(ptr::null_mut()),
        }
    }

    pub fn push(&self, value: T) {
        let new_node = Box::into_raw(Box::new(Node {
            value,
            next: self.head.load(Ordering::Relaxed),
        }));

        while!self.head.compare_and_swap(ptr::null_mut(), new_node, Ordering::SeqCst).is_null() {
            new_node = Box::into_raw(Box::new(Node {
                value: value.clone(),
                next: self.head.load(Ordering::Relaxed),
            }));
        }
    }

    pub fn pop(&self) -> Option<T> {
        loop {
            let old_head = self.head.load(Ordering::Relaxed);
            if old_head.is_null() {
                return None;
            }

            let new_head = unsafe { (*old_head).next };
            if self.head.compare_and_swap(old_head, new_head, Ordering::SeqCst) == old_head {
                return Some(unsafe { Box::from_raw(old_head).value });
            }
        }
    }
}

原子操作确保该栈在多线程环境下的正确性主要体现在以下方面：

compare_and_swap 操作：
- 在 push 方法中，使用 compare_and_swap 操作来更新栈顶指针。只有当栈顶指针的值等于预期值（最初为 null_mut 或者上次循环中读取的值）时，才会将新节点的指针设置为栈顶指针。如果其他线程在这期间修改了栈顶指针，compare_and_swap 操作会失败，当前线程会重新构建新节点并再次尝试，保证新节点能够正确入栈。
- 在 pop 方法中，同样使用 compare_and_swap 操作来更新栈顶指针。只有当栈顶指针的值等于预期值（即当前读取的栈顶节点指针）时，才会将栈顶指针更新为下一个节点的指针，同时返回栈顶节点的值。如果其他线程在这期间修改了栈顶指针，compare_and_swap 操作会失败，当前线程会重新读取栈顶指针并再次尝试，保证出栈操作的正确性。
Ordering::SeqCst：使用 SeqCst 顺序保证了所有线程对栈操作的全局顺序一致性。这确保了不同线程对栈的修改和读取操作能够按照合理的顺序发生，避免了数据竞争和不一致的情况。

星途面试题库

面试题：Rust原子操作在无锁栈中的基础应用

知识考点

面试题答案