Testing Concurrent Java Programs using Randomized Scheduling
Scott D. Stoller
The difficulty of finding
errors caused by unexpected interleavings of threads in concurrent
programs is well known. Model checkers can pinpoint such errors and
verify correctness but are not easily scalable to large programs.
The approach discussed here is more scalable but less systematic. We
transform a given Java program by inserting calls to a
scheduling function at selected points. The scheduling function
either does nothing or causes a context switch. The simplest
scheduling function makes the choice blindly using a pseudo-random
number generator; more sophisticated scheduling functions use
heuristics to weight the choices. We try to insert as few calls as
possible while still ensuring that for each reachable deadlock and
assertion violation, there is a sequence of choices by the scheduling
function that leads to it; thus, there is a non-zero probability of
finding it by testing the transformed program, regardless of the
scheduling policies of the underlying Java Virtual Machine.
BibTeX
PDF
Scott Stoller's Home Page