notify vs notifyall

[Pallav Shyam]



Queue.java

 

Attached is a file containing a simple producer consumer scenario that I wrote.

Changing queue.notifyAll() to queue.notify() in the push method creates a deadlock.

Not sure why? Is there any significant difference between notify and notifyAll which I am missing?

 

 

Thanks,

Pallav

[Neil Coffey]

I couldn't see the attached file -- perhaps you can just paste the code in?

[Pallav Shyam]

The attached file is named Queue.java.

Posting the code below

 

import java.util.ArrayList;
import java.util.List;

public class Queue {
private List<String> queue = new ArrayList<String>();
private final int MAX_SIZE = 1;

public void push(String s){
synchronized(queue){
while(queue.size() >= MAX_SIZE){
try{
System.out.println("[" + Thread.currentThread().getName() + "] entering push waitset");
queue.wait();
System.out.println("[" + Thread.currentThread().getName() + "] exiting push waitset");
}catch(InterruptedException ie){
ie.printStackTrace();
Thread.currentThread().interrupt();
}
}
queue.add(s);
queue.notifyAll(); // changing this to notify creates a deadlock.
}
}


public String pop(){
synchronized(queue){
while(queue.isEmpty()){
try{
System.out.println("[" + Thread.currentThread().getName() + "] entering pop waitset");
queue.wait();
System.out.println("[" + Thread.currentThread().getName() + "] exiting pop waitset");
}catch(InterruptedException ie){
ie.printStackTrace();
Thread.currentThread().interrupt();
}
}

String popedValued = queue.remove(0);
queue.notify();

return popedValued;
}
}

public static void main(String args[]){
final Queue queue = new Queue();

Runnable producer = new Runnable(){
public void run() {
for(int i=0; i<10; i++){
String s = String.valueOf(i);
System.out.println("[" + Thread.currentThread().getName() + "] Pushing : " + s);
queue.push(s);
}
}
};

Runnable consumer = new Runnable(){
public void run() {
for(int i=0; i<2; i++){
System.out.println("[" + Thread.currentThread().getName() + "] Poping : " + queue.pop());
}
}
};

// start 1 producer
new Thread(producer).start();


// start 5 consumers
new Thread(consumer).start();
new Thread(consumer).start();
new Thread(consumer).start();
new Thread(consumer).start();
new Thread(consumer).start();

}

}
 



[happy goofy]

I replaced reply for replyAll as indicated in the source. I kept runnning it for some times. Yes, I saw the deadlock. Anyone got an insight?

[happy goofy]

This program creates 1 producer thread and 5 consumer threads, all synchronized on an Object of type ArrayList. With notify (not notifyAll) executed by each thread , there will be,of course, at most one thread running (RUNNABLE), at most one awaken but blocking(BLOCK) to acquire the lock, the rest are in the waiting state(WAITING). There is a possible moment when the producer is in WAITING state, one cosumer is running, the rest are in WAITING state. Just before the running consumer returns (the last return statement), it wakes one and just one another consumer by execute notify (the JVM did not wake the producer). The consumer which finished running releases the lock. Now there are two consumers competing for the lock, the other three consumers and the single producer are in WAITING state. The two competing consumers will go into WAIT soon before there is nothing to consume. All threads are in WAITING state.

So there is not the kind of deak lock situation we normally talk about. The running threads hold a lock the other is waiting to acquire. Both threads are in BLOCK state.

Here all threads are in WAITING state. No thread come to wake them up. And they are no in TIMED_WAIT state.

In this 1 p 5 c example, the 1 p is guaranteed to wake at least 1 c. At least 1 c is competing the lock. But 1 c is not guaranteed to wake up 1 p, resulting no p is competing the lock.

"Thread-5" prio=10 tid=0x081aaea0 nid=0x12 in Object.wait() [0xb393b000..0xb393bab8]
        at java.lang.Object.wait(Native Method)
        - waiting on <0xf0e24650> (a java.util.ArrayList)
        at java.lang.Object.wait(Object.java:474)
        at Queue.pop(Queue.java:31)
        - locked <0xf0e24650> (a java.util.ArrayList)
        at Queue$2.run(Queue.java:63)
        at java.lang.Thread.run(Thread.java:595)

"Thread-4" prio=10 tid=0x081aa2c8 nid=0x11 in Object.wait() [0xb397c000..0xb397cd38]
        at java.lang.Object.wait(Native Method)
        - waiting on <0xf0e24650> (a java.util.ArrayList)
        at java.lang.Object.wait(Object.java:474)
        at Queue.pop(Queue.java:31)
        - locked <0xf0e24650> (a java.util.ArrayList)
        at Queue$2.run(Queue.java:63)
        at java.lang.Thread.run(Thread.java:595)

"Thread-3" prio=10 tid=0x081a95b0 nid=0x10 in Object.wait() [0xb39bd000..0xb39bddb8]
        at java.lang.Object.wait(Native Method)
        - waiting on <0xf0e24650> (a java.util.ArrayList)
        at java.lang.Object.wait(Object.java:474)
        at Queue.pop(Queue.java:31)
        - locked <0xf0e24650> (a java.util.ArrayList)
        at Queue$2.run(Queue.java:63)
        at java.lang.Thread.run(Thread.java:595)

"Thread-2" prio=10 tid=0x081a8938 nid=0xf in Object.wait() [0xb39fe000..0xb39fec38]
        at java.lang.Object.wait(Native Method)
        - waiting on <0xf0e24650> (a java.util.ArrayList)
        at java.lang.Object.wait(Object.java:474)
        at Queue.pop(Queue.java:31)
        - locked <0xf0e24650> (a java.util.ArrayList)
        at Queue$2.run(Queue.java:63)
        at java.lang.Thread.run(Thread.java:595)

"Thread-1" prio=10 tid=0x081a7808 nid=0xe in Object.wait() [0xb3c75000..0xb3c75cb8]
        at java.lang.Object.wait(Native Method)
        - waiting on <0xf0e24650> (a java.util.ArrayList)
        at java.lang.Object.wait(Object.java:474)
        at Queue.pop(Queue.java:31)
        - locked <0xf0e24650> (a java.util.ArrayList)
        at Queue$2.run(Queue.java:63)
        at java.lang.Thread.run(Thread.java:595)

"Thread-0" prio=10 tid=0x081a6c30 nid=0xd in Object.wait() [0xb3cb6000..0xb3cb6b38]
        at java.lang.Object.wait(Native Method)
        - waiting on <0xf0e24650> (a java.util.ArrayList)
        at java.lang.Object.wait(Object.java:474)
        at Queue.push(Queue.java:13)
        - locked <0xf0e24650> (a java.util.ArrayList)
        at Queue$1.run(Queue.java:54)
        at java.lang.Thread.run(Thread.java:595)

 

 

 

If any of the thread executes notifyALL, then all WAITING threads get a chance to be awaken.

 

 

 

 

[Pallav Shyam]

Hi Goofy,

Good explaination. This is certainly not the deadlock scenario we generally talk about. 

By the way, how did you produce the thread trace which shows very clearly the state of each thread.

Thanks,

Pallav

[happy goofy]

I ran this in Solaris. When the waiting dead lock happens, press ctl+\.  (SIGQUIT, 3).  On Windows, try ctl + break.

This problem may result if the program creates say 5 producers and 1 consumer, and each can wake up just one other thread, this problem may result if the program creates say 5 producers and 5 consumer, and each can wake up one other thread.

This problem happens because all producers can quickly enter WAITING state before they wake any one consumer, or consumers enter WAITING state before they wake any one producer.

If we increase MAX_SIZE of the ArrayList(the queue), there is less chance the threads are in WAITING state, instead they are more likely in BLOCK state, while one thread is hold the lock and running. BLOCKED threads don't depend on others to wake themselves. Then there is less chance for the program to dead lock.

One more factor, the ratio between the number of producers and consumers, may affect the running of th program. One can reason that if the ratio is skewed, for instance, there are much more producers than consumers, the problem could be more pronounced. However, my experiment on this did not prove it. This could be clouded by the MAX_SIZE. The MAX_SIZE has more impact on the resulting of dead lock than the ratio. I could be wrong on this.  

More experiements are welcome and encouraged.