Deadlock situation in threads?

Question

want to know what is deadlock condition in threads, because in many of the books i studied how to avoid deadlock situation, i just want to know what is deadlock situation and a example code for that?

Answer 1

Deadlock is a situation that a concurrent program cannot proceed.

A thread is waiting for another thread, while the other thread is waiting for the first thread's completion.

The commonly used real world example is a traffic flow.

No traffic can move until the other queue moves.

You may find a good discussion on deadlocks here.

Update : This is one java example I found on web (Oreilly book). It has comments on that so you can understand it easily.

Dining Philosophers problem is another good example to understand the deadlocks.

Dead lock detection and Deadlock prevention are two of related areas that might be useful while learning about the deadlocks.

Answer 2

A deadlock is when two (or more) threads are each waiting for the other to finish. Thread A cannot complete until thread B does something, and thread B cannot finish until thread A does something else.

Answer 3

Deadlock is when A waits on B and B waits on A.

So you could have in thread A:

while(B.incomplete()){
    B.wait();
} A.complete = true;

and have in thread B:

while(A.incomplete()){
    A.wait();
} B.complete = true;

Answer 4

Deadlock is caused by resource contention that is not directly solvable without some sort of resource control (such as a graph cycle which relies on two resource locks).

One of the most common (and generally used for illustration) deadlock scenarios is lock inversion:

• Consider an application which has two critical resources (resA, resB), and two locks (lockA, lockB). Each resource is protected by the corresponding lock (resA => lockA, resB => lockB).
• Two resources are contending for the resources, Thread A reserves lockA (and thus resource A) and then is suspended for a context switch) before being able to reserve lockB. Thread B receives control, reserves lockB and then attempts to reserve lockA. This causes the thread to be suspended and control returned back to Thread A, who is waiting on lockB, which is held be Thread B.

In this scenario you will have a deadlock because of a cyclic dependency between the two threads on the two contended resources (lockA and lockB) which cannot be resolved without separate intervention.

This can be trivially resolved by either:

1. Ensuring the two locks are resolved in order (not the best choice)
2. Only holding one lock for each critical section at a time (i.e. release lockA before attempting to acquire lockB)

Answer 5

Here's an example of a deadlock that doesn't use wait. As long as you've got synchronization, there's a potential for deadlock.

public class Deadlock {
  static class Deadlocker {
    private Deadlocker other;

    public void setOther(Deadlocker other) {
      this.other = other;
    }

    synchronized void doSomethingWithOther() {
      try {
        Thread.sleep(1);
      } catch (InterruptedException e) {
      }
      other.doSomething();
    }

    synchronized void doSomething() {
    }
  }

  public static void main(String[] args) {
    final Deadlocker d1 = new Deadlocker();
    final Deadlocker d2 = new Deadlocker();
    d1.setOther(d2);
    d2.setOther(d1);

    Thread t1 = new Thread() {
      public void run() {
        d1.doSomethingWithOther();
      }
    };

    Thread t2 = new Thread() {
      public void run() {
        d2.doSomethingWithOther();
      }
    };

    t1.start();
    t2.start();
  }
}

The deadlock occurs when t1 is in d1.doSomethingWithOther() (ie: has a lock on d1) and t2 is in d2.doSomethingWithOther(). When each thread tries to call doSomething() on the object the other thread has a lock on, they end up stuck, waiting for eachother.

Note that a deadlock doesn't necessarily involve only two threads. It's possible to have a cycle of any size. Worse, once a deadlock has been obtained, any other thread that also tries to depend on a deadlocked thread will end up becoming deadlocked itself, even without being part of the cycle, per se.

Answer 6

Dining Philosophers Problem is a theoretical explanation of deadlock:

The dining philosophers problem is summarized as five philosophers sitting at a table doing one of two things: eating or thinking. While eating, they are not thinking, and while thinking, they are not eating. The five philosophers sit at a circular table with a large bowl of spaghetti in the center. A fork is placed in between each pair of adjacent philosophers, and as such, each philosopher has one fork to his left and one fork to his right. As spaghetti is difficult to serve and eat with a single fork, it is assumed that a philosopher must eat with two forks. Each philosopher can only use the forks on his immediate left and immediate right.

Please see this link:

http://en.wikipedia.org/wiki/Dining_philosophers_problem

Answer 7

Imagine the following threads of logic.

1. In catch-22, the novel, the fighter pilot was to be grounded due to insanity. He could prove against the case of insanity by saying he was not insane so that he could fly again. But by asking, wanting to fly into battle to endanger his life would demonstrate that he is crazy.

2. North Korea wants the G7 to deliver economic aid before stopping uranium refinement. The US and Japan says "No Way, because they would renege after getting the aid."

3. System reboot conflict.

   1. The system would not shut down until all user processes have been terminated.
   2. The editor, a user process would not terminate unless the edit has been saved.
   3. The edit cannot be saved unless the usb drive is present because the editor executable was called from the usb drive.
   4. The usb drive was dismounted because of a driver upgrade. The usb drive could not be mounted until the system is shut down and rebooted.

4. The Android robot has prime directives

   A robot may not injure a human being or, through inaction, allow a human being to come to harm.

   A robot must obey any orders given to it by human beings, except where such orders would conflict with the First directive.

   A robot must protect its own existence as long as such protection does not conflict with the First or Second directive.

The human occupants of the base sent robot to retrieve a radio-active power source. Without the power source, the base would shut down and the human colony would die. But the robot discovers that the power source is so powerful and unshielded, handling it would cause the robot to malfunction and become a danger to the human colony.

Answer 8

Threads deadlock when waiting on each other to release some resources, but by performing that blocking wait, they're not releasing the resources the other threads need in order to unblock. The threads can't make any progress until the resources are released, but because they're not making progress, the resources will never be released, the threads are locked up, and thus "deadlock."

A nice article by Stephen Toub might help you a bit.