How to properly synchronize two threads

Question

This is a problem I have always heard about in school but never had a reason to mess with until I was asked for an interview.

Prompt: Using 2 threads print "Thread i: The number is 'j'" in order where j = 1:100 and i is the thread number. Thread 1 can only print odd j's and Thread 2 can only print even j's.

EDIT the output of j must be ordered

This was my attempt but I did not move on in the interview process. Is there any fundamental part I am missing? Are there any optimizations?

import java.util.concurrent.Semaphore;

public class ThreadSynchronization implements Runnable {

  private int start;
  private Semaphore semaphore;

  private ThreadSynchronization(int start, Semaphore semaphore) {
      this.start = start;
      this.semaphore = semaphore;
  }

  public static void main(String[] args) {
      Semaphore semaphore = new Semaphore(1, true);
      semaphore.acquireUninterruptibly();

      start(1, semaphore);
      start(2, semaphore);

      semaphore.release();
  }

  private static void start(int start, Semaphore semaphore) {
      ThreadSynchronization ts = new ThreadSynchronization(start, semaphore);
      Thread thread = new Thread(ts);
      thread.start();
      while (thread.getState() != Thread.State.WAITING) ;
  }

  @Override
  public void run() {
      for (int i = start; i <= 100; i += 2) {
          semaphore.acquireUninterruptibly();
          System.out.println("Thread " + start + ": The number is '" + i + "'");
          semaphore.release();
      }
  }
}

Hospitalet

I can not see why Synchronization is even needed – Batruk

Do you need to print the numbers in sequential order starting from 1 to 100. If not you can dispense with the synchronization here, since you don't access shared data concurrently. – Penult

yes the order matters, i updated with an edit note – Hospitalet

Why is the main thread acquiring the semaphore? – Mainland

As @ScaryWombat rightly mentioned, there is no need for synchronization. Correct check conditions and an AtomicInteger should suffice. – Stadiometer

What is the purpose of while (thread.getState() != Thread.State.WAITING) ;? And how do you ensure that thread 1 prints 1 before thread 2 prints 2? – Tarsia

@DavidSchwartz i am essentially making sure both threads are active but waiting for the semaphor – Hospitalet

@MadPhysicist the semaphor is used just to make sure i wait for both threads to fire up before they start doing work – Hospitalet

Answer 1

One thread can keep aquiring and releasing the Semaphore, while the other thread starves.

You can do this with wait and notify, try this:

import java.util.concurrent.atomic.AtomicInteger;

class Odd implements Runnable {

    private AtomicInteger integer;
    private final Object lock;

    public Odd(AtomicInteger integer, Object lock) {
        this.integer = integer;
        this.lock = lock;
    }

    @Override
    public void run() {
        synchronized (lock) {
            try {
                while (integer.get() <= 100) {
                    while (integer.get() % 2 == 0) {
                        lock.notify();
                        lock.wait();
                    }
                    if (integer.get() <= 100) {
                        System.out.println("Thread " +
                                Thread.currentThread().getName() + ": The number is '" + integer.get() + "'");
                    }
                    integer.getAndIncrement();
                    lock.notify();
                }
            } catch (Exception e) {

            }
        }
    }
}

class Even implements Runnable {

    private AtomicInteger integer;
    private final Object lock;

    public Even(AtomicInteger integer, Object lock) {
        this.integer = integer;
        this.lock = lock;
    }

    @Override
    public void run() {
        synchronized (lock) {
            try {
                while (integer.get() <= 100) {
                    while (integer.get() % 2 != 0) {
                        lock.notify();
                        lock.wait();
                    }
                    if (integer.get() <= 100) {
                        System.out.println("Thread " +
                                Thread.currentThread().getName() + ": The number is '" + integer.get() + "'");
                    }

                    integer.getAndIncrement();
                    lock.notify();
                }
            } catch (Exception e) {

            }
        }
    }
}

public class ThreadSynchronization {

    public static void main(String[] args) throws Exception{
        Object lock = new Object();
        AtomicInteger integer = new AtomicInteger(1);
        Odd odd = new Odd(integer, lock);
        Even even = new Even(integer, lock);

        Thread thread1 = new Thread(odd, "1");
        Thread thread2 = new Thread(even, "2");

        thread1.start();
        thread2.start();

        thread1.join();
        thread2.join();
    }

}

Elisa

i think this is what i was looking for, could you explain why synchronized (lock) doesnt cause one of the threads to freeze? does wait give up synchronization? – Hospitalet

@LoganMurphy Yes – Elisa

Answer 2

Use an object to arbiter:

public class Switch {
    private boolean expected;

    public Switch(boolean init) {
        expected = init;
    }

    public void waitFor(boolean value) {
        synchronized(this) {
            while (value != expected) {
                try {
                    wait();
                } catch (InterruptedException ex) {
                    // deal with it
                }
            }
            expected = !expected;
            notifyAll();
        }
    }
}

Then:

public class ThreadSynchronization implements Runnable {
    private static Switch arbiter = new Switch(true);

    private int start;

    private ThreadSynchronization(int start) {
        this.start = start;
    }

    public static void main(String[] args) {
        start(1);
        start(2);
    }

    private static void start(int start) {
        ThreadSynchronization ts = new ThreadSynchronization(start);
        Thread thread = new Thread(ts);
        thread.start();
    }

    @Override
    public void run() {
        boolean odd = start%2 != 0;
        for (int i = start; i <= 100; i += 2) {
            arbiter.waitFor(odd);
            System.out.println("Thread " + start + ": The number is '" + i + "'");
        }
    }
}

Merkel

Answer 3

You was very close to the right solution, but the task requires 2 semaphores:

public class ThreadSynchronization implements Runnable {

    private int start;
    private Semaphore semaphore1;
    private Semaphore semaphore2;

    private ThreadSynchronization(int start, Semaphore semaphore1, Semaphore semaphore2) {
        this.start = start;
        this.semaphore1 = semaphore1;
        this.semaphore2 = semaphore2;
    }

    private static void start(int start, Semaphore semaphore1, Semaphore semaphore2) {
        ThreadSynchronization ts = new ThreadSynchronization(start, semaphore1, semaphore2);
        Thread thread = new Thread(ts);
        thread.start();
    }

    @Override
    public void run() {
        for (int i = start; i <= 100; i += 2) {
            semaphore1.acquireUninterruptibly();
            System.out.println("Thread " + start + ": The number is '" + i + "'");
            semaphore2.release();
        }
    }

    public static void main(String[] args) {
        Semaphore semaphore1 = new Semaphore(1);
        Semaphore semaphore2 = new Semaphore(0);

        start(1, semaphore1, semaphore2);
        start(2, semaphore2, semaphore1); // in reverse order
    }
}

Recalcitrant

wow this one is really interesting, did not know you could start a Semaphore at 0 – Hospitalet

@LoganMurphy it even an be negative. RTFM! – Recalcitrant

Answer 4

For this simple task it is enough to use AutomicInteger:

 public static class CounterTask implements Runnable {

    private final int id;
    private final AtomicInteger counter;
    private final int max;
    private final IntPredicate predicate;

    public CounterTask(int id, AtomicInteger counter, int max, IntPredicate predicate) {
        this.id = id;
        this.counter = counter;
        this.max = max;
        this.predicate = predicate;
    }

    @Override
    public void run() {
        while (counter.get() <= max) {
            if (predicate.test(counter.get())) {
                System.out.format("Thread %d: The number is '%d'\n", id, counter.get());
                counter.incrementAndGet();
            }
        }
    }
}

public static void main(String... args) throws InterruptedException {
    final int max = 100;
    final AtomicInteger counter = new AtomicInteger();
    Thread oddThread = new Thread(new CounterTask(1, counter, max, val -> val % 2 == 0));
    Thread evenThread = new Thread(new CounterTask(2, counter, max, val -> val % 2 != 0));

    oddThread.start();
    evenThread.start();

    oddThread.join();
    evenThread.join();
}

Guanaco

How does the thread that's not supposed to print wait for the other thread to finish printing with just an AtomicInteger? You think it's acceptable for the non-running thread to spin on counter.get() and potentially starve the thread that's trying to make useful forward progress? – Tarsia

Just check it! It is enough, no additional synchronization needed. – Guanaco

your approach is really extensible but has a lot of wasted thread work, thanks for your submission! – Hospitalet

It is better than sleep thread and lock. Not blocking algo is better than blocking – Guanaco

Answer 5

While wait and notify can do the job, I think the use of Semaphore can make for more readable code. The code below focusses on a solution for threads "talking" to each other and synchornizing where needed: I imagine in a real use case 2 threads do important work and at some point need to synchronize and determine who goes first.

import java.util.concurrent.Semaphore;

public class LockStep {

    public static void main(String[] args) {

        Semaphore evenTurn = new Semaphore(1);
        Semaphore oddTurn = new Semaphore(0);

        int max = 50;

        Thread even = new Thread(new Worker(evenTurn, oddTurn, max));
        even.start();
        Thread odd = new Thread(new Worker(oddTurn, evenTurn, max));
        odd.start();

        try {
            even.join();
            odd.join();
        } catch (Exception e) {
            System.out.println("No join for me: " + e);
        }
        System.out.println("Finished");
    }

    static class Worker implements Runnable {

        final Semaphore myTurn;
        final Semaphore theirTurn;
        final int maxTurns;

        public Worker(Semaphore myTurn, Semaphore theirTurn, int maxTurns) {
            this.myTurn = myTurn;
            this.theirTurn = theirTurn;
            this.maxTurns = maxTurns;
        }

        @Override
        public void run() {

            int turn = 0;
            while (turn < maxTurns) {
                try {
                    myTurn.acquire();
                    turn += 1;
                    System.out.println(Thread.currentThread().getName() + " " + turn);
                    theirTurn.release();
                } catch (Exception e) {
                    System.out.println("Oops: " + e);
                }
            }
        }
    }
}

Goggle

i can see how i can manipulate this to get what i want, thanks! – Hospitalet