基于Lockset和Happens-before的数据竞争方法汇总

之前的文章介绍都是单独使用lockset或是单独使用happens-before关系进行动态数据竞争检测的方法。单纯使用lockset算法,由于不考虑其他的一些同步原语,会导致很多的误报,但是该方法对线程交错不太敏感。单纯使用happens-before关系,该方法对线程交错比较敏感,因此会导致出现很多漏报。因此结合lockset算法和happens-before关系的混合(hybrid)算法由此而生。

Hybrid混合算法的思想主要有两种:

  • 首先利用happens-before关系找到所有潜在的并发的访问,然后利用lockset算法验证这些并发访问是否受到公共的锁集保护。
  • 首先利用lockset算法找到不受公共锁保护的潜在的并发访问,然后利用happens-before关系推导哪些访问之间没有确定性先后关系。

这篇文章中主要介绍的是第一种混合算法,主要相关的方法包括如下:

Helgind+

Helgrind+中提出了一种线程段(thread segment)用来分割一个线程的执行序列。通过线程段来进行happens-before关系的推导。同时结合lockset算法中的共享内存状态机在某些状态下判断是否构成数据竞争。该方法中每个共享内存单元只只能够保留最近的一个线程段,并且该方法中涉及到大量的状态 切换。

Helgrind+

ThreadSanitizer

ThreadSanitizer中同样也是使用线程段这个概念来分割一个线程的执行序列。和Hengrind+不同的是,该方法通过分析happens-before关系来保存所所有潜在的并发写segment集合,以及保存所有潜在的并发读segment集合并且在任意写segment之后发生。然后通过锁集算法验证是否并发的两个segment有公共的锁集保护其中至少一个是写segment。

ThreadSanitizer

Acculock

Acculock中使用FastTrack中提到的基于epoch的轻量级逻辑时钟来进行happens-before分析,同时对解锁操作增加时间戳,根据锁集的时间戳来去掉一些冗余的分析。由于该方法中使用保留的都是共享内存最后一次的读和写相关的epoch和锁集,因此混存在一定的误报和漏报。

Acculock

MultiLock-HB

MultiLock-HB方法是在Acculock方法上的改进,主要针对Acculock中固有的缺陷,因此采用类似ThreadSanitizer中保留一定长度的完整的历史读写访问信息,包括锁集和epoch,同时根据锁集的集合的包含关系,去掉一些冗余的分析。

这里写图片描述

SimpleLock

SimpleLock方法使用的假设是程序中一般不会发生使用两个不同锁的情况,一般都是由于没有加锁或是少加锁。因此该方法中不需要使用锁集来进行分析,而是直接统计共享内存有多少个锁保护。

SimpleLock+

SimpleLock+方法在SimpleLock的基础上,继续精简,使用布尔变量来表示共享内存访问是否有锁保护。

到此为止的话,基本的动态数据竞争检测相关的方法都已经介绍完毕,想要详细了解的同学可以参考这些论文。

后序将介绍对之前介绍的动态数据竞争检测方法进行的实验测评

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阿凯的Excel

或关系模糊匹配求均值(pandas插播版7)

上期用Excel的复杂函数解决了或关系模糊匹配求均值。本期和大家分享一下如何使用Python的Pandas解决该问题。 郑重说明:本期只是分享解决方案,且pan...

52280
来自专栏黒之染开发日记

PIXI输出base64图像

如果想使用 canvas 原生的 toDataURL ,参考这篇问答,以下代码是具体方法。但这个方法如果在iOS设备上使用,获取到的图像会上下翻转(效果相当于c...

16310
来自专栏数据分析

[数据清洗]- Pandas 清洗“脏”数据(二)

概要 了解数据 分析数据问题 清洗数据 整合代码 了解数据 在处理任何数据之前,我们的第一任务是理解数据以及数据是干什么用的。我们尝试去理解数据的列/行、记录、...

38040
来自专栏吉浦迅科技

DAY39:阅读扩展数据类型

15220
来自专栏算法修养

poj-1185 炮兵阵地

炮兵阵地 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 22654 ...

35330
来自专栏小詹同学

​我拿 12 年 36 套四级真题做了什么 ?

不会英语的程序员不是好程序员 ?小詹不敢乱立 flag ,但是我知道的是程序员就喜欢自己动手干些实事 ,比如今天教大家自己动手做个有意思的项目——从历年四级英语...

16210
来自专栏生信宝典

Python解析psiBlast输出的JSON文件结果

什么是JSON文件 JSON文件是一种轻量级的数据存储和交换格式,其实质是字典和列表的组合。这在定义生信分析流程的参数文件中具有很好的应用。 { "公众...

22450
来自专栏华章科技

最全Python数据工具箱:标准库、第三方库和外部工具都在这里了

导读:Python数据工具箱涵盖从数据源到数据可视化的完整流程中涉及到的常用库、函数和外部工具。其中既有Python内置函数和标准库,又有第三方库和工具。这些库...

2.9K20
来自专栏数据结构与算法

洛谷P2147 [SDOI2008]Cave 洞穴勘测

题目描述 辉辉热衷于洞穴勘测。 某天,他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测,辉辉发现这片区域由n个洞穴(分别编号为1到n)以及若干通道...

36290
来自专栏架构师之旅

JVM内存管理------GC算法精解

相信不少猿友看到标题就认为LZ是标题党了,不过既然您已经被LZ忽悠进来了,那就好好的享受一顿算法大餐吧。不过LZ丑话说前面哦,这篇文章应该能让各位彻...

21880

扫码关注云+社区

领取腾讯云代金券