Is it possible for a thread to Deadlock itself?

Question

Is it technically possible for a thread in Java to deadlock itself?

I was asked this at an interview a while back and responded that it wasn't possible but the interviewer told me that it is. Unfortunately I wasn't able to get his method on how to achieve this deadlock.

This got me thinking and the only situation that I can think of is where you can have this happen is where you have an RMI server process which contained a method that calls itself. The line of code that calls the method is placed in a synchronized block.

Is that even possible or was the interviewer incorrect?

The source code I was thinking about was along these lines (where testDeadlock is running in an RMI server process)

public boolean testDeadlock () throws RemoteException {
    synchronized (this) {
        //Call testDeadlock via RMI loopback            
    }
}

Gummy

Synchronized RMI calls of this method would only enqueue the RMI dispatch threads on monitor of this RemoteObject on server-side. – Apocryphal

The purpose of these sort of gotcha interview questions eludes me. It makes the whole process more akin to a game show than an interview. I'm sure the interviewer believed he discovered some outlier and thought it would make a great trick question. But what is the point? I'm curious what the rest of the interview was like? I tend to hedge my answers to questions like this one by discussing the concepts involved more than giving a definitive. Which goes against my naturally objective disposition but in these situations it seems appropriate. – Auric

I wonder if the interviewer had something like a pthreads non-recursive mutex in mind. From the pthreads documentation: "A normal mutex cannot be locked repeatedly by the owner. Attempts by a thread to relock an already held mutex, [...] result in a deadlock condition." IIRC Java mutexes are a bit smarter than that. – Ave

Maybe the best answer would have been "Not if you had ME write the code!" – Poddy

I don't think so. A thread can just do one thing at the time. so it cannot do some work and also wait for something else to complete – Harriott

I don't think, Haven't heard of deadlocks in single threaded applications .. – Fishy

An RMI loopback would happen in a separate thread. It isn't an instance of a thread deadlocking itself. I agree entirely with @Sorax. Some interviewers can't help showing off. The question isn't relevant to any conceivable development situation I have ever encountered, or to any iphring decision. If the interviewer is so knowledgable he should have an interest in educating his workers as necessary, and also in debating things like this rationally rather than lay them down as entry requirements. – Pelota

I've accidentally managed to deadlock a thread... It's waiting for it's own object lock to release the object it wants (and no, I didn't embed object locks). Or at least, that's how the Eclipse debugger shows it. Edit: It really isn't, I just didn't properly check the waiting for thread IDs. – Fruma

Answer 1

The JVM only keeps track of the local thread that has the monitor, if the calling class makes an external call back in on itself the incoming call causes the original thread to deadlock itself.

You should be able to run this code to illustrate the idea

import java.rmi.*;
import java.rmi.registry.LocateRegistry;
import java.rmi.registry.Registry;
import java.rmi.server.*;

public class DeadlockThreadExample {

    public static interface DeadlockClass extends Remote {
        public void execute() throws RemoteException;
    }

    public static class DeadlockClassImpl extends UnicastRemoteObject implements DeadlockClass {
        private Object lock = new Object();

        public DeadlockClassImpl() throws RemoteException {
            super();
        }

        public void execute() throws RemoteException {
            try {
                System.out.println("execute()::start");

                synchronized (lock) {
                    System.out.println("execute()::Entered Lock");
                    DeadlockClass deadlockClass = (DeadlockClass) Naming.lookup("rmi://localhost/DeadlockClass");
                    deadlockClass.execute();
                }
                System.out.println("execute()::Exited Lock");
            } catch (NotBoundException e) {
                System.out.println(e.getMessage());
            } catch (java.net.MalformedURLException e) {
                System.out.println(e.getMessage());
            }
            System.out.println("execute()::end");
        }
    }

    public static void main(String[] args) throws Exception {
        LocateRegistry.createRegistry(Registry.REGISTRY_PORT);
        DeadlockClassImpl deadlockClassImpl = new DeadlockClassImpl();
        Naming.rebind("DeadlockClass", deadlockClassImpl);
        DeadlockClass deadlockClass = (DeadlockClass) Naming.lookup("rmi://localhost/DeadlockClass");
        deadlockClass.execute();
        System.exit(0);
    }
}

The output from the program looks like

execute()::start
execute()::Entered Lock
execute()::start

Additionally the thread also dump shows the following

"main" prio=6 tid=0x00037fb8 nid=0xb80 runnable [0x0007f000..0x0007fc3c]
    at java.net.SocketInputStream.socketRead0(Native Method)
    at java.net.SocketInputStream.read(SocketInputStream.java:129)
    at java.io.BufferedInputStream.fill(BufferedInputStream.java:218)
    at java.io.BufferedInputStream.read(BufferedInputStream.java:235)
    - locked <0x02fdc568> (a java.io.BufferedInputStream)
    at java.io.DataInputStream.readByte(DataInputStream.java:241)


"RMI TCP Connection(4)-172.17.23.165" daemon prio=6 tid=0x0ad83d30 nid=0x1590 waiting for monitor entry [0x0b3cf000..0x0b3cfce8]
    at DeadlockThreadExample$DeadlockClassImpl.execute(DeadlockThreadExample.java:24)
    - waiting to lock <0x0300a848> (a java.lang.Object)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)


"RMI TCP Connection(2)-172.17.23.165" daemon prio=6 tid=0x0ad74008 nid=0x15f0 runnable [0x0b24f000..0x0b24fbe8] 
    at java.net.SocketInputStream.socketRead0(Native Method)
    at java.net.SocketInputStream.read(SocketInputStream.java:129)
    at java.io.BufferedInputStream.fill(BufferedInputStream.java:218)
    at java.io.BufferedInputStream.read(BufferedInputStream.java:235)
    - locked <0x02ffb6d8> (a java.io.BufferedInputStream)
    at java.io.DataInputStream.readByte(DataInputStream.java:241)

which indicates that the thread has indeed managed to lock itself

Gummy

did you answer your own question? – Clymer

if the calling class makes an external call back in on itself the incoming call causes the original thread to deadlock itself. This is not true; they are 2 (or more, in fact) separate threads. A thread cannot deadlock itself, the interviewer dude was a moron, that's all. – Lewendal

+1, see my answer as to why this post should probably not have been marked correct. Its pedantic I know, buts its describing a livelock not a deadlock! – Clymer

I think that the interviewer meant the case that JCIP notes. I answered the question using the teachings of the JCIP. See the mine! – Grendel

Answer 2

Well, based on the definition of:

A deadlock is a situation wherein two or more competing actions are each waiting for the other to finish.

I would say that the answer is no - sure a thread can sit there waiting indefinitely for something, however unless two competing actions are waiting for each other it is by definition not a deadlock.

Unless someone explains to me how a single thread can be simultaneously waiting for two actions to finish?

UPDATE: The only possible situation that I can think of is some sort of message pump, where a thread processes a message that asks it to wait indefinitely for something to happen, where in fact that something will be processed by another message on the message pump.

This (incredibly contrived) scenario could possibly be technically called a deadlock.

Thecla

+1. Agree that you need two to tango ( I mean deadlock ), but just only 1 to hang itself. – Foil

+1 to Kragen for the explanation, +1 to Alexander for the tl;dr version. – Rimma

I would consider some of the scenarios involving one thread and a message pump to constitute deadlock. The current thread is one 'thing', the queue of messages is another; the main thread may wait for a message in the queue to do something which can't happen while the main thread waits. If the message queue supports priorities, a locked situation may arise if processing a message before a low-priority message is processed will reenqueue that message at high priority. – Brayton

Funny you should mention that particularly contrived scenario, Kragen, as that happened to me just a few weeks ago (though it wasn't Java). I had a heck of a time convincing my co-workers that not only had it happened, but that it was possible at all. – Fenske

how a single thread can be simultaneously waiting for two actions to finish? Because at some level a thread is just an abstraction - otherwise you get into a reductio ad absurdum whereby a single core machine can't be deadlocked. – Tshirt

Well, the update scenario has nothing contrived if you are into concurrent programming (yet I am still curious to know if this situation is technically a deadlock, or some other beast ?) – Joub

Answer 3

It depends on what you mean by "deadlock" exactly. For example, you could easily wait() on a monitor which nothing would ever pulse... but I don't think I'd call that deadlock, as such.

Thinking along your "method that calls itself" lines, if your server only ran a certain number of threads, they could all be busy waiting from responses from the same server, if that counts. (Simplest example: the server only uses one thread for processing. If you write a request handler which calls into the same server, it will be waiting for the blocked thread to finish handling the request before it can serve the same request...) This isn't really a "synchronized block" sort of deadlock, but it's certainly a danger to be aware of.

EDIT: To apply this answer to the definition in the others, the competing actions here would be "complete the current request" and "handle the new request". Each action is waiting for the other to occur.

Rhombohedral

Also consider this trivial case Thread.currentThread.join() – Catapult

Answer 4

Maybe he meant LOCK itself, that's certainly too easy:

synchronized( this )
{
    wait( );
}

Foil

He just asked is it technically possible for a thread to lock it self, not whether it may appear in RL very often. +1 – Henriques

I upvoted this, but it doesn't deadlock the thread. Another thread only has to notify the object. – Pollack

@JeremyP. That's the point, you cannot deadlock 1 thread, see the post by Kragen here. On the other hand, if you only have a single thread, then calling wait() will definitely lock it, and without cooperation of other thread it will not be able to proceed. – Foil

Your example is different from mine in that theoretically, another thread could unlock the the one that runs your code. My example represents a kind of degenerate case that cannot be unlocked by another thread. I don't see why the "two competing actions" need to be in separate threads. – Pollack

Answer 5

Maybe what the interviewer was thinking of was:

Thread.currentThread().join();

However I would argue that it does not count as a deadlock.

Viand

It doesn't. It's jst a block. – Pelota

Answer 6

A deadlock is a form of resource starvation with an interaction between multiple threads.

When a thread gets into a state of resource staving itself, it is referred to a livelock which is similar to a deadlock, but not the same by definition.

An example of a livelock is using ReentrantReadWriteLock. Despite being reentrant on reading OR writing, it doesn't allow upgrading the lock from read to write.

public class LiveLock {
    public static void main(String[] args) {
        ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
        lock.readLock().lock();
        if (someCondition()) {
            // we want to write without allowing another thread to jump in.
            lock.writeLock().lock();
        }
    }

    private static boolean someCondition() {
        return true;
    }
}

results in the process blocking here

"main" #1 prio=5 os_prio=0 tid=0x0000000002a52800 nid=0x550c waiting on condition [0x000000000291f000]
   java.lang.Thread.State: WAITING (parking)
    at sun.misc.Unsafe.park(Native Method)
    - parking to wait for  <0x00000007162e5e40> (a java.util.concurrent.locks.ReentrantReadWriteLock$NonfairSync)
    at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:836)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:870)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1199)
    at java.util.concurrent.locks.ReentrantReadWriteLock$WriteLock.lock(ReentrantReadWriteLock.java:943)
    at LiveLock.main(LiveLock.java:10)

---

A related question is; can a thread get into a deadlock without creating additional threads. This is possible as there are background threads e.g. the finalizer thread, which can run user code in the background. This allows for the main thread and the finalizer thread to deadlock each other.

Oilcan

Answer 7

Upgrading from a read lock to a write lock (trying to acquire a write lock while holding a read lock) will result in the thread getting completely blocked. Is that a deadlock? You be the judge... But that's the easiest way to create the effect with a single thread.

http://download.oracle.com/javase/6/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

Cymbre

Answer 8

According to Wikipedia, "A deadlock is a situation wherein two or more competing actions are each waiting for the other to finish, and thus neither ever does."

..."In computer science, Coffman deadlock refers to a specific condition when two or more processes are each waiting for each other to release a resource, or more than two processes are waiting for resources in a circular chain."

I think two or more are key words here if you stay strict to definition.

Garret

Answer 9

The answer (Pram's) marked as correct isn't technically a deadlock as others have suggested. Its just blocked.

I would suggest in Java, you can lean on Java's definition (which is consistent with the two thread idea). The ultimate judge then can be the JVM if it detects the deadlock itself. So, in Pram's example, the thread would show something like the following if it was a geniune deadlock.

Deadlock detected
=================

"Negotiator-Thread-1":
  waiting to lock Monitor of com.google.code.tempusfugit.concurrency.DeadlockDetectorTest$Cat@ce4a8a
  which is held by "Kidnapper-Thread-0"

"Kidnapper-Thread-0":
  waiting to lock Monitor of com.google.code.tempusfugit.concurrency.DeadlockDetectorTest$Cash@7fc8b2
  which is held by "Negotiator-Thread-1"

This deadlock detection has been available for intrinsic locks since 1.5 and Lock based cyclic deadlocks since 1.6.

A continuously blocked resource, or at least something that is waiting for something that will never happen is called a livelock. Similar problems where processes outside the VM (for example) databases deadlocking are entirely possible but I'd argue not appropriate for the question.

I'd be interested in a write up of how the interviewer claims its possible...

In answer to your original question, it takes two to tango and I'd suggest Pram's answer shouldn't be marked as correct because its not! ;) The RMI thread which calls back can cause blocking but it runs on a different thread (managed by the RMI server) than that of main. Two threads are involved even if the main thread didn't explicitly set another one up. There is no deadlock as witnessed by the lack of the detection in the thread dump (or if you click 'detect deadlock' in jconsole), it'd be more accurately described as a livelock.

Having said all that, any discussion along the lines of each of these answers would be enough to satisfy me as an interviewer.

Clymer

Answer 10

While I haven't used Java I have deadlocked a single-thread app before. IIRC: Routine A locked a piece of data to update it. Routine B also locked the same piece of data to update it. Due to requirements changes A ended up calling B. Oops.

Of course this was just an ordinary development bug that I caught the first time I tried to run the code but it did deadlock itself. I would think deadlocks of this type would be possible in any language that supports a filesystem.

Penmanship

I was going to write the same thing. – Spinster

Answer 11

No, because Java implements reentrancy. But please don't mix up concurrency and RMI like that. Synchronization in stubs is something completely different than remote objects that are internally synchronized.

Apocryphal

Answer 12

You can get yourself into a single thread Deadlock with ReentrantReadWriteLock. Write locks can acquire read locks but not the other way around. The following will block indefinitely.

    ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    lock.readLock().lock();
    lock.writeLock().lock();

Forney

Answer 13

Although the comments here are being pedantic about "deadlock" happening if at least two threads/actions are competing for the same resource...I think the spirit of this question was to discuss a need for Reentrant lock - especially in context of "recursive" locking

Here's an example in python (I am certain the concept stays the same in Java): If you change the RLock to Lock (i.e. reentrant lock to lock, the thread will hang)

import threading

"""
Change RLock to Lock to make it "hang"
"""
lock = threading.Condition(threading.RLock())


def print_list(list):
    lock.acquire()
    if not list:
        lock.release()
        return
    print(list[0])
    print_list(list[1:])
    lock.release()


print_list([1, 2, 3, 4, 5])

Externalization

Answer 14

Ideally a thread should never create a deadlock itself using 'synchronized locks' unless there really is a bug in the JVM itself as 'allegedly' noticed by some people in older versions

Hospitalization

Answer 15

Here's a way for a thread to deadlock itself.

public class DeadlockMe
{
    public static void main(String[] args)
    {
        DeadlockThing foo = new DeadlockThing();
        synchronized(foo)
        {
            try
            {
                foo.wait();
            }
            catch (InterruptedException e)
            {
                e.printStackTrace();
            }
        }
    }
}

The thread creates an instance of a class - any class and waits on it. Because the thread created an object with local scope, there's no possible way for any other thread to notify the object to wake up the thread.

Pollack

Once again, it's locked, hanged, but not DEADLOCKED. See the definition of deadlock in Kragen's post. Also, according to your own logic, this thread is not deadlocked. The OTHER thread only has to interrupt the waiting thread, so it becomes unlocked. – Foil

@Alexander Pogrebnyak: that's pedantry. Kragen's post says competing actions, not competing threads or processes. Also, if you say a thread that can be interrupted is not deadlocked, then no thread can be deadlocked. – Pollack

@Pollack It is the accepted meaning of the word. This code merely blocks. There aren't two threads or even two actions here. – Pelota

@Jeremey No. There is a difference between permanently locked and deadlocked. A deadlock requires two or more resources. – Pelota

Answer 16

You write a thread which can receive messages from other threads telling it to, for example, terminate. You write code in the thread to monitor other threads and send them terminate messages and wait for a response. The thread would find itself in the list, send itself a message to terminate and wait for itself to terminate. If it wasn't written in a way which prioritised incoming messages over the wait state ...

Escapement

Answer 17

If you stretch the definition of the term deadlock: a single thread can find itself blocked on a non-reentrant lock that it took earlier.

Manifold

Answer 18

When a thread enters the synchronized block, it checks if the current thread is the owner of the lock, and if it is, the the thread just proceeds without waiting.

So I don't think it is possible.

Lilley

Answer 19

I know this is a old post. Here is another example how it could happen if your code has interaction with external resources:

I have a thread, that open a database connection, start a transactionA, and begin update. The same thread, open another connection, start another transactionB. However, because transactionA hasn't committed yet, and it has database table locked, transactionB happens to access this locked table, so it has to wait

In the end the same thread is block by itself because it opened up more than one database connection.

---

This happened a lot in the application that I work with because there are many modules in the application, and a thread can run though many methods. These methods opens their own connections. Since we had different developers write their code, they may not see the how their code are begin called, and therefore couldn't see the overall database transactions that opened by the application.

Sharice

Answer 20

The interviewer was right. A thread can deadlock itself according to JCIP. But how?

In the section 2.3.2 of the JCIP we have the following paragraph about Reentrancy:

Reentrancy facilitates encapsulation of locking behavior, and thus simplifies the development of objectͲoriented concurrentcode. Without reentrantlocks, the very natural-looking code in Listing 2.7, in which a subclass overrides a synchronized method and then calls the super class method, would deadlock.

The synchronized keyword's lock is a reentrant lock so a thread can lock and unlock in a nested manner but if you use a non-reentrant lock like the following example I wrote as a proof. You will have a deadlock! According to JCIP.

public class SelfDeadLock {


    public static class Father{
        volatile protected int n = 0;
        protected Lock ourLock = new Lock();

        public void writeSth(){
            try {
                ourLock.lock();
                n++;
                System.out.println("Father class: " + n);
            } catch (InterruptedException ex) {
                Logger.getLogger(SelfDeadLock.class.getName()).log(Level.SEVERE, null, ex);
            }
            ourLock.unlock();
        }
    }

    public static class Child extends Father{

        @Override
        public void writeSth() {
            try {
                ourLock.lock();
                n++;
                System.out.println("Child class: " + n);
                super.writeSth();
            } catch (InterruptedException ex) {
                Logger.getLogger(SelfDeadLock.class.getName()).log(Level.SEVERE, null, ex);
            }
            ourLock.unlock();
        }   
    }

    public static void main(String[] args) {
        Child child = new Child();
        child.writeSth();
    }
}

Grendel

But where does Java provide locks that aren't re-entrant? – Pelota

@EJP in the example on the answer. – Grendel

The lock used in the example is reentrant. See the Javadoc. Or else it is some home-grown thing we have no information about. – Pelota