Click here to Skip to main content
15,867,453 members
Articles / Programming Languages / Visual Basic

Deadlocks, avoidance and detection

Rate me:
Please Sign up or sign in to vote.
4.97/5 (50 votes)
22 Sep 2013CPOL16 min read 109.3K   2.5K   66   38
Identifying, avoiding and detecting deadlocks in .NET

Introduction 

In this article I will discuss deadlocks, what they are and how they can be avoided. I will also provide a sample implementation of how to detect when a deadlock occurs in a .NET application. The article uses the Dining Philosopher problem as a basis for discussion.

Background 

Avoiding a deadlock is in theory quite simple as there are four, well defined, conditions that must all hold true simultaneously for the code to deadlock. Preventing or avoiding a single one of these conditions stops a deadlock from happening, but deadlocks are still not uncommon in production code.

In this article I will be taking a fairly academic approach and the implementations I provide to avoid the deadlock are simple and obvious, this is rarely the case in production code but for clarity I have decided to keep things cut-down. It is very possible this approach makes it harder to translate the contents of this article to a real life scenario, for that I apologize.

Using the code

There are two downloads for this article, a VB.NET version, DeadlockVB.zip, and for completeness a C# version, DeadlockCS.zip. Both downloads contain six different console applications;

  • DiningPhilosophers.Deadlock
  • DiningPhilosophers.CircularWait
  • DiningPhilosophers.HoldAndWait
  • DiningPhilosophers.MutualExclusion
  • DiningPhilosophers.NoPreemption
  • DiningPhilosophers.Detection
All of these are variations on the same console application implementation of Dining Philosophers with the first one, DiningPhilosophers.Deadlock resulting in a deadlock and the other ones either detect or prevent deadlocking by preventing one of the Coffman Conditions from being fulfilled.

Running the applications results in a whole lot of text being outputted but there's no UI implementation.

Dining Philosophers

The Dining Philosophers problem is a classic problem used in computer science to illustrate concurrency and locking problems, it was initially formulated by Edsger W. Dijkstra and Wikipedia has a detailed article on it, but in short it goes something like this;

Five philosophers are sitting in front of five plates of food, between each plate is one fork. Each philosopher needs to think and eat but to eat they need to hold two forks. Since the forks are shared between two plates a philosopher is only able to grab a fork if it is not already held by another philosopher. After eating for a while the philosophers drops the forks making them available for someone else.

A diagram of the problem shows the five philosophers and the forks (and because I can't do graphics or diagrams my forks looks like diamonds):

Image 1

As can be seen from the diagram, if the green philosopher holds fork 1 and 2, then the yellow philosopher (for example) is unable to eat as he cannot grab fork 1, only fork 5.
Such an arrangement might lead to a deadlock as each philosopher might hold one of their forks, but are unable to grab the second fork because it is already held by someone else. As all philosophers are waiting for someone else to drop a fork the system deadlocks and no philosopher will be able to grab a second fork or drop the current one they hold.

Using this problem I'll show the cause of the deadlock and by preventing the Coffman Conditions, one by one, show how the application no longer deadlocks.
But let's start at the beginning with an application that does deadlock.

DiningPhilosophers.Deadlock

The project DiningPhilosophers.Deadlock contains two main classes; Fork and Philosopher and a Program module that sets up and starts the dining.

Fork

As a Fork must be held by only one Philosopher at a time it acquires an exclusive lock by calling <a href="http://msdn.microsoft.com/en-us/library/de0542zz.aspx" title="Monitor.Enter">System.Threading.Monitor.Enter</a>(object syncRoot), this locks the Fork to the thread on which the call to Fork.Grab is made (by a Philosopher). syncRoot is owned by the Fork and is declared as Private ReadOnly syncRoot As Object = New Object().

After the Philosopher is done using the Fork it is dropped by calling Fork.Drop.
The Forks also have an internal identifier, Private ReadOnly id As Integer, this is not important to the problem but is used to identify the Forks making it is easier to see what's going on.

The Fork class looks like this;

VB.NET
Imports System.Threading

Public Class Fork
  Private Shared idCounter As Integer
  Private ReadOnly id As Integer
  Private ReadOnly syncRoot As Object = New Object()

  Public Sub New()
    idCounter = idCounter + 1
    id = idCounter
  End Sub

  Public Overrides Function ToString() As String
    Return Convert.ToString(id)
  End Function

  Public Sub Grab()
    Monitor.Enter(syncRoot)
  End Sub

  Public Sub Drop()
    Monitor.Exit(syncRoot)
  End Sub
End Class

Philosopher

The Philosopher class takes a name and two Forks in it's constructor, it then uses the Forks in it's Philosopher.Dine method to implement the problem scenario.

A Philosopher starts dining when Philosopher.Start is called, this method creates a new System.Threading.Tasks.Task that runs the Dine method. It is important that this runs on a thread different than the threads that run the other Philosopher's Dine method as it's impossible to get into a deadlock situation on a single thread.

The Philosopher.Dine method is just a loop that tries to grab the first Fork, then grab the second Fork and then drop them;

VB.NET
Public Sub Dine()
  While dining
    Console.WriteLine("{0} is trying to grab fork {1}", name, left)
    left.Grab()
    Console.WriteLine("{0} grabbed fork {1}, trying to grab fork {2}", name, left, right)
    right.Grab()
    Console.WriteLine("{0} grabbed fork {1}, thinking for a bit", name, right)
    left.Drop()
    right.Drop()
    Console.WriteLine("{0} dropped both forks", name)
  End While
End Sub

The part where the Philosopher thinks is essentially just the statement that outputs that the Philosopher is thinking for a bit. This illustrates and important point; it's not required to have long running or complex processing inside locked regions for a deadlock to occur, all it takes is the concurrent nature of multiple threads (or processes) and exclusive locking of resources.

This loop will run until someone call StopDining, or indeed until it deadlocks.
The full listing for the Philosopher class looks like this;

VB.NET
Public Class Philosopher

  Private ReadOnly name As String
  Private ReadOnly left As Fork
  Private ReadOnly right As Fork

  Private dining As Boolean

  Public Sub New(name As String, left As Fork, right As Fork)
    If name Is Nothing Then Throw New ArgumentNullException("name")
    If left Is Nothing Then Throw New ArgumentNullException("left")
    If right Is Nothing Then Throw New ArgumentNullException("right")

    Me.name = name
    Me.left = left
    Me.right = right
  End Sub

  Public Sub Dine()
    While dining
    Console.WriteLine("{0} is trying to grab fork {1}", name, left)
    left.Grab()
    Console.WriteLine("{0} grabbed fork {1}, trying to grab fork {2}", name, left, right)
    right.Grab()
    Console.WriteLine("{0} grabbed fork {1}, thinking for a bit", name, right)
    left.Drop()
    right.Drop()
    Console.WriteLine("{0} dropped both forks", name)
    End While
  End Sub

  Public Function Start() As Task
    If dining Then Throw New InvalidOperationException("Cannot start dining when already dining.")

    dining = True
    Return Task.Factory.StartNew(AddressOf Dine)
  End Function

  Public Sub StopDining()
    If Not dining Then Throw New InvalidOperationException("Cannot stop dining when not already dining.")

    dining = False
  End Sub
End Class

Setting up the scenario

The Program module sets up five Forks and five Philosophers and distributes the Forks between the Philosophers.
It then calls Philosopher.StartDining on all Philosophers and runs the scenario until a deadlock occurs. The Philosophers output to the console what they're doing and when the output stops scrolling, that's when it's deadlocked.

Image 2

In the image above the DiningPhilosophers.Deadlock project has deadlocked, and it is clear that all five philosophers are waiting for a Fork that is already taken.

The scenario is set up in Program and it looks like this;

VB.NET
Module Program
  ''' <summary>
  ''' This program is expected to dead lock.
  '''
  </summary>
  Sub Main()
    ' Setup five forks
    Dim fa = New Fork()
    Dim fb = New Fork()
    Dim fc = New Fork()
    Dim fd = New Fork()
    Dim fe = New Fork()

    Dim philosopherA = New Philosopher("Aristotle", fa, fb)
    Dim philosopherB = New Philosopher("Plato", fb, fc)
    Dim philosopherC = New Philosopher("Paul of Tarsus", fc, fd)
    Dim philosopherD = New Philosopher("Rene Descartes", fd, fe)
    Dim philosopherE = New Philosopher("Confucius", fe, fa)

    philosopherA.Start()
    philosopherB.Start()
    philosopherC.Start()
    philosopherD.Start()
    philosopherE.Start()

    Console.ReadLine()
  End Sub
End Module

Simple, create 5 Forks, create 5 Philosophers that use the Forks and start the dining.

So now we have an application that lock up after a little while and it's time to start looking at possible solutions by going through the four Coffman Conditions and violating them by changing the implementation in such a way that a single of the conditions no longer holds true.

Mutual Exclusion

At least two resources must be non-shareable. Only one process can use the resource at any given instant of time.

Mutual Exclusion means that there must exist resources that consumers require but cannot use at the same time, in Dining Philosophers this is of course the Forks, in a real life application it's likely not to be a fork implementation and can be something like a database table or a file etc.
Note that non-sharable here does not mean that two consumers cannot use the same resource, it only means that they cannot use the same resource at the same time.

If a way can be found to negate the Mutual Exclusion condition then a deadlock cannot occur, one way to achieve this is to saturate the system with enough resources for no contention to take place. In the DiningPhilosophers.MutualExclusion project the Fork and Philosopher classes are unchanged compared to the implementation in DiningPhilosophers.Deadlock, instead, the only changes made are in Program and the setup of the scenario.

There are essentially two ways of violating the Mutual Exclusion condition; make the resources shareable or make sure they don't need to be shared and I've opted for the latter of these two. By providing two Forks for every Philosopher there is no longer possible to get into a state where one Philosopher is waiting for anothers Fork as there are always Forks available.

The setup looks like this;

VB.NET
Module Program

  Sub Main()
    ' Setup ten forks
    Dim fa1 = New Fork()
    Dim fa2 = New Fork()
    Dim fb1 = New Fork()
    Dim fb2 = New Fork()
    Dim fc1 = New Fork()
    Dim fc2 = New Fork()
    Dim fd1 = New Fork()
    Dim fd2 = New Fork()
    Dim fe1 = New Fork()
    Dim fe2 = New Fork()

    Dim philosopherA = New Philosopher("Aristotle", fa1, fa2)
    Dim philosopherB = New Philosopher("Plato", fb1, fb2)
    Dim philosopherC = New Philosopher("Paul of Tarsus", fc1, fc2)
    Dim philosopherD = New Philosopher("Rene Descartes", fd1, fd2)
    Dim philosopherE = New Philosopher("Confucius", fe1, fe2)

    philosopherA.Start()
    philosopherB.Start()
    philosopherC.Start()
    philosopherD.Start()
    philosopherE.Start()

    Console.ReadLine()
  End Sub

End Module

Running that program does not deadlock and it was very easy to implement the change, but in an actual application it is usually very difficult to just double up on the resources so this approach in unlikely to be that useful. If an application deadlocks when accessing the database, for example, one cannot simply add more tables to get rid of the deadlock as that leads to all sorts of other issues.

Hold and Wait

A process is currently holding at least one resource and requesting additional resources which are being held by other processes.

Hold and Wait occurs in the Dining Philosophers problem when a Philosopher holds one of his Forks and are trying to grab the second one whilst this is still held by another Philosopher. The Philosopher Holds one Fork and Waits for the next to be available.

One way to violate this condition could be to check if the second Fork that the Philosopher is trying to grab is already held, and if so drop the first Fork instead of waiting for the second whilst still holding the first.

In project DiningPhilosophers.HoldAndWait I have decided to solve this one in a different way; a new syncRoot object was added as a Shared member to the Philosopher class and the call to Fork.Grab is done within a SyncLock scope;

VB.NET
Public Class Philosopher

  ' Shared by all philosophers, makes grabbing two forks an atomic action
  Private Shared ReadOnly SyncRoot As Object = New Object()

  Private ReadOnly name As String
  Private ReadOnly left As Fork
  Private ReadOnly right As Fork

  Private dining As Boolean

  Public Sub New(name As String, left As Fork, right As Fork)
    If name Is Nothing Then Throw New ArgumentNullException("name")
    If left Is Nothing Then Throw New ArgumentNullException("left")
    If right Is Nothing Then Throw New ArgumentNullException("right")

    Me.name = name
    Me.left = left
    Me.right = right
  End Sub

  Public Sub Dine()
    While dining
      Console.WriteLine("{0} is trying to grab fork {1}", name, left)
      SyncLock SyncRoot
      left.Grab()
      Console.WriteLine("{0} grabbed fork {1}, trying to grab fork {2}", name, left, right)
      right.Grab()
      Console.WriteLine("{0} grabbed fork {1}, thinking for a bit", name, right)
      End SyncLock

      left.Drop()
      right.Drop()
      Console.WriteLine("{0} dropped both forks", name)
    End While
  End Sub

  Public Function Start() As Task
    If dining Then Throw New InvalidOperationException("Cannot start dining when already dining.")

    dining = True
    Return Task.Factory.StartNew(AddressOf Dine)
    End Function

  Public Sub StopDining()
    If Not dining Then Throw New InvalidOperationException("Cannot stop dining when not already dining.")

    dining = False
  End Sub

End Class

Doing this turns the act of grabbing the Forks into an atomic action, it's impossible to aquire one without being guaranteed exclusive access to the other and this prevents the application from deadlocking. This approach is slightly more applicable to an actual application, but there are many situations where this is difficult to achieve as well.

The observant reader will have noticed that a more optimized solution would have had syncRoots that are shared between Philosophers that share Forks, for brevity I've left implementing that out.

No Preemption

The operating system must not de-allocate resources once they have been allocated; they must be released by the holding process voluntarily.

This condition simply states that resources cannot be stolen. If Philosopher A wants to grab a Fork held by Philosopher B then he must simply wait, there is no way for A to force B to release it.

By allowing Forks to be stolen project DiningPhilosophers.NoPreemption prevents deadlocking.

Stealing a held resource is somewhat complicated if transactional integrity must be maintained, but in the sample application this is not a concern. The Fork class has an additional method, Steal that will cause the owning thread to abort. As the Philosopher who owned the Fork has his thread aborted he catches that exception (ThreadAbortException) and Fork.Drops both his Forks as well as reset the thread abort so that he can continue dining.

If you put a breakpoint in the catch-statement that detects the Fork being stolen it might look something like this;

Image 3

This approach, while it is working, is not recommended. There are very few scenarios where one can get predictable results after calling Thread.Abort and it should be avoided when possible to do so. The reason for this is that there's no way of knowing exactly when the ThreadAbortException will be thrown so it is unknown where in the processing the thread aborted.

The Fork class that allows stealing looks like this;

VB.NET
Imports System.Threading

Public Class Fork

  Private Shared idCounter As Integer
  Private ReadOnly id As Integer
  Private ReadOnly syncRoot As Object = New Object()

  Private owner As Thread

  Public Sub New()
    idCounter = idCounter + 1
    id = idCounter
  End Sub

  Public Overrides Function ToString() As String
    Return Convert.ToString(id)
  End Function

  Public Function Grab() As Boolean
    Dim entered = Monitor.TryEnter(syncRoot)
    If entered Then owner = Thread.CurrentThread

    Return entered
  End Function

  Public Sub Steal()
    If Not owner Is Nothing Then owner.Abort()

    Monitor.Enter(syncRoot)
    owner = Thread.CurrentThread
  End Sub

  Public Sub Drop()
    If Monitor.IsEntered(syncRoot) Then Monitor.Exit(syncRoot)
  End Sub

End Class

The changes to Philosopher that allows it to detect a Fork being stolen and recovering from it looks like this;

VB.NET
Imports System.Threading

  Public Class Philosopher

  Private ReadOnly name As String
  Private ReadOnly left As Fork
  Private ReadOnly right As Fork

  Private dining As Boolean

  Public Sub New(name As String, left As Fork, right As Fork)
    If name Is Nothing Then Throw New ArgumentNullException("name")
    If left Is Nothing Then Throw New ArgumentNullException("left")
    If right Is Nothing Then Throw New ArgumentNullException("right")

    Me.name = name
    Me.left = left
    Me.right = right
  End Sub

  Public Sub Dine()
    While dining
      Try
        Console.WriteLine("{0} is trying to grab fork {1}", name, left)
        If Not left.Grab() Then left.Steal()
        Console.WriteLine("{0} grabbed fork {1}, trying to grab fork {2}", name, left, right)
        If Not right.Grab() Then right.Steal()
        Console.WriteLine("{0} grabbed fork {1}, thinking for a bit", name, right)
      Catch ex As ThreadAbortException
        Console.WriteLine("Someone stole a fork from {0}, dropping other fork as well", name)
        Thread.ResetAbort()
      Finally
        left.Drop()
        right.Drop()
        Console.WriteLine("{0} dropped both forks", name)
      End Try
    End While
  End Sub

  Public Function Start() As Task
    If dining Then Throw New InvalidOperationException("Cannot start dining when already dining.")

    dining = True
    Return Task.Factory.StartNew(AddressOf Dine)
  End Function

  Public Sub StopDining()
    If Not dining Then Throw New InvalidOperationException("Cannot stop dining when not already dining.")

   dining = False
  End Sub

End Class

Circular Wait

A process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, P = {P1, P2, ..., PN}, such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3 and so on until PN is waiting for a resource held by P1.

The Circular Wait condition states that if the order in which resources are grabbed is such that a circular graph can exist, then a deadlock can occur. In the deadlocking sample application DiningPhilosophers.Deadlock the Forks are grabbed in what can be a circular order:

  • Aristotle tries to grab Fork 1 then Fork 2.
  • Plato tries to grab Fork 2 then Fork 3.
  • Paul of Tarsus tries to grab Fork 3 then Fork 4.
  • Rene Descartes tries to grab Fork 4 then Fork 5.
  • Confucius tries to grab Fork 5 then Fork 1.
As this forms a circular chain the Circular Wait condition is fulfilled and the application can deadlock.

Simply put, if the resources in a system can be numbered (by some arbitrary number) then make sure you grab the resources in order. In the sequence above Confucius grabs 5 before 1 which is, well, out of order.

To violate this condition the only thing that needs to change is the setup, or Program module, and it's a one line change. By changing the order of the Forks passed to Confucius from;

VB.NET
Dim philosopherE = New Philosopher("Confucius", fe, fa)
to
VB.NET
Dim philosopherE = New Philosopher("Confucius", fa, fe)
no circular graph can be created and the deadlock is no longer possible.

Making sure resources are aquired in order and always in that order is a common way employed to prevent deadlocking while hitting database tables.

Detection

Another way of dealing with deadlocks that falls outside of violating the Coffman Conditions is to detect when a deadlock occurs and then take some action to resolve it. This is an approach taken by some databases for example, where the deadlock is detected and one of the processes involved is selected for eviction (see Avoiding Database Deadlocks).

The approach is somewhat cumbersome as there is no built-in way of detecting deadlock in .NET and it has to be either hand-rolled or delegated to some third-party library. In both cases it's likely that it will affect not only the way exclusive locks are acquired but also the performance of acquiring them.

In the downloadable solutions there is a project called DiningPhilosophers.Detection that depends on Bornander.Locking (also included in the solutions), and that project illustrates using detection by implementing a custom lock mechanism based upon the standard Monitor class.

My Bornander.Locking library includes a class called CheckedLock which is intended to replace the SyncLock scopes normally employed to aquire a lock and it implements IDisposable so that it can be used as a scope in the same manner using the Using keyword. The internals of CheckedLock uses a module called LockManager to aquire and release the locks and that allows LockManager to build up a graph of all the locks aquired and which thread that owns them. It also tracks which thread is waiting for which lock.

By checking the graph whenever a new request to aquire a lock is received by LockManager it is possible for LockManager to detect when a deadlock would occur. When a would-be deadlock is detected the LockManager throws a DeadLockException instead of calling Monitor.Enter to aquire the lock. By doing so the calling code has a chance to handle this exception and react to it.

The CheckedLock class is implemented like this;

VB.NET
Public NotInheritable Class CheckedLock : Implements IDisposable

  Private ReadOnly syncRoot As Object
  Private ReadOnly timeout As TimeSpan

  Private disposed As Boolean

  Public Sub New(syncRoot As Object, timeout As TimeSpan)
    If syncRoot Is Nothing Then Throw New ArgumentNullException("syncRoot")

    Me.syncRoot = syncRoot
    Me.timeout = timeout

    LockManager.Aquire(Me)
  End Sub

  Public Sub New(syncRoot As Object)
   Me.New(syncRoot, System.Threading.Timeout.InfiniteTimeSpan)
  End Sub

  Public Overrides Function ToString() As String
    Return syncRoot.ToString()
  End Function

  Public Overrides Function Equals(obj As Object) As Boolean
    Dim other As CheckedLock = TryCast(obj, CheckedLock)
    Return (Not other Is Nothing) And Object.ReferenceEquals(syncRoot, other.syncRoot)
  End Function

  Public Overrides Function GetHashCode() As Integer
   Return syncRoot.GetHashCode()
  End Function

  Public Sub Dispose() Implements IDisposable.Dispose
    If disposed Then Return

    disposed = True
    LockManager.Release(Me)
  End Sub

  Friend ReadOnly Property LockSyncRoot As Object
    Get
     Return syncRoot
    End Get
  End Property

  Friend ReadOnly Property LockTimeout As Object
    Get
      Return timeout
    End Get
  End Property

End Class

The logic for detecting a deadlock in LockManger uses a class representing a node in the lock-graph called GraphNode that wraps up the identity of who's holding a lock and who's requesting that lock. LockManager is implemented like this;

VB.NET
Imports System.Threading

Friend Module LockManager

  Private ReadOnly syncRoot As Object = New Object()
  Private ReadOnly pendingLocks As HashSet(Of LockInstance) = New HashSet(Of LockInstance)
  Private ReadOnly heldLocks As HashSet(Of LockInstance) = New HashSet(Of LockInstance)

  Friend Sub Aquire(lock As CheckedLock)

    Dim instance = New LockInstance(lock)
    Dim heldInstance As LockInstance

    SyncLock syncRoot
      heldInstance = heldLocks.SingleOrDefault(Function(li) li.CheckedLock.Equals(lock))

      ' Lock held and it's not by the current thread
      If (Not heldInstance Is Nothing) Then
        If Thread.CurrentThread.ManagedThreadId <> heldInstance.ThreadId Then
          pendingLocks.Add(instance)
          Dim lockStack = New Stack(Of GraphNode)
          lockStack.Push(New GraphNode(heldInstance, instance))
          TraverseLockGraph(heldInstance, lockStack)
        End If
      End If

    End SyncLock

    ' TODO: CHECK: Can the lack of internal syncRoot here result in race-condition?
    Dim entered = Monitor.TryEnter(lock.LockSyncRoot, lock.LockTimeout)
    SyncLock syncRoot
      pendingLocks.Remove(instance)
      If entered Then
        If Not heldInstance Is Nothing Then
          If heldInstance.ThreadId = Thread.CurrentThread.ManagedThreadId Then
            heldInstance.Reenter()
            Return ' No need to add it to the held list as it's already there
          End If
        End If

        heldLocks.Add(instance)
      Else
        ' Timed out trying to enter the monitor
        Throw New TimeoutException(instance, heldInstance)
      End If
    End SyncLock
  End Sub

  Private Sub TraverseLockGraph(heldInstance As LockInstance, lockStack As Stack(Of GraphNode))
   For Each pending In pendingLocks.Where(Function(pl) pl.ThreadId = heldInstance.ThreadId)
      Dim held = heldLocks.SingleOrDefault(Function(hl) Object.ReferenceEquals(hl.CheckedLock.LockSyncRoot, pending.CheckedLock.LockSyncRoot))
      If Not held Is Nothing Then
        lockStack.Push(New GraphNode(held, pending))
        If held.ThreadId = Thread.CurrentThread.ManagedThreadId Then
          Throw New DeadlockException(lockStack.Reverse())
        Else
          TraverseLockGraph(held, lockStack)
        End If
        lockStack.Pop()
      End If
    Next
  End Sub

  Friend Sub Release(lock As CheckedLock)
    SyncLock syncRoot
      Dim heldInstance = heldLocks.Single(Function(li) Object.ReferenceEquals(li.CheckedLock.LockSyncRoot, lock.LockSyncRoot))
      If heldInstance.DoExit() Then
        heldLocks.Remove(heldInstance)
      End If

      Monitor.Exit(lock.LockSyncRoot)
    End SyncLock
  End Sub

End Module
   

The CheckedLock class is used by the Fork class in DiningPhilosophers.Detection like this;

VB.NET
Imports System.Threading
Imports Bornander.Locking

Public Class Fork

  Private Shared idCounter As Integer
  Private ReadOnly id As Integer
  Private ReadOnly syncRoot As Object = New Object()

  Private lockWrapper As CheckedLock

  Public Sub New()
    idCounter = idCounter + 1
    id = idCounter
    syncRoot = Convert.ToString(id)
  End Sub

  Public Overrides Function ToString() As String
   Return Convert.ToString(id)
  End Function

  Public Sub Grab()
   lockWrapper = New CheckedLock(syncRoot)
  End Sub

  Public Sub Drop()
   lockWrapper.Dispose()
  End Sub

End Class

Note:
While this approach of dealing with deadlocks technically works it is not one that I would recommend. It suffers from the same problem as the No Preemption solution where the thread is aborted in order to steal the lock; the point where the deadlock is detected is unknown and because of this predictable results are hard to come by. Yes, the deadlock is guaranteed to happen at the aquiring of a lock but if a thread needs to grab 15 locks it also needs to be able to handle the deadlock situation in all of those 15 places. It makes for convoluted code and it is not a good solution I feel.

Points of Interest

Avoiding deadlocks in complex applications can be hard, even if in theory one only needs to remember one of the Coffman Conditions. I think one of the reasons for this is that applications grow over time in unexpected directions and that makes it hard for developers to gain the overall picture required to see the how the Coffman Conditions are upheld.

There are a few tips one can follow to avoid dead locks;

  • Never lock on public members
    This includes locking on Me (this in C#) or on GetType(SomeType) (or typeof(SomeType) in C#). Locking on public members means that you are not alone in deciding when the lock will be aquired, and that means there might be some other place that you are unaware of that is also locking on the same thing.
  • Be verbose with concurrency
    If calling a method on your class spawns a new thread make sure the caller is aware of this. One way of doing that is returning the spawned Task or a WaitHandle that sets when the thread is done.
    If callers are aware of the concurrency incurred they're more likely to take precautions to avoid threading issues such as deadlocks.
  • Always order the resources and aquire them in order
    Doing this prevents the Circular Wait condition and it is probably one of the easiest ways to prevent a deadlock that is feasable in practice.
    Note that this can be achieved on-the-fly even if the actual resources are unknown at compile time as long as there is some way of ordering the resources, as desribed here in the Avoiding deadlock with arbitrary locks section.
  • Never call Overridable (virtual in C#) methods if you're currently holding a lock
    The reason for this is that if a sub class that overrides the method decides to grab a lock you might end up in a deadlock that you did not see coming as one rarely has control over all sub-classes.
    It is also a good idea to avoid firing events whilst holding a lock, the reason for this is that the class firing the event has little control over what locks the listener of the event will take in their event handler. 
  • Put the test effort in
    Deadlocks are annoying in the way they don't always kick in when running an application as they may depend on timing and race conditions. By making sure you test (preferrably through unit testing) for all locking scenarios the offending code can be identified early.
    Having said that, this type of testing is usually more difficult that verifying the result of something like Math.Abs and requires a bit of practice to get right I think.
  • Keep an open mind
    Deadlocks are creative and can strike where you least expect it, keep an open mind and be vigilant when implementing concurrent systems that aquire exclusive locks.
    Eric Lippert has a great blog-post on The no-lock deadlock which highlights some of the sneaky ways deadlocks can attack your code (sorry for not converting this to VB.NET for you):
    C#
    class C
    {
      static C() 
      {
        // Let's run the initialization on another thread!
        var thread = new System.Threading.Thread(Initialize);
        thread.Start();
        thread.Join();
      }
      static void Initialize() { }
      static void Main() { }
    }
    Whilst this example is obviously a bit contrived it still illustrates the point I think.

History

2013-09-15 : First version
2013-09-23 : Second version, fixed typos, added note on firing events and included Lippert's snippet.  

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
Sweden Sweden
Article videos
Oakmead Apps Android Games

21 Feb 2014: Best VB.NET Article of January 2014 - Second Prize
18 Oct 2013: Best VB.NET article of September 2013
23 Jun 2012: Best C++ article of May 2012
20 Apr 2012: Best VB.NET article of March 2012
22 Feb 2010: Best overall article of January 2010
22 Feb 2010: Best C# article of January 2010

Comments and Discussions

 
Questionhow to run this project? Pin
Member 142085581-Apr-19 20:54
Member 142085581-Apr-19 20:54 
QuestionDeadlockCS.zip does not have any code files Pin
Shanmugam R P3-May-18 0:54
Shanmugam R P3-May-18 0:54 
GeneralMy vote of 5 Pin
darkliahos19-Feb-16 3:09
darkliahos19-Feb-16 3:09 
GeneralRe: My vote of 5 Pin
Fredrik Bornander20-Feb-16 4:47
professionalFredrik Bornander20-Feb-16 4:47 
GeneralMy vote of 5 Pin
jamicore16-Jul-14 11:56
jamicore16-Jul-14 11:56 
AnswerRe: My vote of 5 Pin
Fredrik Bornander22-Jul-14 10:25
professionalFredrik Bornander22-Jul-14 10:25 
Questionvery nice Pin
BillW339-Oct-13 10:28
professionalBillW339-Oct-13 10:28 
AnswerRe: very nice Pin
Fredrik Bornander9-Oct-13 19:39
professionalFredrik Bornander9-Oct-13 19:39 
GeneralMy vote of 5 Pin
Shmuel Zang30-Sep-13 20:15
Shmuel Zang30-Sep-13 20:15 
GeneralRe: My vote of 5 Pin
Fredrik Bornander30-Sep-13 21:16
professionalFredrik Bornander30-Sep-13 21:16 
GeneralMy vote of 5 Pin
GregoryW20-Sep-13 1:44
GregoryW20-Sep-13 1:44 
Such a great article. Added to my fav, thanks!
GeneralRe: My vote of 5 Pin
Fredrik Bornander20-Sep-13 1:59
professionalFredrik Bornander20-Sep-13 1:59 
GeneralRe: My vote of 5 Pin
GregoryW20-Sep-13 2:11
GregoryW20-Sep-13 2:11 
GeneralMy vote of 5 Pin
Rob Philpott19-Sep-13 1:40
Rob Philpott19-Sep-13 1:40 
GeneralRe: My vote of 5 Pin
Fredrik Bornander19-Sep-13 2:02
professionalFredrik Bornander19-Sep-13 2:02 
GeneralMy vote of 5 Pin
fixthebugg18-Sep-13 4:25
fixthebugg18-Sep-13 4:25 
GeneralRe: My vote of 5 Pin
Fredrik Bornander18-Sep-13 6:32
professionalFredrik Bornander18-Sep-13 6:32 
GeneralMy vote of 5 Pin
Monte Christo18-Sep-13 1:12
professionalMonte Christo18-Sep-13 1:12 
GeneralRe: My vote of 5 Pin
Fredrik Bornander18-Sep-13 1:45
professionalFredrik Bornander18-Sep-13 1:45 
QuestionMy vote of 5 Pin
Kenneth Haugland17-Sep-13 20:14
mvaKenneth Haugland17-Sep-13 20:14 
AnswerRe: My vote of 5 Pin
Fredrik Bornander17-Sep-13 20:41
professionalFredrik Bornander17-Sep-13 20:41 
GeneralMy vote of 5 Pin
rspercy6517-Sep-13 12:33
rspercy6517-Sep-13 12:33 
GeneralRe: My vote of 5 Pin
Fredrik Bornander17-Sep-13 18:56
professionalFredrik Bornander17-Sep-13 18:56 
GeneralMy vote of 5 Pin
fredatcodeproject17-Sep-13 1:20
professionalfredatcodeproject17-Sep-13 1:20 
GeneralRe: My vote of 5 Pin
Fredrik Bornander17-Sep-13 1:36
professionalFredrik Bornander17-Sep-13 1:36 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.