Can a good type system prevent concurrency errors? Or is this a quest for the Holy Grail?
There are two parts to this question, corresponding to two major types of concurrency errors:
- Preventing data races
- Preventing deadlocks
I’ll start with the first one.
Data races occur only when memory is shared between threads. Disallow sharing and data races are gone! In fact there is a name for threads that don’t share memory: processes. It’s perfectly feasible to have a concurrent language that disallows sharing–Erlang is one (see my post about Erlang). The trick is to always pass data between threads by value. This is especially easy in functional languages.
Non-functional languages like C++, Java, or D (I was told by Walter Bright, the creator of D, to always use the full name, “the D programming language,” so that search engines can index it properly) tend to share data almost by default (see, however, this post).
In Java, all non-primitive types have reference semantics. When you pass a Java object between threads, you’re only passing a handle; the object behind it becomes accessible from both threads.
C++ at least has means to express passing by value and move semantics for user-defined types. Still, it’s up to the programmer to use them.
Who ordered Guava?
For every type-system idea there is one or more dialects of Java that implement it. I’ll start with an older attempt at data-race free Java called Guava, as it illustrates some of the basic premises.
-Explicit sharing
The most important step–if we don’t want to completely ban the sharing of data–is to regulate it. Let the programmer explicitly mark the data destined for sharing as such. The corollary is that the data that is not marked for sharing cannot be shared. This can be accomplished, for instance, by making all objects thread-local by default, or by using type modifiers that prevent references to such objects from escaping.
In Guava, the data type designed for sharing is called a Monitor. As the name suggests, all access to a Monitor is automatically synchronized by the Monitor’s lock. This, incidentally, eliminates the need for the synchronized keyword, which is absent from Guava.
The non-shared data types are either Objects or Values.
Objects are just like regular Java Objects, except that they don’t have a built-in lock, since they can never be shared between threads.
Values are either primitive values, like integers, or user-defined types with value semantics.
Monitors, Objects, and Values are collectively called instances.
-Value semantics
When you pass a Value, the compiler will make a deep copy of it (well, sort of–the monitors embedded in a Value are not deep copied). Since deep copying might be expensive, Guava defines operator “move”, which nulls the source. The syntax is:
v2 = v1--;
The value v1 becomes null after the move to v2. This is similar to C++ unique_ptr and std::move.
-Ownership
The biggest problem in lock based concurrency is to make sure that the correct lock(s) are taken when accessing shared data. In Guava, all Monitor’s data are protected by that Monitor’s lock. As long as they stay inside that Monitor, nothing bad can happen to them from the point of concurrency.
Values stored inside a Monitor are never accessible outside of the Monitor–only their copies may be passed out.
The same is not true about Objects. Since Objects have reference semantics, there is a real danger that Objects’ references might escape the Monitor that protects them. Imagine a situation where two Monitors have references to the same Object. It is possible then that two threads may operate on that Object at the same time–one entering through one Monitor, the other through the other Monitor. We have a data race!
Therefore it is important that every Object have an owner at all times. The Object’s owner is either a Value or a Monitor. (The exception is a fresh Object that’s been just allocated–it has no owner until it is assigned to a variable.) Since an Object may only be owned by at most one Monitor, it is that Monitor that protects it from simultaneous (racy) access.
-Regions
All Objects that are owned by a particular Monitor or Value form a region. Equivalently, assigning a monitored region to an object specifies what lock must be held when accessing it.
All instances may contain (references to) monitors, but monitors are not “owned” by anybody. References to the same monitor may appear in multiple regions and may be freely passed around. It is thus up to programmers to define an ordering scheme for their monitors in order to avoid deadlocks.
How can we protect Objects from moving between regions and acquiring multiple owners? We need a way to control aliasing.
Here are some Guava rules for passing Objects. A method may declare its Object parameter as either kept or lent. (By default, parameters to Object methods are kept and to Monitor methods are lent.) If the parameter is kept it must belong to the same region as this, and there are no limitations on its use. If, however, the parameter is lent, the method may not store a reference to it in this, nor may it store this inside a lent Object. No cross-aliasing is allowed.
A method may also be marked new if it returns a freshly created object, which has no owner yet. Constructors are considered new unless they accept kept parameters.
Notice that you may have multiple references to the same Object, but they will all be within the same region. The only instances that may be passed between threads are Monitors and Values.
-Constructors
Guava final fields may either be initialized inside a constructor or in a private method that is only called from inside a constructor. (BTW, in D a private method is not private within a module, so the compiler would have to analyze the whole module to establish the latter condition.) [Note to self: The same scheme might be useful in the construction of immutable objects in D.]
Partially constructed Objects must not be visible outside constructors. The compiler must verify that constructors don’t pass this to other methods, and don’t store this inside other instances (no alias cross-contamination).
-Optimizations
Copying Values around may be expensive. I already mentioned one optimization, the use of the “move” operator. The other optimization is related to immutability. If a Value is immutable, it may be safely passed by reference. Guava defines immutable classes as ones that have no update methods. Any method that may modify this must be marked update. The update notation is also extended to method parameters–by default parameters are immutable.
There is a bonus advantage to separating update methods from the rest. In a Monitor, a non-update method may safely use a readers’ lock, which allows multiple readers to access data simultaneously, to increase concurrency.
-Global and local methods
A method is considered local if its effects cannot be observed or influenced by other threads. All Object and Value methods are by default local. A local method is immune to races thus allowing single-thread optimizations.
Conversely, all Monitor methods are considered global, since operations on Monitors may be visible or influenced by other threads.
These defaults may be overridden. For instance, an Object may contain a reference to a Monitor. The methods that call this Monitor’s methods must be marked global. Moreover, Object or Value methods that access Monitors that are passed to them as arguments must also be marked global. So touching a Monitor (which is equivalent to using its lock) taints the whole callers’ tree with the global annotation.
This is similar to the way update taints the callers tree, except the update annotation of a method only pertains to this, not to its arguments. However, when global and update are combined, they have the same tainting power as global. In particular, a method that invokes a global update method on its argument becomes tainted with global update.
Methods that are global update cannot be invoked from non-update methods, even if they only global-update their arguments.
Note: This part of the paper is not very clear to me. The authors never explain the importance of global update methods (other than optimization opportunities).
-Limitations
Guava implements a relatively simple and somewhat limited system to eliminate races. It punts the problem of ownership-passing and lock-free programming. Even with those limitations the Guava type system is not simple.
The idea that safe multithreading may be achieved with a few simple modification to the type system seems to be untenable. However, as long as special type annotations are limited to the code that does actual multithreading, I think they’re worth the added complexity.
March 24, 2009 at 3:10 pm
Thank you for another great blog. In general, it feels like Guava has over-complicated their type system by using an object-centric abstraction rather than a thread-centric one. I agree that safety using the type system alone is probably untenable; however, the ability to segregate fast, serial code from slower, thread safe code is a boon. Here’s what I took home:
Good Ideas
1. The concept of shared objects (Monitors) being able to have and use private helper objects. While this is mainly about performance rather than correctness, documenting and enforcing the concept of a member variable that must be contained within an object’s scope is useful. Though not mentioned, the ability to debug with these promoted to a fully protected shared object, would help find bugs.
2. kept/lent are neat, intuitive keyword names.
Additional Limitations
1. Not breaking good idea #1(scope member variables) into a separate type, adds a fair amount of complexity to the compiler (in terms of tracing, analysis, etc) and programmer (in terms of cognitive load as two objects now behaving differently)
2. Both ‘new’ methods and the move (aka mobile) mechanics of value types break region-local garbage collection heaps, necessitating less efficient, less scalable and higher latency alternatives.
3. They use class centric region boundaries. This seems to add several layers of complexity without any benefit. Particularly, the kept/lent system exists solely because objects need to be passed across this boundary regularly and therefore doing so must be efficient. This seems like a hallmark that the wrong region boundaries where chosen. For instance, a thread-centric boundary avoids the need for a kept/lent system since the local objects don’t exit or enter the thread. (Thread-centric design also fixes additional limitation 2)
4. Somehow, having both update and read (also global and local) seems a little redundant.
5. The viral nature of global + update. I couldn’t find exactly why global + update were important and so far all my guesses are just plain bad ideas.
March 24, 2009 at 5:15 pm
[…] Types for Concurrency Can a good type system prevent concurrency errors? Or is this a quest for the Holy Grail? There are two parts to this […] […]
March 26, 2009 at 12:13 pm
Robert, moving objects between threads is an essential part of any concurrent program. You can pass them by value or by reference. It’s the latter case that requires move semantics.
The basic pattern is this: Thread 1 produces an object, let’s say a task to be performed by thread 2, and passes it to a shared queue (a Monitor). Thread 2 picks the task from the queue and executes it. If both threads retain a reference to the task object, that object will have to be a Monitor. But if you can move the object, you don’t leave any references behind and you don’t have to lock it.
March 26, 2009 at 2:25 pm
Yes, moving objects between threads is essential. But, I draw a distinction between moving objects local to a region and moving objects shared between regions (Guava Objects and Monitors, respectively). Guava’s problem has to do with allowing local objects to move between regions, which makes it unable to support region-local garbage collection. Consider your basic pattern. Thread 1 allocates a local object A on its local GC and passes it to thread 2. Thread 1’s GC now runs. Since there are no references to A in thread 1, its GC collects A. Thread 2 now calls a method on A undefined memory with undefined results. This occurs because a region-local GC is by definition unaware of other regions. However, if shared objects were passed between regions instead, this wouldn’t happen since the shared GC is aware of all threads. Now, the efficiency (and the problems) of a ‘mobile’ has long been known, but these should have a separate type, allocated on the shared GC. Besides, my main criticism was the choice of boundary: 1 per Monitor vs 1 per Thread.
March 26, 2009 at 4:25 pm
I think the authors are using the word “region” in a different sense, not related to GC. But I see your point. I’m currently working on the next installment of my blog, in which I’ll describe another dialect of Java. This dialect allows per-instance, rather than per-class, choice of sharing. In pseudo-D it would look something like this:
auto msg = new Message!(unique);
The compiler would interpret “unique” as something that may be passed between threads, so it would allocate it from the shared heap. However, it would not use locking on it, because “unique” could only be passed by “move”. This way it’s always alias free.
April 28, 2009 at 12:27 am
[…] my previous post about Guava, a dialect of Java, I talked about a type system that enforces the separation of thread-local and […]
May 11, 2009 at 11:52 am
Thanks for your interest in Guava, and the interesting discussion. I’ll make some comments on our work with the benefit of hindsight:
We tried very hard to create a language (dialect) that maintained a shared-memory programming model (as opposed to going all the way to Erlang’s pure process model) with as small and simple a set of annotations as possible.
Nevertheless, the increase in complexity, keywords, and concepts is greater than we would have liked, and I don’t think it reaches a level of “cleanliness” where it would be adopted in a mainstream language.
Other approaches to type-based avoidance of data races (eg by Boyapati et al and Vitek et al) are, I think, at least as bad if not worse. Fundamentally, it’s just a very hard problem and while many people have attacked it I don’t think anyone has cracked it yet. Whether it can be done, or whether the shared memory model is just doomed, is still open to debate.
The treatment of “values” as being deep-copied was an expedient to avoid further changes to the language. In separate work, I designed a language called Kava (JavaGrande’01), which adds a true value type to Java, allowing the definition of primitive-like data types (eg complex numbers, quaternions, etc etc). This design is being used in the Lime language for our Liquid Metal project (ECOOP’08). Having real values avoids the need for deep copies, move operators, etc.
A minor nit in your description: Values can’t “own” objects — objects are uniquely owned by a monitor.
As for regions and garbage collection, Bartosz is correct: our use of the term “region” is different from its use in memory management circles (eg in the Cyclone language). Regions are a compile-time way of talking about monitor ownership.
How you might go about implementing garbage collection is fairly orthogonal to this question. You could GC the entire heap, or a monitor at a time, or “chunks” of monitors at a time. If a monitor has an outstanding call into another monitor, the lent parameters must be kept live, but this is no different in principle from any other stack-based roots for the collection process. However, in general for a per-monitor GC strategy, it would probably be a good idea to treat the GC as another “method” which is only invoked when no other method is running inside the monitor. However, an exception would have to be made for long-running monitor methods.
Erlang has gone back and forth between using per-process GC (which has nice real-time properties, but can cause space blow-up when immutable values are copied across many processes) and using global heap GC (which achieves better space efficiency at the expense of real-time behavior). There doesn’t seem to be any one-size fits all solution.
May 18, 2009 at 8:54 pm
A few things (I am also a designer of Guava and co-author of the Guava paper):
1. I just communicated with David and I need to correct his correction to the earlier poster.
The original poster was correct, see 2.1.1. of the paper. Objects can be owned by values; if monitor M contains values V1 and V2, then
V1 can own O1 and V2 can own O2, and the language rules will still make sure that O1 doesn’t reference O2 (because otherwise V2 might later be moved to be inside a different monitor M2 in which case a thread in M and a thread in M2 could both access O2). The only thing special about the owners being values is that there is no need to acquire a lock.
2. If you were to implement separate GC in each monitor of Guava, you would need a different GC algorithm. I would treat objects differently than values, since values can migrate from monitor to monitor and objects can’t.
May 18, 2009 at 8:54 pm
Oops, forgot to check the box “notify me of follow-up comments”.
May 19, 2009 at 1:15 pm
David, Rob, thank you for taking the time to comment on my blog. There is part of your paper that I couldn’t figure out. I understand the rules about “global” and “local”, but I don’t see what they buy you in terms of safety.
May 26, 2009 at 9:57 am
[…] also my previous posts on Guava and GRFJ that discuss race free dialects of Java. Possibly related posts: (automatically […]