基于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技术栈

Java序列化技术即将被废除!!!

1463
来自专栏Java学习网

书写高质量代码之状态维护

状态之始 我们第一眼接触新事物所触发的思考方式,决定了以后我们看待这样事物的角度,进而影响更深层次的理解和行为。 编程相对于人类历史的进程而言,不过是个六七岁孩...

2834
来自专栏PHP在线

从零开始学设计模式(1):基础编程模式

Introduction 俗话说,“PHP是世界上最好的语言”,因为PHP什么都能干。但是在PHP编程中,你是否会遇到这样的困惑:明明是相同的需求,但是之前写的...

3607
来自专栏PHP实战技术

PHP面向对象编程基本原则

首先祝大家节日快乐!!! ? 额,不知道你们剁手没,小梦是没有!整整已经错过了第九个年头! ? 小伙伴是不是有一种感觉,PHP入门的时候简直爱不释手,总是把 ...

3349
来自专栏take time, save time

python 爬虫 入门 commit by commit -- commit5

代码你可以在https://github.com/rogerzhu/relwarcDJ 上得到,并且带有我完整的commit记录。

500
来自专栏Jed的技术阶梯

Java设计模式之命令模式

假设某个项目组分为需求组(Requirement Group,简称RG)、美工组(Page Group,简称PG)、代码组(Code Group,简称CG),还...

673
来自专栏Java学习网

书写高质量代码之状态维护

状态之始 我们第一眼接触新事物所触发的思考方式,决定了以后我们看待这样事物的角度,进而影响更深层次的理解和行为。 编程相对于人类历史的进程而言,不过是个六七岁孩...

3625
来自专栏个人随笔

Java核心技术(Java白皮书)卷Ⅰ 第一章 Java程序设计概述

第1章 Java程序设计概述 1.1 Java程序设计平台  具有令人赏心悦目的语法和易于理解的语言,与其他许多优秀语言一样,Java满足这些要求.  可移植...

32010
来自专栏精讲JAVA

Gof设计模式之单例模式(一)

今天开始更新设计模式系列,题目中Gof指的是《Design Patterns: Elements of Reusable Object-Orie...

2065
来自专栏Golang语言社区

Golang语言社区--Go基础课程第一节聊聊Go语言

提及Go语言,有些人还是很陌生,不过更多的人是有所耳闻;还有一些人已经开始接触学习了。越来越多的人开始留意她,特别是再大数据下Go语言本身层面支...

55615

扫码关注云+社区