Testing concurrency/thread-safety

Question

A program I have wrote uses multiple threads and I believe my program is thread-safe but how can I really know?

I've read a number of examples online and none of them describe how to test the code is actually thread-safe or not, nor have I found a reliable way to cause a conflict.

Most of what I've tested regarding concurrency has mostly been cross your fingers and hope stuff. Indeed there have been a few instances where the code would conflict on a regular basis, but what can I do to reassure the people using my code, and myself, that the code is robust and reliable?

Answer 1

You can't (realistically) prove thread safety exhaustively for a language like Java, but there are ways to detect some bugs.

The official behaviour of your Java program when run on several threads is defined by Chapter 17 of the JLS. The only way to prove that a program is thread safe is by applying all those rules in a theoretical way, which in most scenarios is too complex.

There are a few static analysis tools that can help, such as FindBugs, but they will only cover the most obvious errors.

There are some stress testing tools such as jcstress that will run your code many times until they get confident that they behave as expected - but some concurrency bugs will only appear on specific hardware / JVMs. For example the memory model of x86 CPUs is fairly strong and will never display concurrency bugs that would show up on weaker memory models.

Similarly, some JVMs will optimise your code more aggressively then others and will trigger more bugs by doing so (for example: variable hosting).

In the end, a reasonable path is a combination of:

• in-depth understanding of the memory model to avoid as many pitfalls as possible at design time
• a good testing framework (e.g. jcstress) that you run on various computers (mixing OSes and CPUs) to hopefully spot any remaining issues

Answer 2

Thread safety means correctness in the face of the exponentially many possible interactions between concurrent processes. Many concurrency-related bugs occur only in a small minority of possible interleavings (but still occur in production because "One in a million is next Tuesday"). Additionally, testing in general is better at finding bugs than assuring their absence. These facts combined mean that software testing has a very hard time giving any confidence for the absence of thread safety bugs.

There is a lot of research into improving this state, by devising techniques that more efficiently find an interleaving that triggers a bug. However, the cost/benefit ration is still rather bad compared to testing for other kinds of bugs.

A more effective approach may be to adopt discipline that is guaranteed to prevent data races. For example, data that is not shared between threads at all doesn't cause problems, and immutable data can't cause data races either. This means using better abstractions than shared-everything-mutable-memory with bare locks. Actors, message passing, map-reduce, fork-join workers that don't share data (serialize the accumulation of the partial results), and other paradigms have greater probability of correct code. Even if these tools can't express everything you'd like to parallelize, you can try doing as much as possible with them.

Unfortunately, Java the language doesn't provide a lot of tools to enforce such discipline, but using libraries/frameworks that provide them and perhaps perform run-time checks are better than nothing. There are also tools (for C++ at least, don't know if something similar exists for Java) that try to enforce proper locking discipline by associating the secured data with the lock and trying to make sure the data is not accessed while the lock isn't held.

Answer 3

Demonstrating thread-safety means proving that every possible interleaving of the instructions in two opcode streams leads to the correct result. Therefore, in order to test this property, you must be able to interleave those instructions as desired.

In practice, this means that you must have some kind of hook within code that is normally run as a unit. This usually involves adding hooks of some kind to the code that allow you to start and stop the processing at well-defined points. It can be done via AOP, or via reflection, or of course manually; Jaroslav Tulach once described a cool technique in which he exploits the log4j statements that are already present in his business code for this purpose. But all of those possibilities tend to be high-effort endeavours. That is only one reason why thread-safety is rare, and proper thread-safety testing is even rarer.

Answer 4

You have not told us what kind of multi-threading you do, but I presume you do multi-threading of the locking kind, (you use the synchronized keyword of java,) otherwise you probably would not be asking the question.

As testing has gained ground in the software engineering discipline during the last decade or so, multi-threading of the locking kind has fallen from favor proportionally. That's because multi-threading code of the locking kind cannot really be tested.

Instead, the modern line of thinking with respect to multi-threading is to prefer mechanisms which eliminate dependencies between threads. This way, the code can be properly tested in a sequential fashion, and it is (sort of) guaranteed to work when put in parallel threads, because the parallel threads do not depend on each other.

One very important tool for accomplishing this is message passing. This means that each thread receives data to operate upon in a message queue, and sends processed data out via another message queue. The messages are immutable objects, so it is impossible for one thread to inadvertently modify the contents of a message, causing corruption in a different thread. Essentially, locking is still used, but it is localized in just one small class, the class that implements the actual message queue, which can be safely be presumed to already be thoroughly tested and in perfect working order.

If you have a lot of data to process, you might think that collecting it and packaging it into immutable objects and placing it in queues might represent a significant overhead, but actually this tends to be offset (sometimes greatly offset) by the fact that once a thread has a chunk of data to process, it can work on it without having to keep locking it all the time. You see, every time you try to lock something which happens to already be locked by another thread, your thread gets placed in a waiting state, which is a huge performance penalty.