A Framework for Testing Concurrent Programs
A Framework for Testing Concurrent Programs
by
Mathias Guenter Ricken
A thesis submitted
in partial fulfillment of the
requirements for the degree
Doctor of Philosophy
This study proposes a new framework that can effectively apply unit testing to concurrent programs, which are difficult to develop and debug. Test-driven development, a practice enabling developers to detect bugs early by incorporating unit testing into the development process, has become wide-spread, but it has only been effective for programs with a single thread of control. The order of operations in different threads is essentially non-deterministic, making it more complicated to reason about program properties in concurrent programs than in single-threaded programs. Because hardware, operating systems, and compiler optimizations influence the order in which operations in different threads are executed, debugging is problematic since a problem often cannot be reproduced on other machines. Multi-core processors, which have replaced older single-core designs, have exacerbated these problems because they demand the use of concurrency if programs are to benefit from new processors.
The existing tools for unit testing programs are either flawed or too costly. JUnit, for instance, assumes that programs are single-threaded and therefore does not work for concurrent programs; ConTest and rstest predate the revised Java memory model and make incorrect assumptions about the operations that affect synchronization. Approaches such as model checking or comprehensive schedule-based execution are too costly to be used frequently. All of these problems prevent software developers from adopting the current tools on a large scale. The proposed framework (i) improves JUnit to recognize errors in all threads, a necessary development without which all other improvements are futile, (ii) places some restrictions on the programs to facilitate automatic testing, (iii) provides tools that reduce programmer mistakes, and (iv) re-runs the unit tests with randomized schedules to simulate the execution under different conditions and on different machines, increasing the probability that errors are detected.
The improvements and restrictions, shown not to seriously impede programmers, reliably detect problems that the original JUnit missed. The execution with randomized schedules reveals problems that rarely occur under normal conditions.
With an effective testing tool for concurrent programs, developers can test programs more reliably and decrease the number of errors in spite of the proliferation
of concurrency demanded by modern processors.
