Can You Spot the DeadLock?


Hi everyoneI was considering starting to put some code in this blog, but was lacking the proper motivation. But I found one: trivia game!

So welcome to the first instalment of

Can You Spot the Deadlock?

Rules are simple: I publish some code which exhibits some concurrency related problem and ask some questions about it such as:

  • What concurrency issue(s) is(are) present in the code? (deadlock, race condition, livelock…)
  • Where does it occurs or what are the impacts?
  • How can it be fixed

Please post your answer(s) in the comment section, I will provide the expected answers one week after first submission. Of course, debugging is not allowed here.
So without further ado, here is the first one, quite easy for a starter.

Where is the deadlock?

Which single line needs to be changed to fix this?

Problem is now closed, please see the solution.

class Program
{
  /// Main function
  static void Main(string[] args)
  {
    DeadLock1 sample1 = new DeadLock1();
    sample1.Start();
  }
}
/// First instance of 'Can you Spot the DeadLock?
/// Let's start easy to put things in motion
internal class DeadLock1
{
  private Thread _firstRunner;
  private Thread _secondRunner;
  private bool _stopSignal = false;
  private readonly object _synchro = new object();

  public DeadLock1()
  {
    _firstRunner = new Thread(FirstRunner);
    _secondRunner = new Thread(SecondRunner);
  }

  // start your engines
  public void Start()
  {
    _firstRunner.Start();
    _secondRunner.Start();
    Thread.Sleep(100);
    lock (_synchro)
    {
      _stopSignal = true;
      Monitor.Pulse(_synchro);
    }
    _firstRunner.Join();
    _secondRunner.Join();
  }
  // first thread logic
  private void FirstRunner()
  {
     lock (_synchro)
     {
       if (!_stopSignal)
       {
         Monitor.Wait(_synchro);
       }
     }
   }
  // second thread logic
  private void SecondRunner()
  {
    lock (_synchro)
    {
      if (!_stopSignal)
      {
        Monitor.Wait(_synchro);
      }
    }
  }
}

Several quality comments can be made about this code, but please focus on the multithreading issues. Bonus points if the second design weakness is identified!

PS: I’ll wait a few days before approving comments not to disclose the solution. I already have at least one good answer (but not perfect) and one wrong one. Keep commenting!

edited to explicitly initialize _stopSignal for clarity.

Advertisements

15 thoughts on “Can You Spot the DeadLock?

  1. Don’t be selfish: PulseAll() instead of Pulse(). Otherwise, only the first runner will be able to exit the waiting queue. And then, the second runner will be waiting for Godot ;-), so your main thread will also be blocked at the line:

    _secondRunner.Join(); at the end of the Start() method.

    According to me, the more obvious design weakness in that first “Can you spot the deadlock” (BTW, I like this idea ;-), is the call to Thread.Join() without indicating a timeout as argument.

    I look forward to read the next Spot the deadlock episodes!

    Like

    1. Yes, the issue is clearly the lack of PulseAll(). In terms of code quality, adding timeout raises interesting question I should probably address on a dedicated post. Adding them willbring some improvments, but that does not really drives toward cleaner code. Stay tuned for full disclosure next week end.
      Thanks for your time and consideration. BTW, next trivia is planned on Feb 12th.

      Like

  2. Here’s my take:

    stopSignal is not initialized, so we don’t know if worker threads are going to wait on _synchro.

    If we assume that stopSignal is initialized to false, then we have the following scenario:
    – one worker thread get to wait on the monitor (A), the other wait one the lock (B).
    When pulsed, A release the monitor and terminates, main thread can possibly join on A.
    – however, B will wait forever on the monitor, since no one will pulse synchro after that. Using PulseAll() wouldn’t change that, that wouldn’t be a fix.

    If stopSignal is initialied to true, then the program terminates.

    Like

  3. You don’t have the garanty that the pulse is called after waits. In this case, the pulse is lost -> deadlock

    Like

      1. Hello loracle, can you give a bit more details on this ‘loop’? I cannot figure out something out of this. Care for pasting some code lines?

        Like

    1. By the way only on thread is pulsed with the Pulse method. Agreed, even pulseAll() wouldn’t work.

      Like

  4. I can’t see too a “real single line” fix. The design of this example is so broken… 🙂

    Like

  5. PulseAll() should in fact work, you are right.
    I mentally forgot that the lock is being released while you Monitor.Wait() on the sync object. The two threads can and will wait on the same sync object. Hence pulseAll() should wake them both, and the program should terminate.
    No offense intended :p

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s