Is it possible to reach a deadlock on a single thread?

Question

Popular screening interview question is: What minimal number of threads required to reach a deadlock?

Correct answer is 2.

But is it theoretically possible to make a deadlock using one single thread?

Answer 1

Here's a single-threaded program that deadlocks, due to the fact that pthreads mutexes are (by default) non-recursive:

#include <stdio.h>
#include <pthread.h>

int main(int, char **)
{  
   pthread_mutex_t m;
   pthread_mutex_init(&m, NULL);

   printf("Locking non-recursive mutex once...\n");
   pthread_mutex_lock(&m);

   printf("Locking non-recursive mutex again...\n");
   pthread_mutex_lock(&m);   // deadlock occurs here, as we wait forever for the locked mutex to be unlocked...

   printf("You won't ever see this text printed, because we'll be deadlocked above\n");

   return 0;
}

(If you set the mutex to be a recursive mutex, OTOH, this scenario will be handled by the mutex and a deadlock will be avoided)

Answer 2

It depends on precisely how you are defining "thread". For example, consider a singly-threaded server that processes requests using coroutines. The coroutine for one request might hold a lock that the coroutine for another thread requires and vice versa. Neither coroutine can make forward progress until the other does.

Do you consider those coroutine execution contexts threads? Or not?

Answer 3

By definition of deadlock: https://en.wikipedia.org/wiki/Deadlock:

a deadlock is a state in which each member of a group of actions, is waiting for some other member to release a lock.

You cannot reach a deadlock state with just one single thread.

For single thread, you may run into infinite loop: https://en.wikipedia.org/wiki/Infinite_loop.

If we include coroutines into consideration, a single-threaded application could indeed run into deadlock situation. This is mentioned by @David Schwartz.

Answer 4

Consider the following code snippet:

  #include<signal.h>
  some_struct data;
  int main(){
     sigset(SIGINT, handler);
     computation_fn();
     return 0;
  }
  computation_fn(){
     pthread_mutex_lock(&m);
     update_state(&data);
     pthread_mutex_unlock(&m);
  }
  void handler(int signo){
     pthread_mutex_lock(&m);
     display_state(&data);
     pthread_mutex_unlock(&m);
  }

• In the above snippet, the data is accessed by the handler for display and therefore accessed through the mutex. For update also it requires the mutex in computation_fn() as well.
• Now consider if the computation_fn() takes a long time to execute and the user decides to submit CNTRL-C, then the handler() will be executed. Since the lock would not be released from the computation_fn(), it would wait infinitely for it to be available.
• Also since there is no other thread in the program to release the mutex from computation_fn() as the handler uses (borrows) the same thread as that of computation_fn(), there would be no way to release this mutex.

Ultimately we can see that this way a single threaded program can enter into deadlock.

Answer 5

Deadlock means a loop in the resource graph. Such a loop can be created using single thread, e.g.

    Thread.currentThread().join();