计算机应用 ›› 2015, Vol. 35 ›› Issue (7): 2004-2008.DOI: 10.11772/j.issn.1001-9081.2015.07.2004

• 计算机软件技术 • 上一篇    下一篇

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

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

  1. 北京化工大学 信息科学与技术学院, 北京 100029
  • 收稿日期:2015-02-04 修回日期:2015-03-25 出版日期:2015-07-10 发布日期:2015-07-17
  • 作者简介:石存沣(1990-),男,天津人,硕士研究生,CCF会员,主要研究方向:软件测试; 李征(1974-),男,河北清苑人,教授,博士,CCF会员,主要研究方向:软件测试、模型切片; 郭俊霞(1977-),女,山西朔州人,讲师,博士,主要研究方向:网络信息定向抽取技术及测试
  • 基金资助:
    国家自然科学基金资助项目(61472025, 61170082);教育部新世纪优秀人才支持计划项目(NCET-12-0757)。

Generation method of thread scheduling sequence based on all synchronization pairs coverage criteria

SHI Cunfeng, LI Zheng, GUO Junxia, ZHAO Ruilian   

  1. College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China
  • Received:2015-02-04 Revised:2015-03-25 Online:2015-07-10 Published:2015-07-17
  • Contact: 赵瑞莲(1964-),女,山西忻州人,教授,博士,CCF会员,主要研究方向:软件测试、软件可靠性,rlzhao@mail.buct.edu.cn

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

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

Abstract: Aiming at the problem of low efficiency on generating Thread Scheduling Sequence (TSS) that cover synchronization statements in multi-thread concurrent program, a TSS Generation Based on All synchronization pairs coverage criteria (TGBA) method was proposed. First, according to the synchronization statements in concurrent program, the synchronization pair and All Synchronization Pairs Coverage Criteria (APSC) were defined. Second, a construction method of Synchronization Pair Thread Graph (SPTG) was given. On that basis, TSSs that satisfied APSC were generated. Finally, by using JPF (Java PathFinder) detection tool, TSS generation experiments were conducted on four Java Library concurrent programs, and the comparison analysis of generation efficiency was conducted with general sequence generation methods of Default Scheduling (DS), Preemptive Scheduling (PS) and Cross Scheduling (CS). The experimental results illustrate that TSSs generated by TGBA method can cover all synchronization pairs compared to the DS and CS method. Moreover, when satisfying APSC, TGBA method decreases at least 19889 states and 44352 transitions compared to the PS method, and the average generation efficiency increases by 1.95 times. So TGBA method can reduce cost of state space and improve the efficiency of TSS generation.

Key words: multi-thread concurrent program, synchronization pair, All Synchronization Pairs Coverage (APSC) criteria, Thread Scheduling Sequence (TSS), test generation efficiency

中图分类号: