Formal testing for multithreaded code

No, there isn't. The problem is that unit testing has a lot of trouble catching race conditions and other surprising multi-threaded behavior, because the hardware and the other programs running on the computer have a non-deterministic impact on testing.

Ultimately, you should never develop a non-trivial multi-threaded app, instead keeping yourself to a non-trivial app with trivial multi-threading. There are a lot of known techniques available to ensure that multi-threading is kept local and does not affec other parts of the program. Resist the temptation to let multi-threading overflow its bounds and permeate everything.

In theory, a unit test that achieves 100% code coverage, will test for all deterministic behavior. With multi-threaded code, this isn't even nearly sufficient criteria.

A google search for "testing concurrent-programs" returns some interesting results, including several articles.

Quote:

Original post by ToohrVyk Ultimately, you should never develop a non-trivial multi-threaded app, instead keeping yourself to a non-trivial app with trivial multi-threading. There are a lot of known techniques available to ensure that multi-threading is kept local and does not affec other parts of the program. Resist the temptation to let multi-threading overflow its bounds and permeate everything.

I don't think you can develop a complex app which effectively uses threading by trying to keep threading in its own little box... this isn't a game with a render loop, AI loop, logic loop etc, but an event driven system where the events are basically fired by several external threads.

Quote:

Original post by d000hg I don't think you can develop a complex app which effectively uses threading by trying to keep threading in its own little box... this isn't a game with a render loop, AI loop, logic loop etc, but an event driven system where the events are basically fired by several external threads.

You won't be able to develop a complex app which effectively uses threading by letting threads play around everywhere. The human brain is simply too limited to handle it. You need some kind of separation somewhere, otherwise you'll just end up missing a race condition somewhere.

Even if your system does not fit the "render loop, AI loop, logic loop" common in video games, there are many other parallel architectures that you can apply (sinks/pipelines, communicating servers, service-based designs etc) to reduce the pervasiveness of threading.

Quote:

Original post by d000hg Is it appropriate to use unit testing to verify the thread-safety of code

Typically no unit testing is for units of functionality say a function or a class. Once you move on from the unit level it is no longer called unit testing, but integration testing since you are integrating units together.

Victor - can you point to resources on good thread architecture by established authors who know their stuff? Free and paid.

Quote:

Original post by thedustbustr Victor - can you point to resources on good thread architecture by established authors who know their stuff? Free and paid.

In a general sort of way, have you looked at parallel design strategies out there? ACE's Active objects,ACE's services, OpenMp's compiler directives, MPI's share nothing and pass messages, Intel's TBB(similar to openmp but template based instead of compiler directives). Those are all implementations of different design patterns for parallel development reading up on them should help expose you to their underlying theories of parallel development.

Quote:

Original post by thedustbustr Victor - can you point to resources on good thread architecture by established authors who know their stuff? Free and paid.

Pi-calculus (book, wikipedia) is a sound theoretical starting point for examining message-based architectures. Wikipedia also has a short list of patterns that can be at home in a concurrent environment. Although for Java, this book hints at some architecture possibilities despite Java's suicide-inducing approach to concurrent programming.

In fairness, while unit testing is far from foolproof, you can develop some tests for multi-threaded code, as long as you do it under the understanding that knowing the test passed doesn't necessarily mean your multi-threaded code will always work under those same input parameters. In particular, I had worked on one system where we used such a technique to detect potential deadlocks. We could dynamically configure things so the mutexes and semaphores would timeout if they were locked longer than expected. If a mutex or semaphore timed out and raised an exception, we would know about it, knew where things were when they deadlocked and it would give some indication of how to solve things.

In general though, multi-threaded code is among the most difficult to test reliably, and is one of the areas where the TDD books will say unit testing isn't the best mechanism for approaching it.

As a general response, I agree with ToohrVyk about multi-threading recklessly being dangerous. If you limit the scope of the code that has to be aware of the multi-threading, you can eliminate most of the risk involved.

It's not unit testing, but I recently attended a talk given by Andreas Zeller, and I think what he had to say might be relevant. His focus is to provide automatic assistance during debugging to make debugging a less onerous effort. You can see how this has direct links to formal testing.

Anyway, he was pretty enthusastic about the potential for automated debugging techniques to detect and assist in the correction of problems in concurrent environments. His research on Delta Debugging is here, and most of his work is open source.

http://www.st.cs.uni-sb.de/dd/

His work on threads involved some secret IBM tech, but he does explain what the IBM system had that made this possible. Here's the paper: http://www.st.cs.uni-sb.de/papers/issta2002/.

If you're interested, I implemented the Boost.Thread API in terms of user space threads (Fibers on Windows, on POSIX). It allows you test algorithmic correctness in isolation from synchronization correctness. Or looking at it another way, it provides a mock for threads.

You'll still need your stress tests and so on of course, but every little helps.

Currently, it matches the boost 1.34 threads API. I still need to update to 1.35.

Quote:

if you're interested, I implemented the Boost.Thread API in terms of user space threads (Fibers on Windows, on POSIX). It allows you test algorithmic correctness in isolation from synchronization correctness. Or looking at it another way, it provides a mock for threads.

Wow!!, You wouldn't by any chance implement a coroutine interface on top of the boost::thread api would you ? i have looked at the boost coroutine thing/attempt/submission that i think wasnt accepted in the past quickly and it looked arbitrarily complex - i think you had to carry around a context as a template specialisation or something

apologies for not pursuing the link - its almost midnight at work here and i have to leave and will loose the connection, but will check it out first instance tommorow.

Quote:

Original post by chairthrower Quote: if you're interested, I implemented the Boost.Thread API in terms of user space threads (Fibers on Windows, on POSIX). It allows you test algorithmic correctness in isolation from synchronization correctness. Or looking at it another way, it provides a mock for threads. Wow!!, You wouldn't by any chance implement a coroutine interface on top of the boost::thread api would you ? i have looked at the boost coroutine thing/attempt/submission that i think wasnt accepted in the past quickly and it looked arbitrarily complex - i think you had to carry around a context as a template specialisation or something

I wouldn't :) But! It should be very easy to do yourself. My thread class has a schedule function that you can use to force a context switch.

You may also be interested in this thread on the boost developers mailing list. The conclusion is that I may implement my library in terms of boost.coroutine because it was recently refactored to make it more suitable for this kind of thing; you may also want to look at Boost.Coroutine again.

EDIT: it would be irresponsible of me to not mention that I wouldn't use either Boost.Coroutine or my implementation of Boost.Thread in production code. The interaction with C++ language constructs is sparsely documented and rather fragile. For example, fibers work in conjunction with the DWARF exception handling mechanism, but not SJLJ exceptions. Also the POSIX API for user-space threads has been deprecated.

But it's still fun to play with and serves it purpose as a testing tool rather well, I think.

well i was going to say that your project sounded very worthy of boost inclusion consideration - but you beat me to it ;-). its amazing how far c++ can be made work - thanks for the information and context.