Facebook Twitter MySpace Stumble Reddit Delicious More...

The Java Specialists' Newsletter
Issue 1842010-06-04 Category: Concurrency Java version: 1.2, 1.3, 1.4, 1.5, 6+

Welcome to the 184th edition of The Java(tm) Specialists' Newsletter, sent to you from Chorafakia, where the birds are singing outside and the blue sea smiles at me in the distance (not too much of a distance though :-)). On Wednesday my wife and I visited the police station, where I was asked to hand over my driver's license for two months. The Law of Cretan Driving caught up with me, as I knew it would. I will tell you the whole story later this evening when we cover that law in our Master Course day 1.

In about 6.5 hours from now, we are running the first day of the Java Specialist Master Course as a welcome gift for members of our Java Specialist Club. If you have not signed up yet, please do. I would not want you to miss out on this opportunity. And yes, it is completely free for club members. The course runs from 13:00-21:00 GMT today on June 4th. Once you have signed up to the club, please find the registration link by visiting our club forum. Please note that the webinar requires either Mac OS X or Windows. Linux is currently not supported.

Deadlocks through Cyclic Dependencies

In my last newsletter, I asked readers why Vector had a writeObject() method that just did the default, without a readObject() method. The answer is to simply make the writeObject() method synchronized. The quiz was easy, I admit.

One of my readers pointed out that in another JVM implementation, Vector had been coded specifically to avoid a deadlock situation that was found in production. Instead of making the entire method synchronized, they first cloned the Vector with the underlying Object[], but not the elements inside, and then wrote those out in a synchronized block.

This led me to the question - could I generate a deadlock by writing out two Vectors with a cyclic dependency from two threads? Turns out it was easy as pie:

import java.io.*;
import java.util.*;
import java.util.concurrent.*;

public class VectorSerializationDeadlock {
  public static void main(String[] args) {
    ExecutorService pool = Executors.newFixedThreadPool(2);

    final Vector[] vecs = {
        new Vector(),
        new Vector(),
    };
    vecs[0].add(vecs[1]);
    vecs[1].add(vecs[0]);

    for (int i = 0; i < 2; i++) {
      final int threadNumber = i;
      pool.submit(new Callable() {
        public Object call() throws Exception {
          for (int i = 0; i < 1000 * 1000; i++) {
            ObjectOutputStream out = new ObjectOutputStream(
                new NullOutputStream()
            );
            out.writeObject(vecs[threadNumber]);
            out.close();
          }
          System.out.println("done");
          return null;
        }
      });
    }
  }
}

public class NullOutputStream extends OutputStream {
  public void write(int b) throws IOException {
  }
}
  

After a very short time, this causes a deadlock on the Sun's Java Virtual Machine (JVM). On other JVMs, this might not cause a deadlock, as they specifically coded around it.

When I mentioned this in the Java Specialist Club, Olivier Croisier pointed out that there are lots of cases in the JDK with a synchronized writeObject() method:

    - java.beans.beancontext.BeanContextServicesSupport
    - java.beans.beancontext.BeanContextSupport
    - java.io.File
    - java.lang.StringBuffer
    - java.lang.Throwable
    - java.net.Inet6Address
    - java.net.SocketPermission
    - java.net.URL
    - java.util.Hashtable
    - java.util.PropertyPermission
    - java.util.Vector
    - javax.security.auth.kerberos.DelegationPermission
  

He even managed to cause a deadlocks with Throwable, although I would argue that a cyclic dependency in Throwables would be a bug. If you try to print the stack space you will get a StackOverflowError. All he did was replace my Vectors with Throwables:

Throwable t1 = new Throwable("t1");
Throwable t2 = new Throwable("t2", t1);
t1.initCause(t2);

final Throwable[] vecs = {t1,t2};

My Vector example is contrived, meaning that it is extremely unlikely that with a simple object graph you would have two vectors that contain one another. However, with a complicated data structure, it is entirely possible that this could happen. In fact, it has happened to someone in production, which is why the "other" JVM had to code around it specifically.

Synchronized List

Another interesting point is that the List returned by the Collections.synchronizedList() method does not protect itself against concurrent updates in the writeObject() method. Collections.synchronizedCollection returns a class that does also use the synchronized writeObject() approach. In the case of the Synchronized Collection, we might quite easily also cause deadlocks on the write, I imagine, though I have not tried that out.

Here is an example of how we can cause a ConcurrentModificationException with a Synchronized List. This does not happen with the Synchronized Collection.

import java.io.*;
import java.util.*;

public class MangledSynchronizedList {
  public static void main(String[] args) {
    final List<String> synchList = Collections.synchronizedList(
        new ArrayList<String>());
    Collections.addAll(synchList, "hello", "world");
    Thread tester = new Thread() {
      { setDaemon(true); }
      public void run() {
        while (true) {
          synchList.add("hey there");
          synchList.remove(2);
        }

      }
    };
    tester.start();

    while (true) {
      try {
        ObjectOutputStream out = new ObjectOutputStream(
            new NullOutputStream()
        );
        for (int i = 0; i < 100 * 1000; i++) {
          out.writeObject(synchList);
        }
        out.close();
      } catch (IOException e) {
        e.printStackTrace();
        break;
      }
    }
  }
}

After a short while, we see ConcurrentModificationException.

Kind regards

Heinz

Concurrency Articles Related Java Course Discuss at The Java Specialist Club