Deadlocks: Why if 2 threads are waiting for a lock from each other results in a deadlock?

Question

I am confused as to why 2 threads waiting for a lock from each other will result in a deadlock. Let's say I have a Thread 1 that needs to execute contents in Lock 1 and then Lock 2 and a Thread 2 that needs to execute contents in Lock 2 and then Lock 1. Why does this situation result in a deadlock?

Once Thread 1 is done with Lock 1, it unlocks Lock 1, allowing Thread 2 to execute Lock 1. Once Thread 2 is done with Lock 2, it unlocks Lock 2, allowing Thread 1 to execute Lock 2. Where is the infinite stalling (deadlock)?

Answer 1

The situation you are describing is not a deadlock.

A deadlock would be more like this:

• Both Thread A and Thread B require both Lock 1 and Lock 2.
• Thread A first acquires Lock 1, then Lock 2.
• Thread B first acquires Lock 2, then Lock 1.

Then you can get the following interleaving:

1. Thread A acquires Lock 1.
2. Thread B acquires Lock 2.

Now, Thread A can only progress after Thread B releases Lock 2. But in order to progress, Thread B needs Lock 1, which is currently held by Thread A, which can only progress using Lock 2, which is currently held by Thread B, which can only progress using Lock 1, which is currently held by Thread A, which can only progress using Lock 2, which is currently held by Thread B, which …

These are the necessary conditions for a deadlock to occur:

1. Mutual exclusion: At least two resources must be held in a non-shareable mode. Otherwise, the processes would not be prevented from using the resource when necessary. Only one process can use the resource at any given instant of time.
2. Hold and wait or resource holding: a process is currently holding at least one resource and requesting additional resources which are being held by other processes.
3. No preemption: a resource can be released only voluntarily by the process holding it.
4. Circular wait: each process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, $P = {P_1, P_2, …, P_N}$, such that $P_1$ is waiting for a resource held by $P_2$, $P_2$ is waiting for a resource held by $P_3$ and so on until $P_N$ is waiting for a resource held by $P_1$.

In your example, you are missing condition #2 (your threads are not holding a lock and requesting another, but rather holding a lock, releasing it, and then requesting another) and consequently #4 (because of the fact that the threads release the locks before acquiring the next one, there is no dependency at all, let alone a circular one), so this is not a deadlock.

Or, to put it more simply

I am confused as to why 2 threads waiting for a lock from each other will result in a deadlock.

In your example, they aren't waiting for a lock from each other. At any given point in time, Thread 1 may be waiting for Thread 2 to release Lock 1, and at any given point in time, Thread 1 may be waiting for Thread 2 to release Lock 2, and at any given point in time, Thread 2 may be waiting for Thread 1 to release Lock 1, and at any given point in time, Thread 2 may be waiting for Thread 1 to release Lock 2, but at no point in time is Thread 1 waiting for Thread 2 to release Lock 1 and Thread 2 waiting for Thread 1 to release Lock 1, nor is at any point in time Thread 1 waiting for Thread 2 to release Lock 2 and Thread 2 waiting for Thread 1 to release Lock 2.

So, in your example, it is simply never the case that there are "2 threads waiting for a lock from each other", there are only cases where a thread is waiting for a lock from another thread. In other words: your counterexample isn't a counterexample.