动态数据竞争验证方法(一)

动态数据竞争检测算法可以在不知道程序中是否存在数据竞争前提下执行,而动态数据竞争验证方法则是在知道程序中可能存在的数据竞争前提下,对这部分可疑的数据竞争进行验证,看这些数据竞争是否真的发生,同时也可以验证这些数据竞争是否对程序造成有害的影响。

Reference http://web2.cs.columbia.edu/~junfeng/09fa-e6998/papers/racefuzz.pdf 这篇文章提出的RaceFuzzer采取随机调度的方式来验证数据竞争是否是有害的,主要分为如下几个阶段:

Phase1 首先利用hybrid的动态数据竞争检测方法找到程序中所有的数据竞争,这些数据竞争将会构成一个数据竞争语句对集合。之前的文章已经分析很多hybrid的动态数据竞争检测方法,这里就不再重复。

Phase2 根据Phase1中得到的数据竞争语句对,在动态的时候调度线程尽量让这些数据竞争语句对能够临时地相遇(同时发生)。相关的算法如下所示,为了方便描述,这里给出相关的一些定义: • s:程序在执行过程中的状态 • Enabled(s):当前状态s下可用的线程集合,线程不可用表明当先线程阻塞在一些同步操作上 • Alive(s):当前状态s下还没有结束的线程集合 • Execute(s,t):返回线程t在当前状态s下执行语句之后的状态 • NextStmt(s,t):返回线程t在当前状态s下即将要执行的语句

首先输入RaceSet为Phase1中的竞争语句对集合,并且程序当前状态为s为初始状态s0。其中postponed集合用来保存认为干预中止的线程,初始的时候同样是空集。

从while循环也可以发现,只要当前有可用的线程,那么就会一直执行下去。否则的话,一旦当前状态存在没有结束的线程就表明程序陷入了死锁(L30)。

该算法调度线程的核心就是每次只让一个线程执行,并且是随机的挑选可用的线程(L5)。

当被选择的线程即将执行的语句在RaceSet中,也就是数据竞争语句。 • 如果此时postponed中存在其他的线程即将访问的操作和当前线程t即将访问的操作构成数据竞争,那么此时机会随机是否当当前的线程继续执行还是让postponed中的线程继续执行(如果有多个阻塞的线程那么会让所有参与数据竞争的被阻塞的线程都继续执行)。 • 否则的话,当前线程就会被阻塞中止执行。 下图展示的是一个数据竞争的例子:

其中存在两个数据竞争[5,7]和[1,10]。对于数据竞争[1,10]来说,如果线程1先到达1,那么此时会被阻塞等待线程2到达10,线程1被加入到postponed中,但是由于y初始为0,因此线程2会一直执行到结束,此时线程1就会从postponed中被移除。对于数据竞争[5,7]来说,如果线程1先到达5,此时就会被阻塞,当线程到达7时,此时就会被验证为一个数据竞争。而一旦随机挑选线程1继续执行,那么此时就会执行6导致程序出现错误,此时,数据竞争[5,7]就是一个有害的数据竞争。

上述数据竞争验证方法每次只能够允许一个线程执行,使得数据竞争验证较慢。并且由于其使用确定性阻塞来中止线程的执行,因此可能会引入新的死锁。同时该方法每次执行程序能够验证的数据竞争很少。

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python小白到大牛

有轻功:用3行代码让Python数据处理脚本获得4倍提速

Python是一门非常适合处理数据和自动化完成重复性工作的编程语言,我们在用数据训练机器学习模型之前,通常都需要对数据进行预处理,而Python就非常适合完成这...

18030
来自专栏我是攻城师

学习使用Lock+Conditionk编写三个经典多线程例子

在jdk5之后的高级并发包里面Lock接口可以替换原来jvm内置的锁synchronized关键字,同理使用Condition接口的await,signal,s...

6920
来自专栏乐享123

从MongoDB迁移到TokuMx

26680
来自专栏信安之路

ROP Emporium 挑战 WP

ROP Emporium 挑战是用来学习 ROP 技术的一系列挑战,本文就对于其中涉及的所有挑战记录一下 wirte up。

12200
来自专栏DevOps时代的专栏

你可能会忽略的 Git 提交规范

一直是 ESLint 的忠实用户,深知规范的重要性。然而,在新项目交接中,我被 Git Commit 规范逼疯了。才意识到自己的疏忽,于是便有了一探究竟的想法。

10920
来自专栏月色的自留地

AngularJS2+调用原有的js脚本(AngularJS脚本跟本地原有脚本之间的关系)

19260
来自专栏java一日一条

一个基于Java的开源URL嗅探器

今天,我们很高兴做一个分享,因为我所在的 Linkedin 公司 开源了我们做的一个ULR探测工具:URL-Detector Java 库。

16020
来自专栏大数据文摘

维基百科中的数据科学:手把手教你用Python读懂全球最大百科全书

几年前谁能想到,匿名贡献者们的义务工作竟创造出前所未有的巨大在线知识库?维基百科不仅是你写大学论文时最好的信息渠道,也是一个极其丰富的数据源。

17230
来自专栏琯琯博客

Git 提交规范

一直是 ESLint 的忠实用户,深知规范的重要性。然而,在新项目交接中,我被 Git Commit 规范逼疯了。才意识到自己的疏忽,于是便有了一探究竟的想法。

30320
来自专栏小巫技术博客

App性能优化浅谈

20030

扫码关注云+社区

领取腾讯云代金券