Software Transactional Memory

published: Tue, 11-Apr-2006   |   updated: Wed, 12-Apr-2006

(This article is also published on ctodx.)

I happened to be browsing through the Microsoft Research site last night, when I came across a project that I'd read about some months back, filed it as "interesting, must come back and read some more", but filed it in short term memory instead of in OneNote, and promptly forgot about it.

The biggest problem with writing multithreaded applications is the race condition, with deadlocking coming hard on its heels. To solve race conditions, we're pretty much used to using thread locks: we lock some object, mess around with some data, and then unlock the object (C#, of course, makes this easy with the lock() keyword and its associated block). So long as we're religious about putting accesses to the data inside a locked block (and locking the same object), we're fine.

Except that locking is fairly disruptive, efficiency-wise. Or, rather, trying to lock an object that's already locked is disruptive: context switches abound, even on multi-processor machines. So that's why there's been so much work done on lock-free algorithms and data structures in academe: researchers recognize that on a machine with tens of processors, a locking algorithm is always going to do much worse than a lock-free algorithm.

The other big, massive, horrendous problem with a locking methodology is that locks are not composable. In other words, if we are not careful (and it can be really difficult to make sure we are careful) composing an operation using two locks may cause deadlocks, which of course is another great reason for exploring lock-free algorithms.

Anyway, one of the more promising avenues being explored is Software Transactional Memory. This is a multithreaded framework where traditional locks are replaced by lightweight transactions. A transaction is a sequence of memory accesses (read or write) executed by a single thread. Just as with your favorite database engine, transactions are atomic in that the framework guarantees that either the changes in the transaction all take place (commit) or are all discarded (rollback). The transaction framework uses lock-free techniques to ensure the commit or rollback.

Anyway, the point of all this is that Microsoft Research have released SXM, a software transactional memory framework for .NET and C#. You can read the readme here, and download the code here (agree to the EULA first). For a layman's explanation of STM see wikipedia.

Update Wed 12-Apr-2006

The download of SXM now requires you to agree to the EULA. I've updated the link above.