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

前一篇文章提到的是使用Lockset最经典的方法，但是存在很多误报，针对这些误报产生的原因，有很多分析并改进了原始的Lockset方法，今天主要和大家谈的就是有关Lockset中状态ownership transition的一种改进。

Reference

von Praun C, Gross T R. Object race detection[C]//ACM SIGPLAN Notices. ACM, 2001, 36(11): 70-82.

乍一看这篇文章是将有关在Java对象层面进行的数据竞争检测，说了一大堆有关Java对象自身具有的一定特性，然后基于这些特性怎么进行面向对象的数据竞争检测，为了保证数据竞争检测的精确性，引入了Ownership Model，而这就和Lockset相关了，因此，我将 重点谈谈在Lockset方面的改进以及这样做有什么好处，而Object-oriented Data Race Detection有兴趣同学可以仔细去读读这篇文章（虽然是2001年的，但是也比较经典）。

如果没有读过我之前的Lockset方法汇总一，建议大家先去看一看那篇，不然继续往下看的话，可能理解会有一定的难度。

在进行数据竞争检测的时候，我们需要去跟踪共享对象，之前Erase提出Lockset方法给我们展示了共享对象整个生命周期状态的一些变化，细心的同学可能会发现，这样的恭喜对象的声明周期是不完善的。为什么呢？？只管来说，对象有出生必有死亡，因此对象在死亡的过程中必然会最终只进入到一个线程中而被销毁，而在Eraser状态图中并没有体现这一点（状态图最终的状态就是Shared-Modified），因为它没有将状态变迁考虑周全。因此共享对象状态变迁，提出了在Erase Lockset状态上的扩展，如下图所示：

这张状态转换图和Eraser中状态转化图最明显的两处就是Eclusive2和Conflict这两个状态，下面就和大家讨论一下有关这张状态转换图中的一些信息。

Virgin：这个状态和Eraser中的区别就是它考虑了在对象初始化构造过程中可能会有并发访问，如果有的话就直接转到Conflict状态

（这种情况个人感觉应该是一些在静态函数中初始化对象时会产生-比如说经典的双检锁问题，如果是对象的构造函数的话，不大可能）。

Exclusive：这个状态的话整合了Eraser中的Virgin和Exclusive，读/写都是在状态Exclusive。

上述两个状态的话，是归属给first owner，大家不妨想一想，多线程程序中最经典的一些应用就是主线程开一个循环，不断等待客户端的连接，有连接之后，初始化一些必要的对象，然后创建一个新的线程，把初始化的对象传递给新线程，新线程其实就是一个工作者线程，真正执行客户端需要的一些工作，新线程将要结束前，可能会结束这些对象信息。这样的场景和这张图非常吻合。

Exclusive2：这个状态就表明ownership的变迁，在first owner之后，第二个线程将会成为其second owner，注意的是，此时一旦ownership转交出去之后，first owner就没有ownership了，对于Exclusive2来说，first owner应该就是其他线程访问了，从图上也可以 直观的看出，因为ownership transition不可逆。

Shared read：和Eraser一样。

Shared modified：和Eraser一样。

Conflict：当产生数据竞争之后，就走到了这个状态，并且后续的任何读写都会停留在该状态。

这个状态转化图和我们预想的还是有些差距（后面会说），不过还是看一看这样的状态转换能够带来怎样的改进。

为了支持上面这种状态的变迁，我们有必要给每个对象配置一个threadId字段，用来标注这个对象是属于哪个线程的。每当一个线程访问这个对象的时候，首先就会比较这个对象的threadId是否和当前线程的id相同，如果相等的话，就直接访问；否则的话，就会激活下面的访问协议：

1、如果owner thread已经terminated，那么当前访问线程自然而然的就会继承这个对象，当前线程成为first  owner。

2、如果owner thread是active，那么访问线程就会发送异步的信号表明想要获得对象的ownership并且阻塞。owner 线程投票选择给哪个线程转交ownership，最终释放自己的ownership然后被转交的线程就成为了second owner。

3、如果owner thread阻塞了（join、sleep、wait）那么此时访问线程便会直接成为second owner，这里要保证的就是没有线程从阻塞变为活跃状态。

4、从second owner之后的运作和Eraser没有什么区别，也是对访问进行精细操作，然后如果锁集为空并且在shared modified状态，就报数据竞争警告。

上述的状态图相对Eraser来说减少了一些误报，上一篇文章中举得那个例子可以避免，但是从某种意义上来说也不是真正的声明周期的状态转化，因为本质上还是单调层次的，状态之间不可逆。因此对有些问题，使用该状态图还是爱莫能助，不过作为学习，我觉的这样循序渐进是一种好事，至少我们能够在原始的基础上进行改进，并且提高了数据竞争检测的精度。

该方法没有具体的实现代码，有需要的同学可以参考这里，结合我给出的Erase的代码，稍作改动即可。

下一篇文章的话同样也是分析Lockset状态图的转换（有一点真正意义上生命周期的味道）！