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

图 2：修改程序代码对共享内存读操作进行观测 (标记「」的为插入的代码)
难与易之间的矛盾是观测并发程序执行的开销。虽然锁可以实现有效的观测，但却降低了系统的并行度、拖慢了程序的执行。并发性存在于计算机系统栈的各个层次上，因此来自体系结构、计算机系统、程序设计语言和软件工程领域的研究者，全都对实现高效的并发程序动态分析有兴趣。在三十多年的研究历程中，我们看到了很多非常精彩的锁机制的实现：借助硬件的缓存一致性协议 [2]，使用虚拟机、分支计数和用分页机制实现的 CREW 协议 [3, 4]，以及在线程局部访问下「乐观」的锁机制 [5]。另一方面，我们可以通过记录间接信息 (如每个线程执行的路径)，使用约束求解的方式去恢复共享内存访问的日志 [6]。我的博士论文在运行时获取共享内存访问数据依赖这一问题上做了一些微小的贡献，主要集中在利用局部性减少锁的开销。例如，我们发现在空间 (地址) 上连续的多个变量，例如数组的一部分，在共享内存访问的意义上通常可以看成是一个大的「虚拟变量」。
如果以虚拟变量为单位进行记录，则可以有效减少锁的数量，并大幅减少日志的数量 [7]。
在观测并发程序执行的基础上就可以实现各式各样的动态分析技术了。这里举一个我们测试并发程序的例子 [8] (参见知乎专栏中的科普文)：
midwinter1993：拧龙头法测试并发程序专栏地址：https://zhuanlan.zhihu.com/p/51341151
试想我们把线程中的读/写事件按顺序串在一根绳子上 (图 3)，处理器按照固定的速度按顺序执行绳子上的事件。改变绳子的长度 (例如拉绳子相当于把线程执行的速度变慢) 就得到了不同的线程调度——那些触发并发缺陷的调度，很可能隐藏在某些绳子长度的配置中。我们设计了聪明的策略生成具有多样性的线程调度，在先前研究者已经反复测试过的并发程序上找到了前所未知的并发缺陷。对于复杂性日渐增长的并发程序来说，动态分析是一项非常有前景的技术，对具体内容感兴趣的读者可以参考我们的中文综述 [9]。