Что такое Deadlock в Java?

Уровень знаний, необходимых для понимания статьи: вы прошли квесты Java Syntax и Java Core, и сейчас в процессе изучения Java Multithreading. Deadlock или дедлок в Java или взаимная блокировка — это ошибка, которая происходит когда нити имеют циклическую зависимость от пары синхронизированных объектов. Представьте, что одна нить входит в монитор объекта x, а другая — объекта y. Если нить в объекте x пытается вызвать любой синхронизированный метод объекта y, а объект y в то же самое время пытается вызвать любой синхронизированный метод объекта x, то нити застрянут в процессе ожидания.Ниже — пример из туториала java docs о таком понятии, как deadlock. Где тут происходит блокировка нитей?

public class Deadlock {
    static class Friend {
        private final String name;
        public Friend(String name) {
            this.name = name;
        }
        public String getName() {
            return this.name;
        }
        public synchronized void bow(Friend bower) {
            System.out.format("%s: %s" + "  has bowed to me!%n", this.name, bower.getName());
            bower.bowBack(this);
        }
        public synchronized void bowBack(Friend bower) {
            System.out.format("%s: %s"
                + " has bowed back to me!%n",
                this.name, bower.getName());            
        }
    }

    public static void main(String[] args) {
        final Friend alphonse =
            new Friend("Alphonse");
        final Friend gaston =
            new Friend("Gaston");
        new Thread(new Runnable() {
            @Override
            public void run() { 
               // System.out.println("Thread 1");
                alphonse.bow(gaston); 
               // System.out.println("Th: gaston bowed to alphonse");
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() { 
              //  System.out.println("Thread 2");
                gaston.bow(alphonse);
              //  System.out.println("2.gaston waiting alph bowed");
            }
        }).start();
    }
}

Здесь нужно понять две важные вещи:

1. Что именно делает каждая из одновременно выполняющихся нитей?
2. Какие локи используются?

Начнем с конца. Допустим, вы создали два объекта класса Friend: alphonse и gaston. У каждого из них есть свой лок. Таким образом, этих локов два: альфонсов и гастонов. При входе в синхронизированный метод объекта, его лок запирается, а когда из метода выходят, он освобождается (или отпирается). Теперь о нитях. Назовем первую нить Alphonse (с большой буквы, чтобы отличить от объекта alphonse). Вот что она делает (обозначим её буквой A, сокращённо от Alphonse):

A: alphonse.bow(gaston) — получает лок alphonse;
A: gaston.bowBack(alphonse) — получает лок gaston;
A: возвращается из обоих методов, тем самым освобождая лок. 

А вот чем в это время занята нить Gaston:

G: gaston.bow(alphonse) — получает лок gaston;
G: alphonse.bowBack(gaston) — получает лок alphonse;
G: возвращается из обоих методов, тем самым освобождая лок. 

Теперь сведем эти данные вместе и получим ответ. Нити могут переплетаться (то есть, их события совершатся) в разных порядках. Дедлок получится, например, если порядок будет таким:

A: alphonse.bow(gaston) — получает лок alphonse
G: gaston.bow(alphonse) — получает лок gaston
G: пытается вызвать alphonse.bowBack(gaston), но блокируется, ожидая лока alphonse
A: пытается вызвать gaston.bowBack(alphonse), но блокируется, ожидая лока gaston

В этом случае обе нити заблокированы и каждая ожидает, что другая отдаст лок. Но ни одна это не сделает, потому что для этого нужно завершить свой метод, а он заблокирован другой нитью. Поэтому они застряли на месте, случился deadlock. Впрочем, возможно и другое переплетение, в котором одна из нитей успеет завершиться до начала второй:

A: alphonse.bow(gaston) — получает лок alphonse
A: gaston.bowBack(alphonse) — получает лок gaston
A: возвращается из обоих методов, открывая оба лока
G: gaston.bow(alphonse) — получает лок gaston
G: alphonse.bowBack(gaston) — получает лок alphonse
G: возвращается из обоих методов, открывая оба лока

В этом случае взаимной блокировки нитей нет. Например, добавлен какой-то метод, позволяющий другой нити успеть выполниться. Когда результат зависит от порядка одновременно происходящих событий (запланированного порядка или скорости выполнения), такой процесс называется race condition по-русски — «состояние гонки». Не все race condition потенциально производят дедлок, однако, по моему опыту, дедлоки происходят только в race condition. Автор ответа: Dave Lillethun