Computing Thoughts Bruce Eckel's Programming Blog

Constructors Are Not Thread-Safe

When you imagine the construction process, it can be easy to think that it’s thread-safe. After all, no one can even see the new object before it finishes initialization, so how could there be contention over that object? Indeed, the Java Language specification (JLS) confidently states:

“There is no practical need for a constructor to be synchronized, because it would lock the object under construction, which is normally not made available to other threads until all constructors for the object have completed their work.”

Unfortunately, object construction is as vulnerable to shared-memory concurrency problems as anything else. The mechanisms can be more subtle, however.

Consider the automatic creation of a unique identifier for each object using a static field. To test different implementations, we’ll start with an interface:

// HasID.java

public interface HasID {
  int getID();
}

Then implement that interface in an obvious way:

// StaticIDField.java

public class StaticIDField implements HasID {
  private static int counter = 0;
  private int id = counter++;
  public int getID() { return id; }
}

This is about as simple and innocuous a class as you can imagine. It doesn’t even have an explicit constructor to cause problems. To see what happens when we make multiple concurrent tasks that create these objects, here’s a test harness:

// IDChecker.java
import java.util.*;
import java.util.function.*;
import java.util.stream.*;
import java.util.concurrent.*;
import com.google.common.collect.Sets;

public class IDChecker {
  public static int SIZE = 100_000;
  static class MakeObjects
  implements Supplier<List<Integer>> {
    private Supplier<HasID> gen;
    public MakeObjects(Supplier<HasID> gen) {
      this.gen = gen;
    }
    @Override
    public List<Integer> get() {
      return
        Stream.generate(gen)
          .limit(SIZE)
          .map(HasID::getID)
          .collect(Collectors.toList());
    }
  }
  public static void test(Supplier<HasID> gen) {
    CompletableFuture<List<Integer>>
      groupA = CompletableFuture
        .supplyAsync(new MakeObjects(gen)),
      groupB = CompletableFuture
        .supplyAsync(new MakeObjects(gen));
    groupA.thenAcceptBoth(groupB, (a, b) -> {
      System.out.println(
        Sets.intersection(
          Sets.newHashSet(a),
          Sets.newHashSet(b)).size());
    }).join();
  }
}

The MakeObjects class is a Supplier with a get() that produces a List<Integer>. This List is generated by extracting the id from each HasID object. The test() method creates two parallel CompletableFutures that run MakeObjects suppliers, then takes the results of each and uses the Guava library Sets.intersection() to find out how many ids are common between the two List<Integer> (Guava is much faster than using retainAll()).

Now we can test the StaticIDField:

// TestStaticIDField.java

public class TestStaticIDField {
  public static void main(String[] args) {
    IDChecker.test(StaticIDField::new);
  }
}
/* Output:
47643
*/

That’s a rather large number of duplicates. Clearly, a plain static int is not safe to use for construction. Let’s make it thread-safe using an AtomicInteger:

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

public class GuardedIDField implements HasID {
  private static AtomicInteger counter =
    new AtomicInteger();
  private int id = counter.getAndAdd(1);
  public int getID() { return id; }
  public static void main(String[] args) {
    IDChecker.test(GuardedIDField::new);
  }
}
/* Output:
0
*/

Constructors have an even more subtle way to share state: through constructor arguments:

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

interface SharedArg {
  int get();
}

class Unsafe implements SharedArg {
  private int i = 0;
  public int get() { return i++; }
}

class Safe implements SharedArg {
  private static AtomicInteger counter =
    new AtomicInteger();
  public int get() {
    return counter.getAndAdd(1);
  }
}

class SharedUser implements HasID {
  private final int id;
  public SharedUser(SharedArg sa) {
    id = sa.get();
  }
  @Override
  public int getID() { return id; }
}

public class SharedConstructorArgument {
  public static void main(String[] args) {
    Unsafe unsafe = new Unsafe();
    IDChecker.test(() -> new SharedUser(unsafe));
    Safe safe = new Safe();
    IDChecker.test(() -> new SharedUser(safe));
  }
}
/* Output:
47747
0
*/

Here, the SharedUser constructors share the same argument. Even though SharedUser is using its argument in a completely innocent and reasonable fashion, the way the constructor is called causes collisions. SharedUser cannot even know it is being used this way, much less control it!

synchronized constructors are not supported by the language, but it’s possible to create your own using a synchronized block. Although the JLS states that “… it would lock the object under construction”, this is not true—the constructor is effectively a static method, so a synchronized constructor would actually lock through the class object. We can reproduce this by creating our own static object and locking on that:

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

class SyncConstructor implements HasID {
  private final int id;
  private static Object constructorLock = new Object();
  public SyncConstructor(SharedArg sa) {
    synchronized(constructorLock) {
      id = sa.get();
    }
  }
  @Override
  public int getID() { return id; }
}

public class SynchronizedConstructor {
  public static void main(String[] args) {
    Unsafe unsafe = new Unsafe();
    IDChecker.test(() -> new SyncConstructor(unsafe));
  }
}
/* Output:
0
*/

The shared use of the Unsafe class is now safe.

An alternate approach is to make the constructors private (thus preventing inheritance) and provide a static Factory Method to produce new objects:

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

class SyncFactory implements HasID {
  private final int id;
  private SyncFactory(SharedArg sa) {
    id = sa.get();
  }
  @Override
  public int getID() { return id; }
  public static synchronized
  SyncFactory factory(SharedArg sa) {
    return new SyncFactory(sa);
  }
}

public class SynchronizedFactory {
  public static void main(String[] args) {
    Unsafe unsafe = new Unsafe();
    IDChecker.test(() ->
      SyncFactory.factory(unsafe));
  }
}
/* Output:
0
*/

By synchronizing the static Factory Method you lock on the class object during construction.

These examples emphasize how insidiously difficult it is to detect and manage shared state in concurrent Java programs. Even if you take the “share nothing” strategy, it’s remarkably easy for accidental sharing to take place.

View or add comments

A Canonical equals() For Java

Even with the help of Java 7’s Objects.equals(), the equals() method is often written in a verbose and messy fashion. This article shows how you can write a succinct equals() in a format that allows easy checking with visual inspection.

When you create a new class, it automatically inherits class Object. If you don’t override equals(), you’ll get Objects equals() method. By default this compares addresses, so only if you are comparing the exact same objects will you get true. The default case is the “most discriminating.”

// DefaultComparison.java

class DefaultComparison {
  private int i, j, k;
  public DefaultComparison(int i, int j, int k) {
    this.i = i;
    this.j = j;
    this.k = k;
  }
  public static void main(String[] args) {
    DefaultComparison
      a = new DefaultComparison(1, 2, 3),
      b = new DefaultComparison(1, 2, 3);
    System.out.println(a == a);
    System.out.println(a == b);
  }
}
/* Output:
true
false
*/

Normally you’ll want to relax this restriction. Typically, if two objects are the same type and have fields with identical values, you’ll consider those objects equal, but there may also be fields that you don’t want to include in the equals() comparison. This is part of the class design process.

A proper equals() must satisfy the following five conditions:

  1. Reflexive: For any x, x.equals(x) should return true.

  2. Symmetric: For any x and y, x.equals(y) should return true if and only if y.equals(x) returns true.

  3. Transitive: For any x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.

  4. Consistent: For any x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the object is modified.

  5. For any non-null x, x.equals(null) should return false.

Here are the tests that satisfy those conditions and determine whether the object you’re comparing yourself to (which we’ll call here the rval) is equal to this object:

  1. If the rval is null, it’s not equal.

  2. If the rval is this (you’re comparing yourself to yourself), the two objects are equal.

  3. If the rval is not the same class or subclass, the two objects are not equal.

  4. If all the above checks pass, then you must decide which fields in the rval are important (and consistent), and compare those.

Java 7 introduced the Objects class to help with this process, which we use to write a better equals().

The following examples compare different versions of the Equality class. To prevent duplicate code we’ll build the examples using the Factory Method. The EqualityFactory interface simply provides a make() method to produce an Equality object, so a different EqualityFactory can produce a different subtype of Equality:

// EqualityFactory.java
import java.util.*;

interface EqualityFactory {
  Equality make(int i, String s, double d);
}

Now we’ll define Equality containing three fields (all of which we consider important during comparison) and an equals() method that fulfills the four checks described above. The constructor displays its type name to ensure we are performing the tests we think we are:

// Equality.java
import java.util.*;

public class Equality {
  protected int i;
  protected String s;
  protected double d;
  public Equality(int i, String s, double d) {
    this.i = i;
    this.s = s;
    this.d = d;
    System.out.println("made 'Equality'");
  }
  @Override
  public boolean equals(Object rval) {
    if(rval == null)
      return false;
    if(rval == this)
      return true;
    if(!(rval instanceof Equality))
      return false;
    Equality other = (Equality)rval;
    if(!Objects.equals(i, other.i))
      return false;
    if(!Objects.equals(s, other.s))
      return false;
    if(!Objects.equals(d, other.d))
      return false;
    return true;
  }
  public void
  test(String descr, String expected, Object rval) {
    System.out.format("-- Testing %s --%n" +
      "%s instanceof Equality: %s%n" +
      "Expected %s, got %s%n",
      descr, descr, rval instanceof Equality,
      expected, equals(rval));
  }
  public static void testAll(EqualityFactory eqf) {
    Equality
      e = eqf.make(1, "Monty", 3.14),
      eq = eqf.make(1, "Monty", 3.14),
      neq = eqf.make(99, "Bob", 1.618);
    e.test("null", "false", null);
    e.test("same object", "true", e);
    e.test("different type", "false", new Integer(99));
    e.test("same values", "true", eq);
    e.test("different values", "false", neq);
  }
  public static void main(String[] args) {
    testAll( (i, s, d) -> new Equality(i, s, d));
  }
}
/* Output:
made 'Equality'
made 'Equality'
made 'Equality'
-- Testing null --
null instanceof Equality: false
Expected false, got false
-- Testing same object --
same object instanceof Equality: true
Expected true, got true
-- Testing different type --
different type instanceof Equality: false
Expected false, got false
-- Testing same values --
same values instanceof Equality: true
Expected true, got true
-- Testing different values --
different values instanceof Equality: true
Expected false, got false
*/

testAll() performs comparisons with all different types of objects we ever expect to encounter. It creates Equality objects using the factory.

In main(), notice the simplicity of the call to testAll(). Because EqualityFactory has a single method, it can be used with a lambda expression as the make() method.

The above equals() method is annoyingly verbose, and it turns out we can simplify it into a canonical form. Observe:

  1. The instanceof check eliminates the need to test for null

  2. The comparison to this is redundant. A correctly-written equals() will work properly with self comparison.

Because && is a short-circuiting comparison, it quits and produces false the first time it encounters a failure. So, by chaining the checks together with &&, we can write equals() much more succinctly:

// SuccinctEquality.java
import java.util.*;

public class SuccinctEquality extends Equality {
  public SuccinctEquality(int i, String s, double d) {
    super(i, s, d);
    System.out.println("made 'SuccinctEquality'");
  }
  @Override
  public boolean equals(Object rval) {
    return rval instanceof SuccinctEquality &&
      Objects.equals(i, ((SuccinctEquality)rval).i) &&
      Objects.equals(s, ((SuccinctEquality)rval).s) &&
      Objects.equals(d, ((SuccinctEquality)rval).d);
  }
  public static void main(String[] args) {
    Equality.testAll( (i, s, d) ->
      new SuccinctEquality(i, s, d));
  }
}
/* Output:
made 'Equality'
made 'SuccinctEquality'
made 'Equality'
made 'SuccinctEquality'
made 'Equality'
made 'SuccinctEquality'
-- Testing null --
null instanceof Equality: false
Expected false, got false
-- Testing same object --
same object instanceof Equality: true
Expected true, got true
-- Testing different type --
different type instanceof Equality: false
Expected false, got false
-- Testing same values --
same values instanceof Equality: true
Expected true, got true
-- Testing different values --
different values instanceof Equality: true
Expected false, got false
*/

For each SuccinctEquality, the base-class constructor is called before the derived-class constructor. The output shows that we still get the correct result. You can tell that short-circuiting happens because both the null test and the “different type” test would otherwise throw exceptions during the casts that occur further down the list of comparisons in equals().

Objects.equals() shines when you compose your new class using another class:

// ComposedEquality.java
import java.util.*;

class Part {
  String ss;
  double dd;
  public Part(String ss, double dd) {
    this.ss = ss;
    this.dd = dd;
  }
  @Override
  public boolean equals(Object rval) {
    return rval instanceof Part &&
      Objects.equals(ss, ((Part)rval).ss) &&
      Objects.equals(dd, ((Part)rval).dd);
  }
}

public class ComposedEquality extends SuccinctEquality {
  Part part;
  public ComposedEquality(int i, String s, double d) {
    super(i, s, d);
    part = new Part(s, d);
    System.out.println("made 'ComposedEquality'");
  }
  @Override
  public boolean equals(Object rval) {
    return rval instanceof ComposedEquality &&
      super.equals(rval) &&
      Objects.equals(part, ((ComposedEquality)rval).part);
  }
  public static void main(String[] args) {
    Equality.testAll( (i, s, d) ->
      new ComposedEquality(i, s, d));
  }
}
/* Output:
made 'Equality'
made 'SuccinctEquality'
made 'ComposedEquality'
made 'Equality'
made 'SuccinctEquality'
made 'ComposedEquality'
made 'Equality'
made 'SuccinctEquality'
made 'ComposedEquality'
-- Testing null --
null instanceof Equality: false
Expected false, got false
-- Testing same object --
same object instanceof Equality: true
Expected true, got true
-- Testing different type --
different type instanceof Equality: false
Expected false, got false
-- Testing same values --
same values instanceof Equality: true
Expected true, got true
-- Testing different values --
different values instanceof Equality: true
Expected false, got false
*/

Notice the call to super.equals()—no need to reinvent it (plus you don’t always have access to all necessary parts of a base class).

Equality Across Subtypes

Inheritance suggests that objects of two different subtypes can be “the same” when they are upcast. Suppose you have a collection of Pet objects. This collection will naturally accept subtypes of Pet: In this example, Dogs and Pigs. Each Pet has a name and a size, as well as a unique internal id number.

We define equals() and hashCode() using the canonical form via the Objects class, but we only define them in the base class Pet, and we do not include the unique id number in either one. From the standpoint of equals(), this means we only care if something is a Pet, not whether it is a specific type of Pet:

// SubtypeEquality.java
import java.util.*;

enum Size { SMALL, MEDIUM, LARGE }

class Pet {
  private static int counter = 0;
  private final int id = counter++;
  private final String name;
  private final Size size;
  public Pet(String name, Size size) {
    this.name = name;
    this.size = size;
  }
  @Override
  public boolean equals(Object rval) {
    return rval instanceof Pet &&
      // Objects.equals(id, ((Pet)rval).id) && // [1]
      Objects.equals(name, ((Pet)rval).name) &&
      Objects.equals(size, ((Pet)rval).size);
  }
  @Override
  public int hashCode() {
    return Objects.hash(name, size);
    // return Objects.hash(name, size, id);  // [2]
  }
  @Override
  public String toString() {
    return String.format("%s[%d]: %s %s %x",
      getClass().getSimpleName(), id,
      name, size, hashCode());
  }
}

class Dog extends Pet {
  public Dog(String name, Size size) {
    super(name, size);
  }
}

class Pig extends Pet {
  public Pig(String name, Size size) {
    super(name, size);
  }
}

public class SubtypeEquality {
  public static void main(String[] args) {
    Set<Pet> pets = new HashSet<>();
    pets.add(new Dog("Ralph", Size.MEDIUM));
    pets.add(new Pig("Ralph", Size.MEDIUM));
    pets.forEach(System.out::println);
  }
}
/* Output:
Dog[0]: Ralph MEDIUM a752aeee
*/

If we are just thinking about types, it does make sense—sometimes—to only consider the classes from the standpoint of their base type, which is the foundation of the Liskov Substitution Principle. This code fits nicely with that principle because the derived types don’t add any extra functionality (methods) that isn’t in the base class. The derived types only differ in behavior, not in interface (which of course is not the general case).

But when we provide two different object types with identical data and place them in a HashSet<Pet>, only one of these objects survives. This emphasizes that equals() is not a perfectly mathematical concept but (at least partially) a mechanical one. hashCode() and equals() must be defined hand-in-hand in order to allow types to work properly in a hashed data structure.

In the example, both the Dog and Pig hash to the same bucket in the HashSet. At this point, the HashSet falls back to equals() to differentiate the objects, but equals() also declares the objects to be the same. The HashSet doesn’t add the Pig because it’s already got an identical object.

We can still make the example work by forcing uniqueness on otherwise identical objects. Here, each Pet already has a unique id so you can either uncomment line [1] in equals() or switch to line [2] in hashCode(). In the canonical form you would do both, to involve all “unchanging” fields in both operations (“unchanging” so that the equals() and hashCode() don’t produce different values between storing and retrieving in a hashed data structure. I put “unchanging” in quotes because you must evaluate whether modification might happen).

Side note: in hashCode(), if you are only working with a single field, use Objects.hashCode() and if you are using multiple fields use Objects.hash().

We can also solve the issue by following the standard form and defining equals() in the subclasses (but still not including the unique id):

// SubtypeEquality2.java
import java.util.*;

class Dog2 extends Pet {
  public Dog2(String name, Size size) {
    super(name, size);
  }
  @Override
  public boolean equals(Object rval) {
    return rval instanceof Dog2 &&
      super.equals(rval);
  }
}

class Pig2 extends Pet {
  public Pig2(String name, Size size) {
    super(name, size);
  }
  @Override
  public boolean equals(Object rval) {
    return rval instanceof Pig2 &&
      super.equals(rval);
  }
}

public class SubtypeEquality2 {
  public static void main(String[] args) {
    Set<Pet> pets = new HashSet<>();
    pets.add(new Dog2("Ralph", Size.MEDIUM));
    pets.add(new Pig2("Ralph", Size.MEDIUM));
    pets.forEach(System.out::println);
  }
}
/* Output:
Dog2[0]: Ralph MEDIUM a752aeee
Pig2[1]: Ralph MEDIUM a752aeee
*/

Notice that the hashCode()s are identical, but because the objects are no longer equals(), both now appear in the HashSet. Also, super.equals() means we don’t need access to the private fields in the base class.

One way to look at this is to say that Java separates substitutability from the definition of equals() and hashCode(). We can still place Dogs and Pigs into a Set<Pet> regardless of how equals() and hashCode() are defined, but the objects won’t behave correctly in hashed data structures unless those methods are defined with hashed structures in mind. Unfortunately, equals() is not only used in conjunction with hashCode(). This complicates things when you try to avoid defining it for specific classes, and it’s why it’s worth following the canonical form. However, this is further complicated because there are times when you don’t need to define either method.

View or add comments

Dining Philosophers in Java 8

Because tasks can become blocked, it’s possible for one task to get stuck waiting for another task, which in turn waits for another task, and so on, until the chain leads back to a task waiting on the first one. You get a continuous loop of tasks waiting on each other, and no one can move. This is called deadlock.^[You can also have livelock when two tasks are able to change their state (they don’t block) but they never make any useful progress.]

If you try running a program and it deadlocks right away, you can immediately track down the bug. The real problem is when your program seems to be working fine but has the hidden potential to deadlock. Here, you might not get any indication that deadlocking is possible, so the flaw is latent in your program until it unexpectedly happens—typically to a customer (in a way almost certainly difficult to reproduce). Thus, preventing deadlock through careful program design is a critical part of developing concurrent systems.

The Dining Philosophers problem, invented by Edsger Dijkstra, is the classic demonstration of deadlock. The basic description specifies five philosophers (the example shown here allows any number). These philosophers spend part of their time thinking and part of their time eating. While they are thinking, they don’t need any shared resources, but they eat using a limited number of utensils. In the original problem description, the utensils are forks, and two forks are required to get spaghetti from a bowl in the middle of the table. A more convincing version uses chopsticks; clearly, each philosopher requires two chopsticks to eat.

A difficulty is introduced: As philosophers, they have very little money, so they can only afford five chopsticks (more generally, the same number of chopsticks as philosophers). These are spaced around the table between them. When a philosopher wants to eat, that philosopher must pick up the chopstick to the left and the one to the right. If the philosopher on either side is using a desired chopstick, our philosopher must wait until the necessary chopsticks become available.

A StickHolder class manages a single Chopstick by keeping it in a BlockingQueue of size one. A BlockingQueue is a collection, designed to be safely used in concurrent programs, that blocks (waits) if you call take() and the queue is empty. Once a new element is placed in the queue, the block is released and that value is returned:

// concurrent/StickHolder.java
import java.util.concurrent.*;

public class StickHolder {
  private static class Chopstick {}
  private Chopstick stick = new Chopstick();
  private BlockingQueue<Chopstick> holder =
    new ArrayBlockingQueue<>(1);
  public StickHolder() { putDown(); }
  public void pickUp() {
    try {
      holder.take(); // Blocks if unavailable
    } catch(InterruptedException e) {
      throw new RuntimeException(e);
    }
  }
  public void putDown() {
    try {
      holder.put(stick);
    } catch(InterruptedException e) {
      throw new RuntimeException(e);
    }
  }
}

For simplicity, the Chopstick is never actually produced by the StickHolder, but kept private within the class. If you call pickUp() and the stick is unavailable, pickUp() blocks until the stick is returned by another Philosopher calling putDown(). Note that all the thread safety in this class is achieved through the use of the BlockingQueue.

Each Philosopher is a task that attempts to pickUp() the chopstick to both its right and left so it can eat, then releases those chopsticks with putDown():

// concurrent/Philosopher.java

public class Philosopher implements Runnable {
  private final int seat;
  private final StickHolder left, right;
  public Philosopher(int seat,
    StickHolder left, StickHolder right) {
    this.seat = seat;
    this.left = left;
    this.right = right;
  }
  @Override
  public String toString() {
    return "P" + seat;
  }
  @Override
  public void run() {
    while(true) {
      // System.out.println("Thinking");   // [1]
      right.pickUp();
      left.pickUp();
      System.out.println(this + " eating");
      right.putDown();
      left.putDown();
    }
  }
}

No two Philosophers can successfully take() the same chopstick at the same time. In addition, if a chopstick has already been taken by one Philosopher, the next Philosopher that tries to take that same chopstick will block, waiting for it to be released.

The result is a seemingly-innocent program that deadlocks. I’ve used arrays here instead of collections only because the resulting syntax is cleaner:

// concurrent/DiningPhilosophers.java
// Deadlock can be hidden in a program
import java.util.*;
import java.util.concurrent.*;
import static java.util.concurrent.TimeUnit.*;

public class DiningPhilosophers {
  private StickHolder[] sticks;
  private Philosopher[] philosophers;
  public DiningPhilosophers(int n) {
    sticks = new StickHolder[n];
    Arrays.setAll(sticks, i -> new StickHolder());
    philosophers = new Philosopher[n];
    Arrays.setAll(philosophers, i ->
      new Philosopher(i,
        sticks[i], sticks[(i + 1) % n]));    // [1]
    // Fix by reversing stick order:
    // philosophers[1] =                     // [2]
    //   new Philosopher(0, sticks[0], sticks[1]);
    Arrays.stream(philosophers)
      .forEach(CompletableFuture::runAsync); // [3]
  }
  public static void main(String[] args) {
    // Returns right away:
    new DiningPhilosophers(5);               // [4]
    // Keeps main() from exiting:
    ScheduledExecutorService sched =
      Executors.newScheduledThreadPool(1);
    sched.schedule( () -> {
      System.out.println("Shutdown");
      sched.shutdown();
    }, 3, SECONDS);
  }
}

Test this program by hand. When you stop seeing output, that means the program is deadlocked.

In the DiningPhilosophers constructor, each Philosopher is given a reference to a left and right StickHolder. Every Philosopher except the last one is initialized by situating that Philosopher between the next pair of chopsticks. The last Philosopher is given the zeroth chopstick for its right chopstick, so the round table is completed. That’s because the last Philosopher is sitting right next to the first one, and they both share that zeroth chopstick. [1] shows the right-hand stick selected with a modulus of n, wrapping the last Philosopher around to be next to the first one.

Now all Philosophers can try to eat, each waiting on the Philosopher next to them to put down its chopstick.

To start each Philosopher running at [3], I call runAsync() which means that the DiningPhilosophers constructor returns right away at [4]. Without anything to keep main() from completing, the program simply exits and doesn’t do much. To prevent this, I create a ScheduledExecutorService which holds main() open until it is shutdown(). Then I schedule a task which shuts down the Executor after three seconds, at which point all tasks automatically terminate as the program exits.

In the configuration as given, the Philosophers spend virtually no time thinking. Thus they all compete for chopsticks while trying to eat, and deadlock tends to happen quickly. You can change this:

  1. Add more Philosophers by increasing the value at [4].

  2. Uncomment line [1] in Philosopher.java.

Either one will make deadlock much less likely, which shows the danger of writing a concurrent program and believing it’s safe because it seems to “run OK on my machine.” You can easily convince yourself the program is deadlock free, even though it isn’t. This example is interesting precisely because it demonstrates that a program can appear to run correctly while still prone to deadlock.

To repair the problem, we observe that deadlock occurs when four conditions are simultaneously met:

  1. Mutual exclusion. At least one resource used by the tasks must not be shareable. Here, a chopstick can be used by only one Philosopher at a time.

  2. At least one task must hold a resource and wait to acquire a resource currently held by another task. That is, for deadlock to occur, a Philosopher must be hold one chopstick and wait for a second one.

  3. A resource cannot be preemptively taken away from a task. Tasks only release resources as a normal event. Our Philosophers are polite and they don’t grab chopsticks from other Philosophers.

  4. A circular wait can happen, whereby a task waits on a resource held by another task, which in turn is waiting on a resource held by another task, and so on, until one of the tasks is waiting on a resource held by the first task, thus gridlocking everything. In DiningPhilosophers.java, the circular wait happens because each Philosopher tries to get the right chopstick first, then the left.

Because all these conditions must be met to cause deadlock, you must only prevent one of them to prohibit deadlock. In this program, an easy way to prevent deadlock is to break the fourth condition. This condition happens because each Philosopher tries to pick up its chopsticks in a particular sequence: first right, then left. Because of that, it’s possible for each Philosopher to hold its right chopstick while waiting for the left, causing the circular wait condition. However, if the one of the Philosophers is initialized to try to instead get the left chopstick first, that Philosopher never prevents the Philosopher on the immediate right from picking up a chopstick, precluding the circular wait.

In DiningPhilosophers.java, uncomment the line at [1] and the one following it. This replaces the original philosophers[1] with a Philosopher that has its chopsticks reversed. By ensuring that the second Philosopher picks up and puts down the left chopstick before the right, we remove the potential for deadlock.

This is only one solution to the problem. You can also solve it by preventing one of the other conditions (see advanced threading books for more details).

There is no language support to help prevent deadlock; it’s up to you to avoid it by careful design. These are not comforting words to the person who’s trying to debug a deadlocking program. And of course the easiest and best way to avoid concurrency problems is never share resources—unfortunately that’s not always possible.

View or add comments

Notes from The Elm Developer Retreat

This Developer Retreat was held Oct 6-9, 2016. So far the consensus seems to be that Thursday-Sunday is best, because Monday is often a big meeting day at companies (and taking two days at the end of the week is within tolerability). At peak, we had six attendees including myself; on the weekend we had two students from Colorado Mesa University in Grand Junction.

There will be another retreat directly following the Winter Tech Forum.

  1. We all agreed that developer retreats are great, and we will continue doing them and evolving the format.

    A. For one thing, it’s much, much easier to figure things out in a group.

  2. This is the second themed retreat (versus the very first un-themed retreat after the last Winter Tech Forum), and the themed approach is definitely a winner.

  3. We all agreed that Elm is amazing and none of us ever want to write Javascript again (to be honest we already didn’t want to write Javascript anymore).

  4. On the first day we went through The Pragmatic Studio Elm Videos, which are out of date from 0.17 (he’s working on an updated version which I will happily get), and we found this an excellent way to get everyone up to speed. When we ran into problems we stopped the video and figured them out. We also stopped and fixed the example code to make it work with 0.17, and that was a great exercise as well.

  5. For support, the Elm site directs you to the Elm Slack Channel and this was indeed very helpful. One person there even gave me a starting point for my “grid of squares” problem.

  6. The slack channel directs you to the FAQ.

  7. Chromecast is a great way to work in groups to go through and explain code.

  8. There are a lot of useful resources for learning Elm. I’ve captured a number of them, along with the link to our Github repository, at the bottom of this post.

  9. We tried Google Spaces. It’s nice and easy but has a number of drawbacks compared to Slack that were show-stoppers for us. So at the Winter Tech Forum we’ll continue using Slack, unless something better shows up in the meantime.

    A. Messages can only be 170 characters.

    B. You can’t do code snippets like you can in Slack.

  10. Someone on the Elm Slack channel suggested that there be some way to allow remote participation, even if it’s just to set up a dedicated Slack channel. In the past I’ve also had requests to set up a web cam. This merits investigation.

Resources

View or add comments

The Elm Developer Retreat

Developer Retreats are the most relaxed and low-ceremony events you can imagine, and I’ve been very satisfied with the first two.

October 6-9 in Crested Butte CO, we are going to tackle the Elm programming language and make a start on building the Open-Spaces Board UI. You can find full details here.

Some of us have been studying Elm a bit already but this will be a group exploration so if you haven’t had any experience with the language yet you’re in good company (although any pre-retreat studying you do will help).

The retreats are still in their formative stage, so there is no fee yet, although you must still arrange travel, lodging and pay for meals. Details can be found on the site.

View or add comments