并行化的动态数据竞争验证和检测方法

之前系列提到的动态数据竞争验证和检测方法是结合了验证和检测两部分。这篇文章主要介绍一下并行化的动态数据竞争验证和检测方法。

首先我们来谈谈有关利用Pin编写Pintool来检测数据竞争。由于动态二进制插桩就是在原始程序指令前后加入跳转指令,而跳转的目的地就是所谓的分析函数,分析函数中包含了相关的检测逻辑。因此,从这个角度也能发现,我们变现的分析函数和应用程序线程是绑定在一起的。由于应用程序许本身是多线程的程序,因此我们自己编写的Pintool也是多线程的。数据竞争检测用到的相关公共的数据结构包括向量时钟以及锁集等都有可能被多线程访问。为了保证一致性,我们在分析函数中都会加入锁来保护共享的访问操作,并且大部分的操作都可能会涉及到锁保护,尤其是针对读写指令的分析函数中会涉及到比较复杂的验证过程和检测过程分析。因此,频繁使用加锁可能会导致程序在执行过程中不能够有效利用多核的硬件优势。

最近有一篇文章提到了一种并行化的动态数据竞争检测方法。这种方法扩展性非常好而且不用修改之前已经提出的动态数据竞争检测方法,如下图所示。

并行数据竞争检测方法

该方法的核心就是将动态数据竞争检测逻辑从分析函数中分离出来,让单独的检测线程执行相关的逻辑,检测线程之间相互不干扰,因此就不用再使用锁来保护。这里对共享内存空间进行分块,不同的块映射到不同的检测线程上。而原始的应用程序线程则是将程序的行为以事件的形式发送到队列中,对于内存读写事件先缓存到线程TLS中,当缓存慢了之后再发送到队列中,而其他事件则是复制并且发送到各个检测线程队列中。这样的话,唯一需要加锁保护就是针对事件队列的相关访问。

同时我们也能够证明,每个检测线程看到的都是完整程序执行的行为,除了访问的内存块有所不同。

  • 如果两个有明确先后关系的访问,来自不同的线程并且访问相同的共享内存空间,那么针对每一个共享内存块的访问的事件都会被发送到同一个检测线程中,并且发送的顺序也是有先后顺序的。
  • 如果两个访问没有明确的先后关系,那么这两个访问事件被发送到队列时谁在前面和谁在后面都无所谓。

上述方法提出时主要利用FastTrack来进行实验对比分析,我们实现该方法后发现能够应用在基于Lockset算法、基于Happens-before以及基于hybrid上的动态数据竞争检测工具上。之前文章中提到的动态数据竞争检测方法我们全部实验了一下,发现并发的动态数据竞争检测方法和原始的动态数据竞争检测方法检测结果一致。

在该方法的启发下,我们又对之前我们提出的动态数据竞争验证和检测方法进行了并行化的处理,方法框架如下图所示:

并行数据竞争验证检测框架

Application Threads

应用线程中我们同样也是在分析函数中进行相关读写内存事件的分发,而其他同步时间则是继续在原始应用线程中处理。

当应用线程处理非读写内存事件时,之前的方法中我们都是用共享的内存结果保存同步对象信息、向量时钟信息以及锁集锁集信息,而这里我们将会把每个线程相关的信息都保存在自己的TLS中。

当应用线程处理读写内存事件时,分析函数中会将这些事件发送到验证线程队列中,而应用线程随即就被延时阻塞中止执行。

Verification Thread

验证线程主要的作用就是从队列中获取验证请求事件,即应用线程中的读写内存事件,然后处理相关的验证逻辑,和之前的访问类似。

我们只选择了一个验证线程用来处理所有的验证请求,主要是由于验证线程需要和应用线程和检测线程互相沟通,为确保一致性,只是用一个验证线程。验证线程每处理一个验证请求之后,都会根据处理的结果看是否需要唤醒相关的应用线程。同时会根据不同的共享内存块,分发检测请求到不同的检测线程队列中。

Detection Threads

这里检测线程做的工作就是从检测队列中读取检测请求,然后寻找被验证过程中遗漏的数据竞争。

由于验证线程和应用线程是并发进行的,因此验证请求也有可能在验证线程执行过程中失效,一旦请求失效,那么该验证请求就不会再被处理。同时,为了减少向量时钟以及锁集的副本,我们构造的验证请求和检测请求都只包含一个相关的副本以及若干个引用。

我们的并行数据竞争验证和检测方法在充分利用硬件的条件下,每个线程都将会负责好自己的职责。

后序将会介绍ad-hoc类型同步相关的分析。

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WeTest质量开放平台团队的专栏

[分享干货晒技术]Unity 手游内存优化分享

Mono下的foreach使用需谨慎。频繁调用容易触及堆上限,导致GC过早触发,出现卡顿现象。

712
来自专栏有趣的Python

验证码爬取并识别-云大urp教务系统大作战(1)

1. 穷举爬取urp的验证码 因为小道消息得知urp的验证码是有限数量的,因此通过数百万次的请求,下载所有验证码图片到本地,并生成了一份验证码图片的文件名的文...

3238
来自专栏美团技术团队

Android OOM案例分析

在Android(Java)开发中,基本都会遇到java.lang.OutOfMemoryError(本文简称OOM),这种错误解决起来相对于一般的Except...

4444
来自专栏杨建荣的学习笔记

闪回区报警引发的性能问题分析(r11笔记第11天)

自从有了Zabbix+Orabbix,很多监控都有了一种可控的方式,当然对于报警处理来说,报警是表象,很可能通过表象暴露出来的是一些更深层次的问题。这不又来一个...

33710
来自专栏WeTest质量开放平台团队的专栏

用ElasticSearch搭建自己的搜索和分析引擎

互联网产品中的检索功能随处可见。当你的项目规模是百度大搜|商搜或者微信公众号搜索这种体量的时候,自己开发一个搜索引擎,加入各种定制的需求和优化,是非常自然的事情...

883
来自专栏linux驱动个人学习

dm-verity

一、Device Mapper: dm-verity是内核子系统的Device Mapper中的一个子模块,所以在介绍dm-verity之前先要介绍一下Devi...

3016
来自专栏铭毅天下

干货 | Elasticsearch通用优化建议

Elasticsearch开发实战的后期会遇到性能问题,包括:创建索引性能、写入数据性能、检索性能等。网上有很多结合自己实际应用场景的相关优化建议,但“对症下药...

902
来自专栏小狼的世界

[每天五分钟,备战架构师-9]数据库系统

日常数据库使用过程中,离不开SQL语言。Structured Query Language由Boyce和Chamberlin在1974年提出,1975-1979...

912
来自专栏Windows Community

Windows Community Toolkit 3.0 - CameraPreview

Windows Community Toolkit 3.0 于 2018 年 6 月 2 日 Release,同时正式更名为 Windows Community...

741
来自专栏Hadoop数据仓库

HAWQ取代传统数仓实践(四)——定期ETL(Sqoop、HAWQ)

一、变化数据捕获(CDC)         初始装载只在数据仓库开始使用前执行一次,然而,必须要周期性地执行装载源数据过程。与初始装载不同,定期装载一般都是增量...

47410

扫码关注云+社区