Herb Sutter谈论C++无锁编程

摘要

在2014年的C++大会上，Herb Sutter做了C++无锁编程的演讲，在演讲中他解释了无锁编程的基本概念，并用三种算法展示了无锁技术。本文是他演讲重点的概要。

正文

在2014年的C++大会上，Herb Sutter做了C++无锁（译注：lock-free，意为不使用锁来保持代码的同步）编程的演讲，在演讲中他解释了无锁编程的基本概念，并用三种算法展示了无锁技术。本文是他演讲重点的概要。

Herb首先指出了无锁代码的优势：

• 通过减少阻塞和等待，来改进并发性和可扩展性。
• 消除条件竞争（race condition）、死锁、可组合性不足带来的潜在问题。

但是无锁编程不是万能药，因为无锁算法实现起来更复杂，它也有潜在问题，比如竞争（contention），这会极大地影响性能。从这一点出发，Herb引出了他的第一条强烈建议：

• 在使用无锁技术前，你必须先测试你的程序，确定它有性能或可扩展性问题。
• 实现无锁算法后，再次测试你的程序，确定结果得到了有效的改进。

基本概念

以下是考虑无锁算法的时候需要理解的一些基本概念：

• 一致性（Consistency）：一段关键代码可以把系统从一个稳定的状态转换到另一个稳定的状态。
• 隔离（Isolation）：两次转换永远不同时操作同一数据。
• 持续性（Durability）：在一次转换的结果出来之前，不会被另一次转换所打断。

为达到这些目的所用到的基本技术有：

• 把计算结果保存在私有区域中；
• 借助“比较与交换（compare/exchange）”指令，使用单个原子写操作（atomic write）把计算结果公布出去。

在C++ 11中，你可以使用atomic<T>来实现这种操作，这有两大优势：

• 你可以把每个读操作和写操作看作是原子的，不再需要锁。
• 另外，读操作和写操作保证不会被重排序。

关于atomic的一些要点如下：

• 对于占空间小的数据类型，atomic通常是通过平台特定的操作来实现的。
• atomic对象必须要初始化（否则会包含垃圾数据）。
• 两个原子操作可以保证各自是原子的，但是atomic对象的状态有可能来回发生变化。

例子：两次检查的加锁（double-checked locking）
Herb给的第一个例子是如果保证一个全局对象只被构造了一次。
核心思想是：用一个锁来保护原子写操作，但是让原子读操作处于无锁状态。这样只有在各个线程竞争初始化这个单例（singleton）的时候才可能发生阻塞。算法取这个名字的原因是，实例的指针共检查了两次，加锁前和加锁后：

atomic<Widget*> Widget::pInstance{ nullptr };
Widget* Widget::Instance() {
   if (pInstance == nullptr) {
      lock_guard<mutex> lock { mutW };
      if (pInstance == nullptr) {
         pInstance = new Widget();
      }
   }
}

例子：生产者——消费者
Herb描述的第二个例子是经典的生产者——消费者算法。他先描述了传统的使用锁的解决方案：

• 生产者获取共享队列的锁，把一些对象放进去；针对每个对象，都会触发一个条件变量，这样生产者就得到了通知。
• 另一方面，生产者也尝试获取队列的锁，得到锁以后，它检查队列中是否有对象可以消费；如果有，取走对象，并释放锁。

使用无锁技术对这个算法做第一种改进，通过atomic变量来访问单向链表。这样可以使生产者一次性放完它的东西，然后通过原子性地修改队列的头指针来通知消费者。消费者的实现不变。

然后，我们考虑完全无锁的实现。在这种情况下，算法的思想是，生产者要去填满一定数量的“槽（slot）”。当生产者有一个新任务要处理，它会去检查是否有空闲的槽，并把要处理的任务放进去。在下面的代码中，slot是一个atomic变量：

curr = 0;
// 第一阶段：生成任务
while (ThereAreMoreTasks()) {
   task = AllocateAndBuildNewTask();
   while (slot[curr] != null)
      curr = (curr+1)%K;
   slot[curr] = task;
   sem[curr].signal();
}
// 第二阶段: 把邮箱置为done状态
numNotified = 0;
while (numNotified < K) {
   while (slot[curr] != null)
      curr = (curr+1)%K;
   slot[curr] = done;
   sem[curr].signal();
   ++numNotified;
}

对于消费者来说，代码更简单：

myTask = null;
while (myTask != done) {
   while (myTask = slot[mySlot]) == null)
      sem[mySlot].wait();
   if (myTask != done) {
      slot[mySlot] = null;
      DoWork(myTask);
   }
}

消费者等待信号量，直到槽里面有任务为止。任务来了，消费者把它拿出来，并清空槽，然后开始处理任务。这就是把任务处理放到关键区（critical section）之外的思想。但是如果消费者处理得比生产者慢，那么在任务处理完之后再释放锁比较合理，这样，当消费者忙的时候，生产者就不会再去填充同一个槽，而是去找另外一个空闲的槽。这表明了，你的设计决策会对业务吞吐量/可扩展性（throughput/scalability）和负载平衡（load balancing）之间的取舍产生微妙的影响。

例子：单向链表：
单向链表可能是最简单的数据结构之一了，在这个例子中只支持四种操作：构造（construct）、销毁（destroy）、查找（find）、前插入（push_front）。
Herb提出的无锁实现使用了atomic<Node*> head{ nullptr };来访问链表头。唯一有可能导致并发问题的操作是push_front操作，它的单线程版本有可能是这样的：

template
void slist<T>::push_front(T t) {
   auto p = new Node;
   p->t = t;
   p->next = head;
   head = p;
}

这个代码有问题，因为它在设置新的head值的时候可能会引入竞争。使用compare_exchange来写head，我们可以修复这个问题，代码如下：

template
void slist<T>::push_front(T t) {
   auto p = new Node;
   p->t = t;
   p->next = head;
   while (!head.compare_exchange_weak(p->next, p))
      {}
}

这里，我们不停尝试交换head和p的值，直到成功为止。在无锁的代码中，使用compare_exchange_weak很常见。它通常用在循环内，在循环外则使用compare_exchange_strong。

而当我们要实现一个移除节点（pop）的操作时，更多的问题就来了。移除操作会删掉链表中的第一个节点，在这种情况下，导致复杂性的一个主要原因是，返回的对象指针有可能很快被另外一个线程释放掉。这个问题有个广为人知的名字叫ABA问题，Herb随后深入细节，讲述了它在特定的环境下是如何发生的。

C++ 11为这个问题给出了优雅的解决方案，不再使用原始的指针，而是用shared_ptr来取代。用伪代码表示的实现如下：

template
struct Node { T t; shared_ptr<Node> next; };
atomic<shared_ptr<Node>> head;
public:
   slist() =default;
   ~slist() =default;
   class reference { 
      shared_ptr<Node> p;
   public:
      reference(shared_ptr<Node> p_) : p{_p} {}
      T& operator*() { return p->t; }
      T* operator->() { return &p->t; }
   };
   auto find(T t) const {
      auto p = head.load();
      while (p && p->t != t)
         p = p->next;
      return reference{move(p)};
   void push_front(T t) {
      auto p = make_shared<Node>();
      p->t = t;
      p->next = head;
      while (head.compare_exchange_weak(p->next, p))
         {}
   }
   void pop_front() {
      auto p = head.load();
      while (p && !head.compare_exchange_weak(p, p->next))
         {}
   }
};

这里用到的技巧是，返回的指针被指定为一个shared_ptr，这样我们不需要再特别关注指针被意外删除的情况。

这种实现展示了一种很好的属性叫线性化，它可以使一组互相交错的操作看起来像是顺序执行的一样。

演讲的最后部分讨论了一个例子，这个例子展示了如何来衡量一个程序的行为，以及它可以从无锁的实现中获得什么样的好处。

查看英文原文：Lock-free Programming in C++ with Herb Sutter