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.

The Problems with Locking

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:

1. Locks Aren't Enforced

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.

2. Locks Don't Combine

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?

3. Locks Can Deadlock

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.

The Cliff-Hanger

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];

  }

}