print one two three in sequence from three different threads?

Question

I am working on below interview question:

There are three threads in a process. The first thread prints 1 1 1 ..., the second one prints 2 2 2 ..., and the third one prints 3 3 3 ... endlessly. How do you schedule these three threads in order to print 1 2 3 1 2 3 ...

I came up with below code which prints 1 2 1 2 1 2 using two threads but I am not able to figure out the condition on how to print number 3 here from third thread.

public class PrintOneTwoThree {
  private static boolean isFirst = true;
  private static final Object lock = new Object();

  public static void main(String[] args) {
    // first thread
    new Thread(() -> {
      try {
        synchronized (lock) {
          for (;;) {
            while (!isFirst) {
              lock.wait();
            }
            System.out.print("1 ");
            isFirst = false;
            lock.notify();
          }
        }
      } catch (InterruptedException ignored) {
      }
    }).start();

    // second thread
    new Thread(() -> {
      try {
        synchronized (lock) {
          for (;;) {
            while (isFirst) {
              lock.wait();
            }
            System.out.print("2 ");
            isFirst = true;
            lock.notify();
          }
        }
      } catch (InterruptedException ignored) {
      }
    }).start();
  }
}

How to solve this kind of problem efficiently?

Answer 1

    public class PrintOneTwoThree {

    public static void main(String[] args) {

            Printers sp = new Printers();

            ExecutorService executor = Executors.newFixedThreadPool(3);
            executor.submit(new FirstNumberProducer(sp, 9));
            executor.submit(new SecondNumberProducer(sp , 9));
            executor.submit(new ThirdNumberProducer(sp , 9));
            executor.shutdown();
        }

    }


    class Printers {

        Semaphore first = new Semaphore(1);
        Semaphore second = new Semaphore(0);
        Semaphore third = new Semaphore(0);

        public void printFirstNumber() {
            try {
                first.acquire();
            }catch(InterruptedException exception) {

            }
            System.out.print("1");
                second.release();
        }

        public void printSecondNumber() {
            try {
                second.acquire();
            }catch(InterruptedException exception) {

            }
            System.out.print("2");
            third.release();
        }

        public void printThirdNumber() {
            try {
                third.acquire();
            }catch(InterruptedException exception) {

            }
            System.out.print("3");
            first.release();
        }

    }

    class FirstNumberProducer implements Runnable {

        Printers sp;
        int index;

        FirstNumberProducer(Printers sp , int index) {
            this.sp = sp;
            this.index = index;
        }

        @Override
        public void run() {
            for(int i = 1 ; i <= index ; i = i + 3 ) {
                sp.printFirstNumber();
            }
        }
    }

    class SecondNumberProducer implements Runnable{
        Printers sp;
        int index;

        SecondNumberProducer(Printers sp , int index) {
            this.sp = sp;
            this.index = index;
        }

        @Override
        public void run() {
            for(int i = 2 ; i <= index ; i = i + 3) {
                sp.printSecondNumber();
            }
        }
    }

    class ThirdNumberProducer implements Runnable{
        Printers sp;
        int index;

        ThirdNumberProducer(Printers sp , int index) {
            this.sp = sp;
            this.index = index;
        }

        @Override
        public void run() {
            for(int i = 3 ; i <= index ; i = i + 3) {
                sp.printThirdNumber();
            }
        }
    }

Output of the program is :

 123123123

Answer 2

Here's a general working example using a counter to give permission to one thread at a time for n threads:

public class PrintOneTwoThree {
    private static int currentTask;
    private static int totalThreads;
    private static final Object lock = new Object();

    public static void main(String[] args) {
        currentTask = 0;
        totalThreads = 3;

        for (int i = 0; i < totalThreads; i++) {
            createThread(i);
        }
    }

    static void createThread(int id) {
        new Thread(() -> {
            try {
                for (;;) {
                    synchronized (lock) {
                        while (currentTask != id) {
                            lock.wait();
                        }

                        System.out.print(id + 1 + " ");
                        currentTask = (currentTask + 1) % totalThreads;
                        lock.notifyAll();
                    }
                }
            }
            catch (InterruptedException ignored) {}
        }).start();
    }
}

Output:

1 2 3 1 2 3 1 2 3 ...

Try it!

A couple remarks:

• notify() works fine for the 2-thread version (because there is a maximum of one other thread blocking on the variable), but will deadlock in a 3+ version if a thread exits the critical section and notifys that the condition variable currentTask is available but the wrong thread wins the race to obtain the lock. I'm not sure if notifyAll() is appropriate design here, because there is only one thread that can make progress, so it seems like a stand in for re-checking the condition predicate and using notify().

• I moved the for (;;) outside of the synchronized section to keep the thread-safe scope as narrow is possible. This example is contrived because if you wanted this exact behavior of accessing a single resource and nothing else, it doesn't make sense to add the overhead of threading--you may as well do it deterministically in a single thread. In a real-world example, threads would perform thread-safe work elsewhere in the for (;;) loop when they're not blocking on the condition variable, so it seems logical to design with that in mind.

Answer 3

Instead of boolean flag use integer counter and check remainder when divided by 3 and increment counter after each print. And since there will be several threads waiting on the same lock it is better to use notifyAll.

private static int counter = 0;

new Thread(() -> {
        try {
            synchronized (lock) {
                for (;;) {
                    while (counter % 3 != 0) {
                        lock.wait();
                    }
                    System.out.print("1 ");
                    ++counter;
                    lock.notifyAll();
                }
            }
        } catch (InterruptedException ignored) {
        }
    }).start();

//And the same stuff for other two threads just replacing value for remainder in if and value in print