JThreadUnit

New versions of JThreadUnit are available at www.krasama.com/jthreadunit.

JThreadUnit supports deterministic unit testing of multithreaded Java code. It is a simple add-on to the JUnit unit testing framework. A test creates several TestThread instances which it can control at various granularities, including testing for whether a thread is blocked after a controlled sequence of concurrent operations.

This project already has useful code written for immediate release. The project will distribute that code, coordinate enhancements, and serve as a focal point for advancing the science and art of deterministic unit testing of multithreaded Java code.

There are a few packages out there for testing multithreaded Java code, but all use a nondeterministic load-based approach, executing a large number of concurrent operations repeatedly to uncover defects. This project will differentiate itself by promoting deterministic unit testing techniques.

Examples

A handful of examples are included, which also serve as the tests for TestThread itself. In fact, initially I started by test-driving Semaphore and figuring out what I needed. TestThread emerged from those tests.

One of the most common errors in multithreaded Java programming is using notify() where notifyAll() is required, and this has also been one of the hardest errors to test, until now. Some of the examples still use notify() incorrectly, and this is intentional—I will leave them that way until I get around to writing a test that actually uncovers the bug.

Try it: Change any notifyAll() in the examples to notify() and a test should fail. If none does, let me know! :)

And for any remaining usage of notify() which you believe is incorrect, please submit a test case that proves it.

Please see ExtremeProgrammingChallengeFourteen for inspiration. Its BoundedBuffer problem is included in the examples, complete with a test for the bug and a fixed version of the class.

Caveats

JThreadUnit requires Java 1.5, which is still in beta. It uses the new java.lang.management facilities (specifically, ThreadMBean) to check whether a thread is blocked or running. My original approach, prior to Java 1.5, simply did a timed wait for a signal from the thread; if the signal fired within the wait time, the thread was obviously not blocked, and if the signal did not fire within that time, the thread was presumed to be blocked. This was both slow and fragile, so I've been waiting and watching for some way to actually get under the thread manager's skin and see what's going on. Now we have it, and the code is much simpler now, as well as faster and more robust.

There are a few imperfections, things that I've gotten to work reliably but that the language might not guarantee:

A few of the tests (the trickiest ones) rely on the ordering of several threads blocked on a particular monitor. It seems to be the case that the order in which threads acquire a monitor is precisely the order in which they arrive at the monitor. However, the language specification says explicitly that the order is arbitrary. Both make sense to me—I would expect the JVM to simply use a queue of threads, and I would expect the language to not guarantee it.
When checking that a thread has become unblocked, the code does a Thread.yield() and then asks ThreadMBean for the thread's status. This alone does not always give the thread a chance to get into the running state. I have improved the situation by fiddling with thread priorities—the parent thread (the test itself) is set to Thread.MIN_PRIORITY and each TestThread is set to Thread.MAX_PRIORITY to give them as much chance as possible to get their act together.
Threads sometimes block on system objects held temporarily by arbitrary other threads. For example, I've occasionally seen threads blocked on an unknown object of type int[][]. Therefore when checking whether a thread is blocked in an interesting way, we have to be careful to ignore these cases. My solution is to put all TestThreads involved in a particular test into a single ThreadGroup, and then instead of just checking the state of the thread being asserted on, all the threads in the group are allowed to run until they are all either waiting or blocked on locks held by other threads in the same group.

If you ever see any of the included tests fail, please let me know right away!

Code Review

Another caveat is that JThreadUnit does not help to uncover problems with unsynchronized access to shared variables. JThreadUnit is based on carefully choreographing locking, waiting, and notifying actions to make sure that mutual exclusion and signalling are happening as expected. This approach can catch deadlocks and certain kinds of race conditions as well.

However, because TestThread is synchronized itself, every test action is surrounded by memory barriers, causing all variables to be flushed to main memory. Therefore JThreadUnit actually hides potential problems with memory access. The double-checked locking idiom is an all-too-common example of this kind of error.

Short of simulating a multi-processor machine, the only way to find memory access problems is static code analysis, by peer code review with the aid of static analysis tools.

For example, any code that violates any of these rules requires very close scrutiny:

Never read or write a shared variable outside of a synchronized block.
Always surround wait() with a while-loop.
Always use notifyAll() instead of notify().

(Only the first is outside of the scope of JThreadUnit, however.)

Tools such as FindBugs and JLint perform static analysis to automatically detect potential problems with unsynchronized access to shared variables, deadlocks, and race conditions (as well as other classes of common bugs).

We should also watch JML and related tools such as Krakatoa and look forward to being able to formally prove our multithreaded Java code.