Software Transactional Memory in .NET Framework 4

Contents

Software Transactional Memory in .NET Framework 4

I've been looking at some of the new features in .NET framework 4 and it looks like they've finally decided to introduce software transactional memory (STM) into the framework, something that Microsoft research have been working on for years.

So here is a quick overview of STM?

STM is a new feature in the .NET framework that aims to bring database like transactions to .NET variables through the use of a new language construct called an atomic block. This is intended as a conceptual replacement to most of the cases where you'd use locks but not 100%.

So why do we use locks anyway?

Consider a scenario where two threads need to access the same object and at least one of them needs to write.

Shared object :
var sharedVar = new {a,b,c}; // sharedVar is a composite object consisting of 3 value types.

op1 | Thread 1: Read sharedVar -> “{a,b,c}”
op2 | Thread 2: Start Write sharedVar <- “{x,y,z}”
op3 | Thread 1: Read sharedVar -> “{x,b,c}” (race condition, could be either a,b,c or x,y,z or anything in between depending on how far thread 1 has got.)
op4 | Thread 2: Finish Write sharedVar 
op5 | Thread 1: Read sharedVar -> “{x,y,z}”

If you were using locks thread 1 wouldn't be able to read sharedVar until thread2 had finished writing to it.

op1 | Thread 1: Read sharedVar -> “{a,b,c}”
op2 | Thread 2: acquire lock //atomic operation
op3 | Thread 2: Start Write sharedVar <- “{x,y,z}”
op4 | Thread 1: Read sharedVar ->  (thread.sleep() – wait because obj is locked)
op5 | Thread 2: Finish Write sharedVar 
op6 | Thread 2: release lock //atomic operation
op7 | Thread 1: Read sharedVar -> “{x,y,z}” (lock is now released and this thread can continue)
op8 | Thread 1: Read sharedVar -> “{x,y,z}”

So what is wrong with locks?

Locks are exposed via convention rather than programming language construct

In the .NET framework the convention is to expose a .SyncRoot property on objects that are used across threads, however this is not always the case and many projects have their own conventions. STM.NET fixes this by introducing the atomic block:

atomic { something; something completely different; ... } 
// instead of 
lock(object.SyncRoot) { something; something completely different; ... }
// or
lock(this) { something; something completely different; ... }

Locks regions are not atomic

Atomic means that every change to objects made within a transaction occurs or none do. Consider this code:

private object lock = new Object();
private int i;
private int j;

lock (lock) {
        i++;
        j++;
        throw new SomethingIsWrongError();
}

If an exception is thrown the side effects caused by the proceeding code is not unwound, if we wanted to recover from the SomethingIsWrongError then we would have to it manually:

private object lock = new Object();
private int i;
private int j;

lock (lock) {
        try {
        i++;
        j++;
        throw new SomethingIsWrongError();
        } catch (SomethingIsWrongError e) {
            i--;
            j--;
        }
}

the above is error prone but more importantly annoying to write and pretty ugly. STM.NET lets you do the following:

   1 private int i;
   2 private int j;
   3 atomic {
   4     i++;
   5     j++;
   6     throw new SomethingIsWrongError();
   7 }

and that is it. If an exception leaves the boundary of an atomic block (i.e a transaction) then all side effects are unwound. Obviously there are certain operations where the side effect cannot be unwound:

atomic {
    x++;
    Console.WriteLine("x has been incremented"); // this will not compile
}

Because you cannot unwrite a line from the console, you are not allowed to place Console.WriteLine inside an atomic block. This will not even compile, STM.NET knows this will have a side effect because base class library methods which are not undoable are annotated with the [AtomicNotSupported] attribute. So if you write some a non-functional¹ method and you intend to use it with STM.NET then you do the same.

public class WashingMachine {
    private TimeSpan delayTimer;
    
    [AtomicNotSupported]
    public void StartCycle {
       ...
    }

    public void SetDelayTimer(TimeSpan t) {
        delayTimer = t;
    }
}

In the above class you can use the SetDelayTimer method in an atomic block but you can't use the StartCycle method. Think about how you would do that with locks - including the compile time checking? I have no idea.

More exciting attributes like [AtomicSupported] which is mostly redundant as it says that the annotated method can be used inside an atomic block; and [AtomicRequired] which says the annotated method must be used within an atomic block.

Locked regions are not isolated

Isolated means that no transaction sees the effects of any other transaction while it is running. A simple way to think of this is in database terms, when you have a long running stored procedure running on a table - it doesn't stop you from reading values out of that table while it is running. You just see the value before the stored procedure started.

Let's think about code, if a collection object needs a lock to write but not to read and I am looping over the contents of that collection then another thread updates everything in that collection. I will have a corrupted view of the world. Not consistent with the state of the objects in that collect before or after the other thread started operating on it.

In .NET collections, if you are looping over a collection and it is modified you are usually presented with an exception. With STM.NET, you continue to iterate over the collection with all objects in the same state as when you started your loop, even if it has been modified by another thread half way through. You get a consistent and valid view of the state of those objects at the time you started your loop.

Locks lead to deadlock

In advanced locking scenarios you might need to perform some operation involving two objects, let's call them obj1 and obj2. Operation1 needs to acquire a lock on obj1 then a lock on obj2. Another operation, called Operation2 needs to do something to obj2,obj1 and a new object called obj3. Operation2 acquires a lock on obj2 then on obj3 finally on obj1. If both Operation1 and Operation2 were running concurrently then one possible scenario is as follows:

Operation1: acquire lock on obj1
Operation2: acquire lock on obj3
Operation2: acquire lock on obj2
Operation1: tries to acquire lock on obj2, but is blocked
Operation2: tries to acquire lock on obj1, but is blocked

all threads are now waiting and the system is dead.

This is a common problem with a simple resolution, always acquire locks in the same order by introducing a lock-levelling strategy. This is again tedious to write by hand and has no place in high level languages like C#.

STM.NET does the right thing by default and you don't have to worry about this!

So what is the catch?

At the time of .NET Framework Beta 4 there are two issues with STM.NET, first of all it is almost completly unoptimized and is about 15x-20x slower than using locks, however a fully optimized STM.NET should only be (conservatively) 4x-5x slower than using locks. Newer hardware with support for STM is in the pipeline and if your memory/hardware² has support for STM then it might even be faster than using locks although this is still a few years off.

The second problem with STM.NET is that there is no language support yet all those lovely atomic blocks I've shown you in this article don't really exist in C# yet and for now you have to import the System.TransactionalMemory assembly and call your atomic sections through an ugly construct like this:

using System.TransactionalMemory;
class Whatever() {
    private int x, y;
    private void Whatever() 
    {
        Atomic.Do(() =>
            {
                x++;
                y++;
            }
        );
    }
}

which I guess we'll have to live with until C#5 is released.

So how does STM.NET work

The simplest way to express how it works it so say that it uses the read-copy-update pattern, sometimes called optimistic lock-free concurrency control.

In that a writer thread can write to any shared resource by copying a version of it, making required changes then updating the original object with the changes if the original has not been updated by something else in the meantime; if it has then the atomic block fails. The truth is far more nuanced than that and you'll have to read an 84 page pdf to get a good idea, but this write up is enough to explain where and why you might want to use STM in .NET.