基于Lockset的数据竞争检测方法汇总（三）

        上一篇文章中我们看到了有关共享对象状态变迁在Eraser基础上进行的改进，但是改进的不是特别明显，下面这篇论文不是单纯的用Lockset作为数据竞争检测方法，而是采用的Djit+以及改进的Lockset方法结合来进行动态数据竞争检测。

        Djit+方法在这篇文章中已经说得比较明白了，想了解的同学可以看这里。

        改进的Lockset方法用到了Djit+中的一些概念（后面会提到），不过这里我们还是主要看一下共享对象状态变迁，如下图所示:

        从这张状态变迁图中可以很明显的发现有点生命周期的味道，至少乍一看我们发现状态之间有些是可逆的，这点和前两篇文章有很大的不同，那么下面就介绍一下在这张状态变迁图中各个状态所传达的信息。

barrier，在图中经常出现，那到底在这个状态图中代表什么呢，从Wiki来看，一个 barrier就是一个同步方法，只有当所有的线程都到达这个点才能继续进行后续处理，而在这里的话，一旦所有的线程到达barrier，那么就可以重新初始化C(v)为所有可能的locks。

Clean：每当所有线程执行到barrier后，就会到达这个状态进行C(v)的重新初始化，进而进入到Exclusive状态。

Virgin：这个状态和Eraser中很像，不过这里多了一个barrier，但是由于还是在初始化线程中并且没有写操作，因此不必跳转到Clean。

Initializing：一旦有写操作访问，那么就会转到这个状态，这个状态相当于前面Eraser的Exclusive状态，但是如果有barrier的话会进入到Clean状态。

Shared：这里的Shared状态和上一篇文中的Shared状态是一样的，将Read Shared和Shared Modified组合在了一起。

Empty：和上一篇文中的Conflict状态有点类似，都是在Shared状态中如果C(v)={ }就会转到这个状态，然而区别在于，Conflict状态是最终终止状态，而在Empty状态，如果有barrier的话，还会进入到Clean状态。

Exclusive：在Clean状态，第一个进行访问操作的线程就会使得状态进入到Exclusive状态，如果相同的线程进行读/写，不会改变状态，这个和Eraser中的Exclusive是一样的，不过，这里发现Exclusive状态还能够回到Shared和Empty状态。

        好了，这些表面的信息分析的差不多了，那这个状态转换图背后想传达什么呢？

        图中一眼就能看出有一个环路，因此通过添加Exclusive和Clean，就能够实现共享对象的ownership的传递，不过这种传递所依据的媒介是barrie，上一篇文章中ownership传递依据的媒介是owner thread（但是很遗憾的没有能够完成Exclusive和Shared两个状态之间的环路传递），这也是这篇文章的一个改进点，因此我才会说有一点生命周期的味道。

        如果我们去掉Exclusive和Clean状态以及相关状态转化边：

        我们可以发现这个和Erase没有多大区别，因此传达出的信息就是耦合度 太高了，也是说太过于依赖载体barrier，不过作为针对某一 特殊条件进行的改进也是可以的，不过还没有看到做的比较全面的状态转换（还需要多读论文）。

        说完了状态转换，论文中还提到了在使用Lockset方面的一些优化，在上面两篇论文中，由于没有注入任何Happens-Before关系模型，因此采用的基本都是对共享变量的每次访问操作都需要进行精细操作，因此效率是比较低的。引入了Happens-Before之后就可以省去很多的不必要的Lockset检测：

        相同的time-frame中，只需要对共享变量的第一次读和写进行Lockset检测（相同的time-frame表示后续对共享的操作间隙不存在release 同步操作，最多就是有acquire 同步操作-即lock操作，因此首次读写的Lockset是后续读写的Lockset的子集，因此后续读写操作进行精细化操作将不会获得任何额外的信息）。

        改进的Lockset算法可以实现分析出一些潜在的数据竞争，然后交给Djit+算法进行分析，到底哪些是真的数据竞争。如果某个共享变量当前的C(v)不为空的话，那么Djit+算法就不需要对该变量的历史执行时钟进行Happens-Before分析，因此这两种方法相辅相成，效率上和精度上理论上比前面两篇文论都要提高不少（不过没有正真实现，有兴趣的同学可以研读论文试着实现，和前面两种两种方法对比一下）。

 下一篇文章的话同样也是分析Lockset状态图的转换（但是基于Threadset的）！