基于并发覆盖准则的线程调度序列生成方法研究

摘要

多核处理器的出现使得多线程技术发展迅速，多线程并发程序的软件质量保障受到业界的普遍关注。多线程并发程序由于线程调度序列(Thread Scheduling Sequence，TSS)的不同，使得程序执行将产生不同的结果。线程调度序列是多线程并发程序测试的关键。随着线程数的增加，线程调度序列的数量呈指数型增长。线程调度序列数量多，测试生成开销大，严重影响了多线程并发程序的测试效率。测试覆盖准则作为一项度量测试有效性的指标，可用来指导并发程序的测试生成。根据并发测试覆盖准则来生成线程调度序列，更加偏重于测试程序的并发特点，因此，针对并发覆盖准则，探讨一种有效的线程调度序列的生成方法，已成为多线程并发程序测试中的一个亟待解决的问题。
　　同步机制是多线程并发程序的一个重要特征。本文提出了一种基于全同步对覆盖的线程调度序列生成方法(TSS Generation based on ASPC，TGBA)。具体而言，对于并发程序中的同步语句，定义了同步对和全同步对覆盖准则(All Synchronization Pairs Coverage Criteria，ASPC)，给出了一个同步对-线程关联图构建方法，存此基础上，探讨了满足全同步对覆盖准则的线程调度序列自动生成方法。最后，借助于模型检验工具JPF，设计并实现了一个基于JPF的线程调度序列生成器，用于多线程并发程序线程调度序列的自动生成。
　　为评估TGBA方法的有效性，本文选用了6个Java类库并发程序作为被测程序，利用开发的线程调度序列生成器进行线程调度序列生成实验，并分别与常用的三种线程调度序列生成方法在生成效率方面进行了对比分析。实验结果表明TGBA方法生成的线程调度序列不仅能够覆盖被测程序的全部同步对，而且当满足全同步对覆盖准则时，测试生成所需要的状态数、迁移数都较少，相比于其他方法，生成效率平均提高了1.85倍，为后续进行线程调度序列对并发程序故障检测效果的研究奠定了基础。

目录

声明

摘要

第一章 绪论

1．1 课题研究背景和意义

1．2 国内外研究现状

1．2．1 并发程序测试研究现状

1．2．2 并发程序测试覆盖准则研究现状

1．2．3 并发程序线程调度序列生成研究现状

1．3 课题主要研究内容

1．4 本文组织结构

第二章 并发程序测试概述

2．1 并发程序测试方法

2．1．1 静态分析方法

2．1．2 动态执行方法

2．1．3 模型检测方法

2．2 并发程序测试覆盖准则

2．3 并发程序线程调度序列生成策略

2．4 本章小结

第三章 同步对及全同步对覆盖准则

3．1 并发程序的同步特征及同步语句

3．1．1 同步特征

3．1．2 同步语句

3．2 同步对定义和识别

3．3 全同步对覆盖准则定义

3．4 本章小结

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

4．1 方法框架

4．2 同步对-线程关联图构建

4．3 基于全同步对覆盖准则的线程调度序列生成方法

4．3．1 线程调度序列生成原理

4．3．2 线程调度序列生成算法描述

4．4 本章小结

第五章 基于JPF的线程调度序列生成器设计与实现

5．1 生成器框架

5．2 并发覆盖监听器

5．3 线程调度序列生成器

5．4 结果分析器

5．5 本章小结

第六章 实验设计与分析

6．1 研究问题

6．2 实验对象和环境

6．3 实验设计及评价指标

6．4 实验结果与分析

6．4．1 线程调度序列覆盖同步对数量分析

6．4．2 线程调度序列生成效率分析

6．4．3 线程调度序列生成数量分析

6．5 本章小结

第七章 结论与展望

7．1 主要成果及创新点

7．2 后续工作与展望

参考文献

致谢

研究成果及发表的学术论文

作者和导师简介