How to use wait and notify protocol with multiple threads

Question

Specifically, can somebody tell me what is wrong with this piece of code. It should start the threads, so should print "Entering thread.." 5 times and then wait until notifyAll() is called. But, it randomly prints "Entering.." and "Done.." and still keeps waiting on others.

public class ThreadTest implements Runnable {
    private int num;
    private static Object obj = new Object();
    ThreadTest(int n) {
        num=n;
    }
    @Override
    public void run() {
        synchronized (obj) {
            try {
                System.out.println("Entering thread "+num);
                obj.wait();
                System.out.println("Done Thread "+num);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }   
        }   
    }   

    public static void main(String[] args) {
        Runnable tc;
        Thread t;
        for(int i=0;i<5;i++) {
            tc = new ThreadTest(i);
            t = new Thread(tc);
            t.start();
        }
        synchronized (obj) {
            obj.notifyAll();
        }
    }
}

Answer 1

You're not doing anything blatantly wrong with the method calls, but you have a race condition.

Although in an ideal world the main thread will reach its synchronized block after all the worker threads reach the wait() call, there is no guarantee of that (you explicitly told the virtual machine that you didn't want the threads to execute in sequence with the main thread by making them threads). It may happen (e.g. if you have only one core) that the thread scheduler decides to block all the worker threads immediately they start to allow the main thread to continue. It may be that the worker threads are context switched out because of a cache miss. It may be that one worker thread blocks for I/O (the print statement) and the main thread is switched in in its place.

Thus, if the main thread manages to reach the synchronized block before all the worker threads have reached the wait() call, those worker threads that have not reached the wait() call will fail to operate as intended. Since the current set up does not allow you to control this, you must add explicit handling of this. You could either add some sort of variable that is incremented as each worker thread reaches wait() and have the main thread not call notifyAll() until this variable reaches 5, or you could have the main thread loop and repeatedly call notifyAll(), so that worker threads are released in multiple groups.

Have a look in the java.util.concurrent package - there are several lock classes that provide more powerful capabilities than basic synchronized locks - as ever, Java saves you from re-inventing the wheel. CountDownLatch would seem to be particularly relevant.

In summary, concurrency is hard. You have to design to make sure that everything still works when the threads execute in the orders you don't want, as well as the orders you would like.

Answer 2

The root problem with your code is that some of the threads don't get to the wait until after the main thread calls notifyAll. So when they wait, nothing will wake them up.

To make this work (using wait / notify) you need to synchronize the main thread so that it waits for all of the child threads to get to a state where they can receive the notify before it makes that call.

Generally speaking, doing synchronization with the wait, notify and primitive locks is tricky. In most cases, you will get better results (i.e. simpler, more reliable and more efficient code) by using the Java concurrency utility classes.

Answer 3

I second the CountDownLatch recommendation. Here is the pattern I use for my multithreaded tests:

final int threadCount = 200;

final CountDownLatch startPistol = new CountDownLatch(1);
final CountDownLatch startingLine = new CountDownLatch(threadCount);
final CountDownLatch finishingLine = new CountDownLatch(threadCount);

// Do a business method...
Runnable r = new Runnable() {
    public void run() {
        startingLine.countDown();
        try {
            startPistol.await();

            // TODO: challenge the multithreadedness here

        } catch (InterruptedException e) {
            Thread.interrupted();
        }
        finishingLine.countDown();
    }
};

//  -- READY --

for (int i = 0; i < threadCount; i++) {
    Thread t = new Thread(r);
    t.start();
}

// Wait for the beans to reach the finish line
startingLine.await(1000, TimeUnit.MILLISECONDS);

//  -- SET --

// TODO Assert no one has started yet

//  -- GO --

startPistol.countDown(); // go

assertTrue(finishingLine.await(5000, TimeUnit.MILLISECONDS));

//  -- DONE --

// TODO: final assert

The idea is to guarantee the very next line of code your threads will execute is the one that challenges the multithreadedness or as close to it as possible. I think of the threads as runners on a track. You get them on the track (create/start), wait for them to perfectly line up on the starting line (everyone has called startingLine.countDown()), then fire the starting pistol (startPistol.countDown()) and wait for everyone to cross the finish line (finishingLine.countDown()).

[EDIT] It should be noted that if you do not have any code or checks you want to execute between startingLine.await() and startingPistol.countDown(), you could combine both startingLine and startingPistol into one CyclicBarrier(threadCount + 1). The double CountDownLatch approach is effectively the same and allows the main test thread to do any setup/checks after all other threads are lined up and before they start running, should that be needed.