基于Happens-before的数据竞争方法汇总 （二）

Happens-before方法中最基础的方法Djit+，Djit+使用向量时钟VC进行数据竞争分析。下面这篇文章介绍的是FastTrack算法，在Djit+基础上进行的改进，将Djit+的时间复杂度从O(n)降到接近于O(1)。首次看的同学还是建议先看我之前写的有关介绍Djit+的相关基础内容。

Reference

http://race-wordpress.stor.sinaapp.com/uploads/2016/01/FastTrack-Efficient-and-Precise-Dynamic-Race-Detection.pdf

Djit+方法每次进行数据竞争分析，都会遍历历史读VC或是历史写VC，这个过程的复杂度是O(n)的，FastTrack(FT)正是在这个点上进行了算法的改进。首先需要明确的一点就是，在一个没有数据竞争的程序中，每一次的写都是有明确先后顺序的；读就不一样，不一定要是顺序读，也可以是并发的。因此的话，对于每一个共享内存单元来说，我们不必像Djit+中那样保存一个历史写VC。保存一个历史写VC无非就是想找到所有竞争的写操作，但是其中有些已经早就被检测出来了，但是线程对应的entry还是存在于VC中，造成时间和空间上的冗余。因此，对于写历史，我们不保留VC，二是直接保留最近访问的线程时间戳就行，也就是epoch形式(timestamp@thread)，这样的话，每次进行数据竞争分析的时候，就不需要像Djit+那样进行VC的遍历，而是常量级别的比较。具体来说：

• 如果当前线程执行写操作，那么对于W/W数据竞争，只需要比较epoch中所对应的timestamp是不是大于当前线程所知道的thread的时间戳，如果是的话，就表明之前的写操作和当前线程的写操作就是并发进行的，报告一个W/W的数据竞争，更新epoch为当前线程的timestamp。
• 如果当前线程执行写操作，那么对于R/W数据竞争，需要遍历历史读VC，类似Djit+，找到所有的R/W数据竞争。这里历史读VC是保存所有并发的读epoch的集合，并不是像Djit+中那样保存所有的线程，只是结构上相似，我们就直接采用历史读VC这种形式表示。最后分析完毕同样更新当前线程的timestamp并且删除历史读VC中所有的信息。这么做是考虑到并发的R/W数据竞争已经被报告出来，不需要再保留这部分读信息；剩下的就是有明确先后顺序的R/W操作，这部分读操作不会和后序的该线程的写操作构成竞争，因此也没必要保留。因此，每次执行完R/W分析，都需要删除历史读VC。
• 如果当前线程执行读操作，那么对于W/R数据竞争，类似W/W分析方法，采用常量比较就能知道两个操作是否是并发的，然后更新epoch到历史读VC中。

论文中给出的例子：

FastTrack举例

其中C0表示第一个线程的VC，C1表示的是第二个线程的VC，Lm表示的是锁m上的VC，Wx表示就是epoch形式的逻辑时钟。我们可以很直观的看出Wx变化以及两个线程VC的变化以及锁m上的VC的变化。

FastTrack举例2

这个例子详细的说明了Wx的epoch变化以及Rx在epoch和VC之间转换的变化的情景。

从上面的两个例子也可以发现，我们只是针对共享内存单元使用了epoch形式的逻辑时钟，但是对于同步对象，我们依然要保留VC形式的逻辑时钟，毕竟线程之间通过同步对象来进行VC的合并。根据论文中的调查，程序中96.8%的操作都是读写操作，剩下很少一部分是同步操作，因此尽管我们在同步对象上保留了VC形式的时钟，但是从整体上来说，时间复杂度接近于O(1)，对比Djit+算法，复杂度是大大降低了。

不知道看完FastTrack，大家是否能够更深入的理解这么设计的道理，以及和Djit+之间的本质区别，好好体会一下的话，应该是不难的。