Simple Deadlock Examples

Question

Hello,

I would like to explain threading deadlocks to newbies. I have seen many examples for deadlocks in the past, some using code and some using illustrations (like the famous 4 cars). There are also classic easily-deadlocked problems like The Dining Philosophers, but these may be too complex for a real newbie to fully grasp.

I'm looking for the simplest code example to illustrate what deadlocks are. The example should:

1. Relate to a "real" programming scenario that makes some sense
2. Be very short, simple and straight forward

What's do you recommend?

Thanks

Answer 1

Please see my answer to this question. Bottom line whenever two threads need to acquire two different resources, and do so in different orders then you can get deadlocks.

Answer 2

The producers-consumers problem together with the dining philosophers' problem is probably as simple as it's going to get. It has some pseudocode that illustrates it, as well. If those are too complex for a newbie they'd better try harder to grasp them.

Answer 3

Here's a code example from the computer science department of a university in Taiwan showing a simple java example with resource locking. That's very "real-life" relevant to me. Code below:

/**
 * Adapted from The Java Tutorial
 * Second Edition by Campione, M. and
 * Walrath, K.Addison-Wesley 1998
 */

/**
 * This is a demonstration of how NOT to write multi-threaded programs.
 * It is a program that purposely causes deadlock between two threads that
 * are both trying to acquire locks for the same two resources.
 * To avoid this sort of deadlock when locking multiple resources, all threads
 * should always acquire their locks in the same order.
 **/
public class Deadlock {
  public static void main(String[] args){
    //These are the two resource objects 
    //we'll try to get locks for
    final Object resource1 = "resource1";
    final Object resource2 = "resource2";
    //Here's the first thread.
    //It tries to lock resource1 then resource2
    Thread t1 = new Thread() {
      public void run() {
        //Lock resource 1
        synchronized(resource1){
          System.out.println("Thread 1: locked resource 1");
          //Pause for a bit, simulating some file I/O or 
          //something. Basically, we just want to give the 
          //other thread a chance to run. Threads and deadlock
          //are asynchronous things, but we're trying to force 
          //deadlock to happen here...
          try{ 
            Thread.sleep(50); 
          } catch (InterruptedException e) {}

          //Now wait 'till we can get a lock on resource 2
          synchronized(resource2){
            System.out.println("Thread 1: locked resource 2");
          }
        }
      }
    };

    //Here's the second thread.  
    //It tries to lock resource2 then resource1
    Thread t2 = new Thread(){
      public void run(){
        //This thread locks resource 2 right away
        synchronized(resource2){
          System.out.println("Thread 2: locked resource 2");
          //Then it pauses, for the same reason as the first 
          //thread does
          try{
      Thread.sleep(50); 
       } catch (InterruptedException e){}

          //Then it tries to lock resource1.  
          //But wait!  Thread 1 locked resource1, and 
          //won't release it till it gets a lock on resource2.  
          //This thread holds the lock on resource2, and won't
          //release it till it gets resource1.  
          //We're at an impasse. Neither thread can run, 
          //and the program freezes up.
          synchronized(resource1){
            System.out.println("Thread 2: locked resource 1");
          }
        }
      }
    };

    //Start the two threads. 
    //If all goes as planned, deadlock will occur, 
    //and the program will never exit.
    t1.start(); 
    t2.start();
  }
}

Answer 4

Reader Writer Problem (for Database or for file ) can be a good example for deadlock, because it matches with our daily programming and software development habits or we faces them very often.

Answer 5

Maybe a simple bank situation.

class Account {
  double balance;
  int id;

  void withdraw(double amount){
     balance -= amount;
  } 

  void deposit(double amount){
     balance += amount;
  } 

   void transfer(Account from, Account to, double amount){
        sync(from);
        sync(to);
           from.withdraw(amount);
           to.deposit(amount);
        release(to);
        release(from);
    }

}

Obviously, should there be two threads which attempt to run transfer(a,b) and transfer(b,a) at the same time, then a deadlock is going to occur.

This code is also great for looking at solutions to the deadlock as well. Hope this helps!

Answer 6

I consider the Dining Philosophers problem to be one of the more simple examples in showing deadlocks though, since the 4 deadlock requirements can be easily illustrated by the drawing (especially the circular wait).

I consider real world examples to be much more confusing to the newbie, though I can't think of a good real world scenario off the top of my head right now (I'm relatively inexperienced with real-world concurrency).

Answer 7

Some real life not-so-serious examples can be found here and here :)

Answer 8

Here's a simple deadlock in c#

void UpdateLabel(string text) {
   lock(this) {
      if(MyLabel.InvokeNeeded) {
        IAsyncResult res =  MyLable.BeginInvoke(delegate() {
             MyLable.Text = text;
            });
         MyLabel.EndInvoke(res);
        } else {
             MyLable.Text = text;
        }
    }
}

If, one day, you call this from the GUI thread, and another thread calls it as well - you might deadlock. The other thread gets to EndInvoke, waits for the GUI thread to execute the delegate while holding the lock. The GUI thread blocks on the same lock waiting for the other thread to release it - which it will not because the GUI thread will never be available to execute the delegate the other thread is waiting for. (ofcourse the lock here isn't strictly needed - nor is perhaps the EndInvoke, but in a slightly more complex scenario, a lock might be acquired by the caller for other reasons, resulting in the same deadlock.)

Answer 9

Go for the simplist possible scenario in which deadlock can occur when introducting the concept to your students. This would involve a minimum of two threads and a minimum of two resources (I think). The goal being to engineer a scenario in which the first thread has a lock on resource one, and is waiting for the lock on resource two to be released, whilst at the same time thread two holds a lock on resource two, and is waiting for the lock on resource one to be released.

It doesn't really matter what the underlying resources are; for simplicities sake, you could just make them a pair of files that both threads are able to write to.

EDIT: This assumes no inter-process communication other than the locks held.