Testing for Synchronization

Testing for Synchronization

The special thing about the objects we tested in was that they created their own threads to handle specific services in the background. The situation is different with objects that do not create threads themselves, but have methods that can be invoked by different threads. Such objects have to be thread-safe, which means that there are synchronization mechanisms to prevent threads from bumping into one another. In addition, we have to ensure that the synchronization does not lead to deadlocks or thread starvation. Another task of synchronization may consist of having a thread wait until a specific condition is true. Consider a simple example: BoundedCounter, a counter with limits. The counter should support incrementing, decrementing, and requesting a number of the type long. In addition, there are upper and lower count limits. As soon as the counter reaches such a limit, then a thread that would potentially exceed the limit with its invocation would be stopped until another thread finishes its reverse count operation. ^[5]

Simple Test Cases

Let's try to do a test-first implementation of this class. We will first use a few single-threaded test cases:

public class SingleThreadBoundedCounterTest extends TestCase {
 private BoundedCounter counter;
 protected void setUp() {
 counter = new BoundedCounter(0, 3);
 }
 public void testCreation() {
 BoundedCounter counter = new BoundedCounter(0, 3);
 assertEquals(0, counter.getMin());
 assertEquals(3, counter.getMax());
 assertEquals(0, counter.count());
 counter = new BoundedCounter(1, 4);
 assertEquals(1, counter.getMin());
 assertEquals(4, counter.getMax());
 assertEquals(1, counter.count());
 }
 public void testCountUpToMax() {
 counter.increment();
 assertEquals(1, counter.count());
 counter.increment();
 assertEquals(2, counter.count());
 counter.increment();
 assertEquals(3, counter.count());
 }
 public void testCountDownToMin() {
 counter.increment();
 counter.increment();
 counter.increment();
 assertEquals(3, counter.count());
 counter.decrement();
 assertEquals(2, counter.count());
 counter.decrement();
 assertEquals(1, counter.count());
 counter.decrement();
 assertEquals(0, counter.count());
 }
}

Note that the test cases of this suite go only up to the limit of the count range. Each attempt to count beyond the limits would eventually doom the counting thread, and thus our test, to wait forever, as per specification.

Concurrent Test Cases

The following test cases require starting and coordinating several threads. In contrast to the service objects used in the previous subsection, this case offers us the benefit that no thread is created in the background. This means that we control all threads, which gives us more control over our testing. Consider the first test case: this test should verify that a thread is suspended as soon as it attempts to increment the counter beyond its maximum value. Basically, this test needs three threads, specifically, two threads to handle the BoundedCounter instance, and another one to verify specific conditions and to keep the actions in the right order. One option to synchronize the order of actions in several threads is to use appropriate sleep times (i.e., Thread.sleep(...)), in each of these threads. However, the drawback of this concept is that calculating the sleep times is expensive and error-prone, especially in complex scenarios. In addition, we have to select much longer times than actually needed due to the scheduler's imponderabilities, the unknown runtime of single command sequences, and the different platforms on which we might want to run the tests. Therefore using sleep() statements in tests should be avoided. One reviewer pointed out that there is another problem with naively inserting Thread.sleep into app code since it can change the program's behavior in the presence of an InterruptedException. All sleeps should therefore use the following pattern which properly resets the internal interruption state without introducing an exception throw:

try {
 Thread.sleep(delay);
} catch (InterruptedException ie) {
 Thread.currentThread().interrupt();
}

An elegant approach to replace sleep() invocations in the tests would again be the use of Java's built-in synchronization mechanisms. A simple way to control several threads exists in the class utmj.threaded.ConcurrentTestCase for testing purposes. We will consider the test case just formulated as source code to better understand this idea:

import utmj.threaded.*;
public class ConcurrentBoundedCounterTest extends
 ConcurrentTestCase {
 public void testCountBeyondMax() {
 final BoundedCounter counter = new BoundedCounter(0, 2);
 Runnable runnable1 = new Runnable() {
 public void run() {
 try {
 counter.increment();
 counter.increment();
 checkpoint("before increment");
 counter.increment(); // should wait
 checkpoint("after increment");
 } catch (InterruptedException ignore) {}
 }
 };
 this.addThread("thread1", runnable1);
 this.startAndJoinThreads(200);
 assertEquals(2, counter.count());
 assertTrue("before checkpoint",
 this.checkpointReached("before increment"));
 assertFalse("after checkpoint",
 this.checkpointReached("after increment"));
 assertTrue("deadlock", this.deadlockDetected());
 }
}

When deriving our test cases from ConcurrentTestCase, we have a way to add test threads by naming and implementing a Runnable object. There are various methods to start all threads. The variant used here-startAndJoinThreads(long timeout)-waits for a maximum of timeout milliseconds for all threads to end. Finally, we can pass a checkpoint-checkpoint (String name)-to check whether or not they have been passed-checkpointReached(String name)-and then verify whether or not a deadlock occurred in one of the threads-deadlockDetected(). Table 10.1 gives an overview of the methods available in ConcurrentTestCase.

The second test case should verify that a thread waiting since it reached the maximum value can start incrementing again in another thread after a decrement():

public void testThreeUpOneDown() {
 final BoundedCounter counter = new BoundedCounter(0, 2);
 Runnable runnable1 = new Runnable() {
 public void run() {
 try {
 counter.increment();
 counter.increment();
 checkpoint("before increment");
 counter.increment(); // should wait
 checkpoint("after increment");
 } catch (InterruptedException ignore) {}
 }
 };
 Runnable runnable2 = new Runnable() {

 public void run() {
 try {
 waitForCheckpoint("before increment");
 sleep(50); // (1)
 counter.decrement();
 } catch (InterruptedException ignore) {}
 }
 };
 this.addThread("thread1", runnable1);
 this.addThread("thread2", runnable2);
 this.startAndJoinThreads(200);
 assertEquals(2, counter.count());
 assertTrue("after checkpoint",
 this.checkpointReached("after increment"));
 assertFalse("no deadlock", this.deadlockDetected());
}

We can see another possibility for synchronization in the runnable2 object, namely, waitForCheckpoint(String name) waits till another thread has passed a specific checkpoint. And yet, we cannot do without sleep(...) in this case either. Although we know from point (1) in thread2 that thread1 has left the checkpoint behind, we want to additionally make sure it has already sent the third increment() message. Unless we manipulate the BoundedCounter class, the only thing that can help us here is pseudodeterminism, by adding sleep calls. Once we have added two appropriate test cases for the minimum value, the implementation of BoundedCounter looks like this:

public class BoundedCounter {
 ...
 public BoundedCounter(long min, long max) {...}
 public long getMin() {...}
 public long getMax() {...}
 public long count() {return count;}
 public synchronized void increment()
 throws InterruptedException {
 while (count == max) {
 this.wait();
 }
 count++;
 this.notify();
 }
 public synchronized void decrement()
 throws InterruptedException {
 while (count == min) {
 this.wait();
 }
 count--;
 this.notify();
 }
}

The Class seems to be working well and, indeed, we managed to infiltrate synchronization and thread mechanisms into the program thanks to our test-first effort. But careful, there are still a few pitfalls.

Nondeterministic Test Cases

Experienced thread programmers can make out the flaws in the preceding implementation quickly: First, the notify() in decrement() and increment() can cause problems when more than two threads are working. It should be replaced by notifyAll() in both cases. Second, the method count() should be synchronized, because access to a variable of the type long may not be atomic. Is it possible now to find test cases that identify these two problematic implementations? First, let's deal with the notify problem. For the problem to be noticed, at least one thread has to be waiting till it gets a chance to increment the counter and another one to decrement the counter. The following test attempts to bring this situation about in a 10 to 1 ratio:

public class NonDeterministicBoundedCounterTest
 extends ConcurrentTestCase {
 ...
 public void test10Inc1Dec() {
 final BoundedCounter counter = new BoundedCounter(0, 1);
 Runnable incRunnable = new Runnable() {
 public void run() {
 try {
 counter.increment();
 } catch (InterruptedException ignore) {}
 }
 };
 Runnable decRunnable = new Runnable() {
 public void run() {
 try {
 for (int i = 0; i < 10; i++) {
 counter.decrement();
 }
 } catch (InterruptedException ignore) {}
 }
 };
 this.addThread("dec", decRunnable);
 for (int i = 0; i < 10; i++) {
 this.addThread("inc-" + i, incRunnable);
 }
 this.startThreads();
 this.joinAllThreads(1000);
 assertTrue("deadlock", !this.deadlockDetected());
 assertEquals(0, counter.count());
 }
}

Initially, the bar remains green while the test case is running. But when we repeatedly click Run, we get a failure now and then: junit.framework. AssertionFailedError: deadlock. What happened? Considering that notify() brings only one single thread back to life, we can wake up a thread with continuation conditions that have not been met yet, depending on our luck and the scheduler's state. However, the outcome of the test is not predictable for each individual case. To provoke a failure with high probability, we have to run the test suite several times; 10 repetitions will do in this case: ^[6]

public class NonDeterministicBoundedCounterTest
 extends ConcurrentTestCase {
 ...
 public static Test suite() {
 TestSuite suite = new TestSuite(
 NonDeterministicBoundedCounterTest.class);
 return new junit.extensions.RepeatedTest(suite, 10);
 }
}

Now, the faulty test suite forces us to correct the class BoundedCounter:

public class BoundedCounter {
 ...
 public synchronized void increment()
 throws InterruptedException {
 while (count == max) {
 this.wait();
 }
 count++;
 this.notifyAll();
 }
 public synchronized void decrement()
 throws InterruptedException {
 while (count == min) {
 this.wait();
 }
 count--;
 this.notifyAll();
 }
}

A similar attempt to force synchronization of the count() method over a repeated nondeterministic test fails. ^[7] The reasons can be manifold: access to a long variable need not be atomic, according to the Java specification, but it can be, and in fact it is atomic on most processors and JVMs.

The problem could also occur when several processors are used, depending on the computer architecture and the operating system. In any event, I was not able to write a test that led to a faulty behavior of the method count(), even repeating it thousands of times. Nevertheless, most developers would probably make the following change:

public class BoundedCounter {
 public synchronized long count() {return count;}
}

^[5]Lea [00] uses this example often. A more complex variant of it (i.e., the class BoundedBuffer) is included in the source code to this tutorial. ^[6]This number can fluctuate strongly, depending on JVM and computer equipment. ^[7]The source code for the test method testCount() is available from the tutorial's Web site.

• Previous
• Next