Testing Concurrent Programs - Java Concurrency in Practice - page 291

12.1.3. Testing Safety
The tests in Listings 12.2 and 12.3 test important properties of the bounded buffer, but are
unlikely to disclose errors stemming from data races. To test that a concurrent class performs
correctly under unpredictable concurrent access, we need to set up multiple threads perform-
ing put and take operations over some amount of time and then somehow test that nothing
went wrong.
Constructing tests to disclose safety errors in concurrent classes is a chicken-and-egg prob-
lem: the test programs themselves are concurrent programs. Developing good concurrent
tests can be more difficult than developing the classes they test.
The challenge to constructing effective safety tests for concurrent classes is identifying easily
checked properties that will, with high probability, fail if something goes wrong, while at the
same time not letting the failureauditing code limit concurrency artificially. It is best if check-
ing the test property does not require any synchronization.
One approach that works well with classes used in producer-consumer designs (like Boun-
dedBuffer ) is to check that everything put into a queue or buffer comes out of it, and that
nothing else does. A naive implementation of this approach would insert the element into a
“shadow”list when it is put on the queue, remove it from the list when it is removed from the
queue, and assert that the shadow list is empty when the test has finished. But this approach
would distort the scheduling of the test threads because modifying the shadow list would re-
quire synchronization and possibly blocking.
A better approach is to compute checksums of the elements that are enqueued and dequeued
using an order-sensitive checksum function, and compare them. If they match, the test passes.
This approach works best when there is a single producer putting elements into the buffer
and a single consumer taking them out, because it can test not only that the right elements
(probably) came out but that they came out in the right order.
Extending this approach to a multiple-producer, multiple-consumer situation requires using
a checksum function that is insensitive to the order in which the elements are combined, so
that multiple checksums can be combined after the test. Otherwise, synchronizing access to
a shared checksum field could become a concurrency bottleneck or distort the timing of the
test. (Any commutative operation, such as addition or XOR, meets these requirements.)