Non Deadlocking Read/Write Locker and Thread-Safe Collections

Introduction

This is a Read-Write Locker which cannot be deadlocked. It supports intuitive upgrade locks and allows a high level of recursion. This means you no longer have to keep track of how many times and what order threads are locking a resource, greatly increasing manageability.

ReaderWriterLock Wrapper Class is a CodeProject article about wrapping the .NET ReaderWriterLock class into using disposable objects that can automatically allow upgrade locks. But it has been my experience that upgrading locks using ReaderWriterLock is not thread safe due to a bug within the class.

This class uses a locker designed from scratch to not only allow all the functionality found in ReaderWriterLock, but also perform better and handle situations where deadlocks would otherwise occur.

Understanding the Deadlock Issue

Part A

lock(A)  // 1. Thread 1 has entered, no other threads can enter lock(A)
         // in Part A or Part B.
{
   sleep(20);  // Sleeps 20 milliseconds to demonstrate race condition failing.
   lock(B)      // 3.
   {

   }
}

Part B

lock(B)  // 2. Thread 2 has entered, no other threads can enter lock(B)
         // in Part A or Part B.
{
   sleep(20);  // Sleeps 20 milliseconds to demonstrate race condition failing.
   lock(A)      // 4.
   {

   }
}

The above is pseudo-code which demonstrates how hard locking occurs. Each lock will only allow one thread to enter it. If two threads enter, the first one that enters goes through, while any other threads are paused at that locks position.

Thread 1 enters lock(A) in Part A. Then it sleeps for a short bit. Thread 2 enters lock(B) in Part B. Then it sleeps a bit too. Then at #3 in Part A, Thread 1 gets held by trying to lock on lock(B), which is already held by Thread 2. Then at #4 in Part B, Thread 2 gets held by lock(A), causing a hard lock.

The Halting Issue in Regards to Deadlocks

A common misconception is that in order to stop deadlocks, you must solve the n-complete halting issue. This is, however, wrong.

"Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable, because the halting problem can be rephrased as a deadlock scenario" - http://en.wikipedia.org/wiki/Deadlock.

This is misleading because it gives the impression that within the locking mechanism, we have no control over the condition in which halting occurs. The Halting problem states, "The proof shows there is no total computable function that decides whether an arbitrary program i halts on arbitrary input x."

Distributed deadlock prevention within the article shows that the halting issue and locking are mutually exclusive, because all conditions within it are known.

Therefore, this article and distributed deadlock prevention are in fact one possible general solution to preventing deadlock.

Quote

"If I shook a magic 8 ball with digital text that I could change after seeing the initial answer, I believe that "without-a-doubt, all signs point to yes" (given I had the room to write that)." -- TamusJRoyce.

Solving the Deadlock Issue

My solution is to allow this hard lock to almost occur. But I keep track of all threads coming in. So when the number of threads that have entered read and write locks equals the number of threads being locked (checked right before the lock occurs), I let that thread "run its course."

By run its course, I mean I track it after assigning it as a super thread. If it enters other locks while being the super thread, it blocks all other threads until this otherwise hard-locked thread is finished, and unlocks. So this hard-lock prevention scheme is recursive.

This idea had to be applied twice. Once for the read-write locker itself (Local DeadLock Prevention), and the second globally between all read-write lockers (Distributed DeadLock Prevention). Below only shows Local DeadLock Prevention for simplicity.

// Class to replace regular locks which one instance alone cannot be deadlocked.
public class RegularLock
{
  private class LockObject : IDisposable
  {
    RegularLock _lock;

    public LockObject(RegularLock __lock)
    {
      _lock = __lock;
    } // End Constructor

    public IDisposable GetLock()
    {
      // Begins locking
      _lock.LockFunction();
      return this;
    } // End GetLock() Method

    public void Dispose()
    {
      _lock.UnlockFunction();
    } // End Dispose() Method
  } // End LockObject class

  //          ManagedThreadId, Number of times each thread recursively locked.
  Dictionary <int,            int> ThreadsEntered  = new Dictionary<int,int>();

  //          ManagedThreadId, Number of times each thread recursively locked.
  Dictionary <int,             int> ThreadsLocked = new Dictionary<int,int>();

  int SuperThreadId    = -1;
  int SuperThreadCount = 0;

  LockObject lockObj = new LockObject(this);

  public IDisposable GetLock()
  {
    // Magic here is that lockObject isn't created each time it is used!
    return lockObject.GetLock();
  } // End GetLock() Method

  bool LockIsNeeded(int currentThreadId)
  {
    lock(ThreadsEntered)
    {
      lock(ThreadsLocked)
      {
        // Guarantees that a hard lock will occur.  Then lets the super thread continue.
        return SuperThreadId != currentThreadId;
      } // End lock
    } // End lock
  } // End LockIsNeeded() Function

  // This could be either read locking, write locking, or normal
  //   locking, depending on how LockIsNeeded() is setup.
  void LockFunction()
  {
    Dim CurrentThreadId As Integer = Thread.CurrentThread.ManagedThreadId;
    Dim CountValue      As Integer

    // This is part of the super thread's "Running its course."
    if (SuperThreadId == CurrentThreadId)
    {
      SuperThreadCount += 1;
    }

    lock(ThreadsEntered)
    {
      if (ThreadsEntered.TryGetValue(CurrentThreadId, CountValue))
      {
        ThreadsEntered(CurrentThreadId) = CountValue + 1;
      } else {
        ThreadsEntered.Add(CurrentThreadId, 0);
      } // End if
    } // End lock

    if (LockIsNeeded(CurrentThreadId))
    {
      lock(ThreadsLocked)
      {
        if (ThreadsLocked.TryGetValue(CurrentThreadId, CountValue))
        {
          ThreadsLocked(CurrentThreadId) = CountValue + 1;
        } else {
          ThreadsLocked.Add(CurrentThreadId, 0);
        } // End If
      } // End lock

      while (LockIsNeeded(CurrentThreadId))
      {
        lock(ThreadsEntered)
        {
          lock(ThreadsLocked)
          {
            if (SuperThreadId == -1 && ThreadsEntered.Count == ThreadsLocked.Count)
            {
              SuperThreadId = CurrentThreadId;
            } // End if
          } // End lock
        } // End lock

        if (SuperThreadId == CurrentThreadId)
        {
          break;
        } // End if

        Thread.Wait(6000);
      } // End while

      lock(ThreadsLocked)
      {
        if (ThreadsLocked.TryGetValue(CurrentThreadId, CountValue))
        {
          if (CountValue == 0)
          {
            ThreadsLocked.Remove(CurrentThreadId);
          } else {
            ThreadsLocked(CurrentThreadId) = CountValue - 1;
          } // End if
        } // End if
      } // End lock
    } // End [LockIsNeeded()] if
  } // End LockFunction() Function

  void UnlockFunction()
  {
    Dim CurrentThreadId As Integer = Thread.CurrentThread.ManagedThreadId;
    Dim CountValue        As Integer

    lock(ThreadsEntered)
    {
      if (ThreadsEntered.TryGetValue(CurrentThreadId, CountValue))
      {
        if (CountValue == 0)
        {
          ThreadsEntered.Remove(CurrentThreadId);
        } else {
          ThreadsEntered(CurrentThreadId) = CountValue - 1;
        } // End if
      } // End if
    } // End lock

    lock(ThreadsEntered)
    {
      lock(ThreadsLocked)
      {
        // Only after the super thread has ran its course is
        // another thread allowed to take its place.
        if (SuperThreadCount == 0 && SuperThreadId == CurrentThreadId)
        {
          SuperThreadId = -1;
        }

        // This is part of the super thread's "Running its course"
        if (SuperThreadId == CurrentThreadId)
        {
          SuperThreadCount -= 1;
        } // End if
      } // End lock
    } // End lock
  } // End UnlockFunction() Function
} // End class

Using the Code

The code below shows detailed methods in using this read-write locker. There are more examples to be found here.

Imports System
Imports System.Threading
Imports System.Collections.Generic

Public Module MainProgram
  Dim Lock   As New ReadWriteLocker(True)
  Dim List   As New List(Of Integer)(New Integer {0,5,0,4,0,3,0,2,0,1})
  Dim IsBusy As Integer = 0

  Public Sub main()
    InitializeThreads()
  End Sub

  Public Sub InitalizeThreads()
    For Index As Integer = 0 To 25
      Interlocked.Increment(IsBusy)
      ThreadPool.QueueUserWorkItem(FunctionToRunInMultipleThreads, Index)
    Next

    While IsBusy > 0
      Thread.Sleep(500)
    End While
  End Sub

  Public Sub FunctionToRunInMultipleThreads(threadContext As Object)
    Dim threadIndex As Integer = CInt(threadContext)
    Console.WriteLine("thread {0} started...", threadIndex);

    Using ReadLock As IDisposable = Lock.GetReadLock()
      ' Iterate through list
      For Index As Integer = 0 To List.Count - 1
        List(Index) += Index
      Next

      ' Upgrade read lock to write lock.  Yes.  It is that simple.
      Using WriteLock As IDisposable = Lock.GetWriteLock()
        For Index As Integer = 0 To List.Count - 1
          List.Add(List(Index))
        Next
      End Using

      ' Iterate through list
      For Index As Integer = 0 To List.Count - 1
        Console.WriteLine("List value: {0}, on thread {1}.", List(Index), threadIndex)
      Next
    End Using

    Interlocked.Decrement(IsBusy)
  End Sub
End Class

Replacing ReaderWriterLock

The included NHLReaderWriterLock is designed to be a drop-in replacement for .NET's ReaderWriterLock. NHLReaderWriterLock is designed for correctness by having thread-safe upgrade locks. It also performs better when deadlock prevention is turned off (comparable when it is turned on).

Other than replacing ReaderWriterLock with NHLReaderWriterLock and including this library in your projects references, no other changes need to be made.

Replacing ReaderWriterLockSlim

There is a NHLReaderWriterLockSlim included as well. But my goal with it is not to replace ReaderWriterLockSlim, but rather detect potential deadlocks so you are able to fix them. And then switch back to using ReaderWriterLockSlim.

If at some point in the future ReadWriteLocker gets setup using spin locks, helping it match ReaderWriterLockSlim's performance, then it may be a viable option towards replacing it.

Stance on Stopping all Deadlocks

Under certain circumstances, this it will in fact deadlock. But those circumstances are external to this locker. To include those, I would have to solve the n-complete halting problem to guarantee they don't cause deadlocks!

I have in no way done that. That is far above my head. But just like if you don't allow recursive locking with ReaderWriterLockSlim, you won't get deadlocks; if you do the same with this locker, you won't get deadlocks either.

I, however, have extended those circumstances to include recursion and upgrading and downgrading locks. So long as other locking mechanisms run mutually exclusive to this lock (they can be used within this lock non-recursively, but not around this lock), and each lock that gets initiated gets unlocked (and hence, no halting problem involved!), deadlocks will not happen.

Collection which Caches Changes During Enumeration

Below is the code showing a collection with the ability to choose whether it is thread-safe or not. Now why would we want to turn off thread-safety while using this locker? Because it contains events which tell us when iterating over the list completes.

So this thread-locker even with thread-safety disabled, will tell our collection when it should cache modifications, and when it should write those modifications directly to the collection. This means that you can perform a for-each on this ThreadSafeList and insert/add/change/remove/clear, it will not modify the list until after the for-each finishes.

And the same goes for multi-threaded instances where the collection is being read from. Even if writing is allowed, you may not want data changed while it is being read. This class is a good example how to setup any resource in which the resource must remain unchanged until reading is finished.

' This example is for ThreadSafeList(Of T) Collection.
Imports NoHardLockReadWriteLocker
Imports ThreadSafeClasses

Public Module MainProgram
  Public Sub main()
    InitializeThreads()
  End Sub

  // List which has thread safety turned on, and initialized to an array of integers.
  Dim List As New ThreadSafeList(Of Integer)(True, New Integer {0,5,0,4,0,3,0,2,0,1})
  Dim IsBusy As Integer = 0

  Public Sub InitalizeThreads()
    For Index As Integer = 0 To 10
      Interlocked.Increment(IsBusy)
      ThreadPool.QueueUserWorkItem(FunctionToRunInMultipleThreads, Index)
    Next

    While IsBusy > 0
      Thread.Sleep(500)
    End While
  End Sub

  Public Sub FunctionToRunInMultipleThreads(threadContext As Object)
    Dim threadIndex As Integer = CInt(threadContext)
    Console.WriteLine("thread {0} started...", threadIndex);

    ' Thread-safety does not need to be turned on for 
    ' just the modifying while enumerating.
    For Each Item As Integer In List
      ' This normally results in a enumeration error!
      List.Add(Item)

      Console.WriteLine("Value {0} found...note that items added in _
			for-each won't appear yet.", Item);
    Next

    For Each Item As Integer In List
      Console.WriteLine("Value {0} found...note that items added in _
			previous for-each appear!", Item);
    Next

    ' This is not thread-safe!  This needs a read lock wrapped around it.
    While (List.Count > 17)
      ' This can throw an error if List.Count is grabbed, an item is removed
      ' via another thread.  Then RemoveAt is called.  That position would be gone.
      List.RemoveAt(List.Count)
    End While

    ' This is thread-safe.  Notice the read lock wrapped around it.
    '
    ' But this will loop forever, because removing an item will be cached
    ' and the count will never decrease.
    Using ReadLock As IDisposable = List.GetReadLock()
      While (List.Count > 14)
        List.RemoveAt(List.Count)
      End While
    End Using

    ' This is correctly thread-safe.
    While (List.Count > 10)
      Using ReadLock As IDisposable = List.GetReadLock()
        List.RemoveAt(List.Count)
      End Using
    End While

    Interlocked.Decrement(IsBusy)
  End Sub
End Module

Below is an overview of the implementation that makes this thread-safe list work.

Imports System
Imports System.Threading
Imports System.Collections.Generic

Imports NoHardLockReadWriteLocker

Public Class ThreadSafeList(Of T)
 Implements IList(Of T)

  ' Both classes within this region are accessed within thread safe locking.
  ' Therefore, thread safety does not need to be done within them.
  #Region "Classes"
    ' This is the object that caches modifications to this collection.
    Private Class ModificationCache
      Private Enum ModificationType
        Added
        Removed
        Cleared
      End Enum

      ' This is used to tells what modification to make when applying this cache.
      Private Structure Item
        Public Type As ModificationType
        Public Item As T
        Public Index As Integer

        Public Sub New(ByVal __type As ModificationType, _
		ByVal __item As T, ByVal __index As Integer)
          Type = __type
          Item = __item
          Index = __index
        End Sub
      End Structure

      ' List to apply changes, when requested.
      Private _List As List(Of T)
      Private _Items As New List(Of Item)()

      Public Sub New(__list As List(Of T))
        _List = __list
      End Sub

      Public Sub Add(item As T)
        ' Adds a modification to the cache.
        _Items.Add(New Item(ModificationType.Added, item, -1))
      End Sub

      ...

      ' This is different than the other modification caching functions.
      '   It clears all the previously cached modifications and caches that a
      '   clear need to be performed.
      Public Sub Clear()
        _Items.Clear()
        _Items.Add(New Item(ModificationType.Cleared, Nothing, -1))
      End Sub

      ...
    End Class

    ' Wrapper around an iterator which disposes both the Iterator and ReadLock.
    Private Class ThreadSafeIterator
      Implements IEnumerator(Of T)

      Private _Iterator As IEnumerator(Of T)
      Private _ReadLock As IDisposable
      Private _IsDisposed As Boolean = False

      Public Sub New(ByVal __iterator As IEnumerator(Of T), _
		ByVal __readLockObject As IDisposable)
        _Iterator = __iterator
        _ReadLock = __readLockObject
      End Sub

      Public ReadOnly Property Current() As T _
        Implements IEnumerator(Of T).Current

        Get
          Return _Iterator.Current
        End Get
      End Property

      ...

      Public Sub Dispose()
        _Iterator.Dispose()
        _ReadLock.Dispose()
      End Sub
    End Class
  #End Region

  Private WithEvents _Locker As ReadWriteLocker
  Private _List As List(Of T)
  Private _ModificationCache As ModificationCache

  ' Thread-Safety is an option for this class. 
  ' Remember to set it to True if you need it.
  Public Sub New(Optional ByVal __isThreadSafe As Boolean = False)
    Dim List As New List(Of T)()

    _Locker = New ReadWriteLocker(__isThreadSafe)
    _List = List
    _ModificationCache = New ModificationCache(List)
  End Sub

  ...

  Public ReadOnly Property Count() As Integer _
    Implements ICollection(Of T).Count

    Get
      ' The first instance of locking so far.  As you see in the above sample,
      '   this is really meaningless in a multi-threaded environment unless
      '   you wrap your own Read Lock around this and whatever else is using Count.
      Using ReadLock As IDisposable = _Locker.GetReadLock()
        Return _List.Count

        ' Todo:  Don't Read-Lock, and throw an exception if this is called
        '        and it is not Read-Locked, and Thread-Safety is enabled!
      End Using
    End Get
  End Property

  Default Public Property Item(ByVal index As Integer) As T _
    Implements IList(Of T).Item

    Get
      Using ReadLock As IDisposable = _Locker.GetReadLock()
        Return _List.Item(index)
      End Using
    End Get
    Set(ByVal value As T)
      Using WriteLock As IDisposable = _Locker.GetWriteLock()
        If _Locker.IsReading Then
          _ModificationCache.Assign(_List(index), Value)
        Else
          _List(index) = Value
        End If
      End Using
    End Set
  End Property

  Public Function Contains(ByVal item As T) As Boolean _
    Implements ICollection(Of T).Contains

    Using ReadLock As IDisposable = _Locker.GetReadLock()
      Return _List.Contains(item)
    End Using
  End Function

  ...

  Public Function GetEnumerator() As IEnumerator(Of T) _
    Implements IEnumerable(Of T).GetEnumerator

    ' Starts Read-Locking before the ThreadSafeIterator is even made.
    Dim ReadLock As IDisposable = _Locker.GetReadLock()

    ' Returns a thread-safe iterator.
    Return New ThreadSafeIterator(_List.GetEnumerator(), ReadLock)
  End Function

  Public Sub Add(ByVal item As T) _
    Implements ICollection(Of T).Add

    Using WriteLock As IDisposable = _Locker.GetWriteLock()
      If _Locker.IsReading() Then
        ' Caching modifications if they happen while reading is occurring.
        _ModificationCache.Add(item)
      Else
        _List.Add(item)
      End If
    End Using
  End Sub

  ...

  Public Sub Clear() _
    Implements ICollection(Of T).Clear

    Using WriteLock As IDisposable = _Locker.GetWriteLock()
      If _Locker.IsReading() Then
        _ModificationCache.Clear()
      Else
        _List.Clear()
      End If
    End Using
  End Sub

  ' When iteration is complete, an event is fired that indicates
  ' a read lock has been released.
  '   When there is no more read locks, apply the changes that have been cached.
  Protected Overridable Sub OnUnlocked() _
    Handles _Locker.UnlockedForReading

    ' Doesn't raise the _Locker.UnlockedForReading event, 
    ' as write locking is being done.
    Using WriteLock As IDisposable = _Locker.GetWriteLock()
      If Not _Locker.IsReading Then
        _ModificationCache.PerformCachedModifications()
      End If
    End Using
  End Sub
End Class

History

Started off as a wrapper to ReaderWriterLock in November of 2009.
Then it was modified to use ReaderWriterLockSlim in March, 2010.
And lastly it was re-implemented using ReaderWriterLock Alternative, which finally exposes enough functionality I could accurately prevent deadlocks in September, 2010.