一种多阶段程序分析的并行任务分配方法及装置

摘要

本发明公开了一种多阶段程序分析的并行任务分配方法及装置。所述方法包括：根据待分析代码中所有任务之间的依赖关系，构建所述待分析代码对应的任务关系图；获取所述待分析代码中需要运行的分析任务；根据所述任务关系图和所述分析任务，对所述分析任务进行阶段划分，得到阶段任务集合；所述阶段任务集合中包含至少一个可被并行执行的并行任务；根据并发运行任务数，运行所述阶段任务集合中的阶段任务，并获取任务运行结果。本发明能够较大程度的发挥硬件性能，缩短整体分析时间，且能够有效解决将所有检查器结果堆积到同一个结果文件中，检查结果较多时，结果文件过大，不便于读取的问题。

说明书

技术领域

本发明涉及代码分析技术领域，特别是一种多阶段程序分析的并行任务分配方法及装置。

背景技术

代码分析是保证软件代码正确性的重要方法。对现代大规模的复杂的软件系统(比如千万行代码规模的Linux操作系统)进行高精度的静态分析,分析精度的提高，往往意味着更长的分析时间。精度、效率和可扩展性相互制约,是静态分析技术在工业界应用的主要障碍。

在提升分析效率方面，人们做了大量的优化研究工作，比如单机

CPU并行、分布式以及GPU实现等。鉴于本发明应用的系统为单机环境，主要针对单机CPU并行情况进行了研究。目前已有的一些并行分析算法有Méndez-Lojo等人提出的一种基于约束图改写的并行指向分析算法，Rodriguez等人提出的一种基于参与者模型的并行数据流分析算法，这两种算法是针对某一类特定的静态分析问题进行特定的处理，不具有普遍性。Albarghouthi等人提出了一个使用map-reduce策略并行化自顶向下分析的通用框架，这种框架比较依赖内存，内存不足时，计算会受限。

对于使用多种类型检查器同时进行分析的情况，有些检查器可能会有些前置任务，比如全局变量分析的检查器在分析前，需要先进行程序构建，再进行函数调用关系计算，检查器的分析有一些前置的依赖条件，需要分多个阶段运行。如果每一个检查器都要等待其前置任务完成，且所有检查器都要顺序进行，那么必然存在项目完整分析效率低的问题。

发明内容

本发明解决的技术问题是：克服现有技术的不足，提供了一种多阶段程序分析的并行任务分配方法及装置。

为了解决上述技术问题，本发明实施例提供了一种多阶段程序分析的并行任务分配方法，包括：

根据待分析代码中所有任务之间的依赖关系，构建所述待分析代码对应的任务关系图；

获取所述待分析代码中需要运行的分析任务；

根据所述任务关系图和所述分析任务，对所述分析任务进行阶段划分，得到阶段任务集合；所述阶段任务集合中包含至少一个可被并行执行的并行任务；

根据并发运行任务数，运行所述阶段任务集合中的阶段任务，并获取任务运行结果。

可选地，所述根据待分析代码中所有任务之间的依赖关系，构建所述待分析代码对应的任务关系图，包括：

以所述所有任务作为图节点；

根据所述依赖关系将具有依赖关系的图节点相连，生成所述任务关系图。

可选地，所述根据所述任务关系图和所述分析任务，对所述分析任务进行阶段划分，得到阶段任务集合，包括：

获取所述分析任务在所述任务关系图中的目标图节点；

获取所述目标图节点中为父节点的第一图节点，并将所述第一图节点划分至阶段任务集合；

在所述目标图节点中删除所述第一图节点，并对剩余的目标图节点循环执行所述获取所述目标图节点中为父节点的第一图节点，并将所述第一图节点划分至阶段任务集合的步骤，直至所有的分析任务均已划分至阶段任务集合。

可选地，所述根据并发运行任务数，运行所述阶段任务集合中的阶段任务，并获取任务运行结果，包括：

根据运行设备的设备性能和所述分析任务对应的平均占用内存，确定所述并发运行任务数；

根据所述阶段任务集合的阶段运行顺序和所述并发运行任务数，分阶段运行所述阶段任务集合中的阶段任务集合中的分析任务，得到任务运行结果。

可选地，所述根据所述阶段任务集合的阶段运行顺序和所述并发运行任务数，分阶段运行所述阶段任务集合中的阶段任务集合中的分析任务，得到任务运行结果，包括：

通过任务调度器将第一阶段运行的任务发送至任务执行器执行；

在所述第一阶段的所有任务执行完成后，根据执行器返回的进程退出码，计算第二阶段任务中无需执行的第一任务，去除所述第一任务，将剩余的任务发送给所述执行器执行；

在运行结束之后，将用户选择的分析任务的结果通过结果数据整合部分进行整合，以得到所述任务运行结果。

为了解决上述技术问题，本发明实施例还提供了一种多阶段程序分析的并行任务分配装置，包括：

任务关系图构建模块，用于根据待分析代码中所有任务之间的依赖关系，构建所述待分析代码对应的任务关系图；

分析任务获取模块，用于获取所述待分析代码中需要运行的分析任务；

任务集合获取模块，用于根据所述任务关系图和所述分析任务，对所述分析任务进行阶段划分，得到阶段任务集合；所述阶段任务集合中包含至少一个可被并行执行的并行任务；

运行结果获取模块，用于根据并发运行任务数，运行所述阶段任务集合中的阶段任务，并获取任务运行结果。

可选地，所述任务关系图构建模块包括：

图节点获取单元，用于以所述所有任务作为图节点；

任务关系图生成单元，用于根据所述依赖关系将具有依赖关系的图节点相连，生成所述任务关系图。

可选地，所述任务集合获取模块包括：

目标图节点获取单元，用于获取所述分析任务在所述任务关系图中的目标图节点；

第一图节点获取单元，用于获取所述目标图节点中为父节点的第一图节点，并将所述第一图节点划分至阶段任务集合；

任务集合获取单元，用于在所述目标图节点中删除所述第一图节点，并对剩余的目标图节点循环执行所述第一图节点获取单元，直至所有的分析任务均已划分至阶段任务集合。

可选地，所述运行结果获取模块包括：

并发任务数确定单元，用于根据运行设备的设备性能和所述分析任务对应的平均占用内存，确定所述并发运行任务数；

任务运行结果获取单元，用于根据所述阶段任务集合的阶段运行顺序和所述并发运行任务数，分阶段运行所述阶段任务集合中的阶段任务集合中的分析任务，得到任务运行结果。

可选地，所述任务运行结果获取单元包括：

第一阶段执行子单元，用于通过任务调度器将第一阶段运行的任务发送至任务执行器执行；

剩余任务执行子单元，用于在所述第一阶段的所有任务执行完成后，根据执行器返回的进程退出码，计算第二阶段任务中无需执行的第一任务，去除所述第一任务，将剩余的任务发送给所述执行器执行；

运行结果获取子单元，用于在运行结束之后，将用户选择的分析任务的结果通过结果数据整合部分进行整合，以得到所述任务运行结果。

本发明与现有技术相比的优点在于：

本发明通过计算任务间的依赖关系，有效地对多个分析过程进行统筹规划，按照顺序优先级分阶段，并行执行，解决了线性运行多阶段多检查器分析任务速度过慢问题；本发明根据任务数量、PC机内存大小、PC机核数，计算了可同时运行的进程数量，并按照计算的并行任务数对单个阶段运行的分析任务进行并发执行，能够较大程度地发挥硬件性能，缩短整体分析时间；本发明采用重定向输出的形式，将一个项目的每个检查器的分析结果独立形成一个文件，有效地解决了将所有检查器结果堆积到同一个结果文件中，当检查结果较多时，结果文件过大，不便于读取的问题。

附图说明

图1为本发明实施例提供的一种多阶段程序分析的并行任务分配方法的步骤流程图；

图2为本发明实施例提供的一种多阶段程序分析的并行任务分配装置的结构示意图。

具体实施方式

针对用户使用多个多阶段检查器，对大规模项目进行分析运行时间长效率低的问题，本发明实施例旨在通过合理调度分析任务，尽可能发挥硬件性能，减少分析总时间。系统分为分析任务设置、分析任务计算、分析任务执行、结果数据整合四个部分。分析任务设置包括检查器设置、参数设置两部分；分析任务计算部分包括分析任务生成、分析任务依赖计算和并发数量计算三部分；分析任务执行分为分析任务调度器和分析任务执行器。本发明将程序分析各阶段需要执行任务的依赖关系构造成有向的图形数据结构，该图形结构的各节点表示待分析的任务；有向边为任务间的依赖关系，即每个任务的父节点是其依赖的任务节点；所有的边都应该是单向的，且不能形成环形结构，即从某一任务节点向上寻找其依赖的任务时不能依赖自己；允许一个节点有多个父节点或多个子节点，即允许一个任务依赖多个任务，或一个任务被多个任务依赖。

实施例一

参照图1，示出了本发明实施例提供的一种多阶段程序分析的并行任务分配方法的步骤流程图，如图1所示，该多阶段程序分析的并行任务分配方法具体可以包括如下步骤：

步骤101：根据待分析代码中所有任务之间的依赖关系，构建所述待分析代码对应的任务关系图。

本发明实施例可以结合待分析代码对应的任务关系图进行程序分析的场景中。

待分析代码是指需要进行分析的程度代码。

在获取到待分析代码之后，可以根据待分析代码中所有任务之间的依赖关系构建待分析代码对应的任务关系图，具体地，可以结合下述具体实现方式进行详细描述。

在本发明的一种具体实现方式中，上述步骤101可以包括：

子步骤A1：以所述所有任务作为图节点；

子步骤A2：根据所述依赖关系将具有依赖关系的图节点相连，生成所述任务关系图。

在本发明实施例中，可以以待分析代码中的所有任务作为图节点，然后根据所有任务之间的依赖关系将具有依赖关系的图节点相连，从而可以生成任务关系图，具体地，按照任务间的依赖关系，生成所有任务的依赖关系图，这个图的节点代表着用户选择要分析的执行任务及这些任务所依赖的任务，显然，这个图的所有节点必须包括用户选择的分析检查器的所有依赖任务。

步骤102：获取所述待分析代码中需要运行的分析任务。

分析任务是指待分析代码中的需要运行的任务。

在一次分析可以只运行部分检查器分析任务，记这些任务的集合为S1，即分析任务所形成的集合。检查器设置是指配置静态分析需要应用的检查器，一般是由用户指定作为输入。参数设置是指对分析工具进行一些额外的参数设置，一般使用默认设置，也可由用户指定作为输入。

分析任务生成主要功能是对分析任务设置部分的输入做整理，并生成用于执行分析任务的命令行。分析任务依赖计算用于计算分析任务的依赖关系，配合分析任务生成部分生成多阶段的分析任务。

在获取待分析代码中需要运行的分析任务之后，执行步骤103。

步骤103：根据所述任务关系图和所述分析任务，对所述分析任务进行阶段划分，得到阶段任务集合；所述阶段任务集合中包含至少一个可被并行执行的并行任务。

在获取任务关系图和分析任务之后，可以根据任务关系图和分析任务，对分析任务进行阶段划分，以得到阶段任务集合，而在每个阶段任务集合中包含有至少一个可被并行执行的并行任务，具体地划分过程可以结合下述具体实现方式进行详细描述。

在本发明的另一种具体实现方式中，上述步骤103可以包括：

子步骤B1：获取所述分析任务在所述任务关系图中的目标图节点；

子步骤B2：获取所述目标图节点中为父节点的第一图节点，并将所述第一图节点划分至阶段任务集合；

子步骤B3：在所述目标图节点中删除所述第一图节点，并对剩余的目标图节点循环执行所述获取所述目标图节点中为父节点的第一图节点，并将所述第一图节点划分至阶段任务集合的步骤，直至所有的分析任务均已划分至阶段任务集合。

在本发明实施例中，可以记所有任务的依赖关系图为G，则S1中的元素为G中的节点。在G中寻找S1中所有元素的父节点，这些父节点形成的集合记为S2，如果存在找不到父节点的元素，那么将这些元素放入另一个集合中，记为S0，并在S1中去除这些元素；之后对S2～Sn-1集合进行上述操作，直到Sn为空集。最终形成多个集合即为不同阶段运行的任务集合，其中S0为第一阶段运行的任务集合，之后按照从Sn-1到S1的顺序排列。

在得到阶段任务集合之后，执行步骤104。

步骤104：根据并发运行任务数，运行所述阶段任务集合中的阶段任务，并获取任务运行结果。

在获取到阶段任务集合之后，则可以根据并发运行任务数，运行阶段任务，并获取任务运行结果，具体地，可以结合下述具体实现方式进行如下详细描述：

在本发明的另一种具体实现方式中，上述步骤104可以包括：

子步骤C1：根据运行设备的设备性能和所述分析任务对应的平均占用内存，确定所述并发运行任务数。

子步骤C2：根据所述阶段任务集合的阶段运行顺序和所述并发运行任务数，分阶段运行所述阶段任务集合中的阶段任务集合中的分析任务，得到任务运行结果。

在本发明实施例中，分析任务调度器用于在执行一个阶段的分析任务期间将任务逐个交给分析任务执行器进行执行，并根据执行器返回的退出码判断任务是否执行成功，并不再执行未成功执行的任务的后续任务。

分析任务执行器的功能是根据任务创建系统进程进行执行，并将各种输出进行重定向到文件中，并接收任务进程的退出码交给分析任务调度器。

经过上述步骤得到的多个任务的集合Sn，集合中的所有任务可以同时进行，但是一般由于执行任务的PC机性能限制，不能同时进行所有任务，因此需要根据PC机的性能(即内存大小和计算机核数)，以及任务的平均内存占用，计算能够同时运行的任务数。

按照上述步骤中计算得的阶段顺序，分阶段创建运行任务的进程，同时运行的任务数不能超过计算得到的并发运行任务数，指定进程输出流和错误流重定向位置，开始执行后，等待任务运行完成并记录进程退出码。

对运行任务(假设为Sn)的进程的退出码进行判断，将进程未正常退出的任务形成一个失败任务集合，记为Sfn，计算Sfn内的任务被下一阶段(即Sn-1)哪些任务依赖，从Sn-1中去除这些任务，并将这些任务加入下一阶段的失败任务集合Sfn-1。

继续下一阶段任务的运行：对下一阶段任务重复运行的过程。

在所有任务运行完成之后，进行结果整合：对S1中最后实际执行的任务，根据上述步骤中的输出文件，将所有输出文件的结果通过数个线程整合到最终结果中，这些线程应至少包含1个读取线程和1个写入线程，假设计算的并发数大于2，那么可以根据输出文件的数量和大小决定创建更多的读取线程或写入线程，需要注意的是，如果开启多个写入线程，需要解决线程间冲突问题。

在本发明实施例中，任务调度器首先将第一阶段运行的任务交给任务执行器执行，待第一阶段所有任务执行完毕后，根据执行器返回的进程退出码，计算第二阶段任务中有哪些任务不必执行，去除这些不必执行的任务，将剩余的任务交给执行器执行。在运行结束后，将用户选择的检查器分析任务的结果通过结果数据整合部分进行整合，首先开启一个结果读入线程将各任务的结果文件逐个读入，再开启一个结果存入线程将读入的结果汇总存入最终结果文件中，如用户选择的任务并发运行数大于2，则可以开启更多的结果读入线程，这些线程也是并发进行的，且只开启一个结果存入线程，避免了写入冲突的问题。

本发明实施例通过根据任务数量、PC机内存大小、PC机核数，计算了可同时运行的进程数量，并按照计算的并行任务数对单个阶段运行的分析任务进行并发执行，能够较大程度地发挥硬件性能，缩短整体分析时间。

实施例二

参照图2，示出了本发明实施例提供的一种多阶段程序分析的并行任务分配装置的结构示意图，如图2所示，该多阶段程序分析的并行任务分配装置具体可以包括如下模块：

任务关系图构建模块210，用于根据待分析代码中所有任务之间的依赖关系，构建所述待分析代码对应的任务关系图；

分析任务获取模块220，用于获取所述待分析代码中需要运行的分析任务；

任务集合获取模块230，用于根据所述任务关系图和所述分析任务，对所述分析任务进行阶段划分，得到阶段任务集合；所述阶段任务集合中包含至少一个可被并行执行的并行任务；

运行结果获取模块240，用于根据并发运行任务数，运行所述阶段任务集合中的阶段任务，并获取任务运行结果。

可选地，所述任务关系图构建模块210包括：

图节点获取单元，用于以所述所有任务作为图节点；

任务关系图生成单元，用于根据所述依赖关系将具有依赖关系的图节点相连，生成所述任务关系图。

可选地，所述任务集合获取模块230包括：

目标图节点获取单元，用于获取所述分析任务在所述任务关系图中的目标图节点；

第一图节点获取单元，用于获取所述目标图节点中为父节点的第一图节点，并将所述第一图节点划分至阶段任务集合；

任务集合获取单元，用于在所述目标图节点中删除所述第一图节点，并对剩余的目标图节点循环执行所述第一图节点获取单元，直至所有的分析任务均已划分至阶段任务集合。

可选地，所述运行结果获取模块240包括：

并发任务数确定单元，用于根据运行设备的设备性能和所述分析任务对应的平均占用内存，确定所述并发运行任务数；

任务运行结果获取单元，用于根据所述阶段任务集合的阶段运行顺序和所述并发运行任务数，分阶段运行所述阶段任务集合中的阶段任务集合中的分析任务，得到任务运行结果。

可选地，所述任务运行结果获取单元包括：

第一阶段执行子单元，用于通过任务调度器将第一阶段运行的任务发送至任务执行器执行；

剩余任务执行子单元，用于在所述第一阶段的所有任务执行完成后，根据执行器返回的进程退出码，计算第二阶段任务中无需执行的第一任务，去除所述第一任务，将剩余的任务发送给所述执行器执行；

运行结果获取子单元，用于在运行结束之后，将用户选择的分析任务的结果通过结果数据整合部分进行整合，以得到所述任务运行结果。

以上所述，仅为本发明的较佳实例而已，虽然本发明已以较佳的实施方法揭露如上，然而并非用于限定本发明的保护范围。

本发明说明书中未作详细描述的内容属本领域技术人员的公知技术。