C++从2006到2020 - 4.1 C++11: 并发

C++11必须支持并发，不是说C++以前不支持并发，而是没有标准化。以前的支持方式都是非常low level的，跟具体硬件和操作系统相关。这样会导致代码的可读性和可移植性都非常差。

C++11对于并发的支持是由concurrency group的专家组完成，负责人是Hans-J Boehm（现在Google）。它分为3个主题：

4.1.1 内存模型
4.1.2 线程和锁
4.1.3 Futures

值得一提的是，并行算法、网络、协程（coroutines）是由其他组来完成的，而且没有打算进入C++11。

4.1.1 内存模型（Memory Model）

当计算机硬件已经支持多核、多级缓存、乱序执行、指令重组等功能的时候，我们必须精确定义内存访问的规则。IBM的Paul Mckenney对这个主题非常积极，剑桥大学的Mark Batty把Paul等人的提案进行了形式化描述。内存模型是C++11非常关键的一部分。

本来C11也会使用C++11的内存模型，但C标准委员会在最后引入了一些不兼容的语法，这对C和C++的用户以及编译器实现者来说都非常痛苦。

提出内存模型的主要动机来自于Linux和Windows内核。现在它们已经用上了C++11的内存模型了。因为内存模型对大多数程序员来说其实并不可见，所以相关的文章也比较少。如果用一句话总结，那就是，有了内存模型，代码的运行才是可预期的。

一开始，大多数委员会成员都低估了这个问题。我们知道Java有一个很好的内存模型，希望能直接采用这个模型，但Intel和IBM的代表对此投了反对票，因为他们指出如果C++采用和Java一样的内存模型会拖慢Java虚拟机的运行速度（至少2倍）。最终，为了保持Java的性能，C++采用了一个非常复杂的内存模型，很讽刺的是，后来人们指责C++的时候，其中一条就包括内存模型比Java复杂。

基本上，C++11内存模型是基于先发（happens-before）关系，并且同时支持序列一致性（sequential consistent）和宽松（relaxed）内存模型。在此之上（这句非常关键），C++11提供了原子类型（atomic types）和无锁（lock-free）编程。具体细节可以参加C++ concurrency in action这本书。

毫无疑问，内存模型的讨论非常激烈，因为它的终稿对硬件厂商和编译器实现者非常关键。其中最艰难的一个决定是同时接受Intel的x86原语（原子类型操作）和IBM的PowerPC原语（fences、内存屏障）。按常理，只需要支持一种。但最终Paul劝服了我，因为IBM的复杂算法里有相当多的code使用fences去适配Intel的指令模型。最终，我们决定两者都支持，也就是现在C++11所采用的内存模型。后来，我和委员会其他成员都对这个决定非常满意，因为当我们把内存屏障和原子操作结合使用的时候，可以实现出比只用其中之一更优的问题解决方案。

再之后，我们又支持了基于数据依赖的一致性（carries_dependency）。

C++11引入原子类型（atomic types），如下所示，简单的操作可以是原子的：

atomic<int> x;
void increment()
{
  x++;  // not x = x + 1
}

很显然，原子类型在很多地方都非常有用。又比如，原子类型可以使双重检查锁优化（double-checked locking optimizatio）更简单。

mutex mutex_x;
atomic<bool> init_x;  // initially false
int x;

if (!init_x) {
  lock_guard<mutex> lck(mutex_x);
  if (!init_x) x = 42;
  init_x = true;
}  // implicitly release mutex_x here (RAII)

// ... use x ...

双重检查锁的关键是使用相对轻量的atomic来保护代价更高的互斥锁。

这里的lock_guard是一个RAII类型数据，目的可以确保它管控的互斥锁能及时释放。

Hans-J Boehm对原子类型的评价是“令人惊讶的流行”，但我其实一点都不惊讶。虽然在并发领域不如Hans专业，我更多的是欣赏其简洁性。C++11也引入了无锁编程，比如compare and swap的实现：

template<typename T>
class stack {
  std::atomic<node<T>*> head;
public:
  void push(const T& data)
  {
     node<T>* new_node = new node<T>(data);
     new_node->next = head.load(std::memory_order_relaxed);
     while (!head.compare_exchange_weak(new_node->next, new_node,
            std::memory_order_release, std::memory_order_relaxed));
    }
    // ...
};

即使用C++11，我依然觉得无锁编程只有专家级别的程序员才能掌握。

4.1.2 线程和锁

在内存模型之上，C++11提供了基于线程和锁的并发模型。我觉得线程和锁级别的并发模型对普通应用程序来说是最差的并发模型，但对于C++这样的语言来说却是必不可少的。不论C++支持多少其他特性，它始终是一门系统编程语言，有能力直接跟操作系统进行交互，会被系统内核和设备驱动程序使用。因此，它必须提供系统能支持的最低级别的并发模型。在此之上，我们才能构建一些更适合普通应用程序的并发模型。就个人喜好而言，我更喜欢基于消息传递（message-based）的系统，因为它能完全消除数据争用（data race），而数据争用是最易引发并发bug的根源。

C++支持的线程和锁级别的编程实际上是POSIX和Windows系统提供的并发模型的变体，不过多了一个类型安全。这在《C++编程语言》和《C++ concurrency in action》里有讲。

线程 - 系统线程的执行，支持join() 和 detach()方法
互斥锁 - 系统互斥锁，提供lock()和unlock()方法，以及RAII方式的锁释放
条件变量 - 系统条件变量，可在不同线程之间交流事件
thread_local - thread-local 存储

与C语言的并发模型相比，类型安全使代码更简单更简洁。比如，再也没有void**和宏。看下面的例子，在别的线程里执行一个函数并返回结果：

class F {    // traditional function objects
public:
  F(const vector<double>& vv, double* p) : v{vv}, res(p) {}
  void operator()();       // place result in *res

private:
  const vector<double>& v;  // source of input
  double *res;              // target of output

double f(const vector<double>& v); // traditional function
void g(const vector<double>& v, double* res); // put result into *res

int cmp(vector<double>& vec1, vector<double>& vec2, vector<double>& vec3)
{
  double res1;
  double res2;
  double res3;
  // ...
  thread t1 {F{vec1, res1}};     // function object
  thread t2 {[&](){ res2 = f(vec2); }};    // lambda
  thread t3 {g, vec3, &res3};       // ordinary function

  t1.join();
  t2.join();
  t3.join();

  cout << res1 << ' ' << res2 << ' ' << res3 << endl;
}

设计一个类型安全库依赖于可变参数模板（variadic template）。比如，std::thread的构造函数就是一个可变参数模板，它可以根据第一个参数来区分和检查后续参数类型和个数的正确性。

lambda也是库的使用更简单。比如上面的例子，t2的参数是一段代码（lambda表达式），可以访问局部（local scope）变量。

在引入新的语言特性的同时，让标准库的实现也使用这些特性很难。这无疑带来很多风险，但它也有很多好处：

给用户一个更好的标准库
给用户展示新特性的示例代码
用户不必自己实现低级别的基础设施
强迫语言特性设计者们去处理真实问题

线程和锁模型的使用需要同步机制来避免race condition。C++11提供标准的互斥锁（mutex）来完成这个目的。

mutex m;    // controlling mutex
int sh;     // shared data

void access()
{
  unique_lock<mutex> lck(m);     // acquire mutex
  sh += 7;                       // manipulate shared data
}  // release lock implicitly

unique_lock是一个RAII对象，确保用户不会忘记释放（unlock）锁（mutex）。这种锁也可以防止用户写出我们最常见到的一种死锁（deadlock）代码：

void f()
{
  // ...
  unique_lock<mutex> lck1 {m1, defer_lock}; // don't yet acquire m1
  unique_lock<mutex> lck2 {m2, defer_lock};
  unique_lock<mutex> lck3 {m3, defer_lock};
  // ...
  lock(lck1, lck2, lck3);      // acquire all three locks
  // ... manipulate shared data ...
}  // implicitly release all mutexex

这个例子里，lock()函数同时获取3个锁，并且同时释放（RAII）。当然C++17对此还有更优雅的实现。

线程库最早是由Peter Becker在C++0x中提出的，基于boost::thread提供的接口，在提出该提案的同一次会议（2004年）上，内存模型的第一个提案也出现了，也许这并非巧合。

最大的争论是线程撤销（cancellation），就是让线程从正在运行的状态直接停止执行。C++委员会的每个程序员都希望拥有这个特性，但C委员会在一次正式投票里投了反对票，而且是唯一一次来自C委员会对C++的投票。我记得，“C语言没有析构函数，无法使用RAII释放资源”，负责POSIX的Austin Group派代表表示，他们坚决反对任何与线程撤销有关的提案，坚称线程撤销既无必要，也无法安全地实现。考虑到Windows和其他操作系统提供了很多类似的实现，并且C++不是C，对于使用POSIX的人来说并无影响，我担心他们只是在保护C语言，而不是想让C++变得更好。C++标准缺少线程撤销一直都是一个问题。比如，在执行并行搜索的时候，第一个找到答案的线程需要停止搜索，撤销其他线程的执行。C++20提供了一个停止令牌（stop-token）的机制来支持这类用例（use case）。

4.1.3 futures

一个类型安全的类POSIX/WINDOWS线程库是一个极大的提升，但这仍然属于1980年代的低级编程。一些委员会成员，比如我，表明C++亟需更现代和更高级的（并发）编程方式。比如，Matt Austern（来自Google）和我在是否使用消息队列（channel）和线程池上有分歧。主要的争论点是时间太少来不及实现这样一个库。我表示，如果委员会的专家不提供这个库，那很多程序员只能使用我的学生实现出来的库。委员会本应做的更好，“你即使不提供一个完整的库，那至少提供一种方式，可以让程序员在不同的线程之间传递信息，而无需同步”。

委员会分成了两派，一方认为只需要一个改善后的类型安全的POSIX库，另一方认为POSIX是1970年代的设计，所有人都应使用更高级的基础库。在07年的科纳会议室，我们达成妥协。C++0x（当时预期是C++09）会提供promises和futures，以及一个异步任务的发射器（launcher），async()方法，允许提供线程池，但不要钱。像大多数妥协一样，科纳妥协没有让任何人满意，而且存在一些技术性问题。不过，很多人都把这看做是一次进步，多少年了，终于发生改变了（但很多人其实不知道这是一次妥协的结果）。

最终，C++11提供了：

future - a handle from which you can get() a value from a shared one-object buffer, possibly after a wait for the value to be put there by a promise
promise - a handle through which you can put() a value to a shared one-object buffer, possibly waking up a thread waiting on a future
packaged_task - a class that makes it easy to set up a function to be executed asynchronously on a thread with a future for its result and a promise to return the result
async() - a function that can launch a task to be executed on another thread

最简单的用法是使用async()。给定一个函数作为参数，async()运行在一个新起的线程上，并且隐藏了所有线程启动和线程通信的细节。

double comp4(vector<double>& v) // spawn many tasks if v is large enough
{
  if (v.size() < 10000)  // is it worth using concurrency?
    return accum(v.begin(), v.end(), 0.0);
  auto v0 = &v[0];
  auto sz = v.size();

  auto f0 = async(accum, v0, v0+sz/4, 0.0);  // first quarter
  auto f1 = async(accum, v0+sz/4, v0+sz/2, 0.0); // second quarter
  auto f2 = async(accum, v0+sz/2, v0+sz*3/4, 0.0); // third quarter
  auto f3 = async(accum, v0+sz*3/4, v0+sz, 0.0); // fourth quarter

  return f0.get() + f1.get() + f2.get() + f3.get(); // collect the results
}

async把代码封装到一个packaged_task中，定义future，并把结果通过promise返回。

future/promise既可以传递普通的值（value），也可以传递异常。

X f(Y); // ordinary function

void ff(Y y, promise<X>& p) // to execute f(y) asynchronously
{
  try {
    X res = f(y);    // compute a value for res
    p.set_value(res);
  }
  catch (...) {  // oops: couldn't compute res
    p.set_exception(current_exception());
  }
}

便于理解，我这里的参数没有使用perfect forwarding。

这里对future的get()要么是一个值（value），要么是一个异常。和同步调用f()完全等价。

void user(Y arg)
{
  auto pro = promise<X>();
  auto fut = pro.get_future();
  thread t {ff, arg, pro};   // run ff on a different thread
  // ... do something else for a while ...
  X x = fut.get()
  // ...
}

标准库packaged_task实现了把普通函数封装成一个函数对象，并且处理promise/future细节的功能。

我本希望这会成为实现支持work-stealing线程池的基础，但结果令我失望，参考8.4小节。

Refer:

https://www.stroustrup.com/hopl20main-p5-p-bfc9cd4--final.pdf

original refer

Pete Yuan

C++从2006到2020 - 4.1 C++11: 并发

Comments