wood burning stoves 2.0*
The moose likes Threads and Synchronization and the fly likes deadlock Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Threads and Synchronization
Bookmark "deadlock" Watch "deadlock" New topic
Author

deadlock

raghuram bikkani
Greenhorn

Joined: Jan 18, 2006
Posts: 16
how will we prevent deadlock
Edward Harned
Ranch Hand

Joined: Sep 19, 2005
Posts: 291

To avoid deadlocks, don't use locks.

Use atomic primatives.


Ed's latest article: A Java Parallel Calamity http://coopsoft.com/ar/Calamity2Article.html
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
Some (all?) deadlocks occur when two threads try to lock the same resources in different sequence. Thread 1 locks A and tries to acquire B while thread 2 locks B and tries to acquire A. So one solution is to always acquire multiple locks in the same order. That's hard to enforce across a system, though. I remember reading about a utility to lock any number of objects in natural sort order, maybe in Doug Lea's concurrency package.


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18488
    
  40

There are a few patterns that are recommended to avoid deadlocks. You can minimize the number and usage complexity of the locks. You can try to grab the locks in the same order -- requiring certain locks be held for other locks to even be grabbed. You can use timeouts to acquire the locks, and if failed, setup some time of release & retry, or alternate algorithm. etc.

However, there is no magic bullet. After all, if there is one, the JVM would have done it for you.

As for the atomic classes... I do recommend using them. However, they are really complex to use in many cases. The concept of optimistic locking can get really hairy.

Henry


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[Edward]: To avoid deadlocks, don't use locks.

And to avoid creating any bugs we could simply not write any programs, too. But that's somewhat limiting, isn't it?

[Edward]: Use atomic primatives.

Sometimes those are exactly what you want. However I think often you need synchronization at a higher level than that. If you have two or more fields and you need them to have a consistent relationship - e.g. if you're transferring a balance from one account to another - then you probably need to make sure that no other threads modify those values in the middle of the transfer. I don't see how you can do that with atomic primitives. Am I missing something?


"I'm not back." - Bill Harding, Twister
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18488
    
  40

Originally posted by Jim Yingst:
Sometimes those are exactly what you want. However I think often you need synchronization at a higher level than that. If you have two or more fields and you need them to have a consistent relationship - e.g. if you're transferring a balance from one account to another - then you probably need to make sure that no other threads modify those values in the middle of the transfer. I don't see how you can do that with atomic primitives. Am I missing something?


Well, it depends... The Java 5.0 atomic classes adds a new functionality that could not be achieved with just volatile variables -- basically, the ability to do a conditional set in a atomic fashion.

This may sound like nothing, but consider this... Imagine doing a really long and complex operation with temporary varibles. And then do a condition set operation to commit those variables, basically commit the object that contains all the variables on the condition that the current object is the previous object that was read before the operation took place. (meaning change the reference to the point to your new object if and only if the reference still points to the old object that you started your calculations with)

If the operation fails, throw away the results, roll back the database, and then try again. If it succeeds, commit the database. And you are done. If this sound complex, it is.

And it can get really complex. In fact, the lock and condition classes, added in Java 5.0, mainly use the atomic classes. There may not be any synchronization primatives under the covers -- I am not sure.

Henry
[ January 23, 2006: Message edited by: Henry Wong ]
Edward Harned
Ranch Hand

Joined: Sep 19, 2005
Posts: 291

Perhaps I should qualify my last statement a bit.

Using a single lock will never result in a deadlock. But complex programs very often incur multiple locks even when the programmer only writes a single lock. Take for example the synchronized methods in Vector. The programmer may use a lock on an object and subsequent code invokes a Vector method, oops, we have multiple locks.

Every program ever written will be debugged, enhanced and tweaked and usually by someone other than the original programmer. Even when care is taken to only lock in the same order (lock A, then lock B) someone will end up locking in the reverse order and a dead lock occurs.

The atomic instruction Compare and Swap has been around since the 1970's. Yes it is a bit difficult, but any locking algorithm can be replaced by atomic instructions. Every modern operating system uses atomic instructions in place of locking. Can you imagine coordinating 32 CPU's using locking? No Way.

Is that a little clearer?
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
OK, thanks for the clarifications. Yes, there are many ways things can go awry when using synchronization. I think it's possible to use it safely, but I agree there are many possibilities for subtle bugs. And yes, you're right that it is possible to protect multiple fields a class using atomic primitives. But - dropping about my previous defense of synchonization - that seems to ignore the java.util.concurrent.locks package. Lock and its implementations seem to offer a higher level abstraction which is (in my opinion) more convenient if the data to be protected is more than just a single primitive value. The key with Locks is that they offer the ability to tryLock() and release() - so it's possible to attempt to acquire multiple locks, and back out of the attempt completely if some locks are currently held elsewhere:

Obviously more complex strategies are possible with timeouts, retries, etc.

[Henry]: In fact, the lock and condition classes, added in Java 5.0, mainly use the atomic classes. There may not be any synchronization primatives under the covers -- I am not sure.

Looks like the classes in java.util.concurrent.locks rely mostly on AbstractQueuedSynchronizer which in turn relies on sun.misc.Unsafe for methods like compareAndSwapInt() and comparAndSwapObject(), which are implemented in native code. This (Unsafe) is the same class that most of the java.util.concurrent.atomic classes rely on to do most of their work. It appears that synchronization is not used anywhere within java.util.concurrent and its subpackages. (Though it's possible there's some sync being used indirectly, somewhere - it's hard to rule it out completely.)

So, java.util.concurrent.locks does use atomic methods, but not "the atomic classes". Implementation aside, I think it's a mistake to say "don't use locks, use atomic primitives" because that seems to rule out the very useful Lock classes. However I think we might all agree on something like "avoid synchronization, prefer java.util.concurrent locks or atomic primitives instead". Sound good?
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18488
    
  40

Originally posted by Jim Yingst:
So, java.util.concurrent.locks does use atomic methods, but not "the atomic classes". Implementation aside, I think it's a mistake to say "don't use locks, use atomic primitives" because that seems to rule out the very useful Lock classes. However I think we might all agree on something like "avoid synchronization, prefer java.util.concurrent locks or atomic primitives instead". Sound good?


Jim, I am actually on your side... well... until you were convinced to prefer atomic primatives...

Seriously, there are many issues with synchronization, deadlocks being one of them -- but that just mean that developers should understand the issues, instead of just avoiding them.

The concurrent locks may not use synchronization, but that does not mean that you can't cause deadlock. Two concurrent locks can deadlock just like regular locks. And while it is true that optimistic locking techniques can't deadlock, it is also a large learning curve, in order to get working correctly.

Synchronization has issues... but let's not "throw the baby out with the bath water" please...

Henry
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
I agree, my last post went to far the other way. How about "be very careful when using synchronization, and consider using concurrent locks or atomic primitives instead". Well, that may be less agreeable to Edward, but it's a truer reflection of my own position.

[Henry]: The concurrent locks may not use synchronization, but that does not mean that you can't cause deadlock. Two concurrent locks can deadlock just like regular locks.

Oh, absolutely. I didn't mean to imply otherwise - I just meant that tryLock() and unlock() give you more options for avoiding deadlock.
Edward Harned
Ranch Hand

Joined: Sep 19, 2005
Posts: 291

The discussion is about deadlocks but there are four problems with using locks in any form:

1. Deadlock,
2. Starvation,
3. Priority Inversion,
4. Excessive Overhead.

Starvation happens when the thread holding the lock refuses to give it up (knowingly or otherwise), the waiting threads starve.

Priority Inversion occurs when a lower priority thread is ahead of a higher priority thread in the queue of waiting threads. Since the lower priority thread gets the lock before the higher priority thread, it�s an inversion.

Now using Lock() instead of synchronize helps with the above problems, but nothing helps with the overhead problem.

The longer the queue of waiting threads the more overhead. Until you watch this in action you�ll have a hard time believing it is really a problem. Sure, the dispatcher has to check the waiting threads to see if any thread is ready to run, so what? It�s what has to be checked and how long it takes that makes long queues a real problem.

If you work with multi-threading in a large SMP server environment, atomic is the way to go. It does take a different mind set but it�s only a learning curve.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18488
    
  40

Edward,

I am not saying that synchronization doesn't have problems. I am just saying that optimistic locking techniques is not the magic bullet, as it too has problems.

The biggest being its complexity. I have been on many projects that used optimistic locking, and frankly, we really have to justify it, as most of the time, it is not worth the complexity. Not only does it take longer to design, and code, but most of the time, I couldn't hand off the project, as it takes dedication to transition the code too.

I actually like optimistic locking techniques, but I guess you can say I am too pragmatic to say that it should be preferred.

Henry

PS... you also raised some good points, which I will address later.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18488
    
  40

Originally posted by Edward Harned:
The discussion is about deadlocks but there are four problems with using locks in any form:

1. Deadlock,
2. Starvation,
3. Priority Inversion,
4. Excessive Overhead.

Starvation happens when the thread holding the lock refuses to give it up (knowingly or otherwise), the waiting threads starve.

Priority Inversion occurs when a lower priority thread is ahead of a higher priority thread in the queue of waiting threads. Since the lower priority thread gets the lock before the higher priority thread, it�s an inversion.

Now using Lock() instead of synchronize helps with the above problems, but nothing helps with the overhead problem.

The longer the queue of waiting threads the more overhead. Until you watch this in action you�ll have a hard time believing it is really a problem. Sure, the dispatcher has to check the waiting threads to see if any thread is ready to run, so what? It�s what has to be checked and how long it takes that makes long queues a real problem.

If you work with multi-threading in a large SMP server environment, atomic is the way to go. It does take a different mind set but it�s only a learning curve.


1. Deadlock -- Optimistic Locking techniques win. As it is not possible to deadlock with optimistic locking.

2. Starvation -- lets come back to this.

3. Priority Inversion -- is not much of a problem with most modern JVMs. Most JVMs, including Windows, Solaris, and Linux (not sure of all flavors) support Priority Inheritance. Yes, it is possible to have a high priority thread block on a low priority thread -- but the high priority thread does not have an effective low priority as the low priority thread is temporary bumped up to the high priority until it releases the lock.

4. Overhead -- this one is a hard call. It really depends on what you plan to do if your optimistic operation fails.

If you just plan to report the failure, then yes, optimistic locking has less overhead, but it is not actually doing what it supposed to. Most people don't like the APIs that may not work sometimes ...

If you just plan to try again, then it depends. Is doing the operation over again more efficient than the synchronization overhead. I guess it would depend on the operation, how many times on average you have to repeat it, and the synchonization overhead that it is being compared to. With Java 5, the synchronization overhead had been significantly improved -- making this a really tough call.

If you just plan to use an alternate technique that will definitely work, then it depends. Why isn't this used in the first place? Because it is slower? In most cases, you are probably back to synchronization in the alternate technique. At minimum, it will be a pain to maintain two tracks in the operation.

2. Starvation -- okay, back to starvation. This occurs when locks are held for a long period of time. Why would you want to do this? Quite simply if the operations take a long time. Unfortunately, with Optimistic Locking, if operations take a long time, it stand a greater chance of failing as the data could have changed by the time the results are posted.

So yes, optimistic techniques can't starve, but if the conditions are ripe for synchronization to starve, it is ripe for optimistic operations to fail -- which if you do an retry operation, will really kick up your overhead.

Henry
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: deadlock
 
Similar Threads
urlyBird 1.2.3
How To Avoid Deadlock?
is this call synchronized ?
Doubt on Thread - Is the code went in to DeadLock state ?