MultiRace-Efficient on-the-fly data race detection

     最近在研究数据竞争检测方法，之前的工作是参考了Eraser这个工具1997年提出的基于Lockset方法的动态数据检测，

在Interl的Pin框架的基础上对方法进行了复现（论文中有关动态注解没有完成，这部分以后再整合）。在后续的论文研读中

发现大多数的方法都是基于Happens-Before和Lockset方法结合的思路，于是就看了下面这篇非常具有代表性的两种方法综

合的论文。

Reference：

Pozniansky E, Schuster A. Efficient on-the-fly data race detection in multithreaded C++ programs[M]. ACM, 2003.

      这篇论文也是中所说的方法也是on-the-fly方法（个人理解就是程序执行过程中监测，与之相对应的就是程序执行完成后
利用log文件中信息进行检测），结合了HB方法和Lockset方法进行的动态数据竞争检测，并且加上了必要的改进。下面就来
说一下这两种方法在本文中的利用。

Happens-Before方法-Djit+
本文中HB方法使用的是基于Vector-Clock，改进之后的算法起名为Djit+。使用Vector-Clock，可以保留每个线程的时间戳，对于
一个正在执行的线程来说，它的Vector-Clock就是它当前所知道的其他线程的最先进展（自己当然知道自己的最新进展）。因此，
对于每个访问操作，都可以知道当前访问操作是不是目前位置最新的访问操作。而数据竞争产生，必然会存在至少两个访问操作
的并行执行，其中至少有一个是写访问并且是不同线程的。因此通过HB关系就能够判断两个操作是否是并行执行，因此检测共享
变量的读和写操作就能够检测出执行过程中产生的数据竞争。
这样效率太低了，对于一些稍微大一点的程序而言，共享变量很多，读/写频繁，如果检测每一次读/写，时间和空间上性能将大大
降低，可不可以减少检测的数量呢？答案肯定是有的，论文中提出了一个time-frame的概念，就是一个时间戳，两个同步操作之间
的SV(共享变量)访问操作会被标记为同一个time-frame，这样的话，同一个time-frame的SV访问只需要对第一次读/写操作进行检测
后续的读写操作不会改变time-frame的值，因此也不会有额外的信息产生。另一方面，考虑如果a和b没有发生数据竞争（假设）a
在b之后发生，那么a和b‘（b之前的操作）肯定不会发生数据竞争，因此，我们只需要记录对SV访问的最近的一次读操作和写操作
的time-frame就能够 满足我们检测 数据竞争。

根据上述这些性质，Djit检测的方法如下：

初始化
        对于每个线程t，给定一个VC，其中VC[t]就初始为1
        对每个共享变量v，初始化两个VC，一个是写VC，另一个是读VC，分别表示最近对该SV进行写操作线程的time-frame以及最近
对该SV进行读操作线程的time-frame
        对于同步对象（锁），同样初始化一个VC（VC[i]全为0）

遇到同步对象Release操作
        表明线程t进入了一个新的time-frame（同步操作有明确的先后顺序），VC[t] += 1，同时，同步对象VC中的每个clock需要被更新
为与当前线程VC比较中较大的那个值（同步对象稍后会被其他线程获取）


遇到同步对象Acquire操作
        当前线程的VC的每个clock更新为与同步对象的VC比较中 较大的那个值（当前线程通过其他线程 得到它所知道的所有线程的最
新进展）


遇到共享变量的读/写操作
        当前线程t会更新SV的改线程对应的历史访问time-frame值，读操作更新读VC[t]，写操作更新写VC[t]
        对于SV的读操作，将写VC和当前线程的VC进行比较，看共享变量写VC[u]>=当前线程VC[u]（是否有其他线程知道最新的写访问
而非t本身）
        对于SV的写操作，同理需要比较 写VC[u]>=当前线程VC[u]，以及读VC[u]>=当前线程VC[u]（是否有其他线程知道最新的读访问
和写访问）
        上述比较成立就会报告数据竞争，也就是说当前线程所知道的访问操作并不是最新的，有其他线程的访问操作超过了当前线程的最新进展，那么肯定就是这两个线程访问操作没有同步。


后续将分析改进的Lockset方法！