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.
public class RegularLock
{
private class LockObject : IDisposable
{
RegularLock _lock;
public LockObject(RegularLock __lock)
{
_lock = __lock;
}
public IDisposable GetLock()
{
_lock.LockFunction();
return this;
}
public void Dispose()
{
_lock.UnlockFunction();
}
}
Dictionary <int, int> ThreadsEntered = new Dictionary<int,int>();
Dictionary <int, int> ThreadsLocked = new Dictionary<int,int>();
int SuperThreadId = -1;
int SuperThreadCount = 0;
LockObject lockObj = new LockObject(this);
public IDisposable GetLock()
{
return lockObject.GetLock();
}
bool LockIsNeeded(int currentThreadId)
{
lock(ThreadsEntered)
{
lock(ThreadsLocked)
{
return SuperThreadId != currentThreadId;
}
}
}
void LockFunction()
{
Dim CurrentThreadId As Integer = Thread.CurrentThread.ManagedThreadId;
Dim CountValue As Integer
if (SuperThreadId == CurrentThreadId)
{
SuperThreadCount += 1;
}
lock(ThreadsEntered)
{
if (ThreadsEntered.TryGetValue(CurrentThreadId, CountValue))
{
ThreadsEntered(CurrentThreadId) = CountValue + 1;
} else {
ThreadsEntered.Add(CurrentThreadId, 0);
}
}
if (LockIsNeeded(CurrentThreadId))
{
lock(ThreadsLocked)
{
if (ThreadsLocked.TryGetValue(CurrentThreadId, CountValue))
{
ThreadsLocked(CurrentThreadId) = CountValue + 1;
} else {
ThreadsLocked.Add(CurrentThreadId, 0);
}
}
while (LockIsNeeded(CurrentThreadId))
{
lock(ThreadsEntered)
{
lock(ThreadsLocked)
{
if (SuperThreadId == -1 && ThreadsEntered.Count == ThreadsLocked.Count)
{
SuperThreadId = CurrentThreadId;
}
}
}
if (SuperThreadId == CurrentThreadId)
{
break;
}
Thread.Wait(6000);
}
lock(ThreadsLocked)
{
if (ThreadsLocked.TryGetValue(CurrentThreadId, CountValue))
{
if (CountValue == 0)
{
ThreadsLocked.Remove(CurrentThreadId);
} else {
ThreadsLocked(CurrentThreadId) = CountValue - 1;
}
}
}
}
}
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;
}
}
}
lock(ThreadsEntered)
{
lock(ThreadsLocked)
{
if (SuperThreadCount == 0 && SuperThreadId == CurrentThreadId)
{
SuperThreadId = -1;
}
if (SuperThreadId == CurrentThreadId)
{
SuperThreadCount -= 1;
}
}
}
}
}
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()
For Index As Integer = 0 To List.Count - 1
List(Index) += Index
Next
Using WriteLock As IDisposable = Lock.GetWriteLock()
For Index As Integer = 0 To List.Count - 1
List.Add(List(Index))
Next
End Using
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.
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);
For Each Item As Integer In List
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
While (List.Count > 17)
List.RemoveAt(List.Count)
End While
Using ReadLock As IDisposable = List.GetReadLock()
While (List.Count > 14)
List.RemoveAt(List.Count)
End While
End Using
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)
#Region "Classes"
Private Class ModificationCache
Private Enum ModificationType
Added
Removed
Cleared
End Enum
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
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)
_Items.Add(New Item(ModificationType.Added, item, -1))
End Sub
...
Public Sub Clear()
_Items.Clear()
_Items.Add(New Item(ModificationType.Cleared, Nothing, -1))
End Sub
...
End Class
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
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
Using ReadLock As IDisposable = _Locker.GetReadLock()
Return _List.Count
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
Dim ReadLock As IDisposable = _Locker.GetReadLock()
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
_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
Protected Overridable Sub OnUnlocked() _
Handles _Locker.UnlockedForReading
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.