动态数据竞争检测方法实验分析(一)

之前的文章大致介绍了一下我们的动态数据竞争检测平台如何构建,这篇文章主要是在动态数据竞争检测平台上实现了之前介绍的数据竞争检测方法,我们扩展了其中的一些方法使得这些方法能够识别所有的Pthread库中的同步原语。

对比的方法主要如下:

: Eraser

: Djit+

: Helgrind+ (HG)

: FastTrack (FT)

: Loft

: Acculock (AL)

: MultiLock-HB (ML)

: SimpleLock (SL)

: SimpleLock+ (SL+)

上述10中方法在之前的文章中都简单介绍过,这里就不再重复介绍,如果有不太清楚的同学可以参考原始论文。

对这10种方法进行测评的目的主要想回答以下几个问题:

  • 各个检测方法的检测能力如何?
  • 各个检测方法对程序造成的影响如何?
  • 各个检测方法的扩展性如何?

##各个动态数据竞争检测方法的检测能力

检测能力的测评主要包括,检测率、误检率、漏检率、正确率以及错误率。

这里我们选择Google的data-race-test测试集,该测试集包含在谷歌开源的ThreadSanitizer中,我们提取了其中的96个小示例程序,然后将这96个小程序组合成一个应用程序Unittest。Unittest中包含了非常多的场景,很多场景都具有欺诈性并且对于一般的数据竞争检测器来说很难发现。

这里为了方便描述,给出如下定义:

FP Case:即False positive示例,数据竞争检测方法报告出了该示例中不存在的数据竞争。

TP Case:即True positive示例,数据竞争检测方法报告出了该示例中至少一个真实的数据竞争并且没有报告出任何不存在的数据竞争。

FN Case:即False negative示例,数据竞争检测方法没有报告出任何该示例中真实存在的数据竞争。

TN Case:即True negative示例,数据竞争检测方法没有报告出任何该示例中不存在的数据竞争并且该示例中也不存在真实的数据竞争。

TPN Case:即TP Case或是TN Case。

FPN Case:即FP Case或是FN Case。

对Unittest进行实验结果分析如下所示:

动态数据竞争检测算法检测能力实验结果

首先对于TP Case项,我们从图表中能够比较清晰的发现ML、TS能够检测到的数据竞争相对其他8种方法来说更多。主要是由于这两种方法都保留了一定数量的锁集的集合,TS中保留了并发读和写的segment集合,而ML中保留了一定数量历史访问。其次的话,我们可以发现单纯使用happens-before关系来检测数据竞争的Djit+、FT以及Loft方法检测能力低于使用hybrid混合算法的动态数据竞争方法。主要是这三种方法对线程执行交错比较敏感,会遗漏部分数据竞争。最后,可以发现基于Lockset算法的Eraser能够检测到的数据竞争更少。

然后对于FP Case项,我们从图表中能够比较清晰的发现Eraser误报的最多,因为该方法不考虑除加锁解锁以外的其他同步原语。其次发现AL和ML的误报也很多,ML在AL的基础上改进了一部分,因此相比AL少一些误报。在这就是HG、TS、SL以及SL+这三种方法也有相当一部分数量的误报。这些hybrid动态数据竞争检测方法至少会有5个误检,其中主要是因为我们在实现的时候对于printf、fget等库函数或是系统调用没有进行动态监视。而Djit+、FT和Loft这三种方法由于使用happens-before关系来检测数据竞争,因此基本没有误检,唯一的误检是由于ad-hoc隐式同步类型导致的,这部分相关内容会在后序的文章中介绍。

对于FN Case项,我们从图表中也能够比较清晰的发现Djit+、FT和Loft单纯使用happens-before关系检测数据竞争的方法有很高的漏检。而使用lockset算法或是hybrid算法的检测方法漏检率要低一些。主要是锁集算法对线程调度不太敏感。

对于TPN Case项,也就是检测的正确示例数目,我们发现Djit+、HG、TS、ML以及SL+有着比较高的得分。

对于FPN Case项,我们分析了一下其中被误检或是漏检的示例,结果如下表所示:

这里写图片描述

在表的FN Case项中,我们可以发现No Locks(数据竞争的两个操作没有任何锁保护)的比例很多,其次是False Continuous Locks(数据竞争的两个操作都有所保护,但是没有公共的锁),最后是No Continuous Locks(数据竞争的两个操作中只有其中一个操作有锁保护)。

在表的FP Case项中,我们发现Customized的比例很多,也就是我们称之为的ad-hoc类型的隐式同步。也可以发现Eraser忽视了大部分的同步原语。

后序将介绍动态数据竞争检测方法对程序造成的影响以及可扩展性两个方面的实验分析。

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我和未来有约会

[Silverlight动画]转向行为 - 介绍

转向行为(steering behaviors)这一术语,指的是一系列使对象行动起来像似长有智商的算法。这些行为都归于人工智能或人工生命一类,是让对象呈现出拥有...

1705
来自专栏大数据智能实战

基于seq2seq的中国古诗词自动生成技术

文本生成技术是深度学习赋予自然语言处理一项全新的技术,而刚好网上有这方面诸多的例子,因此趁着有空实现一下中国古诗的自动生成技术,还是挺好玩的。 具体步骤主要...

27210
来自专栏顶级程序员

Python与人工智能的关系原来是这样的...

人工智能掀起了世界的新一波科技浪潮,如今,你要是不懂点AI、机器学习和python都不好意思说你是现代人,那么python究竟和人工智能什么关系,为什么人工智能...

1025
来自专栏程序员互动联盟

【答疑解惑】失之毫厘谬以千里

1、scanf使用陷阱 ? ? 如果scanf中%d是连着写的如“%d%d”,在输入数据时,数据之间不可以加逗号,只能是空格或tab键或者回车键“1 2” 或 ...

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

21:苹果和虫子2

1:苹果和虫子2 查看 提交 统计 提问 总时间限制:1000ms内存限制:65536kB描述 你买了一箱n个苹果,很不幸的是买完时箱子里混进了一条虫子。虫子...

3638
来自专栏Python小屋

使用Python编写一个聪明的尼姆游戏

关于尼姆游戏的介绍请参考上一篇文章:一个傻傻的尼姆游戏及其Python实现,本文使用Python实现一个聪明的尼姆游戏。 在聪明模式中,计算机每次拿走足够多的物...

2847
来自专栏程序员宝库

每个程序员都应该收藏的算法复杂度速查表

这篇文章覆盖了计算机科学里面常见算法的时间和空间的大 O 复杂度。我之前在参加面试前,经常需要花费很多时间从互联网上查找各种搜索和排序算法的优劣,以便我在面试时...

672
来自专栏racaljk

博弈之最大-最小搜索算法

最近正在做一个人工智能的中国象棋,所以不可避免的接触到了博弈论,因为考虑到以后还会有所涉及 (alpha-beta search),所以写成了一片文章

1072
来自专栏张善友的专栏

.Net脚本语言Boo简介

      对软件工程来说,脚本语言相当于输送管,他们强大的富有表现力的语法是他们能够比较理想地处理软件开发过程中的外围特殊任务。脚本语言常用于批处理、小工具包...

17910
来自专栏Crossin的编程教室

分享一个强大的英汉词典开源数据库

之前我们通过程序整理过一份 Python 及编程相关的英语高频词汇表:我们用程序整理出了一份Python英语高频词汇表,拿走不谢!(回复 单词 查看代码及单词本...

1854

扫码关注云+社区