Why is notifyAll() not waking all of the threads in this example?

Question

I'm trying to figure out how to use wait & notify, so I've written this small example with a few planes waiting for a runway to clear before they take off, the issue I'm having is that when a plane takes off, and calls notifyAll(), only one thread seems to be woken up, i.e. I expect all of the threads to report that they have been notified, but are still waiting. What actually happens is that only one thread is woken, and the rest do nothing. Why does it appear that only the one thread is woken, and how can I fix it?

class Plane extends Thread
{
    Runway runway;

    Plane(int id, Runway runway)
    {
        super(id + "");
        this.runway = runway;

    }

    public void run()
    {
        runway.taxi();
        runway.takeoff();
    }
}

class Runway
{
    boolean isFull;

    Runway()
    {
        isFull = false;;
    }

    public synchronized void taxi()
    {
        System.out.println(Thread.currentThread().getName() + " started to taxi");
        while(isFull)
        {
            System.out.println(Thread.currentThread().getName() + " is queued");
            try
            {
                wait();
            }
            catch(InterruptedException e){}     
        }
        isFull = true;
        System.out.println(Thread.currentThread().getName() + " entering runway");
    }

    public synchronized void takeoff()
    {
        try
        {
            Thread.currentThread().sleep(1000);
        }
        catch(InterruptedException e){}
        System.out.println(Thread.currentThread().getName() + " took off");
        isFull = false;
        notifyAll();
    }

    public static void main(String[] args)
    {
        Runway runway = new Runway();
        new Plane(1, runway).start();
        new Plane(2, runway).start();
        new Plane(3, runway).start();
        new Plane(4, runway).start();
    }
}

Thanks for taking the time to help me :)

Answer 1

Suppose you have 4 Planes that are all start()-ed one after the other.

All 4 will attempt to call taxi() followed by takeoff()

The first one will call taxi():

• acquire the lock,
• find isFull is false
• set isFull to true
• return, releasing the lock

Then one (or more) of the remaining threads may get to call taxi(). If they do, they:

• acquire the lock
• find isFull is false
• call wait() which releases the lock

OR

• block while trying to acquire the lock

In the mean time, the thread that returned from taxi() will call takeoff(). This will:

• acquire the lock
• sleep for 1 second,
• notify any threads that were waiting
• return, releasing the lock.

---

So how does this explain what you are seeing?

Suppose that when the first thread returned from taxi() it was immediately able to reacquire the lock and start the takeoff() call. It would then call sleep() WHILE HOLDING THE LOCK. This would prevent any other threads from starting their taxi() calls (if they hadn't already done so). Then after the sleep, it would call notifyAll(). But that would only notify the threads that were had gotten into the taxi() call and that had called wait(). Any threads that were blocked while starting the taxi() call would never see the notifications.

(Notifications are never queued for threads that are not in wait() calls.)

Is this likely? Well yes it is.

Starting a thread is a relatively expensive / time consuming process, and there is a good chance that the first thread started will get to do a lot of work before the next one gets started. The chances are that it will get all the way to the sleep call before the second one tries to call taxi().

The same pattern is likely to repeat for the remaining threads. When each thread that gets into taxi() is likely to release and then reacquire it before another thread is scheduled. (Thread scheduling is handled by the OS, and it is optimizing for efficiency rather than fairness. If you want fair scheduling, you need to use a Lock object.)

---

... how can a fix it?

Change your code so that you don't sleep while holding the lock. For example:

public void takeoff() {
    try {
        Thread.currentThread().sleep(1000);
    } catch (InterruptedException e) {
        // squash ...
    }
    System.out.println(Thread.currentThread().getName() + " took off");
    synchronize (this) {
        isFull = false;
        notifyAll();
    }
}