Monthly Archives: April 2014

The power of STM semantics

Software Transactional Memory is a concept which offers many advantages when writing concurrent code. Most importantly, it removes the burden of writing correct multi-threaded code from the programmer, allowing her to focus more on the logic of the problem domain. STM will automatically take care of correctness. However, this comes with a cost – the bookkeeping. Tracking every access to a transactional field in order to properly detect and resolve conflicts introduces a cost penalty. But, at the same time, it also introduces the possibility to create and expose to the programmer some very interesting new semantics.

Shielded has for some time already contained one such semantic addition – the Shield.Conditional static method. With it one may define a transaction which should run whenever a certain condition is satisfied by the current, committed “state of the world”. By virtue of its bookkeeping, Shielded can determine the exact fields your condition depends on. This way it easily knows, when another transaction commits into one of those fields, that your condition might have changed, and will re-evaluate it. (It will even track your condition for any changes in its access pattern between calls. This is important since, due to boolean expressions’ short-circuit evaluation, it is very easy for a condition to change its access pattern, and that must be taken into account.)

This feature was inspired by the Haskell STM’s “retry” command, but it does not go as far as that. The Haskell “retry” can be called anywhere in a transaction, and it will block it until any of the fields, that it has accessed before calling retry, changes. Shielded does not do any such thing, it is a deliberate design decision to not include any threading or blocking constructs into the library. The idea is to allow Shielded to easily be combined with any such construct, depending on what the programmer wants to use, and not lock the programmer into a decision made by this library. And so, the Conditional does not even try executing straight away, but merely subscribes a transaction for future execution.

The power of Haskell’s retry and orElse can be achieved by using Reactive Extensions. Combining Shielded with Rx.NET should not be a difficult task – create an IObservable by creating a Conditional which will call methods on an IObserver (tip – make such calls to IObserver as SideEffects of the Conditional transaction, otherwise you might be triggering observers repeatedly, and with non-committed data!). Once you have such an IObservable, the powerful Rx.NET library allows you to easily create very complex time-based logic, which can easily achieve what Haskell’s “retry” and “orElse” offer, and much more. We might call the combination of these two libraries a Reactive Transactional Memory system!

A recent addition to the Shielded library is yet another powerful semantic tool – the Shield.PreCommit static method. It is very similar to Conditional, but with one very important difference – it will execute within a transaction that plans to affect its condition, and it will execute just before that transaction attempts to commit.

The PreCommit method creates a lot of interesting possibilities. For a couple of examples, have a look at the PreCommit tests. Most importantly, you get the ability to prevent the other transaction from committing. Like in the NoOdds test, for example, where a PreCommit check looks like this:

Shield.PreCommit(() => (x.Read & 1) == 1, () => {

This will cause any transaction, that tries to commit an odd number into the field x (which is a Shielded<int>, of course), to roll back and fail.

The Rollback(false) method will quietly abort the transaction, which the code that started the transaction might not expect. It would probably be better to throw an exception, like in the Validation test in the same file. It throws an exception whenever a transaction tries to commit incorrect state, thus guaranteeing that an invariant will always hold!

Last, but by far not the least, this introduces the ability to easily and arbitrarily define what Shielded has so far been missing the most – prioritization. It is often pointed out that STM allows for easy prioritization schemes to be grafted on it, completely eliminating the so-called priority inversion problem. In order to achieve this before, you would have to use the Changed event of a Shielded<> object, and prevent lower-priority transactions from committing from that event’s handler. However, this would require Shielded to expose events for any single piece of information which may be interesting. Instead, by using Shield.PreCommit, you define conditions which can depend on any piece of transaction-aware information. Then, in the PreCommit body, you may check the priority and perhaps block a transaction from committing. Here is a snippet from the above linked tests:

var x = new Shielded<int>();
int ownerThreadId = -1;
Shield.PreCommit(() => { int a = x; return true; }, () => {
    var threadId = ownerThreadId;
    if (threadId > -1 && threadId != Thread.CurrentThread.ManagedThreadId)

This is perhaps the simplest possible prioritization scheme. The condition of the PreCommit just reads the x field and returns true, meaning it will run in every transaction which makes any kind of write into x. It then checks the ownerThreadId, and if any thread has put its ManagedThreadId into that variable, then only that thread will be able to commit. All others will be repeatedly retried, until the field is released (or they stop trying to write into it). It would be possible to insert a SideEffect call before the Rollback, and have an onRollback lambda in it which would cause the thread to block until a certain signal is issued by the thread that owns the field. That would improve this simple solution to eliminate the busy waiting on non-privileged threads.

The beauty of these schemes is that, both with Conditional and PreCommit, the “other” transactions do not need to know anything about them. Their code is equal regardless of whether a conditional or pre-commit are defined or not. In the prioritization test you can see, for example, that the lower priority transactions have no knowledge about the prioritization scheme baked into them, and yet they fully comply with it.

These powerful semantics, the easily achieved composition and correctness, are arguably the biggest advantage of an STM. I believe that in a project of sufficient complexity, paying the price of STM bookkeeping is worth it.

UPDATE – After reading this post again, the problems with Shield.Rollback(false) calls started to seem a little to serious to allow, so the library no longer supports this method. Rollback receives no arguments, and will always do an immediate retry. This way, anyone can be sure that if the InTransaction method exits normally, the transaction has completed. (Of course, just because your InTransaction call returned, does not mean you are necessarily out of a transaction – nesting…)