Supported by the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z449 (国家高技术研究发展计划(863))
针对多线程程序数据竞争分析与检测困难的问题,提出一种基于隐Markov 模型的多线程程序时序分析方法.用随机变量不确定性刻画不同线程之间时序上的交互关系,分析数据竞争条件下程序不确定结果的概率分布情况;建立多线程程序时序分析的隐Markov 模型,使用Baum-Welch 和前向算法仿真上下文对程序实际运行状态的影响.实验结果表明,该模型能够快速有效反映多线程执行时序,用于指导多线程程序时序竞争检测过程.
To overcome the difficulty of analyzing and detecting the data race in multithread programs, a method based on Hidden Markov model is presented for the analysis of time sequences in multithread programs. The random variable uncertainty is used to depict the mutual influence in different multithread in time sequences, and the probability distribution for random variable uncertainty is analyzed as the outcome of multithread programs on the condition of data race. Hidden Markov model is constructed to appreciate the state for the thread running according to the observed values of the running threads. The Baum-Welch and forwarding algorithm are used to simulate the real running process of the programs in the influence of context. It is proved by experiments that HMM model can quickly and effectively reflect the time sequence of the multithread programs, which can be used to instruct the detecting process of multithread programs.