Threading: Lock Nesting - Jonathan Pryor's web log

« HackWeek Summary | Main | Announcing NDesk.Options 0.2.1 »

Threading: Lock Nesting

a.k.a. Why the Java 1.0 collections were rewritten...

Threading is an overly complicated subject, covered in great detail at other locations and in many books. However, there is one subject that either I haven't seen discussed too often, or somehow have managed to miss while reading the plethora of threading sources, something I'll call lock nesting depth:

lock nesting depth

The number of locks that must be acquired and held simultaneously in order to perform a given operation.

In general, the lock nesting depth should be kept as small as possible; anything else results in extra, possibly unnecessary/extraneous locks, which serve only to slow down performance for no added benefit.

First, an aside: why does threading code require locks? To maintain data invariants for data shared between threads, preventing the data from being corrupted. Note that this is not necessarily the same as producing "correct" data, as there may be internal locks to prevent internal data corruption but the resulting output may not be "correct" (in as much as it isn't the output that we want).

The prototypical example of "non-corrupting but not correct" output is when multiple threads write to the (shared) terminal:

using System;
using System.Threading;

class Test {
	public static void Main ()
	{
		Thread[] threads = new Thread[]{
			new Thread ( () => { WriteMessage ("Thread 1"); } ),
			new Thread ( () => { WriteMessage ("Thread 2"); } ),
		};
		foreach (var t in threads)
			t.Start ();
		foreach (var t in threads)
			t.Join ();
	}

	static void WriteMessage (string who)
	{
		Console.Write ("Hello from ");
		Console.Write (who);
		Console.Write ("!\n");
	}
}

Output for the above program can vary from the sensible (and desirable):

$ mono ls.exe 
Hello from Thread 2!
Hello from Thread 1!
$ mono ls.exe 
Hello from Thread 1!
Hello from Thread 2!

To the downright "corrupt":

Hello from Hello from Hello from Hello from Thread 2!
Thread 1!

(This can happen when Thread 1 is interrupted by Thread 2 before it can write out its entire message.)

Notice what's going on here: as far as the system is concerned, what we're doing is safe -- no data is corrupted, my terminal/shell/operating system/planet isn't going to go bonkers, everything is well defined. It's just that in this circumstance "well defined" doesn't match what I, as the developer/end user, desired to see: one of the first two sets of output.

The solution, as always, is to either add a a lock within WriteMessage to ensure that the output is serialized as desired:

	static object o = new object ();
	static void WriteMessage (string who)
	{
		lock (o) {
			Console.Write ("Hello from ");
			Console.Write (who);
			Console.Write ("!\n");
		}
	}

Or to instead ensure that the message can't be split up, working within the predefined semantics of the terminal:

	static void WriteMessage (string who)
	{
		string s = "Hello from " + who + "!\n";
		Console.Write (s);
	}

(Which can oddly generate duplicate messages on Mono; not sure what's up with that... More here.)

For the WriteMessage that uses locks, the lock nesting depth is 2, and this can't be readily improved (because Console.Write is static, and thus must be thread safe as any thread could execute it at any time).

Returning to this entry's subtitle, why were the Java 1.0 collections rewritten? Because they were all internally thread safe. This had it's uses, should you be sharing a Hashtable or Vector between threads, but even then it was of limited usefulness, as it only protected the internal state for a single method call, not any state that may require more than one function call. Consider this illustrative code which counts the number of times a given token is encountered:

Hashtable data = new Hashtable ();
for (String token : tokens) {
    if (data.containsKey (token)) {
        Integer n = (Integer) data.get (token);
        data.put (token, new Integer (n.intValue() + 1));
    }
    else {
        data.put (token, new Integer (1));
    }
}

Yes, Hashtable is thread safe and thus won't have its data corrupted, but it can still corrupt your data should multiple threads execute this code against a shared data instance, as there is a race with the data.containsKey() call, where multiple threads may evaluate the same token "simultaneously" (read: before the following data.put call), and thus each thread would try to call data.put (token, new Integer (1)). The result: a missed token.

The solution is obvious: another lock, controlled by the developer, must be used to ensure valid data:

Object lock = new Object ();
Hashtable data = new Hashtable ();
for (String token : tokens) {
    synchronized (lock) {
        if (data.containsKey (token)) {
            Integer n = (Integer) data.get (token);
            data.put (token, new Integer (n.intValue() + 1));
        }
        else {
            data.put (token, new Integer (1));
        }
    }
}

Consequently, for all "non-trivial" code (where "non-trivial" means "requires more than one method to be called on the collection object in an atomic fashion") will require a lock nesting depth of two. Furthermore, the lock nesting depth would always be at least one, and since many functions were not invoked between multiple threads, or the collection instance local to that particular method, the synchronization within the collection was pure overhead, providing no benefit.

Which is why in Java 1.2, all of the new collection classes such as ArrayList and HashMap are explicitly unsynchronized, as are all of the .NET 1.0 and 2.0 collection types unless you use a synchronized wrapper such as System.Collections.ArrayList.Synchronized (which, again, is frequently of dubious value if you ever need to invoke more than one method against the collection atomically).

Finally, the Threading Design Guidelines of the .NET Framework Design Guidelines for Class Library Developers (book) suggests that all static members be thread safe, but instance member by default should not be thread safe:

Instance state does not need to be thread safe. By default, class libraries should not be thread safe. Adding locks to create thread-safe code decreases performance, increases lock contention, and creates the possibility for deadlock bugs to occur. In common application models, only one thread at a time executes user code, which minimizes the need for thread safety. For this reason, the .NET Framework class libraries are not thread safe by default.

Obviously, there are exceptions -- for example, if a static method returns a shared instance of some class, then all of those instance members must be thread safe as they can be accessed via the static method (System.Reflection.Assembly must be thread safe, as an instance of Assembly is returned by the static method Assembly.GetExecutingAssembly). By default, though, instance members should not be thread safe.

blog comments powered by Disqus