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

Answer 2

The problem isn't autoboxing. The same thing would happen even if boolean primitives were used throughout.

It's a scope problem. Each thread instance has its own flag member, and they are completely distinct. When you assign a new value in one thread, the other thread cannot see it.

To make this work as intended, make a mutable boolean wrapper (an AtomicBoolean would do the job, although you wouldn't be making use of its concurrency properties in this application), and pass that wrapper to each thread. Each thread would mutate that single object, rather than assigning a new object to its own variable.

Answer 3

You actually have two problems here.

1) The first one is this

if (flag == true) {
    flag = false;
    lock.notify();
}

You pass the flag reference to the constructor, but then you change each thread's local flag, which won't affect the other thread's value.

Try something like

class Monitor
{
    public static volatile boolean flag;
}

And then use Monitor.flag in each thread.

2) The second problem (once the 1st one is fixed), is that each thread needs to have this

synchronized(lock)
{
    lock.notify();
}

at the end after the loop because otherwise one thread will wait() but the other thread is already done.

Answer 4

I can never understand these questions. If you want code to execute in a certain order why use threads at all?