194trySynchronize

Author: Dr. Heinz M. KabutzDate: 2011-08-27Java Version: 6Category: Concurrency

Abstract: Did you know that it possible to "try" to synchronize a monitor? In this newsletter we demonstrate how this can be used to avoid deadlocks and to keep the wine coming.

Welcome to the 194th issue of The Java(tm) Specialists' Newsletter. This coming Monday we are running our first Java Specialists Symposium here on Crete. 40 Java experts and enthusiasts from all around the world from as far afield as Canada are honouring our little island with their presence. We will spend 4 intense days discussing Java with the theme "Making Java Fun Again". Not just will we talk Java, but we will walk the mountains and swim the seas. We will try to record as much as possible of the discussions, but nothing will replace coming down to Crete yourself.

This open spaces conference was first named the Java Specialist Roundup. But since we are in Greece, John Kostaras suggested "Symposium" would be a better name. As in previous newsletters, a quick Greek lesson for the Philistines amongst us: The word symposium is made up out of two words. "Sym" comes from "syn" and means "together", as you will find in "symphony", "symbiosis", etc. The word "posium" comes from "poto", meaning drink. Thus the literal and historical meaning is a drinking party for philosophers.

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

trySynchronize

Crete produces so much food, that it is impossible to eat and drink it all. Since the transport system does not work well, we often have to simply throw our produce away. For example, we planted water melons and even after harvesting several tons, still had about 50 that we kept at home. Water melon becomes delicious juice in a blender, pips and all. You can even throw a bit of the rind in. Even en route to our conference hotel, you will drive past fields with hundreds of abandoned water melons.

Another excess is the village wine. It is an interesting drink that takes some getting used to. It is more like dry sherry than red wine. For the South Africans amongst our readership, think Sedgwick's Old Brown. The locals have so much that they simply cannot drink it all, so we are given an abundant supply, far more than would be good for me. I have about 30 liters that need to be finished next week at the Symposium. My friends are harvesting in September and I will probably be inundated with last year's stock!

This brought me to this idea. Instead of the classical "eating philosophers" we will have "drinking philosophers". And instead of forks, we have two cups, because around this table you have to drink with both hands.

The lock for our "symposium" is the class Krasi, Greek for "wine".

public class Krasi { }

Our first "Thinker" has a deadlock, because if everyone picks up the right cup at the same time, then it forms a ring and they cannot pick up the left cup. Thus they end up in a state of limbo and the symposium deadlocks.

import java.util.concurrent.*;

public class Thinker implements Callable<String> {
  private final int id;
  private final Krasi left, right;

  public Thinker(int id, Krasi left, Krasi right) {
    this.id = id;
    this.left = left;
    this.right = right;
  }

  public String call() throws Exception {
    for (int i = 0; i < 1000; i++) {
      drink();
      think();
    }
    return "Java is fun";
  }

  public void drink() {
    synchronized (left) {
      synchronized (right) {
        System.out.printf("(%d) Drinking%n", id);
      }
    }
  }

  public void think() {
    System.out.printf("(%d) Thinking%n", id);
  }
}

It is fairly easy to prove that the system can deadlock. We simply construct a bunch of Thinkers and make their locks form a circle. In order to not cause an early escape of "this" by starting threads in the constructor, we only start the symposium once it has been constructed.

import java.util.concurrent.*;

public class Symposium {
  private final Krasi[] cups;
  private final Thinker[] thinkers;

  public Symposium(int delegates) {
    cups = new Krasi[delegates];
    thinkers = new Thinker[delegates];
    for (int i = 0; i < cups.length; i++) {
      cups[i] = new Krasi();
    }
    for (int i = 0; i < delegates; i++) {
      Krasi left = cups[i];
      Krasi right = cups[(i + 1) % delegates];
      thinkers[i] = new Thinker(i, left, right);
    }
  }

  public void run() throws InterruptedException {
    // do this after we created the symposium, so that we do not
    // let the reference to the Symposium escape.
    ExecutorService exec = Executors.newCachedThreadPool();
    CompletionService<String> results =
        new ExecutorCompletionService<String>(exec);
    for (Thinker thinker : thinkers) {
      results.submit(thinker);
    }
    System.out.println("Waiting for results");
    for (int i = 0; i < thinkers.length; i++) {
      try {
        System.out.println(results.take().get());
      } catch (ExecutionException e) {
        e.getCause().printStackTrace();
      }
    }
    exec.shutdown();
  }
}

We can create a Symposium with 5 thinkers and very quickly we will see that there is a deadlock.

public class JavaSpecialistsSymposium2011Crete {
  public static void main(String[] args)
      throws InterruptedException {
    Symposium symposium = new Symposium(5);
    symposium.run();
  }
}

Here is some output we might see:

    (0) Drinking
    (0) Thinking
    Waiting for results
    (2) Drinking
    (2) Thinking
    (2) Drinking
    (2) Thinking

The jstack program also verifies that we have a deadlock:

Found one Java-level deadlock:
=============================
"pool-1-thread-5":
  waiting to lock monitor 10086e908 (object 7f319c300, a Krasi),
  which is held by "pool-1-thread-1"
"pool-1-thread-1":
  waiting to lock monitor 10080d360 (object 7f319c310, a Krasi),
  which is held by "pool-1-thread-2"
"pool-1-thread-2":
  waiting to lock monitor 10080d2b8 (object 7f319c320, a Krasi),
  which is held by "pool-1-thread-3"
"pool-1-thread-3":
  waiting to lock monitor 10086d408 (object 7f319c330, a Krasi),
  which is held by "pool-1-thread-4"
"pool-1-thread-4":
  waiting to lock monitor 10086d360 (object 7f319c340, a Krasi),
  which is held by "pool-1-thread-5"

There are several ways of avoiding deadlocks. One is to do lock ordering, where we guarantee to always synchronize the same lock first. The last thinker would thus first lock right and then left, whereas all the others would be the other way round. Another approach is to use Java 5 locks which have a tryLock() method. Effectively you could do something like:

while (true) {
  if (Thread.interrupted()) throw new InterruptedException();
  if (left.tryLock()) {
    try {
      if (right.tryLock()) {
        try {
          System.out.printf("(%d) Drinking%n", id);
          return;
        } finally {
          right.unlock();
        }
      }
    } finally {
      left.unlock();
    }
  }
  if (timeoutExceeded()) throw new TimeoutException();
  sleepRandomTime();
}

You have probably seen code like that before. However, did you know that it is also possible to try to synchronize?

In a recent email, one of my youngest readers, 17 year old Mr S.Perlov from the Ukraine, suggested that I tell you about the class sun.misc.Unsafe. Up to now I have avoided writing about it, as it is a class that should be avoided. Here are two reasons: #1 it is "unsafe" and lets us do all the nasty things that we had in C, such as pointer arithmetic or modifying memory directly. #2 it is a sun.misc.* class. You do not know when that might be renamed to oracle.misc.Unsafe or whether you will even run your program on a Sun JVM. By binding yourself to a specific implementation of the JVM, you are limiting the application of your code.

Two reasons to not use Unsafe. I have personally never used Unsafe in production code. Some experts do use it to write directly to memory. Dangerous stuff!

Unsafe allows us to manually lock and unlock monitors, with the monitorEnter() and monitorExit() methods. We can also "try to lock" with the tryMonitorEnter() method. Here is a wrapper class that we can use to do the dirty work for us:

import sun.misc.*;

import java.lang.reflect.*;

public class MonitorUtils {
  private static Unsafe unsafe = getUnsafe();

  public static boolean trySynchronize(Object monitor) {
    return unsafe.tryMonitorEnter(monitor);
  }

  public static void unsynchronize(Object monitor) {
    unsafe.monitorExit(monitor);
  }

  private static Unsafe getUnsafe() {
    try {
      for (Field field : Unsafe.class.getDeclaredFields()) {
        if (Modifier.isStatic(field.getModifiers())) {
          if (field.getType() == Unsafe.class) {
            field.setAccessible(true);
            return (Unsafe) field.get(null);
          }
        }
      }
      throw new IllegalStateException("Unsafe field not found");
    } catch (Exception e) {
      throw new IllegalStateException(
          "Could not initialize unsafe", e);
    }
  }
}

We can now change our "drink()" method to

while (true) {
  if (Thread.interrupted()) throw new InterruptedException();
  if (MonitorUtils.trySynchronize(left)) {
    try {
      if (MonitorUtils.trySynchronize(right)) {
        try {
          System.out.printf("(%d) Drinking%n", id);
          return;
        } finally {
          MonitorUtils.unsynchronize(right);
        }
      }
    } finally {
      MonitorUtils.unsynchronize(left);
    }
  }
  if (timeoutExceeded()) throw new TimeoutException();
  sleepRandomTime();
}

Why use this when we have Lock.tryLock()? You might want to change code that is already implemented with monitor locking. Instead of modifying everything to use Lock, you could get the same functionality with this trySynchronize().

Even better is to avoid locking yourself by using thread-safe classes. Sadly this is not always an option.

Kind regards from Crete

Heinz

We now have a Facebook page for the Java Specialists. If you've enjoyed reading this newsletter, please take a moment to "like" our group.

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