Previously I presented transactions as an alternative conceptual scheme to locking. In this article I'm going to examine an efficient implementation of software transactional memory.

Preamble

Before I begin, I want to re-iterate that these ideas, and in particular the basics of the implementation, are drawn from the chapter "Beautiful Concurrency" by Simon Peyton Jones from this book. He described the Haskell version of software transactional memory; what I'm going to describe is my rendition of that into C#.

Source

The complete source code, plus a few simple test applications, can be found at:

http://www.binarycomponents.com/Resources/Source/TransactionalMemory.zip

You'll need Visual Studio 2008 Beta 2 if you want to compile this project.

Overview

This implementation draws on the usual implementation of database transactions. When a transaction is begun, a "log" is created that will store the state related to the transaction. This state may be read, written, or discarded, without affecting the committed, valid memory. The transaction logs, together with the locks, events, and most of the logic is held in a manager class.

All transactional data is held in classes derived from TransactionalValue. The derived classes proxy all requests through the manager, so that any necessary checks can be made (for example, to check that they aren't accessed outside of a transaction), and so that the log can be read or written appropriately.

Code that acts on transactional values is represented by Actions. To save the hassle of creating a derived class for each block of transactional code, a DelegateAction is provided so that code may be written inline. The code in an action should be side-effect free since it may be executed more than once. The action returns success or failure depending on whether the block should be committed or rolled back. (Of course, just because the block wishes to be committed doesn't mean it will be).

Locking

Each transactional value is associated with one of a number of lock objects, and one of a number of events. Locks and events are allocated in turn as each transactional value is created. The lock is used whenever the real, committed value needs to be read or written. (This will occur on the first read or write of the value in a transaction, or when a transaction log is being verified and committed). The events are simple "wake ups" used to retry transactional code blocks after a rollback. All locking and wake-up logic is contained within the manager. When locks need to be taken, they are taken in strict order, so deadlocking is avoided.

The Log

The first time a particular transactional value is accessed within a transaction (either read or write), it is "promoted" to the log. In the log is stored the working value, together with the value that was initially read. Subsequent reads or writes to that value act on the working value in the log. The log is stored per-thread.

When the log is ready to be committed, it must first be verified for consistency. Failing verification results in a rollback and retry. Before verification (and possible commit), all locks associated with values in the log are locked. A log is verified if all of the stored original values are the same as the current master values. If verified, the master values can safely be overwritten by the log values.

Rollbacks

If a transaction needs to be rolled back (either because the code block requested it, or because the log verification failed), the log is discarded, and the code block is scheduled for re-execution. Because the code is assumed to be free of side-effects, the only time the block could possibly succeed (having just failed) is when one of the values it has read during execution changes. To efficiently perform this wait, the manager waits on the events associated with the values in the log. These events are signaled when a log commits.

Explicitly requesting a rollback is a great way for threads to communicate. For example, in the "Dining Philosophers" sample, a rollback is requested if either fork is in use - the thread will be woken when one of the neighbours puts the fork down - and in the "Producer/Consumer" sample, a rollback is requested by the consumer if the buffer is empty - the thread will be woken when the producer adds a value. Note that none of this communication is explicitly stated in the client code - it just magically works.

In the next and final article, I'll look at some pros and cons of this technique.