aspose file tools*
The moose likes Threads and Synchronization and the fly likes Threads: deadlock or not? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Threads and Synchronization
Bookmark "Threads: deadlock or not?" Watch "Threads: deadlock or not?" New topic
Author

Threads: deadlock or not?

Alexandr Shvedov
Greenhorn

Joined: Jul 12, 2006
Posts: 23
Hello everybody?
I wrote a test program for my employer. But developers there said that it is wrong and cause a deadlock. Please, comment if it is so or not?
The task is that there is N producers and M consumers. One generates integers and another print it to console. My code is below:

==Producer.java==

==Consumer.java==

==Storeable.java==


==Main.java==
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18845
    
  40

But developers there said that it is wrong and cause a deadlock. Please, comment if it is so or not?


With a very quick glance, it looks fine. Did these "developers" give you any context as to what is wrong and what can cause deadlock?

[UPDATE]
With a longer glance, your problem is the notify(). There are two possible wait conditions, sharing the same notify object. If it wakes up the wrong thread, this wrong thread just goes back to wait(), and the notification is lost.

BTW, it is very unlikely you can get two threads waiting for different conditions. You will *need* a lot of threads, that flood the system, and in that case, I am not sure if it will be even noticeable.
[/UPDATE]

Henry
[ February 05, 2007: Message edited by: Henry Wong ]

Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24184
    
  34

Please continue this in our Threads and Synchronization forum.


[Jess in Action][AskingGoodQuestions]
Alexandr Shvedov
Greenhorn

Joined: Jul 12, 2006
Posts: 23
Hello! Well, the developer in company I have been tested in said that it must be deadlock. When I asked he tried to produce deadlock scenario, but he failed. Then he tried to tell me that notify() must be called out of syncronized code, but I said that he is wrong and show him javadoc. Then he just 'found' the deadlock scenario and said that it is certanly deadlock, then he told me bye

If you think that it is deadlock can you produce reasonable deadlock scenario? (please)
Alexandr Shvedov
Greenhorn

Joined: Jul 12, 2006
Posts: 23
You also think that notify() can just send notification to 'wrong' thread. We have two kind of threads here: producers && consumers. If object can notify 'wrong' thread it means that there must be at least 2 different kind of threads in waiting pool, but it seems to me that it is impossible, because the thread here can go in waiting pool only if object is locked be the thread and while() condition matches. We have 2 opposite while() conditions here, when one true and thread going to waiting pool it means another condition is false and thread should be noticeable. Am I right?
[ February 05, 2007: Message edited by: Dmitry Popov ]
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18845
    
  40

If you think that it is deadlock can you produce reasonable deadlock scenario? (please)


Like I said, I don't see a deadlock anywhere. It looks fine to me.

You also think that notify() can just send notification to 'wrong' thread. We have two kind of threads here: producers && consumers. If object can notify 'wrong' thread it means that there must be at least 2 different kind of threads in waiting pool, but it seems to me that it is impossible, because the thread here can go in waiting pool only if object is locked be the thread and while() condition matches. We have 2 opposite while() conditions here, when one true and thread going to waiting pool it means another condition is false and thread should be noticeable. Am I right?


Well, just because it looks like it is impossible -- and in this case, it probably is impossible for many JVMs -- doesn't mean that there isn't someone who going to configure your class in an unexpected way, for some JVM that you never heard of, for some usage that you didn't expect, that will break your code.

Let's say that someone configures a ridiculous number of producers and consumers... say the 20000 producers and 20000 consumers.

1. Let's say the JVM runs all the consumers first. So now you have 20000 consumers waiting.

2. Let's say the JVM runs all the producers next. The first 10000 will add to the vector, and send notifications. And the next 10000 will have to wait as the vector is full. There are now 20000 consumers waiting, and 10000 producers waiting.

3. As for the 10000 notification (from the producers), let's give them all to consumers. They all wake up, take a value from the vector, and send another notification. You now have 10000 consumers and 10000 producers waiting, and an empty vector.

4. As for the 10000 notifications (from the consumers), let's give them to the other 10000 consumers. They wake up, see the vector is still empty, and go back to the wait state. You now have 10000 consumers and 10000 producers waiting.

Henry
[ February 05, 2007: Message edited by: Henry Wong ]
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18845
    
  40

So how do we fix this?

Well, if you are using Java 5, you can use the ReentrantLock class, along with the Condition interface. First, instantiate a ReentrantLock object, then call the newCondition() method twice to get two Condition Objects.

Instead of using Java synchronization, you will now use this Lock object to lock and unlock the code. And instead of calling wait() and notify(), you will now use the await() and signal() method of the condition object. And now, you have two different condition objects bounded to the same lock -- one will be used for empty vector and the other for full vector.

Henry
Alexandr Shvedov
Greenhorn

Joined: Jul 12, 2006
Posts: 23
Hello, Henry!
It seems to me, that deadlock is possible in my program and thank you for your sample. Couldn't we just use notifyAll() to solve the problem?
The deadlock happens when notification is send to 'wrong' thread. If we can move all kind of threads (i.e. notifyAll()) to 'ready-to-run' state then even if some of thema go to 'wait' then the others can solve the 'deadlock'.
Henry Wong
author
Sheriff

Joined: Sep 28, 2004
Posts: 18845
    
  40

Originally posted by Dmitry Popov:
Hello, Henry!
It seems to me, that deadlock is possible in my program and thank you for your sample. Couldn't we just use notifyAll() to solve the problem?
The deadlock happens when notification is send to 'wrong' thread. If we can move all kind of threads (i.e. notifyAll()) to 'ready-to-run' state then even if some of thema go to 'wait' then the others can solve the 'deadlock'.


Prior to Java 5, notifyAll() is the only solution that didn't require external (non core java) support. Calling notify() from the wrong waking thread didn't work, because the thread that got woken was not specified, so in theory, it was possible for the JVM to always be wrong (however unlikely). For me, prior to Java 5, I used my own lock and condition classes.

If you are using Java 5 or above, I would really recommend using the ReentrantLock and Condition classes, as waking up 20000 threads so that you can make sure you wake up the right one, is a bit inefficient.


[EDIT: With all my rambling, not sure if I was clear.... Yes, using notifyAll() instead of notify(), will work.]

Henry
[ February 06, 2007: Message edited by: Henry Wong ]
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
The Java 5 BlockingQueue may do the whole job for you. You can set a fixed capacity so producers block on trying to add beyond capacity and consumers block until there is something in there. The Apache Commons Thread Pool has a beautifully simple BlockingQueue implementation for older JVMs but I'm not sure without looking that it has the "block on full" feature.


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
 
Consider Paul's rocket mass heater.
 
subject: Threads: deadlock or not?