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

     今天讲的这篇文论中提到的Lockset方法同样也是和Happens-Before结合来进行动态数据竞争检测，这篇论文中使用的Happens-Before方法不是上一篇文章中提出的Djit+方法，而是使用Threadset方法，同时这篇论文提出的自适应检测方法能够在Threadset和Lockset自由切换，并且在检测共享对象的粒度上也是自适应的（这里的话不会提如何自适应的，将会在以后的文章中提到）。

Reference：

Yu Y, Rodeheffer T, Chen W. Racetrack: efficient detection of data race conditions via adaptive tracking[C]//ACM SIGOPS Operating Systems Review. ACM, 2005, 39(5): 221-234.

     我们还是主要来关注一下Lockset的状态变迁在这篇文章中是如何进行的。

     在对Lockset进行分析之前，我们有必要需要知道文中使用的Happens-Before方法，这里的话就简单理解方法，不会非常细致的展开说明，只要能够有助于我们立即Lockset方法就行。

Happens-Before方法：Threadset

     此方法和Djit+类似，Threadset为每一个共享变量x维护一个并发访问集Sx，并发访问集中的元素就是<t,Bt(t)>（t表示的就是线程t标志，而Bt(t)表示的就是线程t最近对x进行访问的时钟）。Sx中的元素数目会随着访问增加或是减少，这是因为Sx使用hb关系来检测两个访问操作是否并发，当线程t对x进行访问的时候，Threadset会将<t,Bt(t)>添加到Sx中，然后检查是否存在<u, k>∈Sx，使得k ≤ Bt(u)，如果存在就表明<u,k>和当前的访问操作具有hb关系，所有从Sx中删除<u,k>，那么最后Sx中剩下的都是并发的访问。通过这个可以对Lockset报告的数据竞争进行检测，来判断到底哪些是真正的数据竞争。

     Threadset方法就简单的介绍一下（和后面的Epoch方法有点类似，后面文章会重点讲解）。下面的话我们就来看一下这篇文章中Lockset状态变迁图是怎么设计的：

      这些状态在前面三篇文章中反复出现过了，不过这里状态变迁和前面有很大的不同，那么首先就来认识一下这些状态所表达的信息：

      Virgin：初始化

      Exclusive0：同一个线程访问（不区分读和写），这个状态和前面的Virgin都不用跟踪Sx和Cx（共享变量的锁集）

      Exclusive1：第二个线程访问，和前面第二篇文章有点类似（不清楚同学可以再去回顾一下），这么设计的主要目的还是考虑的实际使用的过程中，类似于主线程初始化一些共享对象，然后交给子线程完成必要的工作（共享对象的ownership转交给子线程了）。因此的话这里使用|Sx|=1说明当前对这个共享变量并发的访问操作只有second thread，这个状态我们不用去跟踪Cx的变化。

      Shared-Read：这个状态和前面文章提到的状态的语义 是一致的（多个线程对共享变量读），在这个状态只需要关注Cx（我们在Exclusive1状态的时候，如果|Sx|>1并且访问操作是读，那么就会转到这个状态，此时Cx就是当前线程获得的锁集），不用关注Sx的变化。

      Shared-Modified：这个状态和前面文章中提到的状态语义一致的（多个线程对共享变量有写操作），在这个状态同样我们只需要关注Cx（如果我们在Exclusive1状态，由于一个其他线程的写操作导致 |Sx|>1 ，那么就会进入到这个状态，此时的Cx就是当前线程获得的锁集；如果我们在Shared-Read状态进行了一个写操作，只要Cx不为空，就会进入到这个状态，此时的Cx就是Shared-Read状态时的Cx）。

      Exclusive2：这个状态我们只需要关注Sx的变化，只有Shared-Read和Shared-Modified这两个状态才能够进入到这个状态，前面两个状态我们只关注了Cx，当Cx为空的时候，会进入到这个状态，此时的话，我们就会得到潜在的数据竞争，但是其中有很多的误报，因此我们还需要通过Sx来区分哪些是真正的数据竞争（就必须等到有并发操作发生），这里还有一点非常重要，由于当前状态不包括并发操作，因此我们还需要初始化Cx为当前线程获得的锁集。

     Shared-Modified2：在Exclusive2状态，如果|Sx|>1就会进入到这个状态，表明有并发操作发生。这个状态我们需要去关注Cx和Sx，如果Cx不为

{ }，并且|Sx|>1 那么继续停留在这个状态，说明有并发操作，但是有公共的锁集保护；如果|Sx|=1，表明当前只有一个线程的操作，因此回到状态Exclusive2,；而如果Cx为空并且|Sx|>1的话，那么表示当前有并发操作但是没有公共的锁集，就会报数据竞争警告。

     看到这里的话，不知道有没有发现什么问题，如果按照我上面说得那样，Sx保存的都是并发操作，那么为什么还要结合Lockset方法呢，正如Shared-Modified状态描述的那样，发生数据竞争警告只有在Cx为空并且|Sx|>1？？？我看这张图的时候也是顿了一下，不过如果我们结合这个算法的伪代码来看的话，那么就一点不奇怪了。

通过伪代码可以发现，这里的时钟同步和我们在Djit+中的有很大的区别，Djit+中我们会在Release同步操作之后增加Vector Clock中的当前线程的clock值，但是此算法中只有在Fork（也就是创建线程）操作时会添加当前线程t的clock值，那么文章中所说的并行就不是真正意义上全局的并行，而是有可能的并行（没有考虑锁之间的同步操作，只有线程创建和等待之间的同步操作），这样的并行首先能够确保每个线程内部对共享变量x的最新访问，同时利用Fork和Join操作可以同步一部分多个线程对共享变量x的最新访问，由于hb关系没有包含Lockset，因此最后我们还要用Lockset方法再检测一下。

      看到这里的话，我想有关Lockset中的状态转换大家应该有比较清楚的了解。另外这篇文章也是给了一个很好的启示就是对于hb关系，我们使用的过程中可以选择部分同步关系，然后最后用其他同步关系再去验证之前的并行是否有效。

到这里的话，有关Lockset方法就要告一段落了，后续工作将会主要放在使用Happens-Before方法的运用上，如果有相关Lockset

方法还会继续更新，敬请期待！