266Threading Questions in Job Interviews Part 2

Author: Dr. Heinz M. KabutzDate: 2019-02-12Java Version: 11Category: Concurrency

Abstract: In our previous newsletter, we showed 14 typical questions that interviewers ask to find out if we know threading. Here are our model answers. Use them with caution. The interviewer is probably reading my newsletter.

Welcome to the 266th edition of The Java(tm) Specialists' Newsletter, sent from the rainy Island of Crete. We will soon have the draw for the JCrete 2019 lottery, so please fill in the application if you would like a chance to join us in July for the hottest Java unconference in the world (literally).

My new Mastering Threads is ready. Also available in German with the title Threads beherrschen. It was tricky recording this as I was suffering from a nasty cold. The editing afterwards was gruesome to listen to, but I think I removed all the hacking. The coughing, that is :-)

Last month I began listening to the Java OffHeap podcast. It is an excellent Java news podcast, with Freddy Guime, Bob Paulin, Michael Minella and Josh Juneau. What I like is that they all four have different perspectives on the Java ecosystem. Freddy is a high-performance, low latency guy, who does not want any framework stealing precious CPU cycles. Josh works as a DB admin and is a great fan of Java EE. Michael works for Pivotal and is thus in the Spring camp. Bob is an independent consultant and an Apache Software Foundation member. I liked their banter so much that I went back to the beginning and am slowly working my way through the 50+ hours of backlog. Great stuff!

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

Threading Questions in Job Interviews (2/2)

In our previous newsletter, we showed some questions that interviewers ask potential employees. We did a live webinar on Heinz's Happy Hour where we went through each of the questions in turn. The recording is available in our paid subscription. I will do my best to summarize our conclusions in this newsletter.

Question 1: Thread Signalling

What is wrong with this class?

import java.util.*;

public class Threading01<E> {
  private final LinkedList<E> elements = new LinkedList<>();

  public boolean offer(E e) throws InterruptedException {
    elements.add(e);
    notify();
    return true;
  }

  public E take() throws InterruptedException {
    if (elements.isEmpty()) wait();
    return elements.removeFirst();
  }
}

Answer: Here are some of the things you could point out:

1. Since offer() is not synchronized, notify() will throw an IllegalMonitorStateException.
2. Similarly, since take() is not synchronized, wait() will throw an IllegalMonitorStateException.
3. In take(), we should use while and not if to check the precondition.
4. It is possible that a notify and an interrupt are sent to the same waiting thread. We thus need to catch InterruptedException in take() and call notify() again in case this happens. This problem would go away if we used notifyAll().
5. We should synchronize on a private monitor if we use notify() instead of notifyAll(), otherwise alien code could synchronize on our instance and "steal" the notify.
6. offer() unnecessarily declares InterruptedException.

As Cay Horstmann pointed out during the webinar, perhaps the correct answer would be to throw away this code and use LinkedBlockingQueue? Whilst a great answer, not necessarily what the interviewer had in mind.

I would probably only offer the first three points in an interview. Points 4 and 5 are subtle and the interviewer might mark us negatively. Point 6 is so obvious that we might want to turn that into a question - "Why are we throwing InterruptedException in offer()?"

Question 2: Static Locks

What is wrong with this code? Is there a way to fix it or a better approach?

public class Threading02 {
  private static final Object LOCK = new Object();
  private static Object myObj = null;

  public static Object retrieve() {
    if (myObj == null) {
      synchronized (LOCK) {
        myObj = create();
      }
    }
    return myObj;
  }

  private static Object create() {
    return new Object();
  }
}

Answer: This is the dreaded double-checked locking idiom. However, it is not correctly implemented. First off, the field myObj is not marked as volatile, meaning that retrieve() could return all sorts of confusing results, such as half-initialized objects and even null. Secondly, a better approach could be Effective Java's lazy initialization holder class idiom:

public class Threading02Holder {
  private static class Holder {
    private static final Object myObj = create();
  }

  public static Object retrieve() {
    return Holder.myObj;
  }

  private static Object create() {
    return new Object();
  }
}

No more synchronized and correct initialization is guaranteed by the Java Virtual Machine Specification.

Question 3: Fastest Way to Signal

Here is a real interview question, forwarded by one of my readers: Let T1 be the main thread, and T2 be a thread running a never ending CPU computation inside a "while(true)" loop. Assuming that both threads run code which you own and can modify, how would you send a signal from T1 to T2 to stop working and exit?

Answer: We can solve this problem by making T2 periodically check the value of a shared volatile field. We could also use the interrupted status of T2 as a flag to stop and return with a CancellationException. T2.stop() is not the correct answer. More advanced would be to use VarHandle and getAcquire() and setRelease() if we are guaranteed that there will always only be one thread writing the state.

Question 4: Possible Values of Shared int

Another real interview question: Assume C is a shared int (say, defined as volatile int), and assume that T1..T100 are 100 threads, each trying to increase C 1000 times (in a naive get-modify-write fashion). What will be the range of possible values of C by the time all threads terminate?

Answer: In theory the range is between 1000 and 100_000. Unless we have a machine that can spin up 100 threads at a time, it is unlikely to be 1000. Since the loop is only up to 1000, there is a good chance that the value will be fairly large, even equal to 100_000. The exact number will be strongly affected by the hardware we run on.

Question 5: Debounce in Java

This one is a lot harder to get right. There are a zillion ways to code it. I think the point of the question is to see how someone would answer the question. Are they going to copy and paste from an online solution, claiming it as their own? Will they use existing concurrency constructs to maximize code reuse?

Sometimes we want to invoke a method call only once per time interval. Let's start with a simple interface Callback:

public interface Callback<T> {
  void call(T t);
}

The Debouncer would extend that interface, but add the functionality to run the call only once per time interval. Thus if someone calls it 1000 times in a row, we still only call it once. The Debouncer follows the protection proxy design pattern, both in intent and in structure. Since it may start a background thread to manage the actual call, we give it a shutdown() method.

public interface Debouncer<T> extends Callback<T> {
  void shutdown();
}

Here is a test that we should pass with our Debouncer implementation:

import org.junit.*;

import java.util.concurrent.atomic.*;

import static org.junit.Assert.*;

public class DebouncerTest {
  private Debouncer<Runnable> makeDebouncer() {
    // Create Debouncer that only runs once a second
    throw new UnsupportedOperationException("TODO");
  }

  @Test
  public void testDebouncer() throws InterruptedException {
    Debouncer<Runnable> db = makeDebouncer();
    AtomicInteger rx_count = new AtomicInteger();
    AtomicInteger ry_count = new AtomicInteger();

    Runnable rx = () -> {
      System.out.println("x");
      rx_count.incrementAndGet();
    };
    Runnable ry = () -> {
      System.out.println("y");
      ry_count.incrementAndGet();
    };

    for (int i = 0; i < 8; i++) {
      Thread.sleep(50);
      db.call(rx);
      Thread.sleep(50);
      db.call(ry);
    }
    Thread.sleep(200); // expecting x and y
    assertEquals(1, rx_count.get());
    assertEquals(1, ry_count.get());

    for (int i = 0; i < 10000; i++) {
      db.call(rx);
    }
    Thread.sleep(2_400); // expecting only x
    assertEquals(2, rx_count.get());
    assertEquals(1, ry_count.get());

    db.call(ry);
    Thread.sleep(1_100); // expecting only y
    assertEquals(2, rx_count.get());
    assertEquals(2, ry_count.get());
    db.shutdown();
  }

  @Test
  public void testManyRunnables() throws InterruptedException {
    Debouncer<Runnable> db = makeDebouncer();
    LongAdder counter = new LongAdder();
    for (int i = 0; i < 100; i++) {
      int finalI = i;
      db.call(() -> {
        System.out.println("i=" + finalI);
        counter.increment();
      });
    }
    Thread.sleep(2500);
    assertEquals(100, counter.longValue());
    db.shutdown();
  }
}

Answer: When I showed my answer in the webinar, someone pointed out a bug in my solution. I had assumed that two different objects would also have different identity hash code. I knew this wasn't the case and have mentioned it in Identity Crisis. The JVM parameters -XX:+UnlockExperimentalVMOptions -XX:hashCode=2 make all objects have the same identity hash code of 1. In my solution I rely on the ConcurrentSkipListSet to throw away duplicates of the objects that we are passing into our Debouncer and to then call them periodically using a ScheduledExecutorService. Here is my solution:

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public class DebouncerHeinz<T> implements Debouncer<T> {
  private final Callback<T> callback;
  private final ScheduledExecutorService timer =
      Executors.newSingleThreadScheduledExecutor();
  private final Set<Holder<T>> jobs = new ConcurrentSkipListSet<>();

  public DebouncerHeinz(Callback<T> c, int time, TimeUnit unit) {
    this.callback = c;
    timer.scheduleAtFixedRate(this::processAll, time, time, unit);
  }

  private void processAll() {
    Set<Holder<T>> toNotify = new ConcurrentSkipListSet<>();
    for (Iterator<Holder<T>> it = jobs.iterator(); it.hasNext(); ) {
      Holder<T> holder = it.next();
      it.remove();
      toNotify.add(holder);
    }
    toNotify.forEach(h -> callback.call(h.t));
  }

  public void call(T t) {
    if (timer.isShutdown())
      throw new IllegalStateException("Debouncer shut down");
    Holder<T> holder = new Holder<>(t);
    jobs.add(holder);
  }

  public void shutdown() {
    timer.shutdown();
  }

  private static class Holder<T> implements Comparable<Holder<T>> {
    private final T t;
    private static final AtomicLong nextOrder = new AtomicLong();
    private final long order = nextOrder.incrementAndGet();

    public Holder(T t) {
      this.t = t;
    }

    public int compareTo(Holder<T> o) {
      if (t == o.t) return 0;

      int tid = System.identityHashCode(t);
      int oid = System.identityHashCode(o.t);
      // identity hashcodes can have duplicates
      if (tid == oid) return Long.compare(order, o.order);
      return Integer.compare(tid, oid);
    }
  }
}

Don't use my solution when you answer the interview question. It most likely contains a bunch of bugs. The interviewer is more interested in how you get to the answer than your exact code.

Question 6: Deadlocks

What is the minimum number of threads that you need for a Java thread deadlock?

Answer: The consensus in our webinar was that you typically needed two threads for a lock-ordering deadlock, but that there were many cases where a deadlock was possible with a single thread. For example, if a thread holds a read lock and tries to upgrade that to a write lock, it will deadlock, all by itself.

Question 7: ConcurrentHashMap

Here is a nasty one that another reader sent me: Explain the internal synchronization details of ConcurrentHashMap.

Answer: The ConcurrentHashMap typically does not block on reads, but may block on writes. The exact mechanism has changed in Java 8. In previous versions, the table was split into different segments from the outset. The exact number of segments was determined by the concurrencyLevel constructor parameter. Since Java 8 this is managed more dynamically. Another factor is that from Java 5 to 7, ConcurrentHashMap used a ReentrantLock. This was replaced in Java 8 with plain synchronized. Your interviewer might not know this and if he says that is wrong, please ask him to check the source code :-)

Question 8: Check Then Act

A question that was recently asked during a real job interview: Explain 5 different check then act scenarios you have implemented in your projects.

Answer: There is no correct answer to this question.

Question 9: Possible Outcomes

This question is quite hard and the Dr who sent it to me told me he only uses it when people claim that they know threading well. It's like when someone say on their CV that they like chess (after all, that's the smart person's game), we haul out the chess board and call Yuri to play a game with them.

public class Threading09 {
  static class Foo {
    public int x, y;
    public boolean f;

    public void bar() {
      x = 5;
      y = 10;
      f = true;
    }
  }

  public static void main(String... args) throws InterruptedException {
    Foo f = new Foo();

    Thread t1 = new Thread(f::bar);
    Thread t2 = new Thread(() -> {
      while (!f.f) { }
      assert (f.x == 5);
    });

    t2.start();
    Thread.sleep(10_000L);

    t1.start();

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

In the interview, my Dr friend sometimes offers the following possibilities to choose from:

1. runs and exits with return code of zero;
2. assertion error;
3. runs forever, always
4. runs forever, sometimes
5. something else

Answer: Since we do not have any synchronization (including, but not limited to: synchronized, ReentrantLock, StampedLock, VarHandle, volatile, ad nauseum), all five of the possibilities could happen. It all depends on what hardware we run and what our JVM parameters are.

Question 10: wait/notify/join/yield

I like this question: Why do wait() and notify() methods have to be in Object class whereas join() and yield() have to be in the Thread class?

Answer: wait() and notify() are closely coupled to synchronized monitors in Java. When we call wait(), the currently held monitor is unlocked and the current thread parked. A notify() wakes up a thread that is currently parked and waiting on the same monitor. join() waits for a thread to die. yield() typically causes a voluntary context switch on the current thread, but it might also do nothing at all if it is turned off with the "-XX:+DontYieldALot" JVM parameter. Yes, that's a real JVM flag. A question to ask back to the interviewer: What should happen when you call these methods on value types?

Question 11: Deadlock Sample

What is a deadlock? Please provide the code sample for deadlock creation.

Answer: I would probably show the simplest possible example of a deadlock, for example:

public class DeadlockExample extends Thread {
  private final Object monitor1, monitor2;

  public DeadlockExample(Object monitor1, Object monitor2) {
    this.monitor1 = monitor1;
    this.monitor2 = monitor2;
  }

  public void run() {
    while (true) {
      synchronized (monitor1) {
        synchronized (monitor2) {
          System.out.println("No deadlock yet ...");
        }
      }
    }
  }

  public static void main(String... args) {
    var a = new Object();
    var b = new Object();
    new DeadlockExample(a, b).start();
    new DeadlockExample(b, a).start();
  }
}

The var construct was added in Java 10 and is a shortcut for declaring local variables.

Question 12: Deadlock Detection

How do you detect a deadlock?

Answer: We can either generate a thread dump with jstack or otherwise search with the ThreadMXBean, like so:

import java.lang.management.*;

public class DeadlockExampleWithCheck extends Thread {
  private final Object monitor1, monitor2;

  public DeadlockExampleWithCheck(Object monitor1,
                                  Object monitor2) {
    this.monitor1 = monitor1;
    this.monitor2 = monitor2;
  }

  public void run() {
    while (true) {
      synchronized (monitor1) {
        synchronized (monitor2) {
          System.out.println("No deadlock yet ...");
        }
      }
    }
  }

  public static void main(String... args) {
    var a = new Object();
    var b = new Object();
    new DeadlockExampleWithCheck(a, b).start();
    new DeadlockExampleWithCheck(b, a).start();
    ThreadMXBean tb = ManagementFactory.getThreadMXBean();
    while(true) {
      long[] deadlock = tb.findDeadlockedThreads();
      if (deadlock != null && deadlock.length > 0) {
        System.out.println("Deadlock detected, exiting");
        System.exit(1);
      }
    }
  }
}

Note that the findDeadlockedThreads() method is costly to call, so calling it continuously is probably not a good idea.

Question 13: Deadlock Avoidance

How can you prevent a deadlock?

Answer: In our DeadlockExample, we could order the locks, so that we always lock in the same order. We might want to use the System.identityHashCode(), keeping in mind that this is not necessarily unique. For example:

import java.lang.management.*;

public class DeadlockExampleOrdering extends Thread {
  private final Object monitor1, monitor2;
  private static final Object TIE_MONITOR = new Object();

  public DeadlockExampleOrdering(Object monitor1,
                                 Object monitor2) {
    this.monitor1 = monitor1;
    this.monitor2 = monitor2;
  }

  public void run() {
    Runnable job = () -> System.out.println("No deadlock ...");
    int id1 = System.identityHashCode(monitor1);
    int id2 = System.identityHashCode(monitor2);
    while (true) {
      if (id1 < id2) {
        synchronized (monitor1) {
          synchronized (monitor2) {
            execute(job);
          }
        }
      } else if (id1 > id2) {
        synchronized (monitor2) {
          synchronized (monitor1) {
            execute(job);
          }
        }
      } else {
        synchronized (TIE_MONITOR) {
          synchronized (monitor1) {
            synchronized (monitor2) {
              execute(job);
            }
          }
        }
      }
    }
  }

  private void execute(Runnable job) {
    assert Thread.holdsLock(monitor1) : "monitor1 not locked";
    assert Thread.holdsLock(monitor2) : "monitor2 not locked";
    job.run();
  }

  public static void main(String... args) {
    var a = new Object();
    var b = new Object();
    new DeadlockExampleOrdering(a, b).start();
    new DeadlockExampleOrdering(b, a).start();
    ThreadMXBean tb = ManagementFactory.getThreadMXBean();
    while (true) {
      long[] deadlock = tb.findDeadlockedThreads();
      if (deadlock != null && deadlock.length > 0) {
        System.out.println("Deadlock detected, exiting");
        System.exit(1);
      }
    }
  }
}

If we remove the TIE_MONITOR and run with -XX:hashCode=2, then the code will still deadlock. If you really want to blow away your interviewer, talk about how calling identityHashCode affects your chances with biased locking. For more details, have a look at Identity Crisis.

Question 14: Plain Java Thread vs Managed Application Server Thread

What is the difference between executing code in "plain" Java thread and application server container managed thread?

Answer: A thread is a thread, regardless of how it is created and what it does. There are background threads called daemon threads, but they are still just ordinary threads. In the current version of Java threads are backed by native threads, but that will change with Project Loom and Fibers.

Kind regards from Crete

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive