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

摘要：

针对多线程并发程序生成覆盖同步语句的线程调度序列(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的生成效率.

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

所属期刊栏目：35

分类号：TP311.5(计算技术、计算机技术)

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

在线出版日期：2015-10-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：2004-2008,2014