Thread Deadlock

Question

I have 2 threads. One thread prints odd numbers and the second thread prints even numbers. Now, I have to execute the threads alternatively so that i can output 1,2,3,4,5,6,.....

I have written a program for this and this is resulting in a deadlock. Can someone explain what is the problem with the code and how to rectify it?

class BooleanObject {
boolean flag;
BooleanObject(boolean flag) {
    this.flag = flag;
}
}
class EvenThread extends Thread {
Object lock;
BooleanObject flagObj;
EvenThread(Object o, BooleanObject flag) {
    lock = o;
    this.flagObj = flag;
}
public void run() {
    for (int i=2;i<100;i+=2) {
        synchronized(lock) {
            if (flagObj.flag == false) {
                flagObj.flag = true;
                lock.notify();
            }
            else {
                try {
                    while (flagObj.flag == true) {
                        lock.wait();
                    }
                }
                catch (InterruptedException e) {

                }
            }
            System.out.println(i);
        }
    }
}
}

class OddThread extends Thread {
Object lock;
BooleanObject flagObj;
OddThread(Object o, BooleanObject flag) {
    lock = o;
    this.flagObj = flag;
}
public void run() {
    for (int i=1;i<100;i+=2) {
        synchronized(lock) {
            if (flagObj.flag == true) {
                flagObj.flag = false;
                lock.notify();
            }

            else {
                try {
                    while(flagObj.flag == false) {
                        lock.wait();
                    }
                }
                catch (InterruptedException e) {

                }
            }
            System.out.println(i);
        }
    }
}
}

public class EvenOddThreads {
public static void main(String[] args) {
    Object obj = new Object();
    BooleanObject flagObj = new BooleanObject(true);
    EvenThread et = new EvenThread(obj,flagObj);
    OddThread ot = new OddThread(obj,flagObj);

    et.setName("even thread");
    ot.setName("odd thread");

    et.start();
    ot.start();
}
}

Answer 1

The problem is with auto-boxing. When you change flag from true to false or vice versa, you are actually getting an entirely new Boolean object. That is, this line:

flag = false;

Is equivalent to:

flag = new Boolean(false);

Once that happens your two threads are then referring to two different Boolean objects, so their flags end up un-synchronized and neither thread is able to signal the other to wake up. When OddThread changes the flag EvenThread still has the old flag object so it doesn't see the new value.

Because a Boolean object is immutable you'll need to change your flag to use some other mutable object which can change values in place without creating new objects. That, or have both classes refer to a common (perhaps global) variable.

As @erickson suggests you could use AtomicBoolean which is mutable. Another kludgy way to do it would be to change flag to:

boolean[] flag = new boolean[1];

And then use flag[0] every where. Both threads would then be able to change flag[0] while always referencing the same boolean[] array object. You wouldn't have the auto-boxing problem.

...

Also, it is a good idea to wrap any call to wait() in a loop. A wait() can be subject to spurious wakeups where the call returns even though nobody has actually called notify(). To workaround that you should always check your guarding condition after waking up to make sure the wakeup isn't spurious.

while (flag == true) {
    lock.wait();
}

---

Update

I have made the changes based on your suggestions above; but i am not getting the expected output. I will paste the modified code above. Here is the output i am getting 1 2 4 3 5 6 8 7 9 10 11 13 12 15 17 14....

When you end up waiting, once you are woken up you don't toggle flag and notify the other thread. I advise reorganizing your code a bit so it looks like "wait; print; notify". Something like:

synchronized (lock) {
    while (flagObj.flag == false) {
        lock.wait();
    }

    System.out.println(i);

    flagObj.flag = false;
    lock.notify();
}