• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Threads: deadlock or not?

 
Alexandr Shvedov
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 21016
78
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please continue this in our Threads and Synchronization forum.
 
Alexandr Shvedov
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 21016
78
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 21016
78
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Pie
Posts: 21016
78
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic