Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Are there ways to unit test your multi-threaded code for race conditions and deadlocks?

To see if they are performing the way they should be...

share|improve this question
add comment

7 Answers

up vote 11 down vote accepted

CHESS, a project of Microsoft Research. Quoting their site:

CHESS is a tool for finding and reproducing Heisenbugs in concurrent programs. CHESS repeatedly runs a concurrent test ensuring that every run takes a different interleaving. If an interleaving results in an error, CHESS can reproduce the interleaving for improved debugging. CHESS is available for both managed and native programs.
share|improve this answer
    
CHESS is a great tool, but it doesn't seem to have been updated for a long time. –  Andy Lowry Nov 25 '10 at 16:50
    
Does it need to be updated, or is it far enough to be very useful? –  Klaim Jan 29 '11 at 11:23
add comment

Valgrind has Helgrind which really helps. Not only does it help point out races that could lead to starvation or deadlock, the slight slowdown of having the program profiled sometimes exposes races that might not be seen otherwise.

So, even if you go commando with some kind of lock free method, it still helps :)

It is POSIX centric, however. It ships with headers that easily make simple unit test libraries like TAP aware that it is running, which is also really helpful. For instance, you could have a thread that normally would not block when trying to acquire a lock go ahead and block (perhaps randomly), just to simulate starvation.

share|improve this answer
1  
speaking of slow down, activating HT on a Pentium provides exactly the opposite thing. It "speeds" up code somehow, which may expose bugs :) –  Matthieu M. Jan 29 '11 at 13:37
add comment

I don't remember the details exactly, but this is the general idea. And I've only done it once, but what I did was separate the re-entrant code from the code performing the task, using an interface to be able to mock the task class.

Then I designed my mock-up to be able to lock on a call so that I know the thread is in the critical section, and then call it again and verify that it is waiting, before releasing the first thread and finish cleanly.

Something like that.

I'm not sure that would work for more complex scenarios, but it helps preserve the behaviour during refactorings.

share|improve this answer
    
I've done this too: separate the part that handles concurrency from the part that does stuff. I ended up with little state-changing objects that plugged into things that handled concurrency. –  Frank Shearar Nov 24 '10 at 13:45
add comment

At JAOO/GOTO this year I saw this presentation:

http://gotocon.com/aarhus-2010/presentation/Testing%20Asynchronous%20Behaviour%20in%20an%20Instant%20Messaging%20Server

The trick is that you model what your hairball application is supposed to DO, in terms of invocation steps as well as the actual operations on your application. John Hughes software then systematically tries many permutations of invocation steps repeatedly in parallel and checks afterwards that the state of the application corresponds with the state of the model. If an error is found, the software knows how to reduce the steps to the minimal case producing the error.

He demonstrated live how to catch several bugs in core Erlang libraries which had been lurking for 15 years and occasionally reported but nobody could figure out where they came from and hence how to fix. With the minimal cases reported by the software, the library maintainer was able to fix each bug within a day.

It was SO impressive.

John Hughes sells this software through his company.

share|improve this answer
    
The basic technology is called QuickCheck - en.wikipedia.org/wiki/QuickCheck –  user1249 Jan 29 '11 at 11:26
add comment
  1. Tests with non-reproducible results are useless. That rules out completely random tests, but leaves in tests generated from pseudo-random sequences.
  2. Every actor in a concurrent environment has algorithmic or otherwise non concurrency components that can be tested by conventional means. Having tested them, any remaining failures must be lie in the concurrency logic.
  3. The events in a concurrent system are always in fact a linear sequence of events. If enough precision is used to measure time, then there are no events happening "at the same time". That means that the actors in a concurrent system can be tested by generating events sequentially. Capturing the sequence of events around the time of failure of a concurrent system provides the required test cases.
  4. The code that provides actors with liveliness (threads) is more-often-than-not provided by the operating system or by system libraries. It is safe to assume that said code needs not be tested. The code in charge of communication and synchronization is normally written by the applications programmer. That code can be tested without invoking the system code, that is, without launching any threads.
  5. Boundary conditions in the algorithmic code (queue empty) often require handling in the synchronization code, and that is a good target for testing.
  6. Defining proxies around system code (t.wait()) allows for the use of stubs/mocks of the functionality during testing.
share|improve this answer
    
random tests can be reproduced, just keep a log of the random values generated –  Steven A. Lowe Nov 24 '10 at 16:14
add comment

You may try my Relacy Race Detector. It's designed to carefully and precisely verify synchronization algorithms like producer-consumer queues and concurrent containers, but not very suitable for verification of whole programs. However, perhaps it's a good idea to spread synchronization and mutexes allover a program anyway, but instead concentrate synchronization in specialized components (that can be verified with Relacy).

share|improve this answer
add comment

It's not easy, but basically the only way is to call the multi-threaded code concurrently from multiple threads and change timing and ordering randomly by playing with random Thread.sleep() and Thread.yield() calls (assuming Java).

There are also ready tools available (such as TestNG) that do something like described above, but they're not very mature yet, as far as I know.

share|improve this answer
1  
As long as you have some way of saying "this combination of timings resulted in an error" because otherwise your tests fail without you knowing why, particularly. –  Frank Shearar Oct 10 '10 at 12:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.