演讲的主题是“C++编程中免等待（Wait-free）算法介绍”，由CMU的教师Daniel Anderson主讲。本文对演讲进行记录与总结，并拓展相关知识。
关键词 C++ 算法 高并发 无锁算法

---

1. 并发与进阶算法分类

演讲首先回顾了并发编程和无锁（Lock-free）编程的基础知识，并引入了用于衡量并发算法性能保证的词汇进度保证（Progress Guarantees）：

• 阻塞 (Blocking/Locking)： 无法保证进度，可能因为线程持有锁后被调度出去（“去吃午饭”）而导致其他线程无限等待。
• 无锁 (Lock-Free)： 保证系统范围内至少有一个线程能取得进展。这意味着系统整体吞吐量得到保证，但单个操作可能会“饿死”（Starve），即可能需要任意长的时间才能完成。
• 免等待 (Wait-Free)： 进度的“黄金标准”。它保证所有线程都能取得进展。每个操作都会在有界步骤内完成，从理论上保证了最坏情况下的延迟。

解读：算法区别

• Blocking（阻塞）
  核心思想：当线程无法获取共享资源时，它会被挂起（阻塞），直到资源被释放。
  工作方式：
  通常使用锁（如 synchronized、ReentrantLock）来实现。
  线程尝试获取锁，如果锁已被其他线程占用，则当前线程会被放入等待队列，进入阻塞状态。
• Lock-Free（无锁）
  核心思想：线程不会被阻塞，而是通过循环重试（自旋）来尝试获取资源。
  工作方式：
  通常使用原子操作（如 CAS，Compare-and-Swap）来实现。
  线程在操作共享资源时，不会阻塞，而是不断重试直到成功。
  即使多个线程同时操作，也能保证只有一个线程能成功修改资源，其他线程会重试。
• Wait-Free（免等待）
  核心思想：每个线程都能在有限步内完成操作，无需等待其他线程。
  工作方式：
  是无锁的一种更强形式。
  线程在执行操作时，不需要等待其他线程释放资源，也不需要重试。
  每个线程的操作都能在有限时间内完成，不依赖其他线程的执行。
  现在可能难以理解免等待算法的实现思路，但是我们稍后就会谈到这个。

2. 激励性问题与无锁设计

演讲以实现一个“粘性计数器”（Sticky Counter）数据结构为例。该计数器允许递增和递减，但一旦达到零，就无法再递增（即“粘”在零）。这是一个实际应用中非虚构的例子，例如C++标准库在 std::weak_pointer::lock 中就需要这种机制。

解读：粘性计数器的实际应用
内核中大量使用引用计数来管理对象（如内存页、文件描述符、设备结构体等）的生命周期。Sticky counter 非常适合这种场景，以确保对象被安全地销毁。

• 工作流程举例：
  假设内核创建了一个代表某个硬件设备的结构体 struct device *dev。
• 初始化：
  对象创建时，其引用计数器（一个 sticky counter）被初始化为 1。

dev->ref_count = 1;

• 获取引用（递增）：
  当另一个内核组件（如驱动程序、文件系统）需要使用这个 dev 对象时，它会调用一个函数来增加引用计数。此时 ref_count 变为 2。这个操作确保了只要还有组件在使用该对象，它就不会被销毁。

sticky_counter_inc(&dev->ref_count);

• 释放引用（递减）：
  当一个组件使用完 dev 对象后，它会调用一个函数来减少引用计数。此时 ref_count 变回 1。

sticky_counter_dec(&dev->ref_count);

• 最终释放（销毁）：
  当最后一个使用该对象的组件调用 sticky_counter_dec 时，计数器降到 0。此时 ref_count 变为 0。粘性效应触发：计数器现在固定在 0。如果此时有一个错误的或迟来的组件试图再次获取对 dev 对象的引用，并调用 sticky_counter_inc：

sticky_counter_inc(&dev->ref_count);

• 由于计数器已经是 0，这个递增操作会失败。函数可能返回 false 或 -1，告知调用者无法再获取引用。
  这就是关键所在：它防止了对一个已经被（或即将被）销毁的对象进行操作，从而避免了使用 - after-free 漏洞，这是内核中最常见且最严重的安全漏洞之一。

锁实现的问题： 使用互斥锁（mutex）虽然解决了线程安全问题，但引入了阻塞问题，导致性能不佳。

无锁设计方法（Compare-Exchange Loop）：
要实现无锁计数器，需要使用原子类型（std::atomic）。无锁设计的核心是比较交换循环（Compare-Exchange Loop，或称CAS Loop）。

1. 读取当前状态。
2. 计算出想要的新状态。
3. 使用原子操作 compare_exchange 提交更改，仅当旧状态仍是预期的值时才成功。
4. 如果失败，则重新尝试（形成一个潜在的无界循环）。

CAS Loop 算法通常是无锁的，因为一个线程的失败意味着另一个线程的成功（系统整体仍在进展）。但它不是免等待的，因为理论上一个线程可能会永远被其他线程“抢占”（clobbered forever），导致操作所需时间是任意长的。

解读：完整代码注释

class StickyCounter {
private:
    // 使用 atomic<int> 保证线程安全
    std::atomic<int> count_;

public:
    // 构造函数，初始化计数器
    explicit StickyCounter(int initial_value) : count_(initial_value) {
    }

    // 递减操作
    // 返回递减前的值
    int decrement() {
        // fetch_sub 是原子操作，返回操作前的值
        int old_value = count_.fetch_sub(1);
        std::cout << "Decrementing from " << old_value << " to " << (old_value - 1) << std::endl;
        return old_value;
    }

    // 递增操作 (核心的“粘性”逻辑在这里实现)
    // 返回是否成功递增
    bool increment() {
        int current = count_.load(); // 读取当前值

        // CAS 循环，直到成功或发现计数器已为0
        while (current > 0) {
            int new_val = current + 1;

            // 尝试将 count_ 从 current 更新为 new_val
            // 这是一个原子操作
            // 如果 count_ 的当前值确实是 current，则更新为 new_val 并返回 true
            // 否则，将 current 更新为 count_ 的最新值，并返回 false
            if (count_.compare_exchange_weak(current, new_val)) {
                std::cout << "Incrementing from " << (new_val - 1) << " to " << new_val << " - SUCCESS" << std::endl;
                return true; // 成功递增
            }
            
            // 如果 compare_exchange_weak 返回 false，循环会继续
            // 此时 current 已经被更新为了 count_ 的最新值
            // 我们会再次检查 current > 0，如果是，则重试
        }

        // 如果循环退出，说明 current <= 0
        std::cout << "Cannot increment. Counter is already at 0 - FAILED" << std::endl;
        return false; // 递增失败
    }

    // 获取当前计数值
    int get() const {
        return count_.load();
    }
};

3. 免等待算法设计：协作与帮助

为了实现免等待算法，必须消除潜在的无界CAS循环。虽然仍需使用原子读-修改-写（RMW）原语，如 compare_exchange、fetch_add、fetch_sub 和 atomic_exchange，但关键在于改变线程间的竞争关系。

“帮助”（Helping）机制：
免等待设计的核心思想是协作而非竞争。当一个线程发现数据结构处于另一个操作正在进行中的状态时，它不会抢占或阻塞，而是会帮助该操作完成，然后再尝试执行自己的操作。

形象比喻： 如果说无锁设计中的CAS循环是一群人抢着通过一扇门，只有一个人能成功，而其他人必须重试；那么免等待设计中的“帮助”机制，就像是大家互相配合，确保即使有人绊倒了，其他人也会先帮忙扶起来，再一起通过，保证每个人都能在有限时间内顺利通过大门。

免等待粘性计数器的实现细节：
为了实现帮助机制，线程需要有一种方式来检测和沟通正在进行的操作。由于核心难点在于线程如何同步地确定计数器是否为零，演讲提出了**“窃取位”（stealing bits）**的关键想法：

1. 从64位计数器中窃取两位作为标志（Flags）。

2. “Is Zero Flag”： 顶部位用于同步表明计数器为零，一旦设置，其他线程就必须将其视为零，即使实际的低位数字大于零。

3. 线性化（Linearizability）： 在没有读取操作的简化版中，即使内存中的位数显示为零，也可以声称递减操作是在递增操作之后发生的，因为在操作重叠的情况下，外部观察者无法证明顺序是错误的。
   
   解读：什么是并行语义下的线性化？
   在并行算法中，操作线性化是指：
   对于一个并发数据结构上执行的所有操作（来自不同线程），我们可以找到一个全局的、线性的操作序列，满足以下两个条件：

   • 正确性 (Correctness)：这个线性序列必须是 “行为正确” 的。也就是说，如果这些操作真的按照这个序列在一个单线程上执行，那么数据结构产生的最终状态和所有操作的返回值，必须与它们在并发执行时的结果完全一致。
   • 实时性 (Real-Time Order)：这个线性序列必须尊重每个操作的实际发生时间。对于任意两个操作 A 和 B，如果操作 A 在物理时间上完全结束之后，操作 B 才开始，那么在这个线性序列中，A 必须排在 B 的前面。
   • 

4. 添加读取操作的挑战： 如果允许读取操作，它可能会观察到计数器为零，但随后看到计数器又被“复活”（resurrected）到一，破坏了线性化。

5. 最终方案（加入 Helping 和 Help Flag）： 当一个线程（例如读取操作）检测到计数器为零时，它会帮助正在进行的递减操作设置零标志。为了解决谁来“认领”将计数器设置为零的责任（这在引用计数中至关重要，因为认领者负责删除对象），引入了第二个标志位：“Help Flag”。帮助者设置此标志，然后尝试进行递减操作的线程会通过原子交换（Exchange）操作来清除该 Help Flag，从而认领自己是将计数器置为零的线程。
   

4. 性能分析与结论

演讲强调，不应盲目猜测性能，而应先进行理论假设，然后通过基准测试（Benchmark）验证。

基准测试结果表明：

• 在读操作居多的工作负载下（高争用），免等待计数器通常展现出更好的延迟性能。
• 在写操作居多的工作负载下（低争用），无锁算法（基于CAS Loop）在足够高的线程数时可能会胜出。

结论：
最优的算法取决于具体的工作负载（读写比例、线程或核心数量）。无锁算法如果CAS循环不发生，速度会很快。

总结：

1. 通过进度保证（Progress Guarantees）对算法进行分类（Lock-Free vs. Wait-Free）。
2. 免等待算法设计的关键技巧是协作（Helping）。
3. 永远不要猜测性能（Don’t just guess and ship it），要先假设，后测试。