Loop synchronization deadlock

Question

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

Answer 1

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.

Answer 2

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();
            }
        }
    }
}