CAJ | 학술논문

为了在并行程序的单次执行中找到更多的数据竞争，提出了用可行序关系替代传统的“happens before”序关系来动态地实现数据竞争预测的算法。该算法认为：从技术上讲，如果在观测到的执行轨迹中，两个临界区之间没有可行序的关系，那么这两个临界区的顺序可以被颠倒以构造出其他的执行轨迹；通过判断可行序关系来分析这些构造出来的执行轨迹，就可以找到单次执行中未暴露出来的可能的数据竞争；所有构造出来的执行轨迹中的数据竞争，可以在O(an)的时间内全部检测出来，其中n为程序中所有访存操作的个数，a为每个共享地址上的最大锁集合数。在Java Grande测试程序集上的实验结果说明，上述算法可以找到其他动态检测数据竞争的方法找不到的数据竞争，而且算法时间也完全符合理论上的O(an)时间复杂度。
위료재병행정서적단차집행중조도경다적수거경쟁，제출료용가행서관계체대전통적“happens before”서관계래동태지실현수거경쟁예측적산법。해산법인위：종기술상강，여과재관측도적집행궤적중，량개림계구지간몰유가행서적관계，나요저량개림계구적순서가이피전도이구조출기타적집행궤적；통과판단가행서관계래분석저사구조출래적집행궤적，취가이조도단차집행중미폭로출래적가능적수거경쟁；소유구조출래적집행궤적중적수거경쟁，가이재O(an)적시간내전부검측출래，기중n위정서중소유방존조작적개수，a위매개공향지지상적최대쇄집합수。재Java Grande측시정서집상적실험결과설명，상술산법가이조도기타동태검측수거경쟁적방법조불도적수거경쟁，이차산법시간야완전부합이론상적O(an)시간복잡도。
To catch more data races in onetime execution of concurrent programs, a new algorithm using the feasibleahead relation to substitute the happensbefore relation to dynamially explore data races is put forward. Technically, the algorithm follows the rules below: Two critical sections without a feasibleahead relation in an inspected execution trace can be reordered to construct conceived execution traces; The data races invoked in these conceived execution traces can be effectively explored by reasoning about the feasibleahead relation in the inspected execution trace; The data race exploration via the feasibleahead relation can be efficiently done with the time complexity of O(an), where a is the maximum number of locksets over a shared location, and n is the total number of memory events. Both the effectiveness and efficiency of the abovementioned algorithm were verified by the experiments on the Java Grande benchmark, and the results demonstrate that the algorithm can detect the data races other appreaches can not detect, and has a lower time complexity.