• 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

Deadlock scenario

 
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Following is a dead lock scenario



if the methods are called in the following way then it may result in deadlock situation.

Thread 1: parent.addChild(child); //locks parent
--> child.setParentOnly(parent);

Thread 2: child.setParent(parent); //locks child
--> parent.addChildOnly()

Now my question is what changes can be made in the code so that we can perform the above two operations without causing deadlock.
 
Sheriff
Posts: 22783
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Don't make the methods synchronized but use synchronized blocks inside the method. This gives you a finer grained control over when locks are acquired. In this case you have two options:
- always get the parent lock first, then the child lock
- always get the child lock first, then the parent lock

It doesn't really matter which one you choose. The import thing is that the order is always the same, no matter which two objects are called.
In the following code I chose the second option:
Note that two methods are still fully synchronized. That's because there is only one lock acquired when those methods are called, so they introduce no extra risk of deadlock.

There is still a potential for deadlock, if you are treating two TreeNodes as both parent and child, e.g. by adding them to each other.
 
Master Rancher
Posts: 4806
72
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Before considering how to also handle the last case Rob mentioned (if you choose to do so), I think it may be helpful to simplify the code a bit. Consider:

Should setChildOnly() and setParentOnly() be public at all? It seems to me that the public API should only be methods which will leave the two objects in a consistent state, ensuring bidirectional links. What reason does anyone outside this class have for calling setChildOnly() or setParentOnly()? For that matter, I'm not sure if anyone inside this class really needs both of these methods. That can be decided later.

Do we need complex synchronization code inside both setChild() and setParent()? Or can we just call one method from the other?

In fact I'm not sure both these methods need to be part of the public API, as it's easy for someone to mistakenly think they need to call both of them - they don't. And anyone who wants to call a.setParent(b) can easily call b.addChild(a) instead, and be done.

Now, "complex stuff" could be exactly what Rob wrote for addChild() - it works well for everything except the case he noted, two nodes (accidentally?) made children of each other. If you want to also handle that case, I think it's probably easiest to avoid using synchronization entirely, and instead use either (a) methods from java.util.locks.Lock, or (b) optimistic locking techniques using AtomicInteger or AtomicLong. I recommend Java Concurrency in Practice if you want to learn about these techniques in detail.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic