C++ Concurrency in Action 笔记

记录一下我从《C++ Concurrency in Action, 2nd Edition》中学到的东西。

注：不怎么全，漏掉的可能是我没学会的，也可能是我本来就会的，还可能是我觉得用不上的。

Chapter 1

为什么要使用并发/为什么不要使用并发？

• 使用并发的理由主要是划分业务和提升性能。提升性能很好理解，划分业务主要指的是另开线程用于处理不确定何时会发生的事件（响应用户请求，监听网络数据之类的）。
• 不使用并发的理由是“这样做不值得”，并发带来的复杂度胜过了带来的性能提升（甚至性能也不一定有提升）。

Chapter 2

std::thread 相关的坑？

• C++'s most vexing parse，也就是把变量定义当作函数声明。所以要尽量用大括号初始化。（相比起运行时的罕见 bug，编译错误真的是小问题。）
• Dangling reference/pointer（悬挂引用/悬挂指针）。这是涉及到闭包时的经典问题，lambda 捕获引用时注意一下被捕获对象的生命周期。
• 在 std::thread 对象被销毁前记得调用 .detach() 或者 .join()，否则 std::thread 析构函数里会帮你调 std::terminate()，然后你所有 thread 就全没了。
  • 此外也要注意代码中的 .join() 会不会因为异常而没被执行。
• 如果要靠 std::thread 传函数参数的话，引用需要用 std::ref/std::cref 包一下。（和 std::bind 的情况一样，更推荐使用 lambda，清晰自然。）

Chapter 3

std::lock_guard, std::scoped_lock 和 std::unique_lock 的区别？

• std::scoped_lock 可以完美替代 std::lock_guard，甚至支持 0 个或者多个锁，而 std::lock_guard 只支持一个。
• std::unique_lock 可以在构造时不上锁（通过第二个参数指定）以及在作用域内释放锁（支持 .unlock()），通常和 std::condition_variable 的 .wait() 一起服用。

一个关于 stack API 设计的坑：

• 以前我一直不明白为啥 std::stack/queue 之类的 STL 的容器的 .pop() 方法不带返回值，用起来不大方便，因为很多时候都是 .top() 和 .pop() 连用的。其中的原因在于，在返回值给用户的过程中可能会（进行拷贝/移动并）抛出异常，而此时那个值已经从数据结构里被移除了，就导致那个元素一去不复返了。
• 但是 .top() 和 .pop() 分离的设计就自带 data race，用户想要取出顶部元素，于是就先调用 .top() 再调用 .pop()，然后托多线程的福两个同样的操作 interleaving 一下，就不对了。
• 解决方法是，依旧把 .top() 和 .pop() 合并为一个方法，同时想办法避免返回时异常导致数据丢失的问题：
  • 方案1：加一个参数让用户传引用进来，这样的话“把值给用户”这个操作可以在从数据结构里移除元素之前完成，这样就不会有数据丢失的问题了。
  • 方案2：提前把返回值用（拷贝/移动时不会抛异常的）  std::shared_ptr 装起来，然后返回给用户。
  • 方案3：常规实现，但是要求用户定义的返回类型有无异常的拷贝或者构造函数（）。
  • 综合方案：方案3肯定不能单独用，方案一最好要有（因为 overhead 最小），所以推荐的是方案 1+2 或者 1+3 组合。

避免死锁的一些建议：

• 尽量不要嵌套锁。
• 需要同时锁多把锁时尽量一次锁完（std::lock 或 std::scoped_lock），不行的话就保证锁的顺序。
• 尽量不要在持有锁的时候调用户代码，因为用户可能也在获取锁。

std::mutex 的一些替代品：

• 用于 lazy 初始化的 std::once_flag 和 std::call_once。
• 适合不怎么写的数据结构的读写锁 boost:shared_mutex。
• 支持递归的 std::recursive_mutex，不过在使用之前需要好好想想能不能避免递归锁。

Chapter 4

std::future 相关：

• std::async 类似于 std::thread 但是通过返回 std::future 来提供返回值，可以通过参数来指定运行时机（另开线程或者在需要值的时候计算）。
• std::promise 属于纯手动，可以通过 set_value()/set_value_at_thread_exit() 设置值，也可以通过 get_future() 来获得 std::future 对象。
• std::packaged_task 可以把一个函数（可调用对象）和一个 std::future 相关联。执行（调用 operator ()）之后便可以从 get_future() 拿到的 std::future 对象里取出返回值。
• std::future 里可以存放异常，在使用 get() 时会把异常重新抛出。如果使用 std::promise 的话可以通过 set_exception()/set_exception_at_thread_exit() 来存放异常。
• 如果想多个线程都从 future 对象里取值的话要使用 std::shared_future，且每个线程都持有自己的 std::shared_future 的 copy。

std::chrono 转换行为：

• std::chrono::duration_cast 的默认行为是截断而不是四舍五入。
• std::duration 可以自动从精度高的转成精度低的。

支持 timeout 的好东西（其中 xxx 可以是 for 或者 until）：

• std::this_thread::sleep_xxx
• std::condition_variable.wait_xxx
• std::timed_mutex.try_lock_xxx
• std::future.wait_xxx

std::experimental 里的好东西：

• std::experimental::future 支持 continuation，就是那种老式的 JS 异步写法，靠 .then() 连在一起。
• std::experimental::when_all/when_any()，就是 JS 里的 Promise.all/any()。
• std::experimental::latch 就是 Go 里面的 sync.WaitGroup，感觉还是挺有用的。
• std::experimental::barrier 和 std::experimental::latch 在功能上有些类似，都可以用于等一些 threads 完成某件事
  • 区别之一，所有 thread 到达 barrier 后，可以再次使用 barrier，而 latch 就保持 ready 状态。
  • 区别之二，latch 可以等别的 thread 完成而自己不参与任务，但是 barrier 里执行任务和等待的是同一组 group。
  • 还有一个 std::experimental::flex_barrier 支持构造时传入一个函数，用于到达后执行并修改等待的 thread 数量。

Chapter 5

注：这一章主要参考 cppreference 了，原因之一是 strongly happens-before 的概念在 C++ 20 中改变了。

一些和执行顺序相关的概念：

• 注：先不考虑 memory_order_consume，因为 ISO C++ 委员会目前不建议使用这个。
• sequenced-before 指的是同一个 thread 里根据 evaluation order 确定的执行顺序。
• synchronizes-with 指的是对于一个 atomic，在 thread A 中的 store 是一个 release operation，而在 thread B 中的 load 是一个 acquire operation，那么这对 store 和 load 有 synchronizes-with 关系。
• happens-before（在不考虑 consume 的情况下等同于 simply happens-before），简单来说它由一些 sequenced-before 和  synchronizes-before 连接而成。
  • strongly happens-before 在 happens-before 的基础上增加了对于 synchronizes-before 用到的 ordering 为 sequentially consistent 的要求，或者有夹在 sequenced-before 中间的任意 synchronizes-with。它能够帮助构建一个 total order（或者说那些东西是 linearizable）的。

std::memory_order 的一些选项：

• memory_order_relaxed 关于执行顺序什么也没保证。不过作为原子操作，还是能保证不会修改了一半被别人看到（atomicity），以及在看到后面修改的值之后不会再看到前面的值（consistent modification order）。
• memory_order_acquire 和 memory_order_release：
  • 效果上，如果一个标记为 release 的 load 读到了来自一个被标记为 acquire 的 store 的值，那么 store 之前发生的（也就是 happens-before）的操作都可见了。
  • 实现上不严谨地说，相当于不能把操作从 acquire store 的前面放到后面，也不能把操作从 release load 的后面放到前面。
• memory_order_seq_cst 在 acquire 和 release 之上提供了一个全局的操作顺序。

std::atomic 系列：

• 可以通过 is_lock_free() 来检查这个 atomic 是不是用锁模拟出来的。
• std::atomic_flag 是唯一一个确保没有 lock 的 atomic 类型，但是它支持的操作比较少。
• compare_exchange_weak 和 compare_exchange_strong 的区别在于 compare_exchange_weak 即使满足条件（atomic 中的值等于 expect）也不一定成功。通常如果在循环里使用就用 weak 版本，否则就 strong 版本。
• 想要原子性地使用 std::shared_ptr 可以用重载版本的 std::atomic_load 之类的函数，C++20 之后直接用 std::atomic<std::shared_ptr<T>>。

Chapter 6

设计带锁数据结构时的一些指导性意见：

• 保证数据结构的不变量被破坏时（或者说数据结构修改的中间状态）对于其它线程不可见。
• 设计 API 时注意避免潜在的 race condition，提供完整的操作而不是让用户去拼。（参考 Chapter 3 中的例子。）
• 在有异常发生的情况下也不要破坏不变量。（同样可以参考 Chapter 3 中的例子。）
• 通过减少锁的范围以及避免嵌套锁来降低死锁的概率。

Chapter 7

lock-free 数据结构的特点：

• 优势在于可以最大化并行程度，以及提升鲁棒性。对于有锁的数据结构，如果拿着锁的线程挂了可能会导致数据结构处于不一致的状态。
• 可能会出现 live lock 的问题，或者说有两个线程都因为对方而反复重启。
• 性能不一定好，比如因为更多数量的原子操作（相比起锁），或者缓存的反复失效。 
• 更难设计。

lock-free 的一些难点（以书中的 stack 为例，代码就不贴了）：

• 内存管理：
  • 问题：pop() 中需要回收 old_head，但是问题是可能有别的 thread 也持有同一个 old_head，而且在 head.compare_exchange_weak(old_head,old_head->next) 的循环里，而这个循环访问了 old_head的 next 指针。所以说在 pop() 时释放 old_head 肯定是不对的。
  • 方案1：先把需要删除的 node 存起来，等某个 pop() 发现没有别人也在 pop() 里的时候，把之前存下来的 node 一并释放。这么搞缺点也很明显，内存释放的时机很不可控，如果运气不好可能就永远都释放不掉。
  • 方案2：拿个东西存一下所有 threads 正在访问的那个指针，然后离开 pop() 时根据有没有别的 thread 访问然后选择立刻释放或者延迟释放。
  • 方案3：引用计数。如果 std::atomic<std::shared_ptr<T>> 是 lock-free 的，那么就还挺方便的，否则就手动实现。
  • 注：可以参考一下 Linux Kernel 里的无锁同步机制 RCU (Read, Copy, Update)。
• ABA 问题：
  • 简单来说，一次 compare_exchange 成功了确实能保证之前的值是你想要的，但并不保证是同一个东西。比如说你 exchange 了一个指针，然后那个指针被其它 thread 释放了然后又有新的 node 复用了那个地址。
  • 一个解决方案是给那些指针附一个计数器，每次你复用地址时给计数器 +1 来保证值的不同。

Chapter 8

一些影响并行性能的点：

• 核的数量（以及缓存的共享情况）。
• Cache ping-pong（中文大概是缓存颠簸？）。如果多个线程经常需要同时修改一块内存区域，会导致经常出现因缓存失效导致的频繁缓存转移。
• Cache false sharing（缓存伪共享）。表面上两个线程在操作不同的内存区域，但是因为靠得近所以在同一个缓存行里，便又导致了 Cache ping-pong。
• 内存访问的时空连续性，也就是对于某个 thread，它所访问的内存区域是分散还是集中。而在多线程应用中，减少所需要的缓存行数量可以降低 false sharing 概率和转移缓存行的代价。
• 线程数量和线程切换开销。如果没控制好数量导致处于就绪态的线程过多，就浪费资源在线程切换上了。

Chapter 10

STL algorithm 里的 execution policy 参数：

• 这个参数是 permission 而非 requirement。
• 出现异常的时候会 std::terminate，std::bad_alloc 除外。
• 渐进复杂度不变，但是常数会变大。
• sequenced_policy 是最普通的串行。unsequenced_policy 指可以向量化，parallel_policy 指可以在别的线程里搞，parallel_unsequenced_policy 在前面两者的基础上还支持在线程之间迁移。
• 其中 unsequenced 会要求用户代码 vectorization-safe，也就是说在同一个线程里同时执行的话不会有问题（反例就是拿锁，或者依赖前一个 iteration 的结果）。

Reference

• C++ Concurrency in Action (2nd edition)
• Concurrency in C++20 and beyond
• https://en.cppreference.com/w/cpp/atomic/memory_order