Write a Program That Will Surely Go into Deadlock

Is it possible to write a guaranteed classic deadlock with synchronized methods?

Create two resources, and have each thread try to get one before releasing the other, but in different orders. For instance:

CountDownLatch a = new CountDownLatch (1);
CountDownLatch b = new CountDownLatch (1);

void one() throws InterruptedException {
  a.await();
  b.countDown();
}

void two() throws InterruptedException {
  b.await();
  a.countDown();
}

The thread that runs one can't release b, because it's waiting for a. It'll wait forever, because the thread that runs two can't release a because it's waiting for b.

One or the classic deadlock scenarios is when you acquire locks in reverse order.

Minimal Java JDBC program that immediately creates an SQL Server deadlock?

I think this does it:

import java.sql.*;
import java.util.*;
import java.util.concurrent.*;

/**
 * Creates an SQL Server deadlock.
 *
 * <pre>
   javac SQLServerDeadlock.java && java -cp ".:sqljdbc.jar" SQLServerDeadlock <server> <db-name> <username> <password>
 * </pre>
 */
public class SQLServerDeadlock {
    static String server, db, user, pw;
    static String TABLE_A = "TABLE_A", TABLE_B = "TABLE_B";
    static CountDownLatch latch = new CountDownLatch(2);

    public static void main(String... args) throws SQLException {
        server = args[0];
        db     = args[1];
        user   = args[2];
        pw     = args[3];
        Connection connection = null;
        try {
            Class.forName("com.microsoft.sqlserver.jdbc.SQLServerDriver");
            connection = getConnection();
            init(connection);
            Thread t1 = new Thread(new Update(TABLE_A, TABLE_B), "A-THEN-B");
            Thread t2 = new Thread(new Update(TABLE_B, TABLE_A), "B-THEN-A");
            if (Math.random() < .5) {
                t1.start();
                t2.start();
            } else {
                t2.start();
                t1.start();
            }
            t1.join();
            t2.join();
        } catch (Exception e) {
            System.err.println(e);
        } finally {
            cleanup(connection);
        }
    }

    static class Update implements Runnable {
        String table1;
        String table2;

        Update(String table1, String table2) {
            this.table1 = table1;
            this.table2 = table2;
        }

        @Override
        public void run() {
            Connection connection = null;
            try {
                connection = getConnection();
                Statement statement = connection.createStatement();
                statement.executeUpdate("UPDATE " + table1 + " SET FOO=1");
                latch.countDown();
                latch.await();
                statement.executeUpdate("UPDATE " + table2 + " SET FOO=1");
                connection.commit();
                System.err.println(Thread.currentThread().getName() + ": SUCCESS!");
            } catch (SQLException sqle) {
                if (sqle.getMessage().contains("Rerun the transaction")) {
                    System.err.println(Thread.currentThread().getName() + ": DEADLOCK VICTIM!");
                }
                System.err.println(sqle);
            } catch (InterruptedException ie) {
                System.err.println(ie);
            } finally {
                try {
                    connection.close();
                } catch (SQLException sqle) {
                    System.err.println(sqle);
                }
            }
        }
    }

    static void init(Connection connection) throws SQLException {
        Statement statement = null;
        try {
            statement = connection.createStatement();
            for (String tableName : Arrays.asList(TABLE_A, TABLE_B)) {
                if (tableExists(connection, tableName)) {
                    statement.execute("DROP TABLE " + tableName);
                }
                statement.execute("CREATE TABLE " + tableName + " (FOO INTEGER)");
                statement.execute("INSERT INTO  " + tableName + " VALUES (0)");
            }
            connection.commit();
        } finally {
            statement.close();
        }
    }

    static void cleanup(Connection connection) throws SQLException {
        if (connection == null) {
            return;
        }
        Statement statement = null;
        try {
            statement = connection.createStatement();
            for (String tableName : Arrays.asList(TABLE_A, TABLE_B)) {
                if (tableExists(connection, tableName)) {
                    statement.execute("DROP TABLE " + tableName);
                }
            }
            connection.commit();
        } finally {
            statement.close();
        }
    }

    static boolean tableExists(Connection connection, String tableName) throws SQLException {
        Statement statement = null;
        try {
            statement = connection.createStatement();
            String sql =
                " SELECT TABLE_NAME                         " +
                "   FROM INFORMATION_SCHEMA.TABLES          " +
                "  WHERE TABLE_CATALOG = '" + db        + "'" +
                "    AND TABLE_NAME    = '" + tableName + "'";
            ResultSet rs = statement.executeQuery(sql);
            return rs.next();
        } finally {
            statement.close();
        }
    }

    static Connection getConnection() throws SQLException {
        Connection connection = DriverManager.getConnection("jdbc:sqlserver://" + server + ";databaseName=" + db + ";", user, pw);
        connection.setAutoCommit(false);
        return connection;
    }
}

The randomization of thread starts isn't necessary, but doesn't affect correctness. The thread scheduler should interleave thread execution arbitrarily. However, in my environment I observed that the second thread to start was almost, but not quite always, the deadlock victim.

Locking strategies and techniques for preventing deadlocks in code

The technique you describe isn't just common: it's the one technique that has been proven to work all the time. There are a few other rules you should follow when coding threaded code in C++, though, among which the most important may be:

• don't hold a lock when calling a virtual function: even if at the time you're writing your code you know which function will be called and what it will do, code evolves, and virtual functions are there to be overridden, so ultimately, you won't know what it does and whether it will take any other locks, meaning you will lose your guaranteed order of locking
• watch out for race conditions: in C++, nothing will tell you when a given piece of data is shared between threads and you don't use some kind of synchronization on it. One example of this was posted in the C++ Lounge on SO chat a few days ago, by Luc, as an example of this (code at the end of this post): just trying to synchronize on something else that happens to be in the neighborhood doesn't mean your code is correctly synchronized.
• try to hide asynchronous behavior: you're usually better hiding your concurrency in your software's architecture, such that most calling code won't care whether there's a thread there or not. It makes the architecture easier to work with - especially for some-one who isn't used to concurrency.

I could go on for a while, but in my experience, the easiest way to work with threads is using patterns that are well-known to everyone who might work with the code, such as the producer/consumer pattern: it's easy to explain and you only need one tool (a queue) to allow your threads to communicate with each other. After all, the only reason for two threads to be synchronized with each other, is to allow them to communicate.

More general advice:

• Don't try your hand at lock-free programming until you've had experience with concurrent programming using locks - it's an easy way to blow your foot off, or run into very strange bugs.
• Reduce the number of shared variables and the number of times those variables are accessed to a bare minimum.
• Don't count on two events always occurring in the same order, even if you can't see any way of them reversing order.
• More generally: don't count on timing - don't think a given task should always take a given amount of time.

The following code will fail:

#include <thread>
#include <cassert>
#include <chrono>
#include <iostream>
#include <mutex>
 
void
nothing_could_possibly_go_wrong()
{
    int flag = 0;
 
    std::condition_variable cond;
    std::mutex mutex;
    int done = 0;
    typedef std::unique_lock<std::mutex> lock;
 
    auto const f = [&]
    {
        if(flag == 0) ++flag;
        lock l(mutex);
        ++done;
        cond.notify_one();
    };
    std::thread threads[2] = {
        std::thread(f),
        std::thread(f)
    };
    threads[0].join();
    threads[1].join();
 
    lock l(mutex);
    cond.wait(l, [done] { return done == 2; });
 
    // surely this can't fail!
    assert( flag == 1 );
}
 
int
main()
{
    for(;;) nothing_could_possibly_go_wrong();
}

Java, threads deadlocked?

The fact that you are not getting a deadlock does not imply a deadlock cannot occur.

You are right in inferring that a deadlock might occur when two threads attempt to acquire monitors on two different resources in opposite orders.

Therefore, this code may produce a deadlock.

However, if any of the two threads manages to acquire both the monitors before the other, no deadlock will occur (which seems to be happening with your execution).

Here's how a deadlock might occur instead:

1. Thread one starts and acquires lock on sb1
2. Thread two starts and acquires lock on sb2
3. Thread one waits to acquire lock on sb2, which is owned by thread two
4. Thread two waits to acquire lock on sb1, which is owned by thread one

As no thread will release its lock and both wait on the other, you get a deadlock.

Note: as Khelwood advises, forcing the threads to sleep may prevent one of the threads from acquiring both locks first, hence producing the deadlock.

Deadlock with a single thread in java

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.

---

Related Topics