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.

As the jdk doc said, ConcurrentHashMap is thread safe and it doesn't block multiple thread read. It is not necessary to doubt that since it was under many and restricted test. But I just curious how to tell and write code to verify that.

Edited: to be more precisely

  1. how to keep read consitent without read block
  2. does it return the latest view of data
share|improve this question
1  
recommended reading: Testing Concurrent Software, a lecture by Bill Pugh and Brian Goetz at Java One '2007. "By a combination of multiple techniques (careful design, static analysis, code review, extensive testing), you can get the upper hand on concurrency bugs...". Pugh and Goetz are among major contributors to API you ask about, members of expert groups for JSR 133 Memory Model and JSR 166 Concurrent Utilities –  gnat Nov 19 '12 at 10:03

3 Answers 3

To all practical purposes, you can't. You can run a number of successful tests numerous times, then without making a change, a test will fail. This is what makes testing multi-threading hard - it is not deterministic.

You may be able to test to an acceptable degree of certainty using statistical methods i.e. we ran 10^y randomized tests with no faults found- it is statistically probable that there are no defects.

You cannot run a test that guarantees thread safety, it has to be done by design and white box testing that the design has been implemented correctly.

As far as ConcurrentHashMap - if your vendor says something is thread safe, you can only decide, do I trust my vendor - or perhaps paraphrasing a great movie line "You've got to ask yourself one question: Do I feel lucky? Well, do ya, punk?" - and if you don't trust your vendor, I think maybe you have bigger problems.

EDIT: My background involves Life critical and Hard Real time (sub nanosecond) embedded systems. My questions is answered in the context of "Whats the worst that happens" being somewhat more important than "an unexplained software crash"......

share|improve this answer
    
I would disagree, I've ensured locking was occurring before by having a sleep in a mock object called inside that lock, the sleep was for 3 seconds and I verified by a mock object that stopped a stopwatch given to the other thread that it was waiting at the lock for 3 seconds, and with timestamps before exiting the lock for thread one I showed thread 2 only entered the lock afterwards. Furthermore you can do tricks by having your tests access the lock object which can give you proofs of behaviors in regards to it. Locking it and executing operations can ensure they aren't blocking operations. –  Jimmy Hoffa Nov 18 '12 at 5:28
    
Granted these techniques I mention aren't faultless 100% deterministic proof guarantees, but they are pretty solid and definitely worth encouraging. –  Jimmy Hoffa Nov 18 '12 at 5:39
    
@Jimmy : All you did was ensure that once successfully locked no other object was able to access the locked object. You do not appear to test obtaining a lock was atomic, and guaranteed to fail if another object simultaneously obtained a lock. I pity your customers if you think your testing is proof that your locking is working..... –  mattnz Nov 18 '12 at 5:44
    
No, I would be ensuring that once locked no other object was able to execute the operation by attempting to execute it. Mock objects are the key to knowing where threads are at any given point in the execution to ensure they are waiting on a lock or inside of a lock at various points in time. And I just said it's not proof but it is solid evidence done correctly. If I lock a lock object and execute an operation I want to be blocking and can show with a mock object inside the lock that thread does not hit until I release my lock, that's solid evidence the operation was blocking as I wanted. –  Jimmy Hoffa Nov 18 '12 at 5:51
    
Do you think I refer to locking the whole object? I'm not brain dead, I'm referring to the lock object the blocking operations use being exposed and accessible so my tests can lock that, not the entire object the operation exists in, just the object I expect them to use for locking. –  Jimmy Hoffa Nov 18 '12 at 5:56

First off, you really never need to go around unit testing frameworks, especially not the main framework of a language.

Unit testing verification's for thread safety can be a little tricky, especially if you aren't super clear on handling threading/concurrency. Also you generally don't get 100% faultless guarantees (though for some scenarios you can), but you can get damn-good using appropriate techniques.

That said, it's a matter of defining the behaviors you don't want and attempting to cause them, then having tests that ensure the desired behavior was at play instead.

For this particular scenario with the steps I laid out you need to:

  • Define the beheaviors you don't want: You don't want reads to be blocked.
  • Attempt to cause them: Create two threads that try to read from the dictionary at the exact same time (use a signal or timestamp based event for both of them).
  • Test the desired behaviour is in play instead: timestamp before and after the read operation, ensure the timestamps started and ended with overlaps between the two threads.

This is a subpar approach though because you're testing for thread safety something where you don't have access to the guts of the system, when you write your own threading systems the trick is to force operations to take longer in the test cases. Normally I put mock objects in the middle of the lock or non-locking operations and force sleeps then ensure the timestamps do or don't overlap as expected depending on if I do want to see locking or don't want to see locking.

share|improve this answer
    
I just wonder why it can keep consistent without read lock –  pythonee Nov 18 '12 at 7:16

But I just curious how to tell and write code to verify that.

It depends what you mean by "verify". The normal Computer Science meaning of "verify" is to show that something is true / correct ... all of the time, not just some or most of the time.

In some cases, it is possible to show thing is true (e.g. certain invariants are always satisfied) purely by testing. But the only way to do that by testing is to test for all possible inputs / starting conditions; i.e. by exhaustive testing In cases which involve multi-threaded behaviour, it is usually not possible to do this.

This is not to say that testing is useless for multi-threaded applications. But as someone said (Tony Hoare?) testing can prove the presence of bugs, but not the absence of bugs. Testing alone is simply NOT SUFFICIENT to verify correctness of multi-threaded code.


The only way to verify (in the accepted sense) that ConcurrentHashMap is thread-safe is to analyse the source code, and construct a formal or informal proof of correctness for the thread-safety criteria. That is hard work. And on top of that "thread-safety" is actually a rather difficult concept to tie down in a formal sense. (Basically, it means "works correctly when there are multiple threads" ... which begs the question - what does "works correctly" mean?

share|improve this answer
    
If I lock an object then execute an operation and the operation completes I have just verified completely that operation doesn't block on that lock object. Proofs are possible with multithreading, you just have to recognize what you're proving and the limits of that proof; in this test it doesn't prove it's not a blocking operation, just that it doesn't block on that object, which may be a proof we want. For instance if locking that object could cause a dead lock due to another operation we know blocks on it, that test proves the operation won't enter that specific deadlock scenario. –  Jimmy Hoffa Nov 18 '12 at 15:49
    
"If I lock an object then execute an operation and the operation completes I have just verified completely that operation doesn't block on that lock object." - Maybe ... but you have NOT verified that the object is thread-safe. The operation that does no locking or synchronization whatsoever would also "pass" your test. –  Stephen C Nov 18 '12 at 22:38
1  
Oh I get it. You are nit-picking that there are some things that you can adequately test in a multi-threaded program. But this only with white-box testing; i.e. testing combined with reasoning to show that what you are testing is equivalent to verification. And it only applies to certain things. And it is only as good as the programmer's (informal) reasoning ... and that can be just as buggy as his / her code. –  Stephen C Nov 19 '12 at 10:30
1  
@JimmyHoffa - what I'm trying to get across is the simple fact that testing is NOT verification. I have not stated or implied that you shouldn't write any tests. What I have stated is that testing alone is NOT SUFFICIENT for verifying thread-safety, particularly for complicated classes like ConcurrentHashMap. –  Stephen C Nov 20 '12 at 15:16
1  
@JimmyHoffa - returning to something you said earlier. "If I lock an object then execute an operation and the operation completes I have just verified completely that operation doesn't block on that lock object.". Actually you haven't. All you have "verified" is that that operation made with all of the overt and hidden variables in the state that they are in that the operation does not block on the lock. –  Stephen C Nov 20 '12 at 16:18

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.