Sequential execution of threads using synchronized

Question

I have a snippet of code that creates 3 threads and expect them to print sequentially using synchronized block on the integer object. But apparently I am getting deadlock sometimes. See below:

public class SequentialExecution implements Runnable {

    private Integer i = 1;

    public void run() {

        String tmp = Thread.currentThread().getName();

        if (tmp.equals("first")) {
            synchronized(i) {
                first();
                i = 2;
            }
        } else if (tmp.equals("second")) {
            while (i != 2);
            synchronized(i) {
                second();
                i = 3;
            }
        } else {
            while (i != 3);
            synchronized(i) {
                third();
            }
        }

    }

    public void first() {
        System.out.println("first " + i);
    }

    public void second() {
        System.out.println("second " + i);
    }

    public void third() {
        System.out.println("third " + i);
    }

    public static void main(String[] args) {
        //create 3 threads and call first(), second() and third() sequentially
        SequentialExecution se = new SequentialExecution();
        Thread t1 = new Thread(se, "first");
        Thread t2 = new Thread(se, "second");
        Thread t3 = new Thread(se, "third");

        t3.start();
        t2.start();
        t1.start();

    }

}

The result I am expecting(and sometimes getting) is:

first 1
second 2
third 3

One sample result I am getting with deadlock(and eclipse hangs) is:

first 1
second 2 

Anyone know why this is not working? I know I can use locks but I just don't know why using synchronized block is not working.

Answer 1

Declare i to be volatile: private volatile Integer i = 1;. This warns the compiler that it must not apply certain optimizations to i. It must be read from memory each time it is referenced in case another thread has changed it.

I also agree with the recommendation in user3582926's answer to synchronize on this rather than i, because the object referenced by i changes as the program runs. It is neither necessary nor sufficient to make the program work, but it does make it a better, clearer program.

I have tested each change by changing the main method to:

  public static void main(String[] args) throws InterruptedException {
    // create 3 threads and call first(), second() and third() sequentially
    for (int i = 0; i < 1000; i++) {
      SequentialExecution se = new SequentialExecution();
      Thread t1 = new Thread(se, "first");
      Thread t2 = new Thread(se, "second");
      Thread t3 = new Thread(se, "third");

      t3.start();
      t2.start();
      t1.start();
      t1.join();
      t2.join();
      t3.join();
    }

  }

There is no deadlock. There is a memory order issue.

The while loops in the second and third threads are outside any synchronized block. There is nothing telling the compiler and JVM that those threads cannot keep i, or the object to which it points, in a register or cache during the loop. The effect is that, depending on timing, one of those threads may get stuck looping looking at a value that is not going to change.

One way to solve the problem is to mark i volatile. That warns the compiler that it is being used for inter-thread communication, and each thread needs to watch for changes in memory contents whenever i changes.

In order to solve it entirely using synchronization, you need to check the value of the Integer referenced by i inside a block that is synchronized on a single, specific object. i is no good for that, because it changes due to boxing/unboxing conversion. It might as well be a simple int.

The synchronized blocks cannot wrap the while loops, because that really would lead to deadlock. Instead, the synchronized block has to be inside the loop. If the updates to i are synchronized on the same object, that will force the updates to be visible to the tests inside the while loops.

These considerations lead to the following synchronization-based version. I am using a main method that does 1000 runs, and will itself hang if any thread in any of those runs hangs.

public class SequentialExecution implements Runnable {

  private int i = 1;

  public void run() {

    String tmp = Thread.currentThread().getName();

    if (tmp.equals("first")) {
      synchronized (this) {
        first();
        i = 2;
      }
    } else if (tmp.equals("second")) {
      while (true) {
        synchronized (this) {
          if (i == 2) {
            break;
          }
        }
      }
      synchronized (this) {
        second();
        i = 3;
      }
    } else {
      while (true) {
        synchronized (this) {
          if (i == 3) {
            break;
          }
        }
      }

      synchronized (this) {
        third();
      }
    }

  }

  public void first() {
    System.out.println("first " + i);
  }

  public void second() {
    System.out.println("second " + i);
  }

  public void third() {
    System.out.println("third " + i);
  }

  public static void main(String[] args) throws InterruptedException {
    // create 3 threads and call first(), second() and third() sequentially
    for (int i = 0; i < 1000; i++) {
      SequentialExecution se = new SequentialExecution();
      Thread t1 = new Thread(se, "first");
      Thread t2 = new Thread(se, "second");
      Thread t3 = new Thread(se, "third");

      t3.start();
      t2.start();
      t1.start();
      t1.join();
      t2.join();
      t3.join();
    }

  }
}

Answer 2

I believe you want to be using synchronized(this) instead of synchronized(i).