DeadLock occur When push to and pop Element from a List simultaneously

The purpose of the following code is to implement a LIFO co开发者_高级运维ntainer just like a Stack, while, when retrieve an element, it will check if there is any existing element in the list, or it hold on thread that retrieving element until there is a new element get inserted.

public class Stack {

LinkedList list = new LinkedList();

public synchronized void push(Object x) {
    synchronized (list) {
        list.addLast(x);
        notify();
    }
}

public synchronized Object pop() throws Exception {
    synchronized (list) {
        if (list.size() <= 0) {
            wait();
        }
        return list.removeLast();
    }
}  

}

but deadlock may occur whenever call pop() where there is no element in the List. How to amend this Class to achieve the initial purpose while avoiding pontential deadlock. Thanks

There are so many things I would change about this class its hard to know where to start. This simplest solution is to remove the synchronized(list) blocks as these are redundant and just cause problems as you can see.

Another solution would be to use the Stack class which is builtin to Java. Your class could be confused for the built one as it has the same name.

Or I would use a LinkedBlockingDeque which is thread safe as my collection and has pop() and push() methods.

EDIT: If you want to know why you are getting a dead lock, it is because you are holding two locks (one on the Stack, the other on the LinkedList) but you are releasing only one lock with your wait() (the one on the Stack) meaning no other thread can get the lock on the list. There is no way to wait() on two objects at once.

Your code is much the same as this (which might be clearer)

public void push(Object x) {
  synchronized(this) {
    synchronized (list) { // cannot get a lock on `list` while pop() is called.
        list.addLast(x);
        this.notify();
    }
  }
}

public Object pop() throws Exception {
  synchronized(this) {
    synchronized (list) {
        if (list.size() <= 0) {
            this.wait(); // releases the lock on `this`, but keep the lock on `list`
        }
        return list.removeLast();
    }
  }
}

This what happens when you call pop on an empty Stack and then push from other thread.
The wait() in pop is in synchronized block so the call to push from another thread will wait for the pop method to return, but pop is blocked waiting for a push and you got your deadlock.

The problem is that you're synchronizing on two different objects : on the stack instance (through the synchronized keyword on both methods) and on the list (through the synchronized (list) statements)

So, when the pop method waits, it calls wait on the stack instance and thus releases the monitor it holds on the stack instance, allowing another thread to enter the push method. But it doesn't release the monitor it holds on the list, so the other thread is blocked waiting for the monitor on the list to be released.

Your problem is a combination of problems.

Firstly your code gets two locks for every method - one on the Stack and one on the list. When 'wait' is called the one on the Stack is released, but the one on list is not. This will prevent any other methods being executed. This is effectively a deadlock. (Thanks Peter Lawrey)

Secondly the code:

if (list.size() <= 0) {
   wait();
}

will cause an attempted pop to wait for a push before continuing. That may seem like a deadlock, but really it's just waiting. However the call

notify();

will only wake up one thread. If more than one thread is waiting to pop, all but one will continue waiting. This seems even more like a deadlock (even though it isn't, technically).

Fixes you should do to this code:

• get rid of the double synchronization. You need either the method synchronization or synchronize(list), not both.
• use "notifyAll() instead of "notify()", and couple it with using "while" instead of "if" when waiting.

It's also much more normal to have a stack throw an exception if there are no items on it rather than wait for a push.