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

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

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

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

并行数据竞争检测方法

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

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

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

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

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

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

Application Threads

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

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

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

Verification Thread

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

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

Detection Threads

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

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

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

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

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FreeBuf

Angr:一个具有动态符号执行和静态分析的二进制分析工具

什么是angr: angr是一个二进制代码分析工具,能够自动化完成二进制文件的分析,并找出漏洞。在二进制代码中寻找并且利用漏洞是一项非常具有挑战性的工作,它的挑...

6865
来自专栏数据和云

如何提高Linux下块设备IO的整体性能?

编辑手记:本文主要讲解Linux IO调度层的三种模式:cfp、deadline和noop,并给出各自的优化和适用场景建议。 作者简介: ? 邹立巍 Linux...

6914
来自专栏owent

理解Raft算法

之前已经有Paxos算法,用于解决分布式系统最终一致性问题,而且已经有了zookeeper这个成熟的开源实现。那么这个Raft算法有啥用呢?按照Raft官网的说...

5133
来自专栏Hadoop数据仓库

将MySQL去重操作优化到极致之三弹连发(二):多线程并行执行

        上一篇已经将单条查重语句调整到最优,但该语句是以单线程方式执行。能否利用多处理器,让去重操作多线程并行执行,从而进一步提高速度呢?比如我的实验环...

2027

控制MongoDB中的集合分布

分片标记(Shard tagging)是MongoDB 2.2.0版中的一项新功能。通过对集合进行标记使其被强制写入到本地数据中心,也可以用来将某个集合固定到一...

2366
来自专栏大内老A

WCF 4.0一个鲜为人知的改变

本篇文章介绍可以算是WCF 4.0基于限流(Throttling)的新特性,是在修订《WCF技术剖析(卷1)》的时候编写演示实例的时候发现的。这个特性没有出现在...

2879
来自专栏漫漫前端路

写个 vue-loading-template 组件

源码(star ? start : start):github.com/jkchao/vue-…

4312
来自专栏FreeBuf

代码审计之任意文件下载漏洞案例分享

继上次审计HDWiki之后,最近拿到一套新的源码Ear_Music_20180510_UTF8最新版进行审计,发现这套cms还是比较安全的,而当我审计遇到一处下...

1574
来自专栏公有云大数据平台弹性 MapReduce

EMR上Zeppelin入门

简而言之,就是一个大数据分析平台。用户可以利用提供好的WEB UI,在线编写分析逻辑代码,输出结果,并且能够利用可视化工具,形象生动的在线展示结果。

1861
来自专栏蓝天

Linux中系统整体性能监控工具详细介绍

 mpstat: mpstat 不但能查看所有CPU的平均信息,还能查看指定CPU的信息。

1162

扫码关注云+社区

领取腾讯云代金券