基于全同步对覆盖的线程调度序列生成方法

来源：计算机应用杂志2015年第7期北京时间：

作者：石存沣, 李征, 郭俊霞, 赵瑞莲

单位：北京化工大学 信息科学与技术学院, 北京 100029

摘要：针对多线程并发程序生成覆盖同步语句的线程调度序列(TSS)效率低问题,提出了一种基于全同步对覆盖(APSC)准则的TSS生成(TGBA)方法。首先,对并发程序中的同步语句,定义了同步对及APSC;然后,给出了一个同步对-线程关联图(SPTG)构建方法;在此基础上,生成满足APSC的TSS;最后,使用JPF检测工具,对4个Java类库并发程序进行了TSS生成实验,并与常用的默认线程调度(DS)、抢占式线程调度(PS)和交叉线程调度(CS)序列生成方法在生成效率方面进行了对比分析。实验结果表明,与DS、CS方法相比,TGBA方法生成的TSS能够覆盖全部同步对;当满足APSC时,与PS方法相比,TGBA方法测试生成所需要的状态数、迁移数至少减少了19889和44352,并且生成效率平均提升了1.95倍,因此TGBA方法能够降低状态空间的规模开销,提高TSS的生成效率。

关键词：多线程并发程序,同步对,全同步对覆盖准则,线程调度序列,测试生成效率

基金资助：国家自然科学基金资助项目(61472025, 61170082);教育部新世纪优秀人才支持计划项目(NCET-12-0757)。