Loop synchronization deadlock

I've got the following classes in Java

public class Counter {
    private int value;

    public Counter(int value) {
        this.value = value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public void decrement() {
        this.value--;
    }
   开发者_运维问答 public int getValue() {
        return this.value;
    }
}

public class Cell extends Thread {

    private Object sync;
    private Counter counter;

    public Cell(Object sync, Counter counter) {
        this.sync = sync;
        this.counter = counter;
    }

    public void run() {
        for (int r=0; r<Simulation.ROUND_NUM; r++) {

            // do something

            synchronized(counter) {
                counter.decrement();
                counter.notifyAll();
            }
            synchronized(sync) {
                try {
                    sync.wait();
                }
                catch (Exception ex) {}
            }

        }
    }
}

public class Simulation extends Thread {

    public static final int THREAD_NUM = 5;
    public static final int ROUND_NUM = 5;

    public Object sync = new Object();
    private Counter counter = new Counter(THREAD_NUM);

    public void run() {

        for (int i=0; i<THREAD_NUM; i++) {
            Cell c = new Cell(sync,counter);
            c.start();
        }

        for (int i=0; i<ROUND_NUM; i++) {
            synchronized(counter) {
                while(counter.getValue() != 0) {
                    try {
                        counter.wait();
                    }
                    catch (Exception ex) {}
                }
                counter.setValue(THREAD_NUM);
            }

            synchronized(sync) {
                sync.notifyAll();
            }
        }
    }
}

The aim is to prevent from executing the next iteration of loop in each Cell Thread, until every Cell Thread will be done on each iteration. My solution sometimes leads to deadlock. I can't understand why. Please help

First of all you could make use of the AtomicInteger class instead of the Counter class you made. The AtomicInteger class is thread-safe so that you can use atomic action such as decrementAndGet and incrementAndGet.

To achieve the functionality of waiting till each of the Cell threads is done you can use a CountDownLatch like mentioned in a previous comment, or even concurrent objects like CyclicBarriers to halt execution till all Cell threads join on the barrier. Through some of these concurrent objects it should be easier to control multiple threads. Using plain synchronization does work as well, you just are typically required to do more coding and thinking to ensure everything works well.

In your code, there seems to be no guarantee that when sync.notifyAll() gets executed, all the Cell threads got to sync.wait(). This refers to the last Cell thread (the fifth in your example) that needs to grab the lock for sync in order to wait on it. But the Simulation thread is also trying the same thing without making sure that everyone is waiting. That race condition makes Simulation sometimes grab the lock before the last Cell is able to do the same and wait.

Since that last Cell is not waiting, it doesn't get notified so the whole thing gets stuck. You can test this by adding a System.out.println() as the first line in each synchronized (sync) block and writing "waiting for sync" and "notifying sync" accordingly. You'll see that only 4 threads are waiting for sync when you notify it.

To make sure everyone is waiting when the Simulator notifies, have the two synchronized blocks in Cell#run() nested:

public class Counter {
    private int value;

    public Counter(int value) {
        this.value = value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public void decrement() {
        this.value--;
    }

    public int getValue() {
        return this.value;
    }

    public static void main(String[] args) {
        new Simulation().start();
    }
}

class Cell extends Thread {

    private Object sync;
    private Counter counter;

    public Cell(Object sync, Counter counter) {
        this.sync = sync;
        this.counter = counter;
    }

    public void run() {
        for (int r = 0; r < Simulation.ROUND_NUM; r++) {

            // do something

            synchronized (sync) {
                synchronized (counter) {
                    counter.decrement();
                    counter.notifyAll();
                }
                try {
                    sync.wait();
                } catch (Exception ignored) {}
            }


        }
    }
}

class Simulation extends Thread {

    public static final int THREAD_NUM = 900;
    public static final int ROUND_NUM = 30;

    public Object sync = new Object();
    private Counter counter = new Counter(THREAD_NUM);

    public void run() {

        for (int i = 0; i < THREAD_NUM; i++) {
            Cell c = new Cell(sync, counter);
            c.start();
        }

        for (int i = 0; i < ROUND_NUM; i++) {
            synchronized (counter) {
                while (counter.getValue() != 0) {
                    try {
                        counter.wait();
                    } catch (Exception ex) {
                    }
                }
                counter.setValue(THREAD_NUM);
            }

            synchronized (sync) {
                sync.notifyAll();
            }
        }
    }
}

Your code can deadlock because you're not making any guarantee that the Cell threads will actually be in the wait() block at the time that notifyAll occurs. The following is one sequence of events that could cause this problem:

1. Simulation starts all threads, and blocks waiting for a 0 value.
2. Each thread in sequence calls decrement, then counter.notifyAll, and then loses its time slice
3. The main thread has been notified, wakes up, finds the counter is at 0, calls sync.notifyAll, loops to the top, and waits indefinitely.
4. Each thread in sequence is given a time slice, advances to the wait(), and waits indefinitely.

Lovely example! It isn't deadlock, since by definition that can only occur when a thread holds more than one lock simultaneously, and another tries to acquire the same locks in a different order.
I suspect that the problem here is caused by spurious wake-ups occurring in the Cell objects (if a spurious wake-up occured in the Simulation object it would have no effect as the wait() is called in a loop which will cause the wait to be re-entered).
A spurious wake-up in a Cell will cause an extra decrement. This in turn will make the test while(counter.getValue() != 0) to be stepped over.
Change that condition to while(counter.getValue() >= 0) and the 'deadlocks should disappear. Please let us know if it works.

This is not a deadlock. Your main thread can miss a notify on the counter and will be stuck on counter.wait() after it is alread at 0. Use jstack JDK tool to analyze what threads are doing in a situation like this.