How are multi-threaded tests in Java possible?

November 26, 2019

Category: The package java.util.concurrent.atomic

Testing multi-threaded software is hard since bugs depend on specific thread interleaving. So to write meaningful tests we need a way to test all thread interleavings. Here comes the Java Memory Model into the play. The Java Memory Model not only enables us to write multi-threaded software but also allows us to write a test for this multi-threaded software. It tells us which thread interleavings exist and gives us a way to create all the different thread interleavings.

The Java Memory Model defines synchronization actions like locking a monitor or reading and writing of a volatile variable. And it guarantees that if all reads and writes to shared variables can be ordered through those synchronization actions there is a total order over all individual actions (such as reads and writes) which is consistent with the order of the program, and each individual action is atomic and is immediately visible to every thread.

On the other side, if the reads and writes to shared variables can not be ordered, a data race exists in the program. A data race means that the order is not defined by the Java Memory Model. Components like the compiler or the CPU can reorder the reads and writes in nonintuitive ways and the threads can read stale values.

How to test all thread interleavings?

So to test all interleavings in a systematic way we need to:

  1. For each related sync action a and b create a run with a before b and b before a. Two synchronization actions are related if they can create a synchronized-with relation defined by the JavaMemory Model. For example, a write to a volatile variable creates a synchronized-with relation with a subsequent read from this variable. So the read and the write to the same volatile variable are related.
  2. Check for data races and flag them as error

Let us look at an example to see how this works in practice. Let us use one thread, thread A, to write to volatile variable v and one thread, thread B, to read from this volatile variable. We have the following two thread interleavings:

First Thread A than B

  • Thread A writes to v
  • Thread B reads from v
And second, thread B than A:
  • Thread B reads from v
  • Thread A writes to v

Only the first interleaving, thread A writes than thread B reads, creates a synchronized with relation. If we add a read and write of a normal variable we will see that the second interleaving leads to data races.

Let us see how this looks like by letting Thread A write to the normal field n before writing to the volatile variable v. And let thread B first write from the volatile variable v and then read from the normal field n. Now we have the following four potential thread interleavings:

First:

  • Thread A writes to n
  • Thread A writes to v
  • Thread B reads from v
  • Thread B reads from n
Second:
  • Thread B reads from v
  • Thread A writes to n
  • Thread A writes to v
  • Thread B reads from n
Third:
  • Thread A writes to n
  • Thread B reads from v
  • Thread A writes to v
  • Thread B reads from n
Fourth:
  • Thread A writes to n
  • Thread B reads from v
  • Thread B reads from n
  • Thread A writes to v

Only the first interleaving is data race free.

The example shows to find all data races we need to test all relations between related sync actions. So the two parts, testing of all sync action and checking for data races depend on each other. To find all data races we need to create runs for every combination of related sync actions. And to make sure that our test and thereby our program does not depend on external components like the uses compiler or CPU our program must be data race free.

Summary

The Java Memory Model allows us to write a test for this multi-threaded software. It defines which thread interleavings exist and gives us a way to create all different thread interleavings.

Make your application thread safe

LEARN MORE