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

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

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

相关文章

来自专栏我是攻城师

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

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

512
来自专栏码洞

Python最广为使用的并发库futures使用入门与内部原理

在使用Python处理任务时,限于单线程处理能力有限,需要将任务并行化,分散到多个线程或者是多个进程去执行。

891
来自专栏pangguoming

黑盒测试和白盒测试的区别

1.        软件测试方法:白盒测试、黑盒测试、灰盒测试、静态测试、动态测试

531
来自专栏小巫技术博客

App性能优化浅谈

1093
来自专栏java达人

如何编写一个简易网络爬虫

感谢小臣投稿 本文将简述网络爬虫及其工作流程,结合个人实践,简单介绍如何使用HttpClient、HtmlParser第三方jar工具包,编写一个简易的网络爬虫...

1967
来自专栏月色的自留地

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

1586
来自专栏Python中文社区

用Python将word文件转换成html

序 最近公司一个客户大大购买了一堆医疗健康方面的科普文章,希望能放到我们正在开发的健康档案管理软件上。客户大大说,要智能推送!要掌握节奏!要深度学习!要让用户...

5396
来自专栏java初学

页面置换算法

52111
来自专栏DevOps时代的专栏

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

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

902
来自专栏大数据文摘

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

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

1053

扫码关注云+社区