并发问题的牛鼻子 II

在《简评：并发问题的牛鼻子》中我阐述了 concurrency problem 的核心来自于 shared data，而其解决方案也相当自然，即：根据不同的粒度，将 concurrent part 变为 serialized part（例如，通过 lock、通过 blocking queue 来实现）。这一说法本身并没有错，但这只是 concurrency problem 的 half story：将关于 shared data 的「并发」部分「顺序化」。但这里还存在着另外一个问题，无论对于「加锁」还是使用 blocking queue，那些“加锁失败”或者“被 blocking”而处于“等待状态”的 thread 应该怎么办？它们如何被管理，又如何被唤醒？即：thread coordination 应该如何被实现？

为什么我们需要关心 thread coordination？难道它们不是被 lib 或者 OS（Operating System）去自动实现的吗？这取决于你的问题本身是否需要更为精细的 thread management。例如，常见于 concurrency 中的一个题目是：可以让两个 thread 交替打印 0 和 1 吗？此时，仅仅依靠对 lock 的认知而对 thread coordination 的实现机制毫不关心的话将直接导致你无法完成这个任务。更何况，现实中需要对某几个 thread 做 coordination 的问题会远远复杂于这道简单的题目。

事实上，要真正理解 thread coordination，就需要透彻地理解 thread 是什么，特别是，什么是关于 thread 的 scheduling，什么是 thread 的 blocking（详见《thread/process 的错误直观》中的阐述）。简单来讲即是，虽然 thread 本身对于 OS program 来讲是 executor，但它对于 CPU 来讲却是 task，它仅仅是 CPU 的 basic scheduling unit task。所以，所谓的 thread blocking，并非是让 CPU 停止运转，而是将该 thread 标记为 sleep 状态，让 CPU 不去执行该 thread。从而对于这个 thread 所包含的 OS program 来讲，它的 executor 似乎是被直接停止了。于是，所谓的 thread coordination 其实就是各个 thread 根据自己的 thread state 去修改其它与之协作的 thread 的 state，从而间接实现 threadA 的 behavior 触发 threadB 的 state 改变。

显然，最直观的管理 waiting threads 的 data structure 是 queue。

而使用 waiting queue 的最简单的情景是关于 lock 的获取：一堆 thread 尝试去获取锁，而根据这把锁的排他性（mutual exclusive，mutex）只能有其中一个 thread 获取成功（例如：threadA 获取 lock 成功）。而剩下的那些获取锁失败的 thread 都会被逐个放进 waiting queue。当这把锁被 threadA 释放时，就会触发这个 waiting queue 中某个 thread 的唤醒。当然，如果再考虑到 lock fairness，也完全可以每次只唤醒这个 queue 中的第一个 thread。

更为复杂的场景是，我们不仅关心获取 lock 的成功与否，更关心某些 waiting business logic 是否被满足、从而触发某些执行特定操作的 thread 的唤醒。例如，对于 blocking queue 来讲，put() 方法可以由 threadA 来负责，而 get() 方法可以由 threadB 来负责。但对于 threadA 来讲，put() 方法的执行需要 queue 本身「未满」的前提条件，而对于 threadB 来讲 get() 方法则需要 queue 本身「不空」的前提条件。这便是它们各自的 waiting business logic。显然，如果 threadA 和 threadB 共用一个 waiting queue 则会将不相关的两种「等待条件」混在一起，不仅低效，更是耦合了本该分离的业务逻辑。

而解决方法也是自然的，这就是为不同的 waiting business logic 引入不同的 waiting queue（也叫 condition queue，或 condition variable，CV）。于是，对某个 shared data 的操作就变成了：首先尝试获取 guarded mutex lock，在它获取成功的情况下，根据不同的 waiting business logic 而将不同的 thread 放到不同的 condition queue 中。

一个立刻可以提出的问题是：为什么还需要一层 guarded mutex lock？直接为各自的 waiting business logic 引入各自的 lock 不可以吗？为什么要为不同的 condition queue 引入同一把 guarded mutex lock？虽然各自的 waiting business logic 是不同的，但它们所维系/访问/修改的 shared data 却是一样的。这就意味着对 shared data 的「某个操作」可能会改变多个 waiting business logic 的检测结果，进而触发不同 condition queue 的唤醒条件。而这些被唤醒的 thread 又会因为不同的执行过程，反过来影响其他 waiting business logic。

另一方面，考虑到对于任何 shared data 来讲，没有 synchronization 保证的修改都是不安全的。所以，需要有一把对于这个 shared data 来讲是 global 的 guarded mutex lock 来保证 thread safety。而各自的 waiting business logic 的检测都是需要在“已获得锁”的前提下进行。毕竟，没有 synchronization 保证的 read 也都是无意义的。例如，对于 blocking queue 来讲，无论是 put() 还是 get() 都会获取同一把 guarded mutex lock（当然，如果你的业务逻辑能够完全保证所实现的 blocking queue 的 put() 和 get() 的 shared data 是完全独立互不影响的，你当然也可以为它们各自引入一把不同的锁，从而实现更高效的并发）。

如此，我们便补齐了关于 concurrency 的另外一半的 basic story：thread coordination。因为 shared data 的存在，所以我们需要 synchronization 的机制来保证 action 之间的顺序性（如：lock、blocking queue）。而引入了 synchronization 就必然会导致 waiting threads 的存在，这就涉及到 thread coordination 的问题。而解决 thread coordination 的方式也很直观，即：根据不同的 waiting business logic 将不同执行逻辑的 thread 放入具备相同「等待条件」所对应的 waiting queue（condition queue）即可（当然，需要注意的关于 thread safety 的坑是：waiting queue 的操作一定要在获得了 guarded mutex lock 的前提下开始）。并且，整个这套机制同 programming language 本身无关，它是一个 general 的 concurrency problem thinking。

Remarks：

1/ 所谓「同步」，即是对于 instruction setA 和 instruction setB 来讲，setA 和 setB 同步（假设 setA 在前），则意味着在所有 setA 中的 instruction 被执行完毕前，setB 中的任何指令不可以被执行，也即是 happens-before 的一个「偏序」关系。而如果 setA 中的操作在被消耗时，setB 中也有操作被执行，无论是通过「并发」还是「并行」发生，setA 和 setB 都是「异步」的。

2/ 关于「shared data 是 concurrency problem 的核心」这个问题，我们还可以顺便考察一下《Java concurrency in practice》这本书。在这本书的 2.2.1 节，作者 highlight 了一段话：Stateless objects are always thread-safe。也即是，对于没有 shared data（即：无公共可修改的 state）的 object 来讲，它是线程安全的，或者说，是并发安全的。

我想，几乎对所有初读（甚至头几遍的复读）此书的人来讲都会对这句 highlight 的话感到疑惑。不是说这句话不对，这句话当然是对的，但这样一句近乎废话的 statement 为何要放在这里？这就像是突然在一本书里突兀地放入一句“地球围绕太阳转”一般，你不能说它是错的，但你无法理解它的 motivation 和用意。

但要真正理解这句话的深意，明白它才是 concurrency problem 的真正核心本质，则需要更多对其它问题的研究和考察。

通常，对 thread-safety 的一个错觉是：你总以为 concurrency control 是关于 behavior 的控制，而实则是关于 shared state，即：shared data 的控制。这样的「直观」，会直接影响到你对很多其它 topic 的判断和理解。例如，一提到 db 的 transaction，在这样的「直观」理解下，可能会下意识地去思考：如果要自己实现 transaction，岂不是要监管各种 action？难道要把所有的 function 都加上监控吗？

但事实却是，transaction 的实现仅需要完成对 data record 本身的控制即可（对应到 isolation level），根本不必关心任何的 function/action。无论你的 action 长什么样，如果不涉及 shared data，那么你随便怎么做，都无所谓。而如果涉及 shared data，你唯一需要关注的就是对 shared data 的修改。这不就是 isolation 的实现方式么：仅控制 data record。

也即是，为何 db 的 transaction 可以仅控制 record 的状态？因为整个 general concurrency problem 本来就是关于 shared data 的控制，而不是关于 action 的。对 db 来讲，它们的 shared data/state，就是所有的 records。

（另：我们会下意识地认为 shared data/state 在一段程序中的数量应该是少量的。可对于 db 和 transaction 来讲，99% 上 GB/TB 的数据都是 shared data。）

开始研究「并发问题」前，必须搞清楚三个问题：

• executor 是谁
• task 是谁
• shared data 又是谁

这是最基本、最核心的三连问，是后续解决问题所依靠的 dashboard。

也即是在这个意义上，我们才能真正理解：并发问题从来不关乎执行代码的 behavior，而是 shared data。也即是在这个意义上才能明白，“没有 shared data 的两个行为是不会有并发问题”这句显然正确的废话所传达的不平凡的实质：并发问题的「因」，不关乎执行代码，关乎的是 shared data。

是 shared data 的存在性，引发了对「执行代码」的关注和辅助。但不是说「行为代码」一定是必不可少的关注点，没有了 shared data，控制行为的代码是不必要和毫无疑义的。

真正的「主动轮」，是 shared data；而 behavior 的控制是「从动轮」。

近期回顾

《thread/process 的错误直观》

《为何信奉/选择 value investing？》

《备忘录：「可口可乐」穿越商业周期的一些宏观考察》