A Concurrent Affair

On the other hand, I think I can re-enable checking if the event thread has finished and generating EventThreadStillProcessingErrors in the “update” Runnable that sets the test thread group the event thread uses, at least in certain cases.

It is possible that test A has generated the EventThreadStillProcessingError by putting a long Runnable aRunnable on the event queue. When test B starts executing, it puts an update Runnable updateB on the event queue, but it doesn’t execute yet.

If aRunnable finishes now and updateB executes while test B is still running, we can enable checking the event thread again. The event thread has “caught up” with the tests, so to speak.

If, on the other hand, test B finishes before aRunnable finishes, then test C will begin and enqueue an update Runnable updateC. Now aRunnable finishes and updateB executes. Here we clearly don’t want to enable checking, because test C is already executing.

So, if the test’s thread group and the new thread group for the event thread are identical, we can re-enable checking the event thread, because that means the event thread has caught up sufficiently.

I think I have just realized that this still isn’t good enough. Now we know that there aren’t any more events, but it is conceivable that a Runnable executing just before the token Runnable has started new threads. Those threads could fail, or add new “token” Runnables. It seems like the whole thing needs to be put in a loop.

I’ve just made a new release of ConcJUnit: 20100112. This release contains an important addition that I had been thinking about for a while.

ConcJUnit already detected failures and uncaught exceptions in the event thread, but since the event thread is a daemon thread started by the system, it is not part of the “join” and “lucky” checks. It is not required to join the event thread with the test’s main thread (in fact, it’s not really possible, since there is no way to terminate the event thread), and that also means that I do not check if the event thread finished processing.

That was a problem, of course. It was possible to put a Runnable on the event queue and then end the test, resulting in a success, even though the code in the Runnable may still fail.

I have now added code that checks if the event thread is running, and if that is the case, we check if the event queue is empty, as it should be. If it isn’t, then we issue an EventThreadStillProcessingError, which is a subclass of a NoJoinError.

However, an empty event queue does not guarantee that the event thread has finished processing. There way still be a Runnable executing in the event thread; there just aren’t any more events queued up after it. So we need to make sure that there isn’t an event being processed right now; I currently do that by adding a “token” Runnable to the event queue and requiring that it executes immediately (@ Immediately practically means “very quickly”; currently within 100 ms. That’s not exactly the same, but hopefully close enough. @).

But even if the token Runnable gets to execute right away, it isn’t guaranteed that the test’s events have all been processed. We also have to ensure that after we checked that the event queue was empty and before the token Runnable began executing, no additional Runnable objects were added to the event queue. Those additional events would have been added after the token Runnable, so inside the token Runnable we check again if the event queue is empty.

If the token Runnable executed immediately and the event queue is still empty when it executes, then we know that there aren’t anymore events that need to be processed and that could fail, and the test has completed in its entirety. We already checked that there aren’t any more regular threads around that could add new events, and the event thread has finished processing all Runnables.

When a EventThreadStillProcessingError is generated, then the event thread is still executing code belonging to a test that has just ended. I didn’t want to let the test wait for the event thread to finish, I want to allow it to move on. This is sort of a greedy process: Let’s run as many tests as we can. Waiting for the event thread, if not specified by the test code, could mean waiting forever if the event thread is deadlocked. However, if it isn’t deadlocked, and code there is still making progress, then it may also still fail after a new test has already started to execute. The event thread is shared among all tests, so I had to make sure that a failure in the event thread caused by a Runnable belonging to the previous test doesn’t fail the test currently executing.

I do this by maintaining a field containing the test thread group belonging to the current Runnable in the event thread. If the event thread is not running yet, then that field is updated directly at the beginning of each test. If the event thread is running, then we want all Runnables already in the event queue to still notify the test group of the previous test. All future Runnables, however, should use the current test’s thread group, so we update the field in an “update” Runnable which will execute when all Runnables belonging to the previous test have been processed.

Of course, if the event thread is deadlocked, then the update Runnable will never execute. This isn’t any worse, though, than JUnit already behaves. ConcJUnit will still allow tests that do not need the event thread to execute. When a test is executed that requires the event thread, for example by executing a invokeAndWait, then that test will hang. But at least there will have been a EventThreadStillProcessingError pointing out which test is responsible for it.

Another small problem is that once an EventThreadStillProcessingError has been generated, I do not want all following tests to also fail with that error. The event thread may still contain Runnables from the first test that was flawed that way, for example if the event thread is deadlocked. Therefore, once an EventThreadStillProcessingError has occurred, checking whether the event thread has finished is disabled. That means that only one EventThreadStillProcessingError will ever be generated. Later tests that also have this problem may go undetected until the first test has been fixed.

I just submitted the publication version of our SIGCSE 2010 paper, Test-First Java Concurrency for the Classroom.

Now I’m waiting for the copyright form to be sent, and I’m wondering why that’s not done automatically…

I coded up two more examples to test the yield strategy. The “split synchronized” example doesn’t work that well (yet), because it fails even without the added yields. I’m looking for common bugs that aren’t obvious.

Thread remover = new Thread() {
public void run() {
while(l.size()>0) {
l.remove(0);
}
}
};
Thread reader = new Thread() {
public void run() {
for(int i=0; i<10; ++i) { if (l.size()==0) { break; } int e = l.get(l.size()-1); // l.size and l.get not atomic } } };

The important thing here is that the calls to l.size() and l.get may get interrupted by the other thread performing an l.remove(0). I know that this happens quite frequently and is not always as obvious as here (in DrJava, this happened when we tried to append text to a document; append was implemented "insert text at index", and the length was used as index), but right now I'm unable to reproduce that in a short example.

However, I have another example from my COMP 402 course last semester that benefits from the inserted yields:

class WaitRunnable implements Runnable {
public void run() {
sleep(1000);
while(true) {
synchronized(_lock) {
if (_flag) break;
}
// lock dropped here!
synchronized(_lock) {
try { _lock.wait(); }
catch(InterruptedException ie) { /* ignore */ }
}
}
}
}

The problem here is that the condition _flag is checked, but before wait() is called, the lock is dropped. Therefore, another thread may call notify() and change _flag and allow the first thread to enter a wait() from which it will not be woken up.

After a lot of work on Mint, I’m now focusing on the concurrent unit testing project again. I had to fight some apparent code rot, which was probably caused by changes from Java 5 to Java 6, but now everything is working again.

I have a nice example that shows that double-checked locking is broken. With a yield probability of 0.5 and yields in all places (thread start, thread run, thread exit, thread join, before notifies, after notifies, before waits, after waits, before synchronized and after synchronized), it usually shows up in under 10 iterations.

It would be nice to have a simpler way of setting these parameters, e.g. by using an annotation on the test:

@Test(yieldProb=0.5, beforeSynchronized=false)
public void testFoo() { ... }