Reader-writer lock

It is very common to see samples of code where the shared state is one of the standard .NET collections: List<T> or Dictionary<K,V>. These collections are not thread safe; thus we need synchronization to organize concurrent access.

There are special concurrent collections that can be used instead of the standard list and dictionary to achieve thread safety. We will review them in Chapter 6, Using Concurrent Data Structures. For now, let us assume that we have reasons to organize concurrent access by ourselves.

The easiest way to achieve synchronization is to use the lock operator when reading and writing from these collections. However, the MSDN documentation states that if a collection is not modified while being read, synchronization is not required:

Another important MSDN page states the following regarding a collection:

This means that we can perform the read operations from multiple threads if the collection is not being modified. This allows us to avoid excessive locking, and minimizes performance overhead and possible deadlocks in such situations.

To leverage this, there is a standard .NET Framework class, System.Threading.ReaderWriterLock. It provides three types of locks: to read something from a resource, to write something, and a special one to upgrade the reader lock to a writer lock. The following method pairs represent these locks: AcquireReaderLock/ReleaseReaderLock, AcquireWriterLock/ReleaseWriterLock, and UpgradeToWriterLock/DowngradeFromWriterLock, correspondingly. It is also possible to provide a timeout value, after which the request to acquire the lock will expire. Providing the -1 value means that a lock has no timeout.

A reader lock puts a thread in the blocked state only when there is at least one writer lock acquired. Otherwise, no real thread blocking happens. A writer lock waits until every other lock is released, and then in turn it prevents the acquiring of any other locks, until it's released.

Upgrading a lock is useful; when inside an open reader lock, we need to write something into a collection. For example, we first check if there is an entry with some key in the dictionary, and insert this entry if it does not exist. Acquiring a writer lock would be inefficient, since there could be no write operation, so it is optimal to use this upgrade scenario.

Note that using any kind of lock is still not as efficient as a simple check, and it makes sense to use patterns such as double-checked locking. Consider the follow code snippet:

if(writeRequiredCondition)
{
  _rwLock.AcquireWriterLock();
  try 
  {
    if(writeRequiredCondition)
      // do write
  }
  finally
  {
    _rwLock.ReleaseWriterLock();
  }
}

The ReaderWriterLock class has a nested locks counter, and it avoids creating a new lock when trying to acquire it when inside another lock. In such a case, the lock counter is incremented and then decremented when the nested lock is released. The real lock is acquired only when this counter is equal to to 0.

Nevertheless, this implementation has some serious drawbacks. First, it uses thread blocking, which is quite performance costly, and besides that, adds its own additional overhead. In addition, if the write operation is very short, then using ReaderWriterLock could be even worse than simply locking the collection for every operation. In addition to that, the method names and semantics are not intuitive, which makes reading and understanding the code much harder.

This is the reason why the new implementation, System.Threading.ReaderWriterLockSlim, was introduced in .NET Framework 3.5. It should always be used instead of ReaderWriterLock for the following reasons:

The following is an example of different locking strategies for Dictionary<K,V> in the multiple readers / single writer scenario. First, we define how many readers and writers we're going to have, how long a read and write operation will take, and how many times to repeat those operations.

static class Program
{
  private const int _readersCount = 5;
  private const int _writersCount = 1;
  private const int _readPayload = 100;
  private const int _writePayload = 100;
  private const int _count = 100000;

Then we define the common test logic. The target dictionary is being created along with the reader and writer methods. The method called Measure uses LINQ to measure the performance of concurrent access.

private static readonly Dictionary<int, string> _map = new Dictionary<int, string>();

private static void ReaderProc()
{
  string val;
  _map.TryGetValue(Environment.TickCount % _count, out val);
  // Do some work
  Thread.SpinWait(_readPayload);
}

private static void WriterProc()
{
   var n = Environment.TickCount % _count;
   // Do some work
  Thread.SpinWait(_writePayload);
  _map[n] = n.ToString();
}

private static long Measure(Action reader, Action writer)
{
  var threads = Enumerable
      .Range(0, _readersCount)
      .Select(n => new Thread(
        () => {
          for (int i = 0; i < _count; i++)
            reader();
        }))
      .Concat(Enumerable
        .Range(0, _writersCount)
        .Select(n => new Thread(
          () => {
            for (int i = 0; i < _count; i++)
              writer();
      })))
      .ToArray();
    _map.Clear();
    var sw = Stopwatch.StartNew();
    foreach (var thread in threads)
      thread.Start();

    foreach (var thread in threads)
       thread.Join();

     sw.Stop();
    return sw.ElapsedMilliseconds;
  }

Then we use simple lock to synchronize concurrent access to the dictionary:

  private static readonly object _simpleLockLock = new object();

  private static void SimpleLockReader()
  {
    lock (_simpleLockLock)
      ReaderProc();
  }

  private static void SimpleLockWriter()
  {
    lock (_simpleLockLock)
      WriterProc();
  }

The second test is using an older ReaderWriterLock class as follows:

  private static readonly ReaderWriterLock _rwLock = new ReaderWriterLock();

  private static void RWLockReader() 
{
    _rwLock.AcquireReaderLock(-1);
    try
    {
      ReaderProc();
    }
    finally
    {
      _rwLock.ReleaseReaderLock();
    }
  }

  private static void RWLockWriter()
  {
    _rwLock.AcquireWriterLock(-1);
    try
    {
      WriterProc();
    }
    finally
    {
      _rwLock.ReleaseWriterLock();
     }
  }

Finally, we'll demonstrate the usage of ReaderWriterLockSlim:

  private static readonly ReaderWriterLockSlim _rwLockSlim = new ReaderWriterLockSlim();

  private static void RWLockSlimReader()
  {
    _rwLockSlim.EnterReadLock();
    try
    {
      ReaderProc();
    }
    finally 
    {
      _rwLockSlim.ExitReadLock();
    }
  }

  private static void RWLockSlimWriter()
  {
    _rwLockSlim.EnterWriteLock();
    try 
    {
      WriterProc();
    }
    finally 
    {
      _rwLockSlim.ExitWriteLock();
    }
  }

Now we run all of these tests, using one iteration as a warm up to exclude any first run issues that could affect the overall performance:

static void Main()
{
  // Warm up
    Measure(SimpleLockReader, SimpleLockWriter);

    // Measure
    var simpleLockTime = Measure(SimpleLockReader, SimpleLockWriter);
    Console.WriteLine("Simple lock: {0}ms", simpleLockTime);

    // Warm up
    Measure(RWLockReader, RWLockWriter);

    // Measure
    var rwLockTime = Measure(RWLockReader, RWLockWriter);
    Console.WriteLine("ReaderWriterLock: {0}ms", rwLockTime);

    // Warm up
    Measure(RWLockSlimReader, RWLockSlimWriter);

     // Measure
    var rwLockSlimTime = Measure(RWLockSlimReader, RWLockSlimWriter);
    Console.WriteLine("ReaderWriterLockSlim: {0}ms", rwLockSlimTime);
  }
}

Executing this code on Core i7 2600K and x64 OS in the Release configuration gives the following results:

Simple lock: 367ms
ReaderWriterLock: 246ms
ReaderWriterLockSlim: 183ms

It shows that ReaderWriterLockSlim is about 2 times faster than the usual lock statement.

You can change the number of reader and writer threads, tweak the lock time, and see how the performance changes in each case.