基于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方法中。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

数据压缩算法LZO (C#)

LZO 是致力于解压速度的一种数据压缩算法,LZO 是 Lempel-Ziv-Oberhumer 的缩写。这个算法是无损算法,参考实现程序是线程安全的。 实现它...

52490
来自专栏水击三千

UML学习-状态图

1.状态图概述 状态图(Statechart Diagram)主要用于描述一个对象在其生存期间的动态行为,表现为一个对象所经历的状态序列,引起状态转移的事件(E...

302100
来自专栏happyJared

Elasticsearch地理坐标类型(Geo-point)在Spring Data ES中的常见使用问题整理解答

  下文整理的几个问答,本人在实际应用中亲身经历或解决过的,主要涉及Elasticsearch地理坐标类型(Geo-point)在Java应用中的一些特殊使用场...

49510
来自专栏数据科学

python流数据动态可视化

“流数据”是连续生成的数据,通常由某些外部源(如远程网站,测量设备或模拟器)生成。这种数据在金融时间序列,Web服务器日志,科学应用程序和许多其他情况下很常见。...

83130
来自专栏蓝天

高质量C++编程补充条款

介绍高质量C++编程的书籍很多,而且都非常好,这里主要针对已有书籍较少涉及到的代码格式条款进行补充。代码是程序员脸面,清清爽爽和干干净净的代码是程序员高职业素质...

12220
来自专栏JackieZheng

把玩爬虫框架Gecco

如果你现在接到一个任务,获取某某行业下的分类。 作为一个非该领域专家,没有深厚的运营经验功底,要提供一套摆的上台面且让人信服的行业分类,恐怕不那么简单。 找不到...

62540
来自专栏大闲人柴毛毛

高质量编程的金玉良言——依赖倒转原则

生活中的例子: 电脑的品牌有很多,但电脑中的所有部件都有标准的接口,不同的厂家都是按照标准去生产各个部件,这些部件的内部实现不同,但接口都是一样的,这样的话,如...

33170
来自专栏zhisheng

Java研发方向如何准备BAT技术面试答案(下)

本文是针对文章《 Java研发方向如何准备BAT技术面试(超级干货)》里面的算法、数据结构、Linux和操作系统问题的一些答案。如有错误,还请各位网友指正。多谢...

1.1K340
来自专栏xingoo, 一个梦想做发明家的程序员

Elasticsearch——multi termvectors的用法

前一篇已经翻译过termvectors的使用方法了,这对于学习如何使用tf-idf来说是很有帮助的了。 更多内容参考我整理的ELK教程 什么是TF-ID...

221100
来自专栏北京马哥教育

shell十三问,为linux学习打基础(一)

本文整理并转自CU上的帖子[学习共享] shell 十三問?,此贴是2003年发表的,但却是相当不错的linux基础知识汇集贴,原帖主使用的台湾风格,本文加以简...

41240

扫码关注云+社区

领取腾讯云代金券