专栏首页开发 & 算法杂谈Ad-hoc类型同步识别
原创

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 条评论
登录 后参与评论

相关文章

  • 前序遍历中序遍历求后序遍历-数组篇

    如果已知前序遍历和中序遍历,那么肯定能够求出后序遍历。正常的思路就是,根据前序遍历和中序遍历,我们把二叉树的结构给描述出来,然后再使用后序遍历。

    chain
  • 基于Lockset的数据竞争检测方法汇总(三)

            上一篇文章中我们看到了有关共享对象状态变迁在Eraser基础上进行的改进,但是改进的不是特别明显,下面这篇论文不是单纯的用Lockset作为数据...

    chain
  • 基于Lockset的数据竞争检测方法汇总(二)

    前一篇文章提到的是使用Lockset最经典的方法,但是存在很多误报,针对这些误报产生的原因,有很多分析并改进了原始的Lockset方法,今天主要和大家谈的就是有...

    chain
  • 监督学习方法总结

    感知机、k近邻法、朴素贝叶斯法、决策树 是简单的分类方法,具有模型直观、方法简单、实现容易等特点

    Michael阿明
  • 从零开始在Python中实现决策树算法

    原文地址:https://machinelearningmastery.com/implement-decision-tree-algorithm-scratc...

    Steve Wang
  • 继1小时训练ImageNet之后,大批量训练扩展到了3万2千个样本

    机器之心
  • How To Implement The Decision Tree Algorithm From Scratch In Python (从零开始在Python中实现决策树算法)

    How To Implement The Decision Tree Algorithm From Scratch In Python 原文作者:Jason B...

    Steve Wang
  • 嘿,请把给汽车喝油的土地还给我们喝咖啡

    城市越来越大,我们拥有了更宽的马路,却失去了可以放心让孩子嬉戏的街道;我们建造了更多的摩天大楼,却仍会想念那些被拆掉的老街。什么样的规划可以在保证出行的同时,将...

    DT数据侠
  • 你值得拥有的单细胞RNA测序分析工具TOP 3

    RNA测序相信大家已经接触到不少了,它的样品通常来自研究某一组织细胞群。这些细胞被认为是同质的,也就是说每一个细胞内的表达水平被认为是相似的。但事实上细胞之间的...

    生信技能树jimmy
  • 工作提高——《程序员思维修炼》中提到的那些点子

    我是一个习惯于多任务处理的人,因为我觉得这样子可以加快步伐,避免单一带来的枯燥。但这本书提到:

    陈黎栋

扫码关注云+社区

领取腾讯云代金券