Deadlocks

The second major problem of multi-threading is that of deadlocks. Simply put, this is when two threads each hold a monitor that the other one wants. Each blocks, waiting for the monitor that it's waiting for to be released - and so the monitors are never released, and the application hangs (or at least those threads involved in the deadlock hang).

Here's an example of a program exhibiting deadlock:

using System;
using System.Threading;

public class Test
{
                  static readonly object firstLock = new object();
                  static readonly object secondLock = new object();
    
                  static void Main()
    {
                  new Thread(new ThreadStart(ThreadJob)).Start();
        
                  // Wait until we're fairly sure the other thread
                  // has grabbed firstLock
        Thread.Sleep(500);
        
        Console.WriteLine ("Locking secondLock");
                  lock (secondLock)
        {
            Console.WriteLine ("Locked secondLock");
            Console.WriteLine ("Locking firstLock");
                  lock (firstLock)
            {
                Console.WriteLine ("Locked firstLock");
            }
            Console.WriteLine ("Released firstLock");
        }
        Console.WriteLine("Released secondLock");
    }
    
                  static void ThreadJob()
    {
        Console.WriteLine ("\t\t\t\tLocking firstLock");
                  lock (firstLock)
        {
            Console.WriteLine("\t\t\t\tLocked firstLock");
                  // Wait until we're fairly sure the first thread
                  // has grabbed secondLock
            Thread.Sleep(1000);
            Console.WriteLine("\t\t\t\tLocking secondLock");
                  lock (secondLock)
            {
                Console.WriteLine("\t\t\t\tLocked secondLock");
            }
            Console.WriteLine ("\t\t\t\tReleased secondLock");
        }
        Console.WriteLine("\t\t\t\tReleased firstLock");
    }
}

And the results:

  
                                Locking firstLock
                                Locked firstLock
Locking secondLock
Locked secondLock
Locking firstLock
                                Locking secondLock

(You'll need to hit Ctrl-C or something similar to kill the program.) As you can see, each thread grabs one lock and then tries to grab the other. The calls to Thread.Sleep have been engineered so that they will try to do so at inopportune times, and deadlock.

Deadlocks can be a real pain in the neck to debug - they're hard to diagnose, they can crop up seemingly randomly (i.e. they're hard to reproduce) and once you've found out why there's a deadlock, it's not always obvious what the best course of action is. Locking strategies always need to be treated very carefully; you can't just start removing all the lock statements from your code, or you'll end up with data races etc.

The solution (which is easier to describe than to achieve) is to make sure that you always take out locks in the same order: in the code above, you might decide to never acquire secondLock unless you already had firstLock. Within one class, it's relatively straightforward to achieve this. It's when you have calls between classes (including delegates, where you don't really know what you're calling) that things get somewhat hairy. If possible, you should avoid making method calls outside your own class within a lock, unless you know pretty definitely that that method won't itself need to lock anything.

More Monitor methods

If you looked at the documentation for Monitor.Enter and Monitor.Exit, you will no doubt have seen that there are various other methods in the Monitor class, all of which can be useful at different times.

Monitor.TryEnter is the easiest one to describe - it simply attempts to acquire a lock, but doesn't block (or only blocks for a given period of time) if the lock cannot be acquired.

The other methods (Wait, Pulse and PulseAll) all go together. They're used to signal between threads. The idea is that one thread calls Wait, which makes it block until another thread calls Pulse or PulseAll. The difference between Pulse and PulseAll is how many threads are woken up: Pulse only wakes up a single waiting thread; PulseAll wakes up all threads waiting on that monitor. That doesn't mean they'll all instantly start running, however: in order to call any of these three methods, the thread has to own the monitor of the object reference it passes in as a parameter. When calling Wait, the monitor is released, but then needs to be reacquired before the thread will actually run. This means blocking again until the thread which calls Pulse or PulseAll releases the monitor (which it must have in order to pulse the monitor in the first place) - and if multiple threads are woken up, they'll all try to acquire the monitor, which only one can have at a time, of course. Just to repeat: calling Wait unlocks the monitor you're waiting on . This is an important point, because otherwise the code looks like it'll just deadlock!

The most common use of these methods is in producer/consumer relationships, where one thread is putting work items on a queue, and another thread is taking them off. The consumer thread typically takes items off the list until it's empty, then waits on a lock. The producer thread pulses the lock when it adds an item to the list (or, if you're worried about efficiency, it can pulse the lock only when it adds an item to a previously-empty list). Here's a sample:

using System;
using System.Collections;
using System.Threading;

public class Test
{
                  static ProducerConsumer queue;
    
                  static void Main()
    {
        queue = new ProducerConsumer();
                  new Thread(new ThreadStart(ConsumerJob)).Start();
        
        Random rng = new Random(0);
                  for (int i=0; i < 10; i++)
        {
            Console.WriteLine ("Producing {0}", i);
            queue.Produce(i);
            Thread.Sleep(rng.Next(1000));
        }
    }
    
                  static void ConsumerJob()
    {
                  // Make sure we get a different random seed from the
                  // first thread
        Random rng = new Random(1);
                  // We happen to know we've only got 10 
                  // items to receive
                  for (int i=0; i < 10; i++)
        {
                  object o = queue.Consume();
            Console.WriteLine ("\t\t\t\tConsuming {0}", o);
            Thread.Sleep(rng.Next(1000));
        }
    }
}

public class ProducerConsumer
{
                  readonly object listLock = new object();
    Queue queue = new Queue();

                  public void Produce(object o)
    {
                  lock (listLock)
        {
            queue.Enqueue(o);

                  // We always need to pulse, even if the queue wasn't
                  // empty before. Otherwise, if we add several items
                  // in quick succession, we may only pulse once, waking
                  // a single thread up, even if there are multiple threads
                  // waiting for items.            
            Monitor.Pulse(listLock);
        }
    }
    
                  public object Consume()
    {
                  lock (listLock)
        {
                  // If the queue is empty, wait for an item to be added
                  // Note that this is a while loop, as we may be pulsed
                  // but not wake up before another thread has come in and
                  // consumed the newly added object. In that case, we'll
                  // have to wait for another pulse.
                  while (queue.Count==0)
            {
                  // This releases listLock, only reacquiring it
                  // after being woken up by a call to Pulse
                Monitor.Wait(listLock);
            }
                  return queue.Dequeue();
        }
    }
}

Here are some results I got:

  
Producing 0
                                Consuming 0
Producing 1
                                Consuming 1
Producing 2
                                Consuming 2
Producing 3
                                Consuming 3
Producing 4
Producing 5
                                Consuming 4
Producing 6
                                Consuming 5
                                Consuming 6
Producing 7
                                Consuming 7
Producing 8
                                Consuming 8
Producing 9
                                Consuming 9

Now, there's nothing stopping you from having more than one consumer or producer in the above. Everything will play nicely, and each produced object will only be consumed once, and will be consumed (almost) immediately if there are any consumers waiting for work.

The reason for having both Pulse and PulseAll is for different situations, where you're waiting on different conditions. If either there'll only be one thread waiting, or (as is the case above) any thread can consume any produced object, you can just use Pulse. If there are several threads waiting on the object, that ends up being more efficient than PulseAll - there's no point in waking up a bunch of threads if you know that only one of them is going to be able to make progress, and that it doesn't matter which you wake up. Sometimes, however, different threads are waiting on different conditions, but all waiting on the same monitor. In that case, you need to use PulseAll so that you make sure that the thread which is waiting for whatever condition has just occurred is able to notice it and make progress.

Note that using these methods can easily lead to deadlock - if thread A holds locks X and Y, and waits on Y, but thread B needs to acquire lock X before acquiring and then pulsing Y, thread B won't be able to do anything. Only the lock which is waited on is released, not all the locks the waiting thread owns. Usually you should ensure that prior to waiting, a thread only owns the lock it's going to wait on. Sometimes this isn't possible, but in those cases you should think extra carefully about how everything is going to work.

Back to the main C# page.