Java Unit Test Challenge Solved

As part of ExtremeProgrammingChallengeFourteen, TomCargill gave us some Java code and asked us ExtremeProgrammers to test it and show that it has a bug of some sort. This is what he gave us:

 import java.lang.*;
 public class BoundedBuffer extends java.lang.Object {
 public Object[] buffer = new Object[4];
 public int putAt, takeAt, occupied;

 synchronized void put(Object x) throws InterruptedException {
 while(occupied == buffer.length)wait();
 notify();
 ++occupied;
 putAt %= buffer.length;
 buffer[putAt++] = x;}

 synchronized Object take() throws InterruptedException {
 while(occupied == 0)wait();
 notify();
 --occupied;
 takeAt %= buffer.length;
 return buffer[takeAt++];}
 }

I took on the task of testing it myself to see what could be done with it. Can we show that it has a bug? Let's see. -- DonWells

---

The first thing we need is of course a SimpleJavaUnitTestFramework. Now that we have that we can add some simple tests, maybe we will see something wrong. I am going to TestThePutMethodFirst in a stand alone fashion. Then I TestTheTakeMethodSecond in a stand alone fashion. No bug yet. I was wrong about there being subtle bugs in the boundary conditions.

Now I have to ExtendTheJavaUnitTestingFramework. The TestingFramework now detects when a deadlock occurs by only letting a test run for a maximum of 5 seconds. Now I feel safe about using real threads in my tests.

I can add a TestForPutInAthread. I can add a TestForTakeInAthread too. Now I have the building blocks to TestBothThreadsRunning simultaneously. That works too. And next I want to TestFourThreadsRunning simultaneously. This works too. I thought it would show a bug, but again UnitTests often show you things are actually working. If this were part of an actual project I would create a few more tests. The first would be to TestTwentyThreadsRunning simultaneously. After that I add a test which tests say TenPutsAndOneTake. Then of course, the opposite, one put and ten takes. And now AbugIsFound. I was thinking though that we should have found this earlier. I decide to go back and AddOneMoreCheckToTestTwentyThreads. Now I am going to remove three of the tests. One is too intrusive and two are redundant. Now as I run this code and listen to it I find that it does not run the same all the time. It is non-deterministic because there is some randomness built into the Java runtime. I need to ExtendTheJavaTestFrameworkForNondeterminism. Now we can see there is indeed a bug.

Fortunately, Tom gave us a quick fix when he gave us ExtremeProgrammingChallengeFourteenTheBug. We can simply change

 notify();

into

 notifyAll();

in both the take and put messages. Let's run our tests again:

We are done. -- DonWells

---

Here is the source for the latest version in zip format.

ftp://members.aol.com/jdwells123/challenge14.zip

I believe it is ok now.

---

Not that I'm sure anybody cares anymore, but why was everyone so hung up about the non-determinism?

 public static void testConcurrency() throws InterruptedException {
final int[] threadsFinished = new int[]{0};
final BoundedBuffer buffer = new BoundedBuffer();

Thread thread1 = new Thread() {
public void run() {
synchronized (buffer) {
synchronized (this) {
this.notifyAll();
}
try {
buffer.wait();
} catch (InterruptedException e) {}
threadsFinished[0]++;
}
}
};
Thread thread2 = new Thread() {
public void run() {
synchronized (buffer) {
synchronized (this) {
this.notifyAll();
}
try {
buffer.wait(); 
} catch (InterruptedException e) {}
threadsFinished[0]++;
}
}
};

synchronized (thread1) {
thread1.start();
thread1.wait();
}
synchronized (thread2) {
thread2.start();
thread2.wait();
}
synchronized (buffer) {
buffer.put("");
thread1.join(1000);
thread2.join(1000);
}
assertEquals("Not all test threads were awoken!", 2, threadsFinished[0]);
 }

Worked the first time, by which I mean, caught the error on the first (and all subsequent runs), and passed on all runs after the notify was changed to notifyAll(). If anything, this would give a false positive, which in the case of concurrency, is much preferable to a false negative one time in a thousand.

The trick in this case is that a usage of 'notify()' vs. 'notifyAll()' can only ever wake up a single thread, and therefore can never wake up both test threads.

Now, a good case could be made for the point that the synchronization object should be an implementation detail; it should really be an internal object being locked on, not the public instance. This would render this particular test useless. So we design for testability, passing in the object to be locked on in the constructor, while still providing a constructor to provide a unique object by default.

--WilliamUnderwood

I haven't examined this page in great detail, but your question "why was everyone so hung up about the non-determinism?" -- you know, the answer to that question never depends on the topic at hand. The answer is, "how can you prove that the non-determinism will never bite you?''

In other words, the real question is not whether a test catches a known non-determinism problem, the question is whether the test is absolutely guaranteed to -- which you didn't comment on. (I trust you are aware that no amount of testing, in itself, can answer that question, since you might get lucky on each test.) -- dm

My point was actually that the first statement of the challenge was to detect a known condition. The 'so hung up about non-determinism' was more of a commentary of the solutions that I saw; basically, I feel they all erred on the wrong side of the coin: why create a test which is known to give false negatives, and that you can therefore never be sure of? Testing has enough holes already, let's not add more.

My improved test shows a single property: that the implementation of 'put()' does not use 'notify()'. That's sufficient if the 'while(<expression>) {wait()}' is used. It would always be sufficient to make sure that 'do{ wait(); notify(); }while(<expression>);' is used.

Basically, I _really_ don't like false negatives in my tests. They're inevitable, but it's best to weed out as many as possible.

--cwillu