Testing concurrent data structures

[maneesh t s v]

How do you test concurrent data structures for correctness? 

I mean how to generate test cases for concurrent data structures to show that they are correct without actually giving proofs?

Appreciate any effort to answer.

Thanks, everyone

[kedar mhaswade]

If you are looking to do it in Java, one way is to look at how the JDK's java.util.concurrent constructs are tested using the TCK developed by Doug Lea et. al.

http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/tck/

Hope that helps.

Regards,

Kedar

[Gavin Lowe]

If by "correctness" you mean linearizability, you might want to look at http://www.cs.ox.ac.uk/people/gavin.lowe/LinearizabiltyTesting/.  There I present a testing framework that allows you to perform random operations on a concurrent datatype, record the history, and then check that the history is linearizable.  My experience is that it's pretty good for finding bugs, an it's easy to use.  My framework uses Scala; you should also be able to use it for testing Java.

Hope that helps.

Gavin