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

对于搞数据竞争检测方向的人来说，Lockset方法大家肯定不陌生，作为一个刚入门数据竞争检测方向的我来说，就和大家总结一下我近期有关Lockset方法的一些研究和心得。

      Lockset方法研究比较早可以追溯到1997年Eraser那篇论文，被引用无数次，非常经典的方法。

      Reference

Savage S, Burrows M, Nelson G, et al. Eraser: A dynamic data race detector for multithreaded programs[J]. ACM Transactions on Computer Systems (TOCS), 1997, 15(4): 391-411.

这篇论文中提出了基于Lockset的动态数据竞争检测方法。这篇论文的出发点非常简单明了，在多线程程序中，我们一般都会使用锁对临界区进行保护，临界区中包含一般都是共享变量的访问操作，如果一个共享变量在程序多线程执行过程中能够始终被一个或多个锁保护的话，那么在该共享变量上肯定不会发生数据竞争。反之，则有可能发生数据竞争。正是从这个作为出发点，论文中提出了最简单的Lockset算法：

Simple Lockset Algorithm

1、Initialization

     对于每个线程t，都会维护一个locks_held(t)表明当前获得的锁集

     对于每一个共享变量v，这个变量在初始化的时候获得程序执行过程中的所有可能锁集C(v)

2、Refinement

当前线程对该共享变量的每次访问（读/写），更新C(v)=C(v)  ∩ locks_held(t)

     如果C(v)为{ } ，那么就报告一个警告

上述 算法简单明了，但是有一个严重的问题就是太严格了有木有，什么优化都做不了，编译器会疯掉的，程序员也会疯掉的，编程简直没有任何艺术。于是乎，就有了稍微的改进，来弱化这种强同步关系。

Improved Lockset Algorithm

如何改进呢，我们不妨考虑一下我们平时经常使用的锁进行同步过程中有没有违反上述严格同步关系但是又不产生数据竞争的情况。

     1、Initialization：共享变量初始化的时候，这个时候这个共享变量只在一个线程中被访问，就是初始化线程，其他线程是访问不到的（除非是初始化失败，这里先不考虑这种已异常情况），此时即使没有锁保护，也不会产生数据竞争。

     2、Read-shared data：这个共享变量出生到现在只有在初始化的时候被写访问过，其他后续线程对这个共享变量只有读操作，那么也不会产生数竞争（数据竞争至少要有一个写操作）。

     3、Read-Write locks：经常会使用到读写锁（一种允许多个线程获取读锁，只允许一个线程获得写锁；获得了读锁之后，写锁将会被阻塞，直到所有获得读锁线程释放；而获得写锁之后，所有读锁将会被阻塞，直到获得写锁的线程释放），这时候是允许多个线程获得读锁并对共享变量进行读访问的。

     上述三种情况在我们的实际使用中是非常常见的，因此针对这三种情况的话，改进的Lockset算法采用了状态图来描述上述共享变量生命周期的变化以及根据状态图怎么实施我们动态数据竞争检测。

     这个状态转化图已经很明显说明了共享变量的状态转换，透过这个转换图，那如何进行数据竞争检测呢？

     可以发现根据上述我们提出的三个问题中的前两个，我们在进行锁集精细化的过程中（即做交运算） ，如果最终C(v)={ }，只有在Shared-Modified状态时才会报数据竞争警告。那么第三个问题如何解决呢，因为有读写锁的存在，我们必须精确的区分读和写操作，因此在之前的线程的held_locks基础上，又添加了一个write_locks，表示当前线程在写模式下获得的锁（写模式简单的来说主要包括读写锁的写锁pthread_rwlock_wrlock以及普通互斥锁pthread_mutex），重新改进上述的算法如下：

1、Initialization

     对于每个线程t，都会维护一个locks_held(t)表明当前获得的锁集

     对于每一个共享变量v，这个变量在初始化的时候获得程序执行过程中的所有可能锁集C(v)

2、Refinement

当前操作是读访问操作，C(v)=C(v)  ∩ locks_held(t)

     当前操作时写访问操作，C(v)=C(v)  ∩ write_locks(t)

     如果C(v)={ }，那么就报数据竞争报告

     可能看到这里有些疑问，我们不妨来细细推导一下。

     假设当前线程访问操作只有读访问操作（除了初始化线程有写访问操作），那么任何的访问做的精细操作和之前的算法做的工作是一样的，而此时C(v)获得的包括读锁和写锁（这里的读锁指的就是pthread_rwlock_rdlock，这里的写锁指的就是pthread_rwlock_wrlock以及pthread_mutex），此时共享变量处在的状态就是Shared；而如果此时有任意一个线程的写访问操作出现的话，那么共享变量的就会切换到Shared-Modified，在这个状态中，进行的精细操作最后的结果就是C(v)只包含能够写锁（能够保护写的上述两种锁），之前单单能够保护读的锁就已经从C(v)中剔除了，后续如果这些剔除的读锁继续访问的时候 ，共享变量就不会受到任何保护了。

     看完这篇文章是不是大受启发呢，本人是大受启发，因此果断实现了这个算法，使用Pin框架比较容易实现，动态对要进行监测的代码进行插桩，然后作分析。我把代码共享在这里

但是方法过于简单往往就是存在很多问题的，Eraser的问题就是存在很多误报，误报类型不胜枚举，作为刚入门的我来说我想到的有如下：

     1、数组，对象中不同区域或是字段的访问

     2、良性的数据竞争（不会影响程序结果），比如生产者消费者模式

     3、不支持其他同步操作，比如create，join，wait，signal，barrier，condition variable等

     4、不支持变量ownership的变更

     等等。。。。。

     举个简单例子

    主线程main new了一个共享变量（无任何加锁操作），传递了一个指针给第二个线程，然后 就不再对其进行访问

    第二个线程对这个共享变量进行读写操作（无任何加锁操作），然后delete了这个共享变量

利用Eraser检测的话就是明显的误报！！！

通过这篇文章能够把握 到Lockset原始脉络，以后的一些Lockset算法都是在此基础上改进的，基于我上面提出的Lockset方法的误报，进行的比较细致和针对性的改进，有的也被整合进Happens-Before方法中。