CODEWITHSUNDEEP
c++testingconcurrency
kefeizhou
kefeizhou

Reputation: 6552

Testing concurrent data structure

What are some methods for testing concurrent data structures to make sure the data structs behave correctly when accessed from multiple threads ?

Upvotes: 4

Views: 1474

Answers (6)

Evan Teran
Evan Teran

Reputation: 90462

All of the other answers have focused on actually testing the code by putting it through its paces and actually running it in one form or another or politely saying "don't do it yourself, use an existing library".

This is great and all, but IMO, the most important (practical tests are important too) test is to look at the code line by line and for every line of code ask "what happens if I get interrupted by another thread here?" Imagine another thread, running just about any of the other lines/functions during this interruption. Do things still stay consistent? When competing for resources, does the other thread[s] block or spin?

This is what we did in school when learning about concurrency and it is a surprisingly effective approach. Bottom line, I feel that taking the time to prove to yourself that things are consistent and work as expected in all states is the first technique you should use when dealing with this stuff.

Upvotes: 1

Fragsworth
Fragsworth

Reputation: 35497

I normally test these kinds of things by interjecting sleep() calls at appropriate places in the distributed threads/processes.

For instance, to test a lock, put sleep(2) in all your threads at the point of contention, and spawn two threads roughly 1 second apart. The first one should obtain the lock, and the second should have to wait for it.

Most race conditions can be tested by extending this method, but if your system has too many components it may be difficult or impossible to know every possible condition that needs to be tested.

Upvotes: 1

BMitch
BMitch

Reputation: 263956

Start with the assumption that your calls to access/modify data are not thread safe and use locks to ensure only a single thread can access/modify any part of the data at a time. Only after you can prove to yourself that a specific type of access is safe outside of the lock by multiple threads at once should you move that code outside of the lock.

Assume worst case scenarios, e.g. that your code will stop right in the middle of some pointer manipulation or another critical point, and that another thread will encounter that data in mid-transition. If that would have a bad result, leave it within the lock.

Upvotes: 1

Mark B
Mark B

Reputation: 96261

Use a pre-existing, pre-tested library that meets your needs if possible.

Make sure that the code has appropriate self-consistency checks (preferably fast sanity checks), and run your code on as many different types of hardware as possible to help narrow down interesting timing problems.

Have multiple people peer review the code, preferably without a pre-explanation of how it's supposed to work. That way they have to grok the code which should help catch more bugs.

Set up a bunch of threads that do nothing but random operations on the data structures and check for consistency at some rate.

Upvotes: 1

Girish Rao
Girish Rao

Reputation: 2669

Concurrent systems are probabilistic and errors are often difficult to replicate. Therefore you need to run various input/output cases, each tested over time (hours, days, etc) in order to detect possible errors.

Tests for concurrent data structure involves examining the container's state before and after expected events such as insert and delete.

Upvotes: 1

kohlehydrat
kohlehydrat

Reputation: 505

Run your concurrent threads for one or a few days and look what happens. (Sounds strange, but finding out race conditions is such a complex topic that simply trying it is the best approach).

Upvotes: 0

Related Questions