Research On Thread Scheduling Sequence Generation Based On Concurrent Coverage Criteria

The emergence of multi-core processor makes multi-threading technology develop rapidly. The software quality of multi-thread concurrent programs becomes a common issue of concern by the industry. Due to the different of Thread Scheduling Sequence, shorted by TSS, multi-thread program will produce different results. Thread scheduling sequence is a key factor in multi-thread concurrent program testing. With the increasing of threads number, TSS number increases exponentially. TSS number and cost of test generation seriously affect the efficiency of multi-thread program testing. Test coverage criteria is a measure of test effectiveness, which is also used to guide the test generation of multi-thread program. Generating TSS based on concurrent coverage criteria pays more emphasis on testing the characteristics of concurrency for programs under test. As a result, according to the concurrent coverage criteria, exploring how to generate TSSs becomes an urgent problem in multi-thread program testing.Synchronization is an important character in concurrent programming. So, this thesis proposes a TSS generation method based on all synchronization pairs coverage criteria, denoted by TGBA. More specifically, we define the synchronization pair with respect to the synchronization statements as well as all synchronization pairs coverage criteria, shorted by APSC. Then a construction method of synchronization pair thread graph is given. On that basis, the method how to generate TSS according to APSC is discussed. Finally, with the help of JPF, a TSS generator is designed and implemented and is used to automatically generate TSSs for the programs under test.To evaluate the efficiency of TGBA method, a lot of experiments are conducted on TSS generation for six Java Library concurrent programs, and generation efficiency is compared with other three widely used TSS generation methods. The results illustrate that TSSs generated by presented method can not only cover all synchronization pairs of programs under test, but also require less number of states and transitions when satisfying the APSC. Moreover, the average generation efficiency increases 1.85 times compared with other three TSS generation methods. As a result, it lays a foundation for exploring the efficiency of concurrent fault detection by using the TSSs.