Java multithreading wait and notify in same block

Question

I am working on a small problem where in I need to print numbers sequentially with two threads in alternate fashion. Like Thread 1 prints 1, thread 2 prints 2, thread 1 prints 3 and so on...

So I have created below piece of code but at some point both the threads go into wait state and nothing prints on the console.

import java.util.concurrent.atomic.AtomicInteger;

public class MultiPrintSequence {

    public static void main(String[] args) {
        AtomicInteger integer=new AtomicInteger(0);
        Sequence sequence1=new Sequence(integer);
        Sequence sequence2=new Sequence(integer);
        sequence1.start();
        sequence2.start();
    }
}

class Sequence extends Thread{

    private AtomicInteger integer;
    boolean flag=false;

    public Sequence(AtomicInteger integer) {
        this.integer=integer;
    }

    @Override
    public void run() {
        while(true) {
            synchronized (integer) {
                while (flag) {
                    flag=false;
                    try {
                        System.out.println(Thread.currentThread().getName()+" waiting");
                        integer.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                System.out.println(Thread.currentThread().getName()+" "+integer.incrementAndGet());
                flag = true;
                System.out.println(Thread.currentThread().getName()+" notifying");
                integer.notify();
            }
        }
    }
}

When observing the console output, I noticed that at some point when one of the thread notifies, the other thread eventually starts even before the notifying thread gets into the wait state and hence at one point both the threads go into wait state. Below is the small portion of console output.

Thread-1 510
Thread-1 notifying
Thread-1 waiting
Thread-0 511
Thread-0 notifying
Thread-0 waiting
Thread-1 512
Thread-1 notifying
Thread-1 waiting
**Thread-0 513
Thread-0 notifying
Thread-1 514
Thread-1 notifying
Thread-1 waiting
Thread-0 waiting**

Answer 1

Your flag variable is not shared between the threads, but the logic around that flag is odd anyway. Note that you don’t need to use an AtomicInteger when you are using synchronized.

When using synchronized properly, an ordinary int variable is already sufficient to implement the entire logic:

public class MultiPrintSequence {
    public static void main(String[] args) {
        final Sequence sequence = new Sequence();
        new Thread(sequence).start();
        new Thread(sequence).start();
    }
}
class Sequence implements Runnable {
    private final Object lock = new Object();
    private int sharedNumber;

    @Override
    public void run() {
        synchronized(lock) {
            for(;;) {
                int myNum = ++sharedNumber;
                lock.notify();
                System.out.println(Thread.currentThread()+": "+myNum);
                while(sharedNumber == myNum) try {
                    lock.wait();
                } catch (InterruptedException ex) {
                    throw new AssertionError(ex);
                }
            }
        }
    }
}

Of course, creating multiple threads to perform a sequential operation is defeating the actual purpose of concurrent programming.

Answer 2

Consider this unlucky sequence of events. Thread1 increments the value, sets the flag to true and notifies any threads in the wait set for the lock. Now Thread0 was already there in the wait set. Then Thread0 awakes and it's flag = false. Then Thread0 exits the while loop and prints the incremented value and notifies any waiting threads. Then it moves on to the next iteration in the while loop and invokes wait on the lock object. But Thread1 is not in the waiting state, rather it is switched out of the CPU by the scheduler after completing it's synchronized block to give a chance to Thread0. Thread1 is in runnable state and is given a chance by the schedular back again since there are no runnable threads left. Then Tread1 enters the while loop since flag = true, and invokes wait on the same lock object. Now both the threads are in waiting state and there's no one to wake them up. So this is a good example of a live lock in a system.

This happens because the flag is an instance field hence not shared between threads. So each thread has it's own copy of the flag. If you mark it as static variable then both threads share that value, hence the issue is solved. Here's how the flag declaration should look.

static boolean flag = false;

How does that fix the issue? Well, consider the same sequence of events. And now Thread1 sets the flag value to true before it calls notify on the lock object. The Thread0 is already in waiting state. The schedular switches Thread1 off the CPU and gives a chance to Thread0. It starts running and since the flag = true, it enters the while loop sets the flag to false and invokes wait on the lock object. Then Thread0 goes into waiting state and schedular gives a chance to Thread1. Thread1 resumes it's execution and flag = false, hence it exits the while loop, printing the incremented value and notifies the waiting Thread. So there's no live lock now.

However I don't see any point of using both synchronized and non-blocking Atomic variables. You should NOT use both of them together. A more better, performant implementation is given below.

public class Sequence extends Thread {
    private static final Object lock = new Object();
    private static int integer = 0;
    static boolean flag = false;

    @Override
    public void run() {
        while (true) {
            synchronized (lock) {
                while (flag) {
                    flag = false;
                    try {
                        System.out.println(Thread.currentThread().getName() + " waiting");
                        lock.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                System.out.println(Thread.currentThread().getName() + " " + ++integer);
                flag = true;
                System.out.println(Thread.currentThread().getName() + " notifying");
                lock.notify();
            }
        }
    }

    public static void main(String[] args) {
        Sequence sequence1=new Sequence();
        Sequence sequence2=new Sequence();
        sequence1.start();
        sequence2.start();
    }
}

Answer 3

In the code, even if integer is Atomic and shared between Threads, the flag itself it is not.

class Sequence extends Thread{

    private AtomicInteger integer; //shared
    boolean flag=false; //local

    public Sequence(AtomicInteger integer) {
      this.integer=integer;
    }

Which causes a change in one thread not reflecting in another.

Proposed solution:

You can solve using Atomic for the flag too and sharing, for example:

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

public class StackOverflow {

    public static void main(String[] args) {
        AtomicInteger integer=new AtomicInteger(0);
        AtomicBoolean flag=new AtomicBoolean(true);
        Sequence sequence1=new Sequence(integer, flag);
        Sequence sequence2=new Sequence(integer, flag);
        sequence1.start();
        sequence2.start();
    }
}

And the sequence:

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

class Sequence extends Thread{

    private final AtomicInteger integer;
    private AtomicBoolean flag;

    public Sequence(AtomicInteger integer, AtomicBoolean flag) {
        this.integer=integer;
        this.flag=flag;
    }

    @Override
    public void run() {
        while(true) {
            synchronized (integer) {
                while (flag.get()) {
                    flag.set(false);
                    try {
                        System.out.println(Thread.currentThread().getName()+" waiting");
                        integer.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                System.out.println(Thread.currentThread().getName()+" "+integer.incrementAndGet());
                flag.set(true);
                System.out.println(Thread.currentThread().getName()+" notifying");
                integer.notify();
            }
        }
    }
}

This is part of the output:

Thread-1 8566
Thread-1 notifying
Thread-1 waiting
Thread-0 8567
Thread-0 notifying
Thread-0 waiting
Thread-1 8568
Thread-1 notifying
Thread-1 waiting
Thread-0 8569
Thread-0 notifying
Thread-0 waiting