188Interlocker - Interleaving Threads

Author: Dr. Heinz M. KabutzDate: 2010-10-31Java Version: 6Category: Concurrency

Abstract: In this newsletter, we explore a question of how to call a method interleaved from two threads. We show the merits of lock-free busy wait, versus explicit locking. We also discuss an "unbreakable hard spin" that can cause the JVM to hang up.

Welcome to the 188th issue of The Java(tm) Specialists' Newsletter, sent to you from the K Trade Fair, an International Trade Fair for Plastics and Rubber. About a quarter of a million people have descended on Dusseldorf to see what is going on in the plastics industry. Since I am a director of a drinking straw factory in South Africa, it seemed like a good place to meet up with our general manager. We have seen a huge number of very interesting products. One of the most interesting was a three dimensional printer. You enter a model in the computer and it constructs this by applying layer after layer of molten plastic. Eventually you have a little plastic shape that accurately represents the model on the computer. One of the things they have not figured out yet is anti-aliasing, so the models have steps in between the levels. Maybe one day they will even solve that problem. Also, the current 3D printers can only apply one colour per layer of plastic.

On Monday I am off to New York, where I will be speaking at the NYC Java Meetup on November 4th 2010.

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

Interlocker - Interleaving Threads

A few months ago, one of my subscribers, Mohammed Irfanulla S., sent me an interesting question. How can you alternately call a method from two threads? Imagine you have two threads, first thread 1 calls a method, then thread 2, then thread 1 again, and so on. One thread should never call the method twice in a row.

Mohammed sent me several different solutions to this puzzle. My first step was to make our testing a bit more robust, so that we could catch any mistakes early. I also spent a while renaming the classes, to make our intentions clearer. Lastly, I marked up the classes with the new jpatterns annotations to indicate where we were using which design patterns. The jpatterns.org annotations are a new project started by The Java Specialist Club. You are welcome to participate in the project if you would like to.

Disclaimer: I cannot think of a practical application of where such an "interlocker" would be useful. However, some of the discoveries might be useful in highly communicative systems. such as the lock-free approach to solving the problem. Only use if you know exactly what you are doing :-)

As a first class, we define Interlocker, which uses the template method to start threads that will call the Runnables. The execute() method will block until all the threads have finished. The Runnable objects returned by the getRunnable() method should guarantee that the InterlockTask is called interleaved by the threads. They do not have to guarantee which thread starts, but the total call count must be correct.

import org.jpatterns.gof.*;

/**
 * This special executor guarantees that the call() method of the
 * task parameter is invoked in turns by two threads.  There is
 * probably no practical application for this class, except as a
 * learning experience.
 */
@TemplateMethodPattern.AbstractClass
public abstract class Interlocker {
  @TemplateMethodPattern.PrimitiveOperation
  protected abstract Runnable[] getRunnables(InterlockTask task);

  @TemplateMethodPattern.TemplateMethod
  public final <T> T execute(InterlockTask<T> task)
      throws InterruptedException {
    Runnable[] jobs = getRunnables(task);
    Thread[] threads = new Thread[jobs.length];
    for (int i = 0; i < threads.length; i++) {
      threads[i] = new Thread(jobs[i]);
      threads[i].start();
    }
    for (Thread thread : threads) {
      thread.join();
    }
    return task.get();
  }
}

Before we look at some possible solutions, let us view the InterlockTask interface. It is self explanatory.

import org.jpatterns.gof.*;

@StrategyPattern.Strategy
public interface InterlockTask<T> {
  boolean isDone();

  /**
   * The call() method is called interleaved by the the threads
   * in a round-robin fashion.
   */
  void call();

  /**
   * Returns the result after all the call()'s have completed.
   */
  T get();

  void reset();
}

In the first test case, we want to simply increment a value. Since we are accessing the field from multiple threads, we need to declare it as volatile, but since only one thread is invoking the call() method, we do not need to synchronize. Since this test does very little, we can also use it to measure the overhead of our thread coordination mechanism.

import org.jpatterns.gof.*;

@StrategyPattern.ConcreteStrategy
public class EmptyInterlockTask implements
    InterlockTask<Integer> {
  public final int upto;
  private volatile int count;

  public EmptyInterlockTask(int upto) {
    this.upto = upto;
  }

  public boolean isDone() {
    return count >= upto;
  }

  public void call() {
    count++;
  }

  public Integer get() {
    return count;
  }

  public void reset() {
    count = 0;
  }
}

The next test verifies that the call() method was invoked by alternating threads. We do this by inserting the current call number into a LinkedHashMap, with the number as key and the thread as a value. Afterwards, when we call get(), we verify that the result is correct. This is returned in the VerifyResult object.

import org.jpatterns.gof.*;

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

@StrategyPattern.ConcreteStrategy
public class InterleavedNumberTestingStrategy implements
    InterlockTask<VerifyResult> {
  public final int upto;
  private final Map<Integer, Thread> numbers =
      new LinkedHashMap<Integer, Thread>();
  private final AtomicInteger count = new AtomicInteger(0);

  public InterleavedNumberTestingStrategy(int upto) {
    this.upto = upto;
  }

  public boolean isDone() {
    return count.get() >= upto;
  }

  public void call() {
    int next = count.getAndIncrement();
    numbers.put(next, Thread.currentThread());
  }

  public VerifyResult get() {
    if (numbers.size() < upto) {
      return new VerifyResult("Only " + numbers.size() +
          " numbers were entered");
    }
    Object previous = null;
    int i = 0;
    for (Map.Entry<Integer, Thread> entry : numbers.entrySet()) {
      if (i != entry.getKey()) {
        return new VerifyResult("numbers out of sequence");
      }
      if (entry.getValue() == previous) {
        return new VerifyResult("Did not alternate threads");
      }
      previous = entry.getValue();
      i++;
    }
    Set<Thread> values = new HashSet<Thread>(numbers.values());
    if (values.size() != 2) {
      return new VerifyResult(
          "More than two threads were inserting values");
    }
    return new VerifyResult();
  }

  public void reset() {
    numbers.clear();
    count.set(0);
  }
}

public class VerifyResult {
  private final boolean success;
  private final String failReason;

  private VerifyResult(boolean success, String failReason) {
    this.success = success;
    this.failReason = failReason;
  }

  public VerifyResult(String failReason) {
    this(false, failReason);
  }

  public VerifyResult() {
    this(true, null);
  }

  public boolean isSuccess() {
    return success;
  }

  public String getFailReason() {
    return failReason;
  }

  public String toString() {
    return success ? "Success" : "Failure - " + failReason;
  }
}

Another task could print the threads, for example:

// *snip*
  public boolean isDone() {
    return row.get() >= upto;
  }

  public void call() {
    System.out.println(Thread.currentThread().getName());
    row.incrementAndGet();
  }

Interlocker Solutions

The easiest solution is to use semaphores. We start with two semaphores. The first has 1 barrier, the second zero. From thread 1, we acquire semaphore 1, do the call(), then release semaphore 2. From thread 2, we acquire semaphore 2, do the call(), then release semaphore 1. The reason this works is that you can release a semaphore from a thread that has not acquired it. This is quite different to locks, where only the thread that acquired the lock can release it.

import java.util.concurrent.*;

public class SemaphoreInterlocker extends Interlocker {
  private static class Job implements Runnable {
    private final InterlockTask task;
    private final Semaphore first;
    private final Semaphore second;

    public Job(InterlockTask task,
               Semaphore first, Semaphore second) {
      this.task = task;
      this.first = first;
      this.second = second;
    }

    public void run() {
      while (!task.isDone()) {
        first.acquireUninterruptibly();
        if (task.isDone()) return;
        task.call();
        second.release();
      }
    }
  }

  protected Runnable[] getRunnables(InterlockTask task) {
    Semaphore even = new Semaphore(1);
    Semaphore odd = new Semaphore(0);
    return new Runnable[]{
        new Job(task, even, odd),
        new Job(task, odd, even)
    };
  }
}    

When running this code, I noticed that it was rather slow. For example, to increment an int one million times took 4 seconds on my machine, of which most was context switching:

InterlockTask task = new EmptyInterlockTask(1000 * 1000);
Interlocker generator = new SemaphoreInterlocker();
long time = System.currentTimeMillis();
generator.execute(task);
time = System.currentTimeMillis() - time;
System.out.println(time);

The other solutions that we developed, using wait-notify and Java 5 Condition, were similar in performance characteristic. We will leave those Interlockers as an exercise for the reader :-) If you want to attempt them, remember the effects that spurious wakeups can have on your Object.wait() and Condition.await().

Lock Free Interlocker

I wanted to write a fast Interlocker implementation, ideally not locking at all and using a volatile field as a communication mechanism. Here is what I did:

public class LockFreeInterlocker extends Interlocker {
  private volatile boolean evenHasNextTurn = true;

  private class Job implements Runnable {
    private final InterlockTask task;
    private final boolean even;

    private Job(InterlockTask task, boolean even) {
      this.task = task;
      this.even = even;
    }

    public void run() {
      while (!task.isDone()) {
        while (even ^ evenHasNextTurn);
        if (task.isDone()) {
          return;
        }
        task.call();
        evenHasNextTurn = !even;
      }
    }
  }

  protected Runnable[] getRunnables(InterlockTask task) {
    return new Runnable[]{
        new Job(task, true), new Job(task, false)
    };
  }
}

This approach to thread communication is faster when the call() method completes quickly. Since we are doing a busy wait, we will burn up CPU cycles in the waiting thread. For a long call() method, one of your CPUs would be running at 100% polling a field value. This is not a good idea unless you have lots of spare CPUs that you do not know what to do with. However, if you want to just do a very task inside call(), then this approah is substantially faster.

Where this might be handy is if you have a lot of thread communication that you need to speed up. Some financial applications might find this information useful.

Caveat: Livelock (or "Unbreakable Hard Spin")

If we modify the LockFreeInterlocker slightly to use a boolean XOR instead of bitwise, then we can cause the JVM to hang up. I called this a livelock, for want of a better term. When I demonstrated this to Doug Lea, he named it an "unbreakable hard spin". Cliff Click also had a look at it and thinks it might be because the server hotspot compiler is not inserting a safepoint at the right place. This problem occurs in OpenJDK / Sun JDK server HotSpot compilers running on at least 2 physical cores and from JDK 1.6.0_14 onwards. Code available on request.

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