Как можно упорядочить блокировки для предотвращения deadlock

Что проверяют

Понимаете ли вы, что взаимная блокировка возникает из-за разного порядка захвата, и знаете ли альтернативы.

Как отвечать

Классическая взаимная блокировка выглядит так: один поток захватил ресурс A и ждёт B, другой захватил B и ждёт A. Ни один не отпустит своё, и оба стоят навсегда.

Решение через глобальный порядок: договориться, что блокировки всегда захватываются в одной и той же последовательности, независимо от логики операции. Тогда цикл ожидания невозможен по построению: поток, дошедший до второй блокировки, точно не мешает тому, кто ещё не взял первую.

Порядок должен быть тотальным и вычислимым. Обычно берут идентификатор объекта:

void transfer(Account from, Account to, BigDecimal sum) {
    Account first  = from.id() < to.id() ? from : to;
    Account second = from.id() < to.id() ? to : from;

    synchronized (first) {
        synchronized (second) {
            from.withdraw(sum);
            to.deposit(sum);
        }
    }
}

Перевод в обратную сторону захватит те же объекты в том же порядке, и взаимная блокировка исчезает.

Тонкость: если идентификаторы могут совпасть, нужен запасной критерий, иначе получится попытка захватить одну и ту же блокировку дважды.

Альтернативы, которые стоит назвать:

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

Обнаружение: анализ дампов потоков, где видно, кто чего ждёт.

Где спотыкаются

Считают, что взаимная блокировка возможна только с двумя потоками.

Упорядочивают по адресу объекта, который может меняться.

Вызывают чужой код под блокировкой.

Держат блокировку во время обращения к сети.