Background

Dealing effectively with [multithreading|multi-threaded programming] is a hot topic these days. [Clock speed]s have more or less plateaued, but the [HyperThreading|number of threads] on a [CMP|chip] (and the [SMP|number of chips in a machine]) is going up. [Lock]s are [deadlock|hard] and [lock convoying|prone] to [priority inversion|bugs]. [Software transactional memory] is one possible alternative, and one that is popular in the [computer science|research community]. The basic idiom of STM is to throw away the locking paradigm entirely, and to replace it with merely declaring a certain section of code [atomic]. The [run-time system] (1), be it the [virtual machine] in a managed language such as [Java], or merely a library (2) in the case of a language such as [C++] then guarantees that the actions performed within that section of code are [isolation|isolated] from the rest of the program, and any updates to shared memory appear, to the rest of the program, to either happen atomically or not at all. While there are indeed many implementations of STM that involve behind-the-scenes locking, our focus in this node will be on those that implement STM using [non-blocking synchronization], specifically lock-freedom vs. obstruction-freedom (3).

Basic STM operations

As further background, let us review the basic operations of an object-level STM. The open operation makes an object available to an STM. An object may be opened either for reading or for writing; clearly, many readers can have an object open simultaneously without conflict, whereas a writer must necessarily conflict with both other writers and readers (note, however, that if a transaction that is reading an object finishes its transaction before a transaction that is writing to it, the nature of atomicity means that this is equivalent to the reader having done all its work before the writer did any of its work. Its linearization point (4) is said to be before that that of the writer). Opening an object for writing is distinct from acquire, which is the point at which the transaction announces to the rest of the world that it has claimed this object for writing. A transaction may do so either at the same time as it opens for writing, or during commit; this difference is known as eager vs lazy acquire. At acquire point any transactions reading the object must abort, as must any other transactions who had planned on acquiring it.

When a transaction aborts, it rolls back any changes it has made (in many STMs a transaction makes local copies of the objects it modifies, so an abort merely means discarding these copies) and starts the computation from the beginning. When a transaction [commit]s , it (atomically) makes all its changes public, after first having validated, i.e. ensured that all objects it read and wrote are the same now as they were when it opened them.

Lock-freedom vs obstruction-freedom

Obstruction freedom means if all other threads are suspended, a single transaction in a single thread will eventually complete. In practice, what this entails is that a transaction must (a) have the ability to abort another and (b) be guaranteed to do so after some amount of time. This guarantee ensures that if one of the hypothetical suspended threads holds an object that our single thread running in isolation needs, our thread can abort the other one and take that object, after some bounded amount of time. [Livelock] is not denied with obstruction-freedom; two threads can repeatedly abort each other forever. The probability of livelock is to be mitigated or denied entirely by an out-of-band [contention manager] (5).

Lock-freedom is obstruction-freedom plus the denial of livelock. Formally, it is the guarantee that every step taken achieves global progress. In practice, in the context of STMs, this means that one transaction can abort another, but only if it itself is guaranteed to commit, i.e. if transaction A aborts transaction B, transaction B (or any other transaction) can never abort transaction A; hence the denial of livelock. Doing so without breaking obstruction-free guarantees (which are implied by lock-freedom) means that a lock-free STM must use lazy acquire (6): objects to be written to are acquired at the end of the transaction rather than as they are opened for writing. Consider:

Since commit must be atomic, the case of a write-write conflict where transaction A aborts transaction B (after some amount of waiting to acquire an object that B has already acquired) can never occur. The only write-write conflicts are transaction A aborting itself while attempting to validate and seeing that transaction B has committed changes to some of A's objects, invalidating A. In this case, A is aborting in favor of a transaction that has already committed.
In the case of a read-write conflict, either readers are visible (the read analogue of eager acquire) or invisible (similarly for lazy acquire). In the former case, transaction A sees that transaction B is reading some of A's objects during A's commit, and aborts B. In the latter case, B sees during validation that A has committed over some objects that B is reading, and aborts itself. In either case, the reader transaction aborted in favor of a transaction that has already committed.

Thus, lazy acquire means that any transaction in favor of which another transaction aborts is guaranteed to commit, because a transaction can only abort in favor of another transaction if the other transaction has already committed.

Of course, lazy acquire also means that every object written to is held in some sort of private write set and is validated on every open of a new object (otherwise, a transaction B could operate on a set of objects that were written to by transaction A, while seeing pre-commit versions of some and post-commit version of the others), which introduces its own inefficiencies.

1: "Software Transactional Memory for Supporting Dynamic-Sized Data Structures", by M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer III. 22nd ACM Symp. on Principles of Distributed Computing (PODC 2003), July 2003.
2: "Lowering the Overhead of Nonblocking Software Transactional Memory," by V. J. Marathe, M. F. Spear, C. Heriot, A. Acharya, D. Eisenstat, W. N. Scherer III, and M. L. Scott. First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT 2006), June 2006.
3: M. Herlihy, V. Luchangco and M. Moir. "Obstruction-Free Synchronization: Double-Ended Queues as an Example." 23rd International Conference on Distributed Computing Systems, 2003, p.522.
4: M. Herlihy and J. Wing. "Linearizability: A correctness condition for concurrent objects." ACM Transactions on Programming Languages and Systems, 12(3):463–492, 1990.
5: "Contention Management in Dynamic Software Transactional Memory", by W. N. Scherer III and M. L. Scott. PODC Workshop on Concurrency and Synchronization in Java Programs (CSJP 2004), July 2004. In conjunction with the 23rd ACM Symp. on Principles of Distributed Computing (PODC 2004).
6: "Adaptive Software Transactional Memory", by V. J. Marathe, W. N Scherer III, and M. L. Scott. 18th Annual Conf. on DIStributed Computing (DISC 2005), Sept. 2005. An earlier version appears as TR 868, Computer Science Department, University of Rochester, May 2005.

Lock-freedom and Obstruction-freedom in Software Transactional Memory (idea)