并行化的动态数据竞争验证和检测方法

之前系列提到的动态数据竞争验证和检测方法是结合了验证和检测两部分。这篇文章主要介绍一下并行化的动态数据竞争验证和检测方法。

首先我们来谈谈有关利用Pin编写Pintool来检测数据竞争。由于动态二进制插桩就是在原始程序指令前后加入跳转指令，而跳转的目的地就是所谓的分析函数，分析函数中包含了相关的检测逻辑。因此，从这个角度也能发现，我们变现的分析函数和应用程序线程是绑定在一起的。由于应用程序许本身是多线程的程序，因此我们自己编写的Pintool也是多线程的。数据竞争检测用到的相关公共的数据结构包括向量时钟以及锁集等都有可能被多线程访问。为了保证一致性，我们在分析函数中都会加入锁来保护共享的访问操作，并且大部分的操作都可能会涉及到锁保护，尤其是针对读写指令的分析函数中会涉及到比较复杂的验证过程和检测过程分析。因此，频繁使用加锁可能会导致程序在执行过程中不能够有效利用多核的硬件优势。

最近有一篇文章提到了一种并行化的动态数据竞争检测方法。这种方法扩展性非常好而且不用修改之前已经提出的动态数据竞争检测方法，如下图所示。

并行数据竞争检测方法

该方法的核心就是将动态数据竞争检测逻辑从分析函数中分离出来，让单独的检测线程执行相关的逻辑，检测线程之间相互不干扰，因此就不用再使用锁来保护。这里对共享内存空间进行分块，不同的块映射到不同的检测线程上。而原始的应用程序线程则是将程序的行为以事件的形式发送到队列中，对于内存读写事件先缓存到线程TLS中，当缓存慢了之后再发送到队列中，而其他事件则是复制并且发送到各个检测线程队列中。这样的话，唯一需要加锁保护就是针对事件队列的相关访问。

同时我们也能够证明，每个检测线程看到的都是完整程序执行的行为，除了访问的内存块有所不同。

• 如果两个有明确先后关系的访问，来自不同的线程并且访问相同的共享内存空间，那么针对每一个共享内存块的访问的事件都会被发送到同一个检测线程中，并且发送的顺序也是有先后顺序的。
• 如果两个访问没有明确的先后关系，那么这两个访问事件被发送到队列时谁在前面和谁在后面都无所谓。

上述方法提出时主要利用FastTrack来进行实验对比分析，我们实现该方法后发现能够应用在基于Lockset算法、基于Happens-before以及基于hybrid上的动态数据竞争检测工具上。之前文章中提到的动态数据竞争检测方法我们全部实验了一下，发现并发的动态数据竞争检测方法和原始的动态数据竞争检测方法检测结果一致。

在该方法的启发下，我们又对之前我们提出的动态数据竞争验证和检测方法进行了并行化的处理，方法框架如下图所示：

并行数据竞争验证检测框架

Application Threads

应用线程中我们同样也是在分析函数中进行相关读写内存事件的分发，而其他同步时间则是继续在原始应用线程中处理。

当应用线程处理非读写内存事件时，之前的方法中我们都是用共享的内存结果保存同步对象信息、向量时钟信息以及锁集锁集信息，而这里我们将会把每个线程相关的信息都保存在自己的TLS中。

当应用线程处理读写内存事件时，分析函数中会将这些事件发送到验证线程队列中，而应用线程随即就被延时阻塞中止执行。

Verification Thread

验证线程主要的作用就是从队列中获取验证请求事件，即应用线程中的读写内存事件，然后处理相关的验证逻辑，和之前的访问类似。

我们只选择了一个验证线程用来处理所有的验证请求，主要是由于验证线程需要和应用线程和检测线程互相沟通，为确保一致性，只是用一个验证线程。验证线程每处理一个验证请求之后，都会根据处理的结果看是否需要唤醒相关的应用线程。同时会根据不同的共享内存块，分发检测请求到不同的检测线程队列中。

Detection Threads

这里检测线程做的工作就是从检测队列中读取检测请求，然后寻找被验证过程中遗漏的数据竞争。

由于验证线程和应用线程是并发进行的，因此验证请求也有可能在验证线程执行过程中失效，一旦请求失效，那么该验证请求就不会再被处理。同时，为了减少向量时钟以及锁集的副本，我们构造的验证请求和检测请求都只包含一个相关的副本以及若干个引用。

我们的并行数据竞争验证和检测方法在充分利用硬件的条件下，每个线程都将会负责好自己的职责。

后序将会介绍ad-hoc类型同步相关的分析。