Ad-hoc类型同步识别

尽管之前的我们提出的动态数据竞争验证和检测方法能够比较精确地找到数据竞争,但是该方法还是会存在一部分误检,误检主要就是由于ad-hoc类型的同步引起的,下图展示了两个例子。

ad-hoc示例

图(a)中动态数据竞争验证和检测方法会报告出两个数据竞争L1,L4和L2,L3。其中L2和L3对于FLAG的访问其实就是一个ad-hoc类型的同步,是一种良性的数据竞争,同时L1必定在L4之前发生,这两个操作不存在数据竞争。

图(b)中动态数据竞争验证和检测方法会报告出来两个数据竞争L1,L3和L2,L3。其中这三个访问构成一个ad-hoc类型的同步,也是一种良性的数据竞争。

Ad-hoc类型的同步指的就是用户自定义的一些简单同步。程序员使用ad-hoc类型的同步主要的目的就是尽量减少程序中过多使用确定性同步带来的性能开销。这篇文章主要研究的是由对端写(counterpart write)和自旋读(spinning read)构成的ad-hoc类型的同步,如上图所示。本文提出一种动静结合ad-hoc类型同步识别方法,主要分为如下几个阶段:

Phase1:静态识别潜在的ad-hoc类型的同步

静态识别潜在的ad-hoc类型的同步主要是为在动态时更加精确地定位ad-hoc类型同步收集必要相关的信息。由于在静态时精确地定位对端写比较困难,因此我们在静态时主要用来识别潜在的自旋读循环相关信息。这部分主要分为如下几个步骤:

  1. 找到所有的循环 对于C/C++程序来说,循环主要包括while、do-while、for以及goto-label这四种类型。其中前三种利用一些已有的静态分析工具比较容易识别,最后一种稍微复杂一些。识别goto-label循环,主要就是遍历每一个函数中label和goto语句,然后对goto语句集合进行倒排,对label语句集合进行正排。然后就遍历label语句找到第一个能够匹配的goto语句。
  2. 剔除计算型循环 对端写和自旋读构成的循环一般来说结构都比较简单并且包含的语句比较少。因此我们通过控制流图能够轻松得到循环中块的数量,超过5就会被认为是计算型循环。同时,如果循环开始到结束的语句包含超过10的话,也会被认为是计算型循环。
  3. 找到循环中所有的退出条件 循环中的退出条件主要包括两类,一类是循环自带的控制表达式,在while、do-while以及for循环中;另外一类是使用break、return、goto语句退出循环。根据这些退出循环标识,就能够找到对应的循环退出条件分支,即if-else分支。
  4. 剔除计算型循环退出条件 如果上述找到的循环退出条件分支和共享变量的读不存在任何直接或是间接地数据依赖,那么这个循环退出条件就是计算型的。同时,如果循环退出条件相关的共享变量在循环中有写访问,那么同样循环退出条件也是计算型的。
    反例
    图(a)中由于cnt不是共享变量,并且不存在和共享变量之间存在数据依赖,因此肯定不是自旋读循环。图(b)中while中仅仅的一个循环退出条件直接和共享变量相关,但是该共享变量在循环中有写访问,因此也不是自旋读循环。图(c)中ptr指向共享变量flag,但是在循环退出条件中是调用了相关的函数,对于这种情况,我们会继续深入该函数进行相关的分析,但也仅仅停留在该函数中,并不会继续深入下去。

完成上述4个捕捉之后,如果循环中不存在任何我们期待的退出条件,那么该循环就不是自旋读循环。

这样,我们就通过静态分析得到了自旋读循环相关的信息。

Phase2:动态确认ad-hoc类型的同步

根据静态得到的潜在的自旋读循环,我们在动态是监视相关的自旋读访问,同时也会监视对共享内存空间的最后一次写访问。当自旋读线程即将执行条件退出分支的第一条语句或是执行循环外的第一条语句,此时才会确认ad-hoc类型的同步。

这样的话,通过动静结合的ad-hoc类型同步识别,我们能够剔除一部分良性和错误的数据竞争,进一步优化我们的数据竞争报告。

下表展示了我们进一步实验结果:

结果

同样也是针对Unittest程序进行测试,其中VD表示就是我们之前提出的动态数据竞争验证和检测方法,而PVD是之前提出的并行化的动态数据竞争验证和检测方法,而VDP表示就是动态数据竞争验证和检测方法执行之后,再执行动态ad-hoc类型同步确认方法。从这张图表中可以明显的发现我们剔除了大部分ad-hoc类型导致的良性和错误的数据竞争。

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏惨绿少年

Python入门篇

3054
来自专栏JavaEdge

设计模式实战 - 简单工厂

最可能给八卦炉下达什么样的生产命令呢? 应该是给我生产出一个黄色人种(YellowHuman类) 而不会是给我生产一个会走、会跑、会说话、皮肤是黄色的人种 ...

975
来自专栏CDA数据分析师

教你一招 | 用Python实现简易可拓展的规则引擎

做这个规则引擎的初衷是用来实现一个可序列号为json,容易拓展的条件执行引擎,用在类似工作流的场景中,最终实现的效果希望是这样的: ? 简单整理下需求 执行结果...

3325
来自专栏芋道源码1024

我的编码习惯 —— API 接口定义

工作中,少不了要定义各种接口,系统集成要定义接口,前后台掉调用也要定义接口。接口定义一定程度上能反应程序员的编程功底。列举一下工作中我发现大家容易出现的问题:

1184
来自专栏申龙斌的程序人生

零基础学编程013:import让你飞起来

在《零基础学编程012:画出复利曲线图》这篇文章中只需6行语句就画出复利曲线图,前两行语句全是import。 import numpy as np import...

2934
来自专栏AI研习社

NumPy 将停止支持 Python 2,这里有一份给数据科学家的 Python 3 使用指导

Python 已经成为机器学习和数据科学的主要编程语言,同时 Python 2 和 Python 3 共存与 Python 的生态体系内。不过,在 2019 年...

33111
来自专栏CSDN技术头条

C#秒杀Java的五个不可替代的特性,完美的编程语言并不存在

如果我们可以同时拥有 C# 和 Java 世界的最好特性,那会是什么样呢? 完美的编程语言并不存在,我希望我们可以在这一点上达成一致。开发新语言往往是为了克服...

22410
来自专栏哲学驱动设计

EntityFramework 元数据 设计分析

    由于之前已经尝试使用过 EF CodeFirst CTP4,所以这次在EF4.1发布的第三天,在 OEA 框架中已经支持使用它来实现数据访问层。而且,我...

1868
来自专栏chafezhou

小说python何时使用生成器

生成器、迭代器作为python的两个高级特性,相信大家肯定耳熟能详,都能说道上一阵,但很多时候都是说说而已,知道有这么个东西,而且是好东西,但再看看写过的代码,...

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

【编程入门】C语言堆栈入门——堆和栈的区别

在计算机领域,堆栈是一个不容忽视的概念,我们编写的C语言程序基本上都要用到。但对于很多的初学着来说,堆栈是一个很模糊的概念。堆栈:一种数据结构、一个在程序运行时...

3966

扫码关注云+社区