Testing Concurrent Java Programs using Randomized Scheduling

Abstract

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.