• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Race condition

 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Likes 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This isn't really a question, more of a cautionary tale. Have a look at this code; it's extracted from a class I wrote several years ago named SoftHashMap:



You'll notice that even though it uses a ConcurrentHashMap, it's still necessary to synchronize the code in the get() method, because it needs to be atomic. You don't want two threads working on the same key simultaneously, so that's what the synchronization is for. It's fine to have two threads working on different keys, since the ConcurrentHashMap will deal with simultaneous access.

This worked fine for quite a few years, until just last month I found that my application which used this code occasionally produced two panels for the same checklist. I managed to replicate the problem and through debugging found that there appeared to be two Checklist objects for the same checklist. (The Checklist objects are the "values" in that map.) So after a lot more debugging I was led to this piece of code, which looked perfectly reasonable to me. Until I stared at it for a while and noticed how it was being called:



Finally I had found the problem: two threads had called that method with the same checklist number, but they used different Integer objects as the key. These objects were equal, but not identical. So the idea of synchronizing on the key failed; it requires the objects to be identical, whereas simple equality is fine for the Map, and nasty race conditions could (and did) happen. After I fixed the code (by synchronizing on the map rather than the key) the problem stopped happening.
 
Ranch Hand
Posts: 172
Redhat Ruby C++
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
SO you changed to use the SoftReference instance as the lock object, right? (or the reference from get()?) Nice story =)
 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No, because you can't get the SoftReference instance without performing index.get(key). This should be done inside the synchronized block, otherwise you can get a condition where the same SoftReference is retrieved by two different threads, and then one thread associates a new SoftReference with the given key, which is not reflected in the other thread.
 
Luan Cestari
Ranch Hand
Posts: 172
Redhat Ruby C++
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:No, because you can't get the SoftReference instance without performing index.get(key). This should be done inside the synchronized block, otherwise you can get a condition where the same SoftReference is retrieved by two different threads, and then one thread associates a new SoftReference with the given key, which is not reflected in the other thread.



I think you are right, but I thought slightly different. If both get the SoftReference instance and following one of them call the synchronize using it, (for this point we know it is just a single thread at time) then it would call the index.get(key) again and check if it is null or any other constraint. This way, when the second thread could access the synchronization block (which means the first thread already done his job) it would do the same, which would avoid get any dirt reference from the previous execution.

I think this is a kind of workaround solution to avoid the caller of the API have so much influence in the concurrency state.
 
Paul Clapham
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just to clarify, the first line of the method is now:



Unfortunately that causes more lock-waiting than is necessary, but in practice it doesn't appear to slow things down noticeably.

I'm surprised that among all of the wide variety of classes in java.util.concurrent there isn't something like this; I was hoping for ConcurrentHashMap to have something like putIfAbsent(K key, Callable<V> valueCalculator) which would evaluate the Callable only if the key was absent, but I don't see anything.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Luan Cestari wrote:If both get the SoftReference instance and following one of them call the synchronize using it, (for this point we know it is just a single thread at time) then it would call the index.get(key) again and check if it is null or any other constraint. This way, when the second thread could access the synchronization block (which means the first thread already done his job) it would do the same, which would avoid get any dirt reference from the previous execution.



Then a third thread comes along, locks on the SoftReference updated by the first thread, finds that it's different from the one that the second thread locks on, and goes into race condition.
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I always thought it was a pity that the Map interface doesn't have a Map.Entry<K,V> getEntry(Object key) method. That way you could lock on the entry object, and also update an existing entry in constant time, regardless of the map implementation (provided you already retrieved the entry at some point).
 
Sheriff
Posts: 3837
66
Netbeans IDE Oracle Firefox Browser
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Synchronizing on instances of Value based classes (which Integer quite certainly is) should always sound some alarm bells, I'd say. By definition, you cannot assume anything about the identity of such instances.

There should be a relatively easy fix, though:Another advantage of this approach is that the objects the code synchronizes on are never published to the outside world, so no one else can synchronize on them.

Edit: you might need to implement removing the object also from the locks map when an entry is removed from the index map. But I don't assume this would be too problematic.
reply
    Bookmark Topic Watch Topic
  • New Topic