基于Happens-before的数据竞争方法汇总 (二)

Happens-before方法中最基础的方法Djit+,Djit+使用向量时钟VC进行数据竞争分析。下面这篇文章介绍的是FastTrack算法,在Djit+基础上进行的改进,将Djit+的时间复杂度从O(n)降到接近于O(1)。首次看的同学还是建议先看我之前写的有关介绍Djit+的相关基础内容。

Reference

http://race-wordpress.stor.sinaapp.com/uploads/2016/01/FastTrack-Efficient-and-Precise-Dynamic-Race-Detection.pdf

Djit+方法每次进行数据竞争分析,都会遍历历史读VC或是历史写VC,这个过程的复杂度是O(n)的,FastTrack(FT)正是在这个点上进行了算法的改进。首先需要明确的一点就是,在一个没有数据竞争的程序中,每一次的写都是有明确先后顺序的;读就不一样,不一定要是顺序读,也可以是并发的。因此的话,对于每一个共享内存单元来说,我们不必像Djit+中那样保存一个历史写VC。保存一个历史写VC无非就是想找到所有竞争的写操作,但是其中有些已经早就被检测出来了,但是线程对应的entry还是存在于VC中,造成时间和空间上的冗余。因此,对于写历史,我们不保留VC,二是直接保留最近访问的线程时间戳就行,也就是epoch形式(timestamp@thread),这样的话,每次进行数据竞争分析的时候,就不需要像Djit+那样进行VC的遍历,而是常量级别的比较。具体来说:

  • 如果当前线程执行写操作,那么对于W/W数据竞争,只需要比较epoch中所对应的timestamp是不是大于当前线程所知道的thread的时间戳,如果是的话,就表明之前的写操作和当前线程的写操作就是并发进行的,报告一个W/W的数据竞争,更新epoch为当前线程的timestamp。
  • 如果当前线程执行写操作,那么对于R/W数据竞争,需要遍历历史读VC,类似Djit+,找到所有的R/W数据竞争。这里历史读VC是保存所有并发的读epoch的集合,并不是像Djit+中那样保存所有的线程,只是结构上相似,我们就直接采用历史读VC这种形式表示。最后分析完毕同样更新当前线程的timestamp并且删除历史读VC中所有的信息。这么做是考虑到并发的R/W数据竞争已经被报告出来,不需要再保留这部分读信息;剩下的就是有明确先后顺序的R/W操作,这部分读操作不会和后序的该线程的写操作构成竞争,因此也没必要保留。因此,每次执行完R/W分析,都需要删除历史读VC
  • 如果当前线程执行读操作,那么对于W/R数据竞争,类似W/W分析方法,采用常量比较就能知道两个操作是否是并发的,然后更新epoch到历史读VC中。

论文中给出的例子:

FastTrack举例

其中C0表示第一个线程的VC,C1表示的是第二个线程的VC,Lm表示的是锁m上的VC,Wx表示就是epoch形式的逻辑时钟。我们可以很直观的看出Wx变化以及两个线程VC的变化以及锁m上的VC的变化。

FastTrack举例2

这个例子详细的说明了Wx的epoch变化以及Rx在epoch和VC之间转换的变化的情景。

从上面的两个例子也可以发现,我们只是针对共享内存单元使用了epoch形式的逻辑时钟,但是对于同步对象,我们依然要保留VC形式的逻辑时钟,毕竟线程之间通过同步对象来进行VC的合并。根据论文中的调查,程序中96.8%的操作都是读写操作,剩下很少一部分是同步操作,因此尽管我们在同步对象上保留了VC形式的时钟,但是从整体上来说,时间复杂度接近于O(1),对比Djit+算法,复杂度是大大降低了。

不知道看完FastTrack,大家是否能够更深入的理解这么设计的道理,以及和Djit+之间的本质区别,好好体会一下的话,应该是不难的。

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闻道于事

js登录滑动验证,不滑动无法登陆

js的判断这里是根据滑块的位置进行判断,应该是用一个flag判断 <%@ page language="java" contentType="text/html...

6848
来自专栏跟着阿笨一起玩NET

c#实现打印功能

2782
来自专栏落花落雨不落叶

canvas画简单电路图

62111
来自专栏C#

DotNet加密方式解析--非对称加密

    新年新气象,也希望新年可以挣大钱。不管今年年底会不会跟去年一样,满怀抱负却又壮志未酬。(不过没事,我已为各位卜上一卦,卦象显示各位都能挣钱...)...

4918
来自专栏杨龙飞前端

scrollto 到指定位置

2514
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2645
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2070
来自专栏张善友的专栏

Silverlight + Model-View-ViewModel (MVVM)

     早在2005年,John Gossman写了一篇关于Model-View-ViewModel模式的博文,这种模式被他所在的微软的项目组用来创建Expr...

2978
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

4868
来自专栏转载gongluck的CSDN博客

cocos2dx 打灰机

#include "GamePlane.h" #include "PlaneSprite.h" #include "BulletNode.h" #include...

5486

扫码关注云+社区