Learning Objectives

At the end of this lecture, you should be able to:

• List the four conditions for a deadlock to occur.
• Solve a deadlock-riddled concurrency problem.

Topics

In this lecture, we will cover the following topics:

• Deadlocks and their conditions.

Notes

• Buffalo’s Guide to CV Problems
• Definition of a Deadlock
• Conditions for a Deadlock
• Cigarette Smokers Problem

Buffalo’s Guide to CV Problems

• Make sure you read Buffalo’s Guide to CV Problems.

Definition of a Deadlock

• A set of threads are said to be in a deadlock state when:
  • Every thread is waiting on an event,
  • that even is only caused by another thread in the set.
• Consider the following simple example:

  void *thread1(void *arg)
  {
    pthread_mutex_lock(&m1);
    pthread_mutex_lock(&m2);
  
    // do stuff
  
    pthread_mutex_unlock(&m2);
    pthread_mutex_unlock(&m1);
  }
  
  void *thread2(void *arg)
  {
    pthread_mutex_lock(&m2);
    pthread_mutex_lock(&m1);
  
    // do stuff
  
    pthread_mutex_unlock(&m1);
    pthread_mutex_unlock(&m2);
  }
  

• In this case, a situation might occur when:
  • T1 locks m1.
  • T2 locks m2.
  • Now we are stuck, T1 is waiting on T2 to release m2 while T2 is waiting on T1 to release m1.
  • Thus a deadlock!

Conditions for a Deadlock

• There are four essential conditions for a deadlock to occur:

  1. Hold & Wait: A thread is requesting and waits on a resource while also holding another resource.

  2. No Preemption: Once a thread owns a resource, no one can forcefully take it away.

  3. Circular Wait: Thread must be waiting on each other in a circular fashion.

  4. Mutual Exclusion: No sharing of resources can happen between the threads.

• Once all four conditions are satisfied, then we have a deadlock!

Cigarette Smokers Problem

• Look at cigarette_smokers.c