Deadlock with a single thread in java

Question

I read that a single user thread can deadlock with a system thread. My question is , this system thread can be any thread (not necessarily a java thread) that is sharing resources with the java thread. E.g. : I/O on 2 files after taking lock on the files. So unless the system thread shares the resource with the java thread, it can't create deadlock. Is there any other example of the above statement in bold.

Another question:

If there are 2 functions using 2 locks, they should lock in the same order. But is it mandatory to release in the same reverse order. Can the lock release order differ for the 2 functions E.g :

function1() {
   try {
    lock1.lock();
    lock2.lock();
   } finally {
     lock2.unlock();
     lock1.unlock();
   }
}

function2() {
   try {
    lock1.lock();
    lock2.lock();
   } finally {
     lock1.unlock();
     lock2.unlock();
   }
}

Link for reference : if a single user thread deadlocks, a system thread must also be involved

Answer 1

It's correct that a single Java thread cannot deadlock against itself if only Java object monitor locks are involved.

It's not entirely clear what you mean by "system thread". Even when running a simple program, a JVM will have several threads running, such as a finalizer thread, or for GUI applications, an event distribution thread (EDT). These threads can potentially take Java object monitor locks and therefore deadlock against a single application thread.

A single Java thread can deadlock against external processes, not other Java threads. For example, consider this program:

public static void main(String[] args) throws Exception {
    Process proc = Runtime.getRuntime().exec("cat");

    byte[] buffer = new byte[100_000];
    OutputStream out = proc.getOutputStream();
    out.write(buffer);
    out.close();

    InputStream in = proc.getInputStream();
    int count = in.read(buffer);
    System.out.println(count);
}

This runs "cat" which simply copies from stdin to stdout. This program will usually deadlock, since it writes a large amount of data to the subprocess. The subprocess will block writing to its output, since the parent hasn't read it yet. This prevents the subprocess from reading all its input. Thus the Java thread has deadlocked against the subprocess. (The usual way to deal with this situation is to have another Java thread read the subprocess output.)

A single Java thread can deadlock if it's waiting for a notification that never occurs. Consider:

public static void main(String[] args) throws InterruptedException {
    Object obj = new Object();
    synchronized (obj) {
        obj.wait();
    }
}

This program will never terminate since nothing will ever notify obj or interrupt the thread. This may seem a bit contrived, but instances of this "lost wakeup problem" do occur in practice. A system with bugs may fail to set state properly, or call notify at the wrong time, or call notify instead of notifyAll, leaving a thread blocked in a wait call awaiting a notification that will never occur. In such cases it might be hard to identify another thread that this thread is deadlocked against, since that thread might have died in the past, or it might not have been created yet. But it is surely deadlock.

UPDATE

I ran across another example of a single-threaded deadlock. Goetz et. al., Java Concurrency In Practice p. 215, describes thread-starvation deadlock. Consider an example where

a task that submits a task and waits for its result executes in a single-threaded Executor. In that case, the first task will wait forever, permanently stalling that task and all others waiting to execute in that Executor.

(A single-threaded Executor is basically a single thread processing a queue of tasks, one at a time.)

UPDATE 2

I've found another example in the literature of a single-thread deadlock:

There are three patterns of pairwise deadlock that can occur using monitors. In practice, of course, deadlocks often involve more than two processes, in which case the actual patterns observed tend to be more complicated; conversely, it is also possible for a single process to deadlock with itself (for example, if an entry procedure is recursive).

Lampson, Butler W., and David D. Redell. Experience with Processes and Monitors in Mesa. CACM Vol. 23 No. 2, Feb 1980.

Note that in this paper, a "process" refers to what we'd call a thread and an "entry procedure" is like a synchronized method. However, in Mesa, monitors are not re-entrant, so a single thread can deadlock itself if it attempts to enter the same monitor a second time.

The same is true in Posix threads. If a thread calls pthread_mutex_lock a second time on a normal (i.e., not recursive) mutex, the thread will deadlock on itself.

From these examples, I conclude that "deadlock" does not strictly require two or more threads.

Answer 2

For the first question: think of any Swing application. The main thread may interfere with the Event Dispatch Thread for example easily (since all the event handling takes place in that specific thread). Also, you could play around with the finalizer thread.

For the second question: yes, you can release the locks in any order.