Non Deadlocking Read/Write Locker and Thread-Safe Collections
A ReaderWriterLock that cannot deadlock, and thread-safe example 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
ReaderWriterLockin November of 2009. - Then it was modified to use
ReaderWriterLockSlimin March, 2010. - And lastly it was re-implemented using ReaderWriterLock Alternative, which finally exposes enough functionality I could accurately prevent deadlocks in September, 2010.