Thread Interleaving Heuristics: A different kind of structural coverage is based on maximizing thread interleavings. Traditional testing frequently misses subtle race conditions or deadlocks because usually the scheduler cannot be controlled directly. One way to expose concurrency errors is to reward “demonic” scheduling by assigning better heuristic values to states reached by paths involving more switching of threads. In this case, the structure we attempt to explore is the dependency of the threads on precise ordering. If a non-locked variable is accessed in a thread, for instance, and another thread can also access that variable (leading to a race condition that can result in a deadlock or assertion violation), that path will be preferred to one in which the accessing thread continues onwards, perhaps escaping the effects of the race condition by reading the just-altered value. One heuristic that has been shown to be effective is calculated by keeping a (possibly size-limited) history of the threads scheduled on each path:
A) At each step of execution, append the thread just executed to a thread history.
B) Pass through this history, making the heuristic value that will be returned worse each time the thread just executed appears in the history by a value proportional to:
- How far back in the history that execution is, and
- The current number of live threads.