4.2 ARM/Power 弱序模型

ARM 和 PowerPC 采用 Weak Memory Model，允许几乎任意形式的重排：

• Load-Load、Load-Store、Store-Load、Store-Store 均可被重排
• 需要显式的屏障指令（DMB、DSB、ISB 在 ARM 上；sync、lwsync、isync 在 Power 上）
• C++ 的 memory_order 语义由编译器自动映射为对应屏障指令

ARM64 提供了细粒度的屏障指令：

DMB SY    // 全系统数据内存屏障
DMB ST    // Store-Store 屏障（仅保证写入顺序）
DMB LD    // Load-Load 屏障
ISB       // 指令同步屏障（清空流水线）

4.3 跨架构挑战

在 x86 上"碰巧正确"的代码很容易在 ARM 上崩溃。永远不要依赖具体架构的内存序行为，应始终使用标准库的 memory_order 显式指定语义。这也是使用 C++11/Rust 标准库 lock-free 编程而非手写内联汇编的根本原因。

五、无锁数据结构设计实战

5.1 Michael-Scott 无锁队列

Michael-Scott Queue 是最经典的无锁 FIFO 队列实现，基于 CAS（Compare-And-Swap）原语，使用带标记指针（Tagged Pointer）解决 ABA 问题：

template<typename T>
class LockFreeQueue {
private:
    struct Node {
        T data;
        atomic<Node*> next;
        Node(T val) : data(val), next(nullptr) {}
    };
    
    struct TaggedPtr {
        Node* ptr;
        uint64_t tag;
    };
    
    alignas(128) atomic<TaggedPtr> head_;
    alignas(128) atomic<TaggedPtr> tail_;

public:
    LockFreeQueue() {
        Node* dummy = new Node(T{});
        TaggedPtr init{dummy, 0};
        head_.store(init, memory_order_relaxed);
        tail_.store(init, memory_order_relaxed);
    }
    
    void enqueue(T value) {
        Node* node = new Node(value);
        TaggedPtr cur_tail, cur_tail_next;
        
        while (true) {
            cur_tail = tail_.load(memory_order_acquire);
            cur_tail_next = cur_tail.ptr->next.load(memory_order_acquire);
            
            if (cur_tail != tail_.load(memory_order_acquire)) continue;
            
            if (cur_tail_next.ptr == nullptr) {
                // 尝试链接新节点
                TaggedPtr new_next{node, cur_tail_next.tag + 1};
                if (cur_tail.ptr->next.compare_exchange_weak(cur_tail_next, new_next,
                        memory_order_release, memory_order_relaxed)) {
                    break;
                }
            } else {
                // 帮助推进 tail
                TaggedPtr new_tail{cur_tail_next.ptr, cur_tail.tag + 1};
                tail_.compare_exchange_weak(cur_tail, new_tail,
                    memory_order_release, memory_order_relaxed);
            }
        }
        // 尝试推进尾指针
        TaggedPtr new_tail{node, cur_tail.tag + 1};
        tail_.compare_exchange_weak(cur_tail, new_tail,
            memory_order_release, memory_order_relaxed);
    }
    
    bool dequeue(T& result) {
        TaggedPtr cur_head, cur_tail, cur_head_next;
        
        while (true) {
            cur_head = head_.load(memory_order_acquire);
            cur_tail = tail_.load(memory_order_acquire);
            cur_head_next = cur_head.ptr->next.load(memory_order_acquire);
            
            if (cur_head != head_.load(memory_order_acquire)) continue;
            
            if (cur_head.ptr == cur_tail.ptr) {
                if (cur_head_next.ptr == nullptr) return false;
                // 帮助推进 tail
                TaggedPtr new_tail{cur_head_next.ptr, cur_tail.tag + 1};
                tail_.compare_exchange_weak(cur_tail, new_tail,
                    memory_order_release, memory_order_relaxed);
            } else {
                result = cur_head_next.ptr->data;
                TaggedPtr new_head{cur_head_next.ptr, cur_head.tag + 1};
                if (head_.compare_exchange_weak(cur_head, new_head,
                        memory_order_release, memory_order_relaxed)) {
                    break;
                }
            }
        }
        delete cur_head.ptr;  // 注意：实际生产环境需要 Hazard Pointer
        return true;
    }
};

关键点分析：

• Tagged Pointer（标签指针）：使用 64 位中的高位作为计数器，每次 CAS 递增，解决 ABA 问题（在 64 位系统上 ABA 概率极低但仍需防护）
• CAS Lock-Free 性质：compare_exchange_weak 在多个线程竞争时可能失败，但至少有一个线程会成功，保证整体进度
• Acquire-Release 配对：enqueue 中的 release 保证 data 写入对 dequeue 的 acquire 可见
• 帮助推进（Help-along）：多个线程可能在推进 tail，但不影响正确性

5.2 ABA 问题与解决方案

ABA 问题是无锁编程的标志性难题。考虑以下场景：

1. 线程 A 读取节点 X 的指针，准备 CAS head 从 X 到 Y
2. 线程 B 也在操作队列：deque 出 X，deque 出 Y，将 X 重新 enque
3. 此时 head 又变回了 X，但 X 后面的链表已完全不同
4. 线程 A 的 CAS 成功，但实际状态已错误

解决方案：

• Tagged Pointer：每次修改递增计数器（如上例所示），是 64 位系统最实用的方案
• Hazard Pointer：延迟内存回收，确保正在被其他线程引用的节点不被释放
• Epoch-Based Reclamation (EBR)：基于时代的批量回收，性能更好但有读写偏斜（Read-Biased）限制
• RCU (Read-Copy-Update)：读多写少场景的王者，Linux 内核广泛用于路由表、文件描述符表等

5.3 Hazard Pointer 实现内存安全

Hazard Pointer 是一种精确的内存回收方案——每个线程声明自己正在访问的指针，其他线程在释放内存前检查这些声明。以下是一个简化实现：

thread_local vector<void*> my_hazards;

template<typename T>
class HPRecord {
    atomic<T*> pointer_;
    HPRecord* next_;
    static atomic<HPRecord*> head_;
    
public:
    static void protect(void* ptr, HPRecord& hp) {
        hp.pointer_.store(static_cast<T*>(ptr), memory_order_release);
        // Store-Load fence 确保 pointer_ 写入在后续加载前可见
        atomic_thread_fence(memory_order_seq_cst);
    }
    
    static bool is_hazardous(void* ptr) {
        HPRecord* rec = head_.load(memory_order_acquire);
        while (rec) {
            if (rec->pointer_.load(memory_order_acquire) == ptr)
                return true;
            rec = rec->next_.load(memory_order_acquire);
        }
        return false;
    }
    
    static void retire(T* ptr) {
        // 清理并尝试回收
        if (!is_hazardous(ptr)) {
            delete ptr;
        }
    }
};

Hazard Pointer 的核心思想可以用一句话概括：让每个线程为自己正在读取的节点上锁，阻止其他人删除它。每个线程维护一个 Hazard Pointer 列表（通常 2-3 个），在访问共享节点时先写入自己的 HP，读完后清除。

5.4 无锁栈（Lock-Free Stack）

无锁栈比队列简单得多，因为只操作一端。但经典的 Treiber Stack 存在 ABA 问题，且退化严重：

template<typename T>
class LockFreeStack {
    struct Node {
        T data;
        Node* next;
        Node(T val) : data(val), next(nullptr) {}
    };
    
    alignas(128) atomic<Node*> head_{nullptr};

public:
    void push(T value) {
        Node* node = new Node(value);
        node->next = head_.load(memory_order_relaxed);
        while (!head_.compare_exchange_weak(node->next, node,
                memory_order_release, memory_order_relaxed)) {
            // CAS 失败说明 head_ 已被其他线程更新，node->next 已被自动更新
            // 重试即可
        }
    }
    
    bool pop(T& result) {
        Node* top = head_.load(memory_order_acquire);
        while (top != nullptr) {
            if (head_.compare_exchange_weak(top, top->next,
                    memory_order_acquire, memory_order_relaxed)) {
                result = top->data;
                // 实际生产需要 Hazard Pointer / EBR 延迟回收
                delete top;
                return true;
            }
        }
        return false;
    }
};

六、性能分析与最佳实践

6.1 无锁 vs 有锁性能对比

无锁数据结构并非总是比有锁版本快。实际性能取决于多种因素：

• 竞争强度：低竞争时，自旋锁（Spinlock）和轻量级互斥锁（如 pthreads mutex）可能更快，因为无锁的 CAS 也有原子指令开销
• NUMA 拓扑：无锁结构的节点分散在多个 NUMA 节点上可能导致跨节点内存访问延迟
• 内存分配：无锁结构通常无法预分配节点，每个入队/入栈操作都需要动态分配内存（可用对象池缓解）
• ABA 防护开销：Tagged Pointer 操作、Hazard Pointer 扫描都有额外开销

经验法则：当并发竞争非常激烈（如每秒百万次操作）且锁争用严重时，无锁方案才显现优势。对于普通应用，一个设计良好的无竞争快速锁（如 Folly 的 MicroSpinLock）已经足够。

6.2 常见陷阱与调试

无锁编程的调试极其困难，常见的陷阱包括：

• 忘记释放语义：写入线程使用 relaxed 而非 release，消费线程可能看不到数据
• Hazard Point 遗漏：每个读取共享指针的地方都必须先保护
• 顺序一致性的隐形代价：滥用 seq_cst 会拖垮 ARM 架构性能，且不影响正确性
• 内存回收时机不当：过早释放导致 use-after-free，过晚释放导致内存泄漏

推荐使用 ThreadSanitizer (TSAN) 检测数据竞争：

g++ -fsanitize=thread -g -O1 program.cpp
clang++ -fsanitize=thread -g -O1 program.cpp

注意：TSAN 目前不支持真正的无锁算法，因为它的 happens-before 模型无法理解 Acquire-Release 语义。对于无锁代码，应使用 CDSChecker 或 Nidhugg 等 C++11 内存模型感知模型检查工具。

6.3 何时选择无锁编程

根据实际经验，无锁编程最适合以下场景：

• 实时系统（RT kernel）中不能使用可能阻塞的锁
• 信号处理 / 中断上下文中需要原子操作
• 超高性能的并发数据结构（MPSC Queue、SPSC Ring Buffer）
• 操作系统内核中的核心路径（Linux RCU、BPF Map）

对于普通业务系统，优先考虑 Thread Pool、Actor 模型、Channel 通信等更高抽象层次的并发方案。如果确实需要共享可变状态，从无锁队列开始是一个不错的切入点。

七、Linux 内核中的无锁技术

7.1 RCU (Read-Copy-Update)

RCU 是 Linux 内核最伟大的无锁发明之一，它实现了近乎零开销的并发读。其核心思想是：读操作完全无锁（不需要原子指令），写入时创建副本、替换旧指针、延后释放。

典型应用场景：

• 路由表、ARP 缓存查找
• 文件描述符表（task_struct->files）的并发访问
• 模块热卸载时的资源保护
• BPF Map 的 RCU 保护读取

RCU 的代价在于写入侧（宽限期等待延迟释放）和内存开销（读者存在时旧数据无法释放）。

7.2 内核内存屏障

Linux 内核提供丰富的内存屏障原语：

• barrier()：编译器屏障，阻止编译器重排
• mb() / rmb() / wmb()：全屏障 / 读屏障 / 写屏障（x86 上 wmb() 编译为空操作）
• smp_mb() / smp_rmb() / smp_wmb()：SMP 屏障（UP 时退化为编译器屏障）
• smp_load_acquire() / smp_store_release()：C++ 风格的 Acquire-Release 语义

八、总结

内存屏障和无锁编程是系统编程皇冠上的明珠。它们让我们在极致性能与正确性之间找到了平衡点。回顾本文的核心要点：

• 从 CPU 缓存一致性（MESI）到内存模型（C++11 memory_order），层层递进的硬件和语言抽象让我们能精确控制指令顺序
• Acquire-Release 模型是无锁编程的"最小可行"内存序，在绝大多数场景足够安全且性能最优
• Tagged Pointer、Hazard Pointer、Epoch-Based Reclamation 是解决 ABA 问题和内存回收的三驾马车
• 无锁不是万能药——它适合极高并发、实时内核路径和信号处理等场景；对于普通应用，Actor 模型或 Channel 才是更好的选择
• 跨平台正确性不能依赖测试——必须使用 C++11/Rust 标准库的 memory_order 显式指定语义

无锁编程的学习曲线陡峭，但掌握它会让你对计算机系统的理解提升到一个全新的高度。每一条内存屏障指令都是程序员与 CPU/编译器之间的契约，理解这些契约，才能写出真正可靠的高性能并发代码。