Re: TDD for multi-threaded programs

I must add that, surprisingly enough, this technique is not new. It
is ca. 3 decades old, see: P. Brinch Hansen, Reproducible testing of
monitors, Software---Practice and Experience 8, 6 (November--
December), 721-729, 1978, John Wiley & Sons, Ltd.
http://brinch-hansen.net/papers/1978b.pdf

Brinch Hansen, who is a pioneer in concurrent programming, used these
techniques already in the mid 70's. The key idea is this:

  If we cannot test multiple processes because their interaction is
  non-deterministic, make it deterministic for the test. Hence, tests
  will be reproducible.

His idea was to allow enough time for the processes to stabilise by
using a virtual clock on which the test processes could synchronise.
So we know that at each tick of the virtual clock which state we are
at. I used explicit delays for simplicity. He did not have the xUnit
framework at that time, so he constructed a separate test program out
of processes that made the shared data structure traverse through the
meaningful states one at a time. With help of the nowadays xUnit
frameworks, however, we can focus on one meaningful state at a time.

Race conditions are not tested in this way, of course. Neither can
this be used for performance test.

However, we can use this technique for Test Driven Development, as I
tried to demonstrate on an example. Since we are working with a
deterministic system, it is similar to the traditional TDD
techniques. We are back home.

The good news is that the technique is language independent.

On the other hand, it only works for processes that synchronise with
the help of monitors because the monitor serialises the control flow.
Fortunately, monitors can be constructed from semaphores too.

Best Regards,
Szabolcs