多线程程序时序分析的隐Markov模型  

Hidden Markov Model for Multi-Thread Programs Time Sequence Analysis

作　　者：孔德光[1] 谭小彬[1] 奚宏生[1] 帅建梅[1] 宫涛[1] 

机构地区：[1]中国科学技术大学自动化系,安徽合肥230027

出　　处：《软件学报》2010年第3期461-472,共12页Journal of Software

基　　金：国家高技术研究 发展计划(863)No.2006AA01Z449~~

摘　　要：针对多线程程序数据竞争分析与检测困难的问题,提出一种基于隐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.

关 键 词：多线程 数据竞争 hidden MARKOV模型 时序 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]