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

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

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最广为使用的并发库futures使用入门与内部原理

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

1201
来自专栏pangguoming

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

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

971
来自专栏北京马哥教育

运维开发:你可能会忽略的 Git 提交规范

如果你有一个项目,从始至终都是自己写,那么你想怎么写都可以,没有人可以干预你。可是如果在团队协作中,大家都张扬个性,那么代码将会是一团糟,好好的项目就被糟践了。...

891
来自专栏大数据文摘

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

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

1283
来自专栏乐享123

从MongoDB迁移到TokuMx

2188
来自专栏Python中文社区

用Python将word文件转换成html

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

6376
来自专栏月色的自留地

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

1716
来自专栏云加头条

Redis 设计思路学习与总结

下半年利用空余时间研究和分析了部分Redis源码,本文从网络模型、数据结构和内存管理、持久化和多机协作四个角度对redis的设计思路进行了分析,若有不正确之处,...

10.7K6
来自专栏DevOps时代的专栏

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

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

1002
来自专栏信安之路

ROP Emporium 挑战 WP

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

940

扫码关注云+社区