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

基于全同步对覆盖准则的线程调度序列生成方法 本文提出了一种基于全同步对覆盖准则的线程调度序列生成方法（TGBA），旨在解决多线程并发程序生成覆盖同步语句的线程调度序列（TSS）效率低的问题。该方法首先定义了同步对和全同步对覆盖（APSC）准则，然后构建同步对-线程关联图（SPTG），接着生成满足APSC的TSS。实验结果表明，TGBA方法生成的TSS能够覆盖全部同步对，并且与常用的默认线程调度（DS）、抢占式线程调度（PS）和交叉线程调度（CS）序列生成方法相比，TGBA方法测试生成所需要的状态数、迁移数至少减少了19889和44352，并且生成效率平均提升了1.95倍。 知识点： 1. 多线程并发程序：多线程并发程序是指在同一个进程中同时执行多个线程，以提高程序的执行效率和响应速度。然而，多线程并发程序也会带来同步问题，导致程序的执行效率下降。 2. 全同步对覆盖准则（APSC）：APSC是指在多线程并发程序中，所有的同步语句都被覆盖的准则。该准则能够确保程序的执行正确性和效率。 3. 同步对：同步对是指在多线程并发程序中，两个或多个线程之间的同步关系。同步对是实现APSC的基础。 4. 同步对-线程关联图（SPTG）：SPTG是指将同步对与线程关联起来的图形结构。该图形结构能够帮助生成满足APSC的TSS。 5. 线程调度序列（TSS）：TSS是指在多线程并发程序中，线程执行的顺序和时序。TSS能够影响程序的执行效率和正确性。 6. 测试生成效率：测试生成效率是指在生成TSS时，程序的执行效率和响应速度。高效的测试生成效率能够提高程序的执行效率和正确性。 7. JPF检测工具：JPF检测工具是一种用于检测多线程并发程序的工具。该工具能够检测程序的执行正确性和效率。 8. 默认线程调度（DS）：DS是一种常用的线程调度方法，该方法根据线程的优先级和执行时间来调度线程的执行顺序。 9. 抢占式线程调度（PS）：PS是一种常用的线程调度方法，该方法根据线程的优先级和执行时间来抢占线程的执行顺序。 10. 交叉线程调度（CS）：CS是一种常用的线程调度方法，该方法根据线程的优先级和执行时间来交叉调度线程的执行顺序。 本文的贡献在于提出了基于全同步对覆盖准则的线程调度序列生成方法，能够提高多线程并发程序的执行效率和正确性。