Stu Smith: Making It Up As I Go Along
“ My life working for BinaryComponents, coding, design, and other stuff. ”
Last article I covered my implementation of software transactional memory in C#. If you haven't read those articles yet, in brief, it's a technique where we can write efficient, thread-safe client code without using having to think about locks or events - all isolation, atomicity and signaling is handled by a small set of common routines.
I've presented this technique, and the code, as the realization of an idea that could be taken further - I'm pretty sure it's not ready for production code yet. In this final article, I'll give a link to the source, and cover some pros and cons of this technique.
The articles and source will be kept up-to-date on:
But for convenience, here's links to everything so far:
Part 1: The Problems with Locking
Part 2: Atomicity and Isolation: That Reminds Me Of A Database
Part 3: Implementation
Source: TransactionalMemory.zip
If you have any comments on this technique, please let me know. I'd be particularly interested if anyone uses it in "real" code, as opposed to my simple examples. Additionally, if you're able to overcome any of the "cons" listed, I'd like to know that too.
If you find any bugs, please do let me know, and I'll update the source. (Any bugs in the implementation will of course go to show how bug-prone normal locking techniques are).
If you're interested in multi-threaded coding techniques, you might find the following .NET-related projects and shows interesting:
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.
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#.
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.
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).
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 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.
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.
Last article I talked about the use of locks to solve threading issues, and how they problematic they are: necessary, but very low level. In this article, I'm going to imagine a different world...
Let's imagine that we can open a transaction, just as we might when using SQL, but for ordinary variables. Transactions have two important properties:
And afterall, that consistency is what we're trying to achieve with locking. If we can get transactions working, we should be able to use them instead of locks.
So let's imagine that this exists for memory, not just SQL databases. Our bank account problem from the previous article suddenly becomes very easy to solve:
class BankAccount
{
public void Deposit( long change )
{
BEGIN TRANSACTION
_amount += change;
COMMIT TRANSACTION
}
private t_long _amount;
}
public static void Transfer( BankAccount a, BankAccount b, long amount )
{
BEGIN TRANSACTION
a.Deposit( -amount );
b.Deposit( amount );
COMMIT TRANSACTION
}
Easy. Of course, we could never have that actual syntax in C#, but that's conceptually what we want to achieve.
Of course, one correct (but really bad) way of implementing this would be to have a single, global, lock, and to lock and unlock that as we enter and exit transactions. If we also checked that we were in a transaction before accessing a variable (and that's why I've changed the type to be "t_long" to imply that), then we have solved all three problems mentioned previously. Of course, that method doesn't scale very well: any contention on the lock, even if it was on different values, would block all other threads. It does at least demonstrate that the concept is good.
So next article I'm going to describe a better way of implementing memory-transactions using optimistic locking. I'll also look into the transaction command I've not mentioned so far, ROLLBACK, and discover it's really useful. I have an actual working implementation of all this in C#, so at the end of these articles, I'll make the source available.
As I mentioned in a previous post, I've been reading through "Beautiful Code: Leading Programmers Explain How They Think", and one chapter that really caught my attention was about Software Transactional Memory. What I'm about to present in this mini-series therefore is merely my take on an idea that greater minds than mine have come up with.
I'm a C# / .NET programmer, and the staple multi-threaded construct is the lock block (which is basically a monitor or mutex):
lock( _lockObject )
{
SharedResource.Foo(); // Access a shared resource.
}
All fine and good, and you certainly can't do without them, but there's a bunch of problems with them:
Since there's no necessary connection between the lock and the resource, it's possible to forget to lock:
Thread_1
{
lock( _lock )
{
SharedResource.Foo(); // Access a shared resource.
}
}
Thread_2
{
SharedResource.Foo(); // Access a shared resource.
// Oops!
}
There's not even a runtime error here. That program is wrong, silently wrong, and difficult to debug.
Let's say we have a bank account class:
class BankAccount
{
public void Deposit( long change )
{
lock( _lock )
{
_amount += change;
}
}
private long _amount;
private object _lock = new object();
}
Then how do we write a thread-safe transfer method?
public static void Transfer( BankAccount a, BankAccount b, long amount )
{
// This is incorrect:
a.Deposit( -amount );
b.Deposit( amount );
}
What can I lock on to make this function correct?
If you're using more than one lock, you'd better get them in the right order, otherwise you're jammed. Getting into deadlock is easy; getting out is near-impossible.
So locks are evil then. A necessary evil, but evil nonetheless. But we can hide them away...
As a parting teaser before the following parts, here's my implementation of the Dining Philosophers problem, written without any (obvious) locks:
using System;
using System.Threading;
namespace ConsoleTests
{
public static class DiningPhilosophers
{
public static void Run()
{
//
// Create fork values.
for( var i = 0; i < _numPhilosophers; ++i )
{
_forks[i] = new BinaryComponents.TransactionalMemory.Values.Boolean( false );
}
//
// Create a thread for each philosopher.
for( var i = 0; i < _numPhilosophers; ++i )
{
var pts = new ParameterizedThreadStart( RunPhilosopher );
var thread = new Thread( pts );
thread.Start( i );
}
}
private static void RunPhilosopher( object data )
{
var n = (int) data;
var rnd = new Random();
var leftFork = _forks[n];
var rightFork = _forks[( n + 1 ) % _numPhilosophers];
while( true )
{
Console.WriteLine( string.Format( "Philosopher {0} is hungry...", n ) );
//
// Try to grab the forks.
BinaryComponents.TransactionalMemory.Manager.Execute( delegate
{
//
// If either fork we want is in use, then retry.
if( leftFork.Value || rightFork.Value )
{
return false;
}
//
// Otherwise, grab them.
leftFork.Value = true;
rightFork.Value = true;
return true;
} );
//
// Eat for a while.
Console.WriteLine( string.Format( "Philosopher {0} is eating.", n ) );
Thread.Sleep( rnd.Next( 5000 ) );
Console.WriteLine( string.Format( "Philosopher {0} puts down the forks and starts thinking.", n ) );
//
// Drop the forks.
BinaryComponents.TransactionalMemory.Manager.Execute( delegate
{
leftFork.Value = false;
rightFork.Value = false;
return true;
} );
//
// Think for a while.
Thread.Sleep( rnd.Next( 5000 ) );
}
}
private const int _numPhilosophers = 5;
private static BinaryComponents.TransactionalMemory.Values.Boolean[] _forks = new BinaryComponents.TransactionalMemory.Values.Boolean[_numPhilosophers];
}
}