[发明专利]一种基于序列模式挖掘的并发程序剖析方法

摘要

本发明公开了一种基于序列模式挖掘的并发程序剖析方法，通过对并发程序的源代码进行分析，获取其中的线程信息以及线程之前的依赖关系，以插桩的方式来捕获程序运行过程中所执行的依赖关系序列，最后通过基于序列模式挖掘的方法获知所执行的并发程序中父子线程交互的剖析结果。

主权项

1.一种基于序列模式挖掘的并发程序剖析方法，其特征在于，该方法包括如下步骤：步骤1)通过并发程序源码的静态分析方法，获得并发程序中存在的所有线程信息集合Sthread＝{Tx}，所有线程位置集合Slocation＝{Ly}，以及线程之间各种类型的依赖关系集合Sdependence＝{}，所述所有线程信息集合Sthread＝{Tx}包括Ta，Tb两个线程，La是Ta的一个代码位置，Lb是Tb的一个代码位置，Type是从La指向Lb的依赖关系类型；步骤2)按照所述步骤1中所得信息进行代码插桩，并通过执行插桩后的并发程序来获取依赖轨迹，具体方法为：a)分别在Ta的代码位置La和Tb的代码位置Lb插入监控执行的桩代码，在插桩后的程序执行中记录其执行轨迹{Trace(n)＝n}，其中n为执行轨迹中各个元素的序号；b)如果执行轨迹中La与Lb的执行次序与依赖关系相符合，则认为线程依赖关系存在于当前执行之中，并将其加入依赖轨迹{DepTrace(n)＝n}之中；若不符合则相应的线程依赖关系没有在执行轨迹中出现，不做处理；其中Li和Lj为每个依赖关系中包含的两个代码位置；步骤3)从所述依赖轨迹{DepTrace(n)＝<Type，L_i，L_j>_n}挖掘长度为e、编号为m的线程依赖关系的执行序列模式并计算的支持度，具体方法为：a)计算依赖轨迹中每个执行序列模式的支持度首先得到e为1时的支持度集合为长度为1、编号为m的线程依赖关系的执行序列模式，为的支持度；b)按照给定的阈值SUP进行剪枝，筛选出支持度不小于阈值的元素，得到元素集合如下所示：c)将筛选出的元素进行连接，获得更长的序列，并按照如下公式计算新序列的支持度：其中，表示长度为2、编号为m的执行序列模式，该执行序列模式由DepTrace(n₁)、DepTrace(n₂)顺序组成，n₁和n₂分别是步骤b)中所得集合中任意两个线程依赖关系的编号，为的支持度；d)重复上述剪枝、计算支持度、以及连接的过程，直至没有新的连接能够满足阈值条件为止，获得线程依赖关系的执行序列模式如下：其中，n_e为执行序列模式中最后一个线程依赖关系的编号；步骤4)将所述步骤3)挖掘到的线程依赖关系的执行序列模式加入剖析结果Profile，得到执行频率满足阈值要求的所有执行序列模式，所述剖析结果Profile是一个集合，其中的元素为以及的频率组成的二元组。