守住发际线：南大蒋炎岩谈读博那些事儿(12)

图 3：基于线程调速的并发程序测试技术示意
有没有免费的午餐？
观测并发程序执行是非常基础且重要的问题，来自各个领域的研究者都取得了丰硕的成果，但唯独「完美」现在还做不到。现有观测并发程序执行的工作可分为两类：要么存在一个 NP-难的最坏情况，要么不可避免会在某些情况下用锁 (类似图 2 的方式) 保证一次观测不被其他线程打断。
「哲学家吃中餐问题」的 NP-完全性一定程度上反映了现有研究工作面临的困境——如果只允许程序进行少量的线程本地记录，则恢复满足顺序一致性的全局调度是困难的。另一方面，我们也已经知道共享内存上的互斥和可序列化并发对象必须借助读-写原子操作才能实现 [10]。这启发我们提出了一个猜想：观测并发程序的执行没有免费的午餐 (no-free-lunch)。具体的陈述是，在一个限定的计算模型下，即便允许对并发程序进行一定程度的修改 (在共享内存访问前后插入一定数量的共享内存读/写操作，其中写操作只限于为观测并发程序执行而额外分配的内存)，只要这些插入的读/写序列是等待无关 (wait-free) 的，就存在某种线程调度，根据线程本地的观测结果恢复满足顺序一致性的程序执行是 NP-完全的。
如果这个猜想成立，就对这 30 年的研究成果给了一个「二分性」的总结——想要观测并发程序的执行，要么添加处理器之间的同步，要么付出 NP-完全的代价。这意味着观测并发程序执行是既困难又容易的。目前我们相信这个猜想是成立的。在试图证明它的过程中，我们对「哲学家吃中餐问题」给出了的一个新的（简化的）证明，并据此得出了一些有用的结论，例如在对程序的修改能写成只读前缀 只写后缀的情形下的 NP-完全性。受限于掌握的数学工具，我们还没能完全证明或否定这个猜想。如果猜想被推翻，我们就更惊奇了——说明 30 年来大家的努力都有本质上的不足，抑或 P = NP，也许我们就需要重新理解整个计算机科学了。
上面都是假话。这个猜想很早就想到了，但一直找不到合适的数学工具证明，加上研究方向的转变，猜想就只证明到这个程度 (也是个课后习题难度)，其实是博士论文烂尾了……
在试图解决这个猜想的过程中，其实给了我们很多启发——猜想必须在很多限定条件下才能成立。因此只要假设的条件被推翻，观测并发程序执行就变得不困难了。例如，我们的复杂性结论是在「最坏情况」下得出的，即存在一个 NP-完全的「极端」线程调度。但最坏情况也许像平滑分析 [11] 中指出的那样，在实际中很难存在。现实中的并发程序执行有它的特征 (例如各种局部性)，也被我们用来降低观测并发程序执行的开销。就在难与易之间，理论和实践得到相互的印证。然而在理论与实践中，我们都仍有很多未解决的难题，博士读了很多年，反而觉得研究才刚刚开始，而不像是告一段落了。