1.一种基于高阶函数的数据竞争检测方法,其特征在于:包括,
对程序进行预处理,构建跨线程函数调用图和各函数的控制流图,按照逆拓扑排序的顺序遍历函数调用图,确定每个函数的分析顺序;
按序选取一个待分析的函数,遍历函数的控制流图,获取各个函数的高阶函数摘要和由于函数调用和参数传递产生的过程间访问事件集;
基于向量时钟和高阶函数摘要对访问事件进行发生序分析;
通过数据竞争发生的条件排除不满足的访问事件对,获取所有可能发生数据竞争的结果。
2.如权利要求1 所述的一种基于高阶函数的数据竞争检测方法,其特征在于:获取各个函数的高阶函数摘要包括,按序选取一个待分析的P函数,对每个函数进行过程内分析,定义一个高阶函数,其参数为调用过程相对应的实参;
对锁语句节点收集锁数据集,对访问节点收集访问事件数据集如下:
初始化P函数的约束集;
对线程交互节点收集线程交互原语信息。
3.如权利要求2 所述的一种基于高阶函数的数据竞争检测方法,其特征在于:还包括,通过数据流分析技术遍历P函数控制流图,对锁语句、访问语句、函数调用语句和线程交互语句四种类型语句进行分析,并按照遍历顺序传递语句的分析结果;
将所述锁数据集和所述访问事件数据集中涉及调用函数的部分利用定义的高阶函数的参数进行表示;
令F(id,l,v,t,L)为待分析语句s的约束函数,其中,id为迭代到语句s的事件号,l为语句s中的锁变量,v为语句s中的共享变量,t为语句s中的与当前线程交互的线程名,L为顺序传递到待分析语句s的约束集;
语句集合{s|si∈S , i =1,2,3...},其中,s为程序语句,i为语句s对应的行号,S为所有程序语句的集合,构建不同语句对应的约束关系抽取方程;
当P函数中的所有语句都处理完后,将分析结果以形式参数为函数参数保存为高阶函数摘要。
4.如权利要求1 3任一所述的一种基于高阶函数的数据竞争检测方法,其特征在于:所~述由于函数调用和参数传递产生的过程间访问事件集包括,
对于函数调用语句,将得到的高阶函数形式的访问事件函数摘要通过实参和函数参数对应的关系进行相应的带入,获取过程内的访问事件集,得到该函数完整的过程间访问事件结果,对于线程调用语句,在得到该线程完整的访问事件结果同时,实例化该线程的线程交互原语集;
在函数调用节点,记被调用函数为Q函数,将迭代到当前语句的事件号和锁集以参数的形式传入Q函数的访问事件中,并根据形参和实参之间对应的关系将高阶函数摘要中的函数参数进行相应代入,得到函数Q的完整的过程间分析结果。
5.如权利要求4所述的一种基于高阶函数的数据竞争检测方法,其特征在于:还包括,在线程函数调用节点,即create方法节点处,记创建th线程,根据形参和实参之间对应的关系将高阶函数摘要中的函数参数进行相应代入,实例化获取th线程的访问事件集和线程交互原语集;
当所有被调用函数的分析结果传递至相应函数调用点处,即可得到每个线程完整的访问事件和线程交互原语消息。
6.如权利要求1所述的一种基于高阶函数的数据竞争检测方法,其特征在于:基于向量时钟和高阶函数摘要对访问事件进行发生序分析包括,在对主线程分析时,初始化线程号gid为0,一个本地向量时钟为clock=[1],将访问事件集和向量时钟抽象在事件集GA中,用于存储具有相同时钟的访问事件集,便于之后进行发生序分析;
在获取每个线程的分析结果后,从主线程的交互原语集开始进行时钟分析;
创建线程原语
等待线程原语
将同一个线程的两个原语ti1和ti2之间的访问事件存储到同一个事件集GAi中,即事件号大于idti1小于idti2的访问事件,若ti1之前无其他交互原语,则事件号从0到idti1,若ti2之后无其他交互原语,则事件号从idti2到当前函数最后一个访问事件的事件号。
7.如权利要求1 所述的一种基于高阶函数的数据竞争检测方法,其特征在于:通过数据竞争发生的条件排除不满足的访问事件对,获取所有可能发生数据竞争的结果包括,在得到事件集GAi即程序所有可能发生数据竞争的事件集后,以数据竞争发生的条件为约束排除不满足发生条件的访问事件对,即相同的变量、至少存在一个访问为写操作、不被同一个锁保护,且不具有发生序关系,最终得到可能发生数据竞争的访问事件对。
8.一种基于高阶函数的数据竞争检测系统,其特征在于,包括,
预处理模块,用于对程序进行预处理,构建跨线程函数调用图和各函数的控制流图,按照逆拓扑排序的顺序遍历函数调用图,确定每个函数的分析顺序;
遍历模块,用于按序选取一个待分析的函数,遍历函数的控制流图,获取各个函数的高阶函数摘要和由于函数调用和参数传递产生的过程间访问事件集;
分析模块,用于基于向量时钟和高阶函数摘要对访问事件进行发生序分析;
输出模块,用于通过数据竞争发生的条件排除不满足的访问事件对,获取所有可能发生数据竞争的结果。
9.一种计算设备,包括:
存储器和处理器;
所述存储器用于存储计算机可执行指令,所述处理器用于执行所述计算机可执行指令,该计算机可执行指令被处理器执行时实现权利要求1至7任意一项所述一种基于高阶函数的数据竞争检测系统的步骤。
10.一种计算机可读存储介质,其存储有计算机可执行指令,该计算机可执行指令被处理器执行时实现权利要求1至7任意一项所述一种基于高阶函数的数据竞争检测系统的步骤。