Can this code cause a dead lock ?

Question

using System;
using System.Threading;

namespace Threading
{
class Program
{
    static void Main(string[] args)
    {
        Semaphore even = new Semaphore(1, 1);
        Semaphore odd = new Semaphore(1, 1);

        Thread evenThread = new Thread(() =>
        {
            for (int i = 1; i <= 100; i++)
            {
                even.WaitOne();
                if(i % 2 == 0)
                {
                    Console.WriteLine(i);
                }
                odd.Release();
            }
        });

        Thread oddThread = new Thread(() => 
        {
            for(int i = 1; i <=100; i++)
            {
                odd.WaitOne();
                if(i%2 != 0)
                {
                    Console.WriteLine(i);
                }
                even.Release();
            }
        });


        oddThread.Start();
        evenThread.Start();
    }


}
}

So I have written this code where one thread is producing Odd numbers and other is producing even numbers.

Using Semaphores I have made sure that they print numbers in orders and it works perfectly.

But I have a special situation in mind, for example each thread waits until the other thread releases its semaphore. So can there be a condition where both threads are waiting and no thread is making any progress and there is a deadlock situation ?

Initializing the semaphores incorrectly will easily do it. Do note that you did it wrong, you created a race condition and both threads will try to WriteLine() at the same time. Ideally it will crash because you call Release on a semaphore that wasn't waited but that won't happen often enough. But no, no deadlock. The System.Threading.Barrier class does this, always better when you don't have to re-invent it. — Hans Passant, Apr 23 '17 at 16:34

score 1 · Accepted Answer · edited May 23 '17 at 10:31

For deadlock to occur, two or more threads must be trying to acquire two or more resources, but do so in different orders. See e.g. Deadlock and Would you explain lock ordering?.

Your code does not involve more than one lock per thread^† and so does not have the ability to deadlock.

It does have the ability to throw an exception. As noted in this comment, it is theoretically possible for one of the threads to get far enough ahead of the other thread that it attempts to release a semaphore lock that hasn't already been taken. For example, if evenThread is pre-empted (or simply doesn't get scheduled to start running) before it gets to its first call to even.WaitOne(), but oddThread gets to run, then oddThread can acquire the odd semaphore, handle the if statement, and then try to call even.Release() before evenThread has had a chance to acquire that semaphore.

This will result in a SemaphoreFullException being thrown by the call to Release().

This would be a more likely possibility on a single-CPU system, something that is very hard to find these days. :) But it's still theoretically possible for any CPU configuration.

† Actually, there's an implicit lock in the Console.WriteLine() call, which is thread-safe by design. But from your code's point of view, that's an atomic operation. It's not possible for your code to acquire that lock and then wait on another. So it doesn't have any relevance to your specific question.

Can this code cause a dead lock ?

1 Answers1