How many threads are involved in deadlock

Question

I am trying to figure out a answer to an interview question How many threads are involved in an deadlock

I answered that it should be two or more but the interviewer said it is a wrong answer.

I tried searching the web for that but couldn't understand why my answer is wrong

Interviewers usually don't tell you whether you answered a question correctly or not (as it demotivates the candidate). If they do tell you that, then they should explain to you why it's wrong. For all you know, the interviewer himself does not know the answer. — Chetan Kinger, Jul 14 '15 at 07:34
see also http://stackoverflow.com/questions/3493441/is-it-possible-for-a-thread-to-deadlock-itself — user140547, Jul 14 '15 at 07:39
Stupid interview question. Liveness failure can take many different forms. It should not matter which ones _you_ call "deadlock" or which ones _I_ call "deadlock". A better question would be to ask you to describe how it can happen. — Solomon Slow, Jul 14 '15 at 12:53

score 1 · Answer 1 · answered Jul 14 '15 at 07:36

1

A thread can deadlock itself if it tries to aquire a resource it already holds. Think of a thread that holds a database lock, then switches to another transaction (without committing the first one) and tries to get the same lock again.

answered Jul 14 '15 at 07:36

Drunix

3,313
8
28
50

2

That's not what is commonly referred to as a "deadlock". [Wikipedia](https://en.wikipedia.org/wiki/Deadlock) says: *In concurrent programming, a deadlock is a situation in which two or more competing actions are each waiting for the other to finish, and thus neither ever does.* – JB Nizet Jul 14 '15 at 07:39
I am not sure if "competing actions" necessarily imply different threads. In my example you just have an unfinished action in the same thread. Maybe a correct answer to the interwiew question would start with "That depends on definition of deadlock" ;-) – Drunix Jul 14 '15 at 07:44
2

It all depends on the context of the question. Did the interviewer asked about multithreading, or about database transactions? The context matters. My guess is that the interviewer asked a very general question and expected the interviwee to give him the solution to a specific bug he had the week before and took days to figure out. – JB Nizet Jul 14 '15 at 07:47

rghome · Answer 2 · 2015-07-14T09:06:46.210

The obvious answer is "two or more", since you can have a chain of dependencies leading to a deadlock.

1 locks A
2 locks B
3 locks C
3 requests A
2 requests C
1 requests B

They may have meant "one or more" if you want to examine situations where the resource being locked is not "owned" by the thread, but by another resource.

If the owning object of the resource is something other than the thread, then you need multiple occurrences of the owning object and not of the thread to cause a deadlock. In the above example, 1, 2 & 3 are owning resources and not threads.

You can think of all sorts of situations where a resource (A) also locks resource (B) and then the same thread requests resource (B) but can't get it. However, I really don't think it is helpful use of the word "deadlock".

Direct quote from the question: "I answered that it should be two or more but the interviewer said it is a wrong answer." — Gimby, Jul 14 '15 at 07:46

Stephen C · Answer 3 · 2019-01-05T11:19:33.987

The answer is that it depends on the kind of lock or locking mechanism.

For reentrant locks, you need two or more threads. (Note that Java primitive locks / mutexes are reentrant).
For non-reentrant lock, a single thread can deadlock itself by attempting to acquire a lock that it already holds¹.

It is also possible for a thread to block itself in other ways that is practically indistinguishable from a deadlock². For example:

    Thread.currentThread().join();

will block a thread by getting it to wait until it finishes. Under the hood, the join() call is waiting for a notification / condition that can never occur. You can do the same thing yourself explicitly; e.g.

    Object lock = new Object();  // local variable
    synchronized (lock) {
        lock.wait();
    }

^{1 - This depends on the precise semantics of the lock. For example, a non-reentrant lock could be implemented to throw an exception rather than deadlocking in this scenario.}

^{2 - Whether this is actually a deadlock depends on the precise definition you use for the term "deadlock". It is inadvisable to get into arguments about terminology in a job interview!}

nabeel · Answer 4 · 2019-01-05T06:12:34.947

At least in Java, it looks a thread cannot lock on itself (like in a recursion); but another thread can; so the answer has to be that there has to be two threads; here is an example:

package threadLockTest;

public class ThreadLocking {

private Object LOCK = new Object();

public void recursionWithSynchronization (int count) {
    System.out.println("inside recursionWithSynchronization: count: " + count);
    synchronized (LOCK) {
        if (count == 10) {
            return;
        } else {
            try {
                Thread.sleep(500);
                recursionWithSynchronization((count+1));
            } catch (Exception ex) {
                ex.printStackTrace();
            }
        }
    }
}

public static void main (String... args) {
    System.out.println("starting Main thread");
    ThreadLocking stli = new ThreadLocking();
    Runnable ry = () -> {
        System.out.println("starting thread");
        stli.recursionWithSynchronization(1);
        System.out.println("ending thread");
    };
    Thread t1 = new Thread(ry);
    Thread t2 = new Thread(ry);
    t1.start();
    t2.start();
    System.out.println("ending Main thread");
}


}

How many threads are involved in deadlock

4 Answers4