基于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 条评论
登录 后参与评论

相关文章

来自专栏Java Edge

Java多线程中join方法的理解

3396
来自专栏上善若水

L016使用/dev/random生成随机数

很多库例程产生的“随机”数是准备用于仿真、游戏等等;它们在被用于密钥生成一类的安全函数时是不够随机的。其问题在于这些库例程使用的算法的未来值可以被攻击者轻易地推...

824
来自专栏Hadoop数据仓库

HAWQ取代传统数仓实践(七)——维度表技术之维度子集

        有些需求不需要最细节的数据。例如更想要某个月的销售汇总,而不是某天的数据。再比如相对于全部的销售数据,可能对某些特定状态的数据更感兴趣等。此时事...

1935
来自专栏Linyb极客之路

浅谈黑盒测试和白盒测试

  从图中可以直接看出来,黑盒测试就当整个程序是个黑盒子,我们看不到它里面做了些什么事情,只能通过输入输出看是否能得到我们所需的来测试。而白盒测试可以当盒子是透...

1011
来自专栏数据结构与算法

P3376 【模板】网络最大流

题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。 输入输出格式 输入格式: 第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个...

2698
来自专栏DannyHoo的专栏

iOS开发中使用算法之二分搜索算法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

592
来自专栏数据分析

[数据分析工具] Pandas 功能介绍(二)

我们需要看第一季度的数据是怎样的,就需要使用条件过滤

2107
来自专栏tkokof 的技术,小趣及杂念

“连连看”小析

近段日子与几位同事聊到了“连连看”这个小游戏,感觉还颇有些趣味,虽然其本身规则并不繁琐,但玩起来确实很能让人投入。出于自己的一点追究癖,自己这几天还认真考虑了...

331
来自专栏机器之心

资源 | 像「花书」一样排版:Ian Goodfellow「亲授」的高级LaTex教程

机器之心整理 作者: Ian Goodfellow 参与:邱陆陆 当地时间 3 月 1 号,深度学习知名同名教材《Deep Learning》的第一作者 Ian...

42710
来自专栏吉浦迅科技

DAY25: 阅读硬件的多线程

994

扫码关注云+社区