Как избежать deadlock

Как избежать тупиковых блокировок в Java

В прошлой статье мы обсуждали многопоточность. В этот раз поговорим о главной проблеме многопоточных приложений — тупиковых взаимных блокировках, известных как deadlocks. Такие блокировки возникают, когда минимум два потока одновременно пытаются работать с общими ресурсами и ограничить доступ к этим ресурсам друг для друга. При этом часто создаётся ситуация, когда ни один поток не может ни получить нужный ресурс, ни освободить занимаемый. Для блокировки «конкурентов» поток может использовать mutex, критическую секцию или семафор.

Как происходит блокировка

Два потока работают с общими ресурсами.

Поток 1 захватывает Ресурс 1 и начинает операции с ним.

Поток 2 последовательно захватывает Ресурс 2 и Ресурс 1.

Поток 2 не получает доступа к Ресурсу 1 и в ступоре ждёт, когда тот освободится.

Поток 1 не завершил работу с Ресурсом 1, но пытается захватить Ресурс 2 и тоже впадает в ступор.

Как это выглядит в коде:

public class DeadlockTest < public static void main(String[] args) < final String res1 = "my sample text"; final String res2 = "some other text"; // Пусть поток P1 навесит замок на ресурс res1, а затем на res2 Thread P1 = new Thread() < public void run() < synchronized (res1) < System.out.println("Поток 1 навесил замок на Ресурс 1"); try < Thread.sleep(100);> catch (Exception e) <> synchronized (res2) < System.out.println("Поток 1 навесил замок на Ресурс 2"); > > > > // Поток P2 последовательно пытается запереть доступ к res2 и res1 Thread P2 = new Thread() < public void run() < synchronized (res2) < System.out.println("Поток 2 навесил замок на Ресурс 2"); try < Thread.sleep(100);> catch (Exception e) <> synchronized (res1) < System.out.println("Поток 2 навесил замок на Ресурс 1"); > > > > P1.start(); P2.start(); > >

Видимо-невидимо

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

Есть несколько способов уберечь Java-приложение от «падений» и «зависаний», связанных с противоречиями в работе потоков. Это механизмы synchronized и volatile, алгоритмы, реализованные в классах Java Concurrent, но главное — забота о структуре вашего приложения.

Ключевое слово volatile в Java

Модификатор volatile используют, когда нужно:

• обеспечить видимость данных — убедиться, что при обращении к переменной любой поток получит её последнее записанное значение;
• исключить кэширование значений переменной и хранить их только в основной памяти.

Как только один поток записал что-то в volatile-переменную, значение идёт прямо в общую память и тут же доступно остальным потокам:

class CarSharingBase < static volatile int your_car_ID = 3222233; >

Но учтите, что модификатор volatile никак не ограничивает одновременный доступ к данным. А значит, в работу одного потока с полем может вмешаться другой поток. Вот что будет, если два потока одновременно получат доступ к операции увеличения на единицу (i++):

int i = 0;

Поток 1: читает переменную (0)

Поток 1: прибавляет единицу

Поток 2: читает переменную (0)

Поток 1: записывает значение (1)

Поток 2: прибавляет единицу

Поток 2: записывает значение (1)

Если бы два потока не мешали друг другу, а работали последовательно, мы получили бы на выходе значение «2», но вместо этого видим единицу. Чтобы такого не происходило, нужно обеспечить атомарность операции. Атомарными называют операции, которые могут быть выполнены только полностью. Если они не выполняются полностью, они не выполняются вообще, но прервать их невозможно.

В примере с увеличением на единицу мы видим сразу три действия: чтение, сложение, запись. Чтение и запись — операции атомарные, но между ними могут вклиниться действия другого потока. Поэтому составная операция инкремента (i++) полностью атомарной не является.

Обратите внимание: с volatile-переменной возможны как атомарные, так и неатомарные операции. Ключевое слово volatile позволяет сделать так, чтобы все потоки читали одно и то же из основной памяти, но не более того.

Простейший способ гарантировать атомарность — выстроить потоки в очередь за ресурсами с помощью механизма synchronized. Представьте, что на электронный счёт одновременно переводят деньги два клиента. Уж лучше попросить одного из них немного подождать, чем допустить ошибки в денежных расчетах.

Ключевое слово synchronized

Модификатор synchronized исключает доступ второго и последующих потоков к данным, с которыми уже работает один поток. Это ключевое слово используют только для методов и произвольных блоков кода.

Используйте synchronized, чтобы:

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

Метод может быть статическим или нет — без разницы. Но синхронизация влияет на видимость данных в памяти. В прошлой статье мы говорили о взаимном исключении (mutex’e). С его помощью synchronized ограничивает доступ к данным. Образно говоря, это замок, с помощью которого поток запирается наедине с объектом, чтобы никто не мешал работать. Обратите внимание: замок запирают до начала работы. То есть проверка, не заняты ли ресурсы кем-то другим, происходит на входе в synchronized-блок или метод.

public class SynchronizeThis < private int syn_result; public synchronized int methodGet() < return syn_result; > >

Разблокировка же ресурсов происходит на выходе. Поэтому атомарность операций гарантирована.

Данные, которые изменились внутри метода или блока sychronized, находятся в кэше поверх основной памяти и видны следующему потоку, к которому перешёл мьютекс.

Подсказки по блокирующей синхронизации

Главное при работе с synchronized — правильно выбрать объект, по которому будет происходить проверка доступности ресурсов. Если вам нужна синхронизация на входе в метод, учитывайте, принадлежит этот метод классу или объекту. Вход в статичный метод блокируют по объекту класса, а в абстрактный метод — по this. Если по ошибке заблокировать метод класса по this, доступ к ресурсам останется открыт для всех.

Никогда не используйте synchronized в конструкторе — получите ошибку компиляции. А ещё остерегайтесь «матрёшек», когда синхронизированные методы одного класса вызывают внутри себя синхронизированные методы других классов.

Помните, что синхронизация требует ресурсов. При обработке большого массива данных вызов мьютексов становится особенно затратным. Чтобы гарантировать атомарность без синхронизации, используют классы Concurrent.

Атомарность с помощью Java Concurrent

Вернёмся к составной операции «чтение-изменение-запись». Когда нам нужно развести потоки по углам, но без мьютекса, можно использовать инструкцию «сравнение с обменом» — compare and swap (CAS).

Для этого сначала заводят переменную, по значению которой можно понять, заняты ли ресурсы и, если да, — кем. Например, пока ресурсы свободны, переменная хранит «-1», а если заняты — номер процессора, который с ними работает (0,1 и т.д.).

Поток приходит за свободными ресурсами, видит «-1», перезаписывает значение на номер процессора, на котором сам работает, выполняет действия. После завершения всех операций переменной возвращается значение «-1». Если же поток на входе видит номер какого-то процессора, он получает отказ и не может выполнить намеченную операцию. Это простейший случай сравнения с обменом. Важно понимать, что поток, который получил отказ, не блокируется. Он может сообщить программе, что у него проблемы, и перейти к запасному плану действий.

Можно сказать, что это более интеллигентная форма взаимодействия между потоками. Они уже не бодаются за ресурс и не закрывают дверь перед носом оппонента, а обмениваются сообщениями в духе: «Хотелось бы поработать вот с этим» — «Извините, оно пока занято. Не желаете ли кофе?».

На этом принципе построен целый ряд алгоритмов синхронизации, которые называют неблокирующими (non-blocking). Создание таких алгоритмов — задача не для новичка. Но, к статью, в Java «из коробки» есть несколько готовых неблокирующих решений. Они собраны в пакете java.util.concurrent.

ConcurrentLinkedQueue

На русский название класса переводится как «параллельная очередь». Работает такая очередь по принципу First In First Out («Первым зашёл — первым выйдешь»). Алгоритм основан на CAS, быстр и оптимизирован под работу со сборщиком мусора.

Если вы хотите создать очередь из объектов, а затем добавлять и удалять их в нужный момент, не нужно писать и синхронизировать методы вручную. Достаточно создать классы для потоков, производящих и потребляющих данные, а затем поставить эти потоки в очередь ConcurrentLinkedQueue.

В прошлой статье мы говорили, что в Java поток можно создать как экземпляр класса Thread или как отдельный класс с интерфейсом Runnable. Сейчас мы используем второй подход. Единственный метод интерфейса Runnable — run(). Чтобы задать нужное поведение для потребителя и производителя, мы будем переопределять этот метод в каждом случае по-своему.

Поток-производитель:

public class ProducerThread implements Runnable < @Override public void run() < System.out.println("Генерируем сообщения в очередь"); try < for (int i = 1; i  10; i++) < QueueTest.enqueueTask("Задача номер " + i); > > catch (Exception ex) < ex.printStackTrace(); > > >

Поток-потребитель:

public class ConsumerThread implements Runnable < @Override public void run() < String task; System.out.println("Ждём задачи \n"); //Пока есть задачи в очереди: while (QueueTest.isTaskHasBeenSet() || QueueTest.getQueue().size() > 0) < if ((task = QueueTest.getQueue().poll()) != null) System.out.println("Выполняю задачу : " + task); try < Thread.sleep(500); > catch (Exception ex) < ex.printStackTrace(); > > > >

Обратите внимание, если очередь пуста, метод poll() вернёт значение null. Поэтому нам нужно было убедиться, что он возвращает что-то другое.

Чтобы узнавать, сколько всего элементов в очереди, у класса ConcurrentLinkedQueue есть метод size(). Он работает медленно, поэтому злоупотреблять им не стоит. При необходимости можно вывести весь список элементов очереди методом toArray(), но сейчас нам это не нужно.

Очередь, в которой будут работать потоки:

import java.util.Queue; import java.util.concurrent.ConcurrentLinkedQueue; public class QueueTest < private static QueueString> queue = null; private static boolean taskHasBeenSet = false; public static void main(String[] args) < queue = new ConcurrentLinkedQueueString>(); // Создаём и запускаем потребителя и производителя Thread producer = new Thread(new ProducerThread()); Thread consumer = new Thread(new ConsumerThread()); producer.start(); consumer.start(); while (consumer.isAlive()) < try < // Оставим время на ожидание постановки задач Thread.sleep(1000); > catch (InterruptedException e) < // Выводим трейс вместе с текстом исключения e.printStackTrace(); > > // Всё выполнено нормально, выходим. System.exit(0); > public static QueueString> getQueue() < return queue; > // Добавляем задачи в очередь public static void enqueueTask(String task) < try < queue.add(task); System.out.println("Добавлена задача : " + task); Thread.sleep(200); > catch (InterruptedException ex) < ex.printStackTrace(); >> public static boolean isTaskHasBeenSet() < return taskHasBeenSet; > public static void setTaskHasBeenSet(boolean taskHasBeenSet) < QueueTest.taskHasBeenSet = taskHasBeenSet; > >

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

Атомарные классы

Пакет java.util.concurrent.atomic включает в себя классы для работы с:

• примитивами — AtomicBoolean, AtomicInteger, AtomicLong;
• ссылочными типами — AtomicReference;
• массивами — AtomicBooleanArray, AtomicIntegerArray, AtomicReferenceArray и др.;
• аккумуляторами — DoubleAccumulator, LongAccumulator;
• обновлениями («апдейтерами») — AtomicIntegerFieldUpdater, AtomicLongFieldUpdater, AtomicReferenceFieldUpdater.

Давайте посмотрим, как два потока могут работать с переменной AtomicInteger без синхронизации. Для этого создадим класс myThread, в котором будет атомарный счетчик:

import java.util.concurrent.atomic.AtomicInteger; class myThread extends Thread< public volatile AtomicInteger counter; /* Для наглядности тестирования мы сделали поле волатильным. Данные не попадут в кэш и работу двух потоков будет легче отследить */ myThread(AtomicInteger counter)< this.counter = counter; > @Override public void run() < for(int i = 0; i  1000; i++)< counter.updateAndGet(n -> n + 2); > // После работы счётчика в каждом потоке будем выводить значение: System.out.println(counter); > >

Для операций над числами мы использовали метод updateAndGet() класса AtomicInteger. Этот метод увеличивает число на основе аргумента — лямбда-выражения

Теперь посмотрим на всё это в действии. Создадим и запустим два потока myThread:

public class MultiCounter < public static void main(String[] args) < AtomicInteger myAtomicCounter = new AtomicInteger(0); // Создаём потоки myThread t1 = new myThread(myAtomicCounter); myThread t2 = new myThread(myAtomicCounter); t1.start(); t2.start(); > >

В результате работы кода получим два значения: первое из них будет случайным числом в диапазоне от 2000 до 4000, а второе — всегда 4000. Например, при первом запуске я получила результат:

Запустите код ещё раз и убедитесь, что меняется только первое значение. Второе число предсказуемо именно благодаря работе атомарного счётчика. Если бы мы использовали для счётчика обычный (неатомарный) Integer, второе число было бы случайным.

Блокирующие и неблокирующие алгоритмы в Java

Блокирующие алгоритмы парализуют работу потока — навсегда или до момента, пока другой поток не выполнит нужное условие. Представьте, что поток A заблокирован и ждёт, когда поток B завершит операцию. Но тот не завершает, потому что заблокирован кем-то ещё. Случайно создать такую западню в приложении очень легко, а вот просчитать, когда она сработает — трудно. Если без синхронизации можно обойтись, лучше обойдитесь — ради экономии нервов и ресурсов.

Неблокирующие алгоритмы тоже могут вести к проблемам, например, к live-lock. Это ситуация, когда несколько потоков буксуют: продолжают работать, но без реального результата. Причиной может быть загруженность потоков сообщениями друг от друга. Чем больше сообщение, тем больше оно грузит память. Другая возможная причина — неудачная реализация алгоритма, при которой в очереди возникает конфликт. Поэтому начинающим лучше не мастерить велосипед, а сначала разобраться с чужими наработками.

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

Два простых правила для предотвращения взаимных блокировок на мьютексах

Так сложилось, что это третий пост в блоге нашей компании, и, как и первые два, он посвящен вопросам многопоточного программирования и проблемам, которые при этом возникают. Получилось так неслучайно, ведь мы на собственной «шкуре» испытали, что ситуации, возникающие при написании многопоточных программ, невероятно сложны для отладки, так как во многом определяются динамикой работы программы на конкретной аппаратной платформе. Уверен, что большинство программистов сталкивались с ситуацией, когда программа, которая прекрасно работает на одном компьютере, на другом совершенно неожиданно начинает дедлочиться практически «на ровном месте».

При написании своих предыдущих постов мы совершили непростительную ошибку, начав рассматривать взаимные блокировки со сложных, но, как нам казалось, наиболее интересных случаев. Этого уважаемая аудитория Хабра, к сожалению, не оценила. Спешим исправиться, и, пусть не с первого раза, но все-таки подойти к рассмотрению проблемы блокировок с самого начала. Однако мы все же рассчитываем, что вы знаете, зачем нужны и какие бывают средства синхронизации при написании многопоточных программ.

Рецепты, описанные в этом посте весьма просты, но далеко не все даже профессиональные программисты используют осознанно, руководствуясь скорее ощущениями «почему-то кажется, что не стоит захватывать тот мьютекс из под захваченного этого». Так жили и мы долгие-долгие годы, когда в один ужасно ответственный момент не обнаружили, что на «железке», которую нужно срочно отправить заказчику, наш любимый софт не может и часа прожить без дедлока. Убив на решение этой задачи несколько дней работы своих ведущих программистов, мы приняли решение, которое изменило нашу жизнь – мы занялись суровой формализацией ситуаций взаимных блокировок, включающей строгие математические доказательства того, почему так можно делать, а так нельзя. Надо сказать, что исследование наше выродилось в кандидатскую диссертацию одного из сотрудников, но я не уверен, что использованный там формат изложения будет интересен здесь…

Итак, о блокировках с самого начала…

Природа взаимных блокировок

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

Традиционно принято считать, что причиной блокировок всегда являются мьютексы (mutex), однако это не совсем точно. Причиной блокировок могут являться любые средства и механизмы синхронизации, которые предполагают ожидание чего-либо одного потока со стороны другого, например, ожидание сигнала на переменной кондиции (condition variable) или, что значительно менее очевидно, ожидание завершение другого потока (wait/join thread). В теории, на самом деле, второй случай является тем же самым «ожиданием сигнала», однако ввиду неявности этой операции синхронизации, при поиске дедлоков о ней просто забывают, как о потенциальном источнике угрозы и часто не замечают в коде.

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

Несколько слов о модели многопоточных программ

Мы назвали эту модель – «моделью переходов» и представляет она собой совокупность ориентированных графов, где каждый граф представляет собой поток (субъект). Каждый граф имеет одну начальную вершину, соответствующую состоянию, когда ни одно средство синхронизации еще не задействовано, и имеет одну конечную вершину, соответствующую состоянию, когда ни одно средство синхронизации уже не задействовано. Предполагается, что при достижении конечной вершины поток автоматически начинается сначала. Все другие вершины графов представляют собой операцию в отношении того или иного средства синхронизации, например, L (lock) – захват мьютекса, U (unlock) – отпускание мьютекса и т.д. Для доказательств утверждений важно, что модель игнорирует время между выполнениями отдельных операций в отношении средств синхронизации, расширяя тем самым возможный диапазон динамик до бесконечности. Если аудитории Хабра интересна математическая и физическая суть модели, то я готов написать отдельный пост на эту тему, а здесь… всего лишь начало долгой, но интересной истории о многопоточном программировании.

Пример модели, состоящей из одного потока (субъекта):

Рисунок 1.

В соответствии с данным рисунком, субъект может пройти по двум веткам: 0, L1, U1, 0 или 0, L1, L2, U2, U1, 0. Эта схема может рассматриваться, как конечный автомат, грамматика которого включает две фразы и . Будем считать, что время перехода между действиями в отношении средств синхронизации конечно, т.е. алгоритмически корректно. Не будем считать ошибкой синхронизации захват и удержание мьютекса в течение ожидания какого-либо действия пользователя, которое потенциально может никогда не наступить.
Для исследования программы на потенциальную возможность возникновения ситуации взаимной блокировки необходимо составить цепочки выполнения всех возможных субъектов в программе.

Простейшая взаимная блокировка с участием мьютексов

Пусть в нашей программе помимо потока (субъекта), приведенного на рисунке 1, есть еще один:

Рисунок 2.

Смею утверждать, что наша программа имеет потенциальный deadlock и даже, если ваши тестировщики утверждают, что все прекрасно работает, то вы не застрахованы от ситуации, что на другом «железе» ваша программа поведет себя вот так:

Рисунок 3.

Ничего не мешает нашим двух независимым потокам выполниться так: поток 1 успел захватить мьютекс 1, затем планировщик переключил выполнение на поток 2, который захватил мьютекс 2, и после этого оба наших потока пытаются захватить мьютексы, которые уже захвачены – deadlock!

Назовем систему потоков (субъектов) несовместимой, если существуют хотя бы один вариант наложения цепочек их выполнения, при котором наступает ситуация взаимной блокировки. Соответственно, совместимой является такая система субъектов, для которой не существует динамики, при которой возможно возникновение ситуации взаимной блокировки.
Рассмотренные два субъекта являются несовместимыми, т.к. существует вариант наложения, приведенный на рисунке 3, при котором возникает ситуация взаимной блокировки. Отметим, что такие субъекты не обязательно будут приводить к блокировке (зависанию) программы. Динамика конкретной работы (время переходов между обращениями к средствам синхронизации) может быть такова, что найденный вариант наложения никогда не проявится в реальности. В любом случае, программный код, описываемый такой моделью, является потенциально опасным и блокировки могут проявиться при портировании на другую программную или аппаратную платформу, а также просто при изменении условий функционирования.

Рисунок 4

Важно помнить, что потоки могут быть попарно совместимы между собой, но не совместимы в большей комбинации. На рисунке 5 показана модель программы, где все субъекты попарно совместимы между собой, но все вместе приводят к ситуации взаимной блокировки.

Рисунок 5

На рисунке 6 показан другой вариант совмещения цепочек выполнения для модели, представленной на рисунке 5, при котором возникает взаимная блокировка.

Рисунок 6

Прямо так и хочется сказать: Как страшно жить!

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

Первое правило

Всегда отпускайте захваченные мьютексы в обратном захвату порядке, т.е. руководствуйтесь логикой «первый захвачен – последний отпущен».

Второе правило

Всегда соблюдайте один и тот же порядок захвата мьютексов.
Если вы в одном потоке захватываете мьютекс 1, а затем мьютекс 2, то недопустимо захватывать их в ином порядке в другом потоке.
На самом деле, правило не так просто, как кажется на первый взгляд. Еще раз посмотрим внимательно на Рисунок 6. Там это правило нарушено, но это несколько неочевидно. Глядя на первый поток, мы фиксируем, что мьютекс 2 мы захватываем после мьютекса 1. Глядя на второй поток, мы фиксируем, что мьютекс 3 мы захватываем после мьютекса 2. Объединение этих наблюдений означает, что мьютекс 3 мы захватываем после мьютекса 1, что не выполняется в потоке 3. Результатом этого невыполнения является deadlock, который и показан на рисунке.

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

В заключение хотелось бы задать вопрос: интересна ли эта тема аудитории Хабра? Если да, то есть желание и возможность рассказать о чуть более интересных ситуациях, возникающих при использовании сигнальных переменных и, может быть, немного глубже окунуться в доказательную базу – это уже для искушенных программистов многопоточных приложений.

Надеюсь, этот пост был полезен.

Как избежать deadlock java

Deadlock (зависание) — это ситуация, когда два или более потоков блокируются, ожидая друг друга, чтобы освободить занятые ими ресурсы, и таким образом не могут продолжить работу. Избежать deadlock в Java можно следующими способами:

• Избегайте вложенных блокировок ( nested locking ). Если у вас есть несколько объектов, которые вы пытаетесь заблокировать, убедитесь, что вы блокируете их в одном и том же порядке во всех потоках.
• Используйте методы с таймаутом ( timeout ) при блокировке ресурсов. Это поможет избежать зависания, когда один поток блокирует ресурс и не освобождает его.
• Используйте неблокирующие алгоритмы и структуры данных. Вместо блокировки ресурсов вы можете использовать алгоритмы, которые не блокируют потоки, чтобы избежать deadlock
• Используйте синхронизированные блокировки ( synchronized locks ) только тогда, когда это необходимо. Избегайте использования синхронизированных блокировок, когда это не обязательно.
• Используйте инструменты, такие как JConsole и jstack , для выявления deadlock в вашем приложении. Эти инструменты могут помочь определить, какие потоки заблокированы и почему.

Взаимная блокировка (deadlock) в Java и методы борьбы с ней

При разработке многопоточных приложений часто возникает дилемма: что важнее надежность или работоспособность приложения. Например, мы используем синхронизацию для поточной безопасности (thread safety), при этом в случаи, неверного порядка синхронизации, мы можем вызвать взаимную блокировки. Так же, мы используем пулы потоков и семафоры, для ограничения потребления ресурсов, при этом ошибка в таком дизайне может привести к взаимной блокировке, вследствие недостатка ресурсов. В данной статье мы поговорим о том, как избегать взаимной блокировки, а так же других проблем в работоспособности приложения. Так же мы рассмотрим, как может приложение быть написано таким образом, чтоб иметь возможность восстановится в случаи взаимной блокировки. Взаимная блокировка – это ситуация в которой, два или более процесса занимая некоторые ресурсы, пытаются заполучить некоторые другие ресурсы, занятые другими процессами и ни один из процессов не может занять необходимый им ресурс, и соответственно освободить занимаемый. Данное определение слишком общее, поэтому сложно для восприятия, для лучшего его понимания мы рассмотрим типы взаимных блокировок на примерах.

Взаимная блокировка порядка синхронизации

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

 public void transferMoney(Account fromAccount, Account toAccount, Amount amount) throws InsufficientFundsException < synchronized (fromAccount) < synchronized (toAccount) < if (fromAccount.getBalance().compareTo(amount) < 0) throw new InsufficientFundsException(); else < fromAccount.debit(amount); toAccount.credit(amount); >> > > 

На первый взгляд, данный код синхронизирован вполне нормально, мы имеем атомарную операцию проверки и изменения состояния счета-источника и изменение счета-получателя. Но, при данной стратегии синхронизации может возникнуть ситуация взаимной блокировки. Давайте рассмотрим пример того, как это происходит. Необходимо произвести две транзакции: со счета A на счет B перевести x денег, а со счета B на счет A – y. Зачастую эта ситуация не вызовет взаимной блокировки, однако, при неудачном стечении обстоятельств, транзакция 1 займет монитор счета A, транзакция 2 займет монитор счета B. Результат – взаимная блокировка: транзакция 1 ждет, пока транзакция 2 освободит монитор счета B, но для этого транзакция 2 должна получить доступ к монитору A, занятому транзакцией 1. Одна из больших проблем с взаимными блокировками – что их нелегко найти при тестировании. Даже в ситуации, описанной в примере, потоки могут не заблокироваться, то есть данная ситуация не будет постоянно воспроизводится, что значительно усложняет диагностику. В целом описанная проблема недетерминированности является типичной для многопоточности (хотя от этого не легче). Потому, в повышении качества многопоточных приложений важную роль играет code review, поскольку он позволяет выявить ошибки, которые проблематично воспроизвести при тестировании. Это, конечно же, не значит, что приложение не надо тестировать, просто о code review тоже не надо забывать. Что нужно сделать, чтобы этот код не приводил к взаимной блокировке? Данная блокировка вызвана тем, что синхронизация счетов может происходить в разном порядке. Соответственно, если ввести некоторый порядок на счетах (это некоторое правило, позволяющее сказать, что счет A меньше чем счет B), то проблема будет устранена. Как это сделать? Во-первых, если у счетов есть какой-то уникальный идентификатор (например, номер счета) численный, строчный или еще какой-то с естественным понятием порядка (строки можно сравнивать в лексикографическом порядке, то можем считать, что нам повезло, и мы всегда можем сначала занимать монитор меньшего счета, а потом большего (или наоборот).

 private void doTransfer(final Account fromAcct, final Account toAcct, final DollarAmount amount) throws InsufficientFundsException < if (fromAcct.getBalance().compareTo(amount) < 0) throw new InsufficientFundsException(); else < fromAcct.debit(amount); toAcct.credit(amount); >> public void transferMoney(final Account fromAcct, final Account toAcct, final DollarAmount amount) throws InsufficientFundsException < int fromId= fromAcct.getId(); int toId = fromAcct.getId(); if (fromId < toId) < synchronized (fromAcct) < synchronized (toAcct) < doTransfer(fromAcct, toAcct, amount)>> > > else < synchronized (toAcct) < synchronized (fromAcct) < doTransfer(fromAcct, toAcct, amount)>> > > > 

Второй вариант, если такого идентификатора у нас нет, то придется его придумать самим. Мы можем в первом приближении сравнивать объекты по хеш-коду. Скорее всего, они будут отличаться. Но что делать, если они все же окажутся одинаковыми? Тогда придется добавить еще один объект для синхронизации. Это может выглядеть несколько изощренным, но что поделать. Да и к тому же, третий объект будет использоваться довольно редко. Результат будет выглядеть следующим образом:

 private static final Object tieLock = new Object(); private void doTransfer(final Account fromAcct, final Account toAcct, final DollarAmount amount) throws InsufficientFundsException < if (fromAcct.getBalance().compareTo(amount) < 0) throw new InsufficientFundsException(); else < fromAcct.debit(amount); toAcct.credit(amount); >> public void transferMoney(final Account fromAcct, final Account toAcct, final DollarAmount amount) throws InsufficientFundsException < int fromHash = System.identityHashCode(fromAcct); int toHash = System.identityHashCode(toAcct); if (fromHash < toHash) < synchronized (fromAcct) < synchronized (toAcct) < doTransfer(fromAcct, toAcct, amount); >> > else if (fromHash > toHash) < synchronized (toAcct) < synchronized (fromAcct) < doTransfer(fromAcct, toAcct, amount); >> > else < synchronized (tieLock) < synchronized (fromAcct) < synchronized (toAcct) < doTransfer(fromAcct, toAcct, amount) >> > > > 

Взаимная блокировка между объектами

Описанные условия блокировки представляют наиболее простой по диагностике случай взаимной блокировки. Зачастую в многопоточных приложениях различные объекты пытаются получить доступ к одним и тем же синхронизированным блокам. При этом может возникнуть взаимная блокировка. Рассмотрим следующий пример: приложение для диспетчера полетов. Самолеты сообщают диспетчеру, когда они прибыли на место назначения и запрашивают разрешение на посадку. Диспетчер хранит всю информацию о самолетах, летящих в его направлении, и может строить их положение на карте.

 class Plane < private Point location, destination; private final Dispatcher dispatcher; public Plane(Dispatcher dispatcher) < this.dispatcher = dispatcher; >public synchronized Point getLocation() < return location; >public synchronized void setLocation(Point location) < this.location = location; if (location.equals(destination)) dispatcher.requestLanding(this); >> class Dispatcher < private final Setplanes; private final Set planesPendingLanding; public Dispatcher() < planes = new HashSet(); planesPendingLanding = new HashSet(); > public synchronized void requestLanding(Plane plane) < planesPendingLanding.add(plane); >public synchronized Image getMap() < Image image = new Image(); for (Plane plane : planes) image.drawMarker(plane.getLocation()); return image; >> 

Понять, что в этом код есть ошибка, которая может привести к взаимной блокировке сложнее, чем в предыдущем. На первый взгляд, в нем нет повторных синхронизаций, однако это не так. Вы, наверное, уже заметили, что методы setLocation класса Plane и getMap класса Dispatcher , являются синхронизированными и вызывают внутри себя синхронизированные методы других классов. Это в целом плохая практика. О том, как это можно исправить, речь пойдет в следующем разделе. В результате, если самолет прибывает на место, в тот же момент, как кто-то решает получить карту может возникнуть взаимная блокировка. То есть, будут вызваны методы, getMap и setLocation , которые займут мониторы экземпляров Dispatcher и Plane соответственно. Затем метод getMap вызовет plane.getLocation (в частности для экземпляра Plane , который в данный момент занят), который будет ждать освобождения монитора для каждого из экземпляров Plane . В то же время в методе setLocation будет вызван dispatcher.requestLanding , при этом монитор экземпляра Dispatcher остается занят рисованием карты. Результат – взаимная блокировка.

Открытые вызовы

С целью не допускать ситуаций вроде описанной в предыдущем разделе рекомендуется использовать открытые вызовы к методам других объектов. То есть, вызывать методы других объектов вне синхронизированного блока. Если с применением принципа открытых вызовов переписать методы setLocation и getMap возможность взаимной блокировки будет устранена. Выглядеть это будет, например, так:

 public void setLocation(Point location) < boolean reachedDestination; synchronized(this)< this.location = location; reachedDestination = location.equals(destination); >if (reachedDestination) dispatcher.requestLanding(this); > ……………………………………………………………………………… public Image getMap() < Setcopy; synchronized(this)< copy = new HashSet( planes); > Image image = new Image(); for (Plane plane : copy) image.drawMarker(plane.getLocation()); return image; > 

Ресурсная взаимная блокировка

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

Как избегать взаимных блокировок?

Безусловно, если код написан без каких-либо ошибок (примеры которых мы видели в предыдущих разделах), то взаимных блокировок в нем не будет. Но кто может поручиться, что его код написан без ошибок? Безусловно, тестирование помогает выявить значительную часть ошибок, но как мы уже видели ранее, ошибки в многопоточном коде нелегко диагностировать и даже после тестирования нельзя быть уверенным в отсутствии ситуаций взаимных блокировок. Можем ли мы как-то перестраховаться от блокировок? Ответ – да. Подобные техники применяются в движках баз данных, которым нередко необходимо восстанавливаться после взаимных блокировок (связанных с механизмом транзакций в БД). Интерфейс Lock и его реализации доступные в пакете java.util.concurrent.locks позволяют попытаться занять монитор, связанный с экземпляром данного класса методом tryLock (возвращает true, если удалось занять монитор). Пусть у нас есть пара объектов реализующих интерфейс Lock и нам необходимо занять их мониторы так, чтоб избежать взаимной блокировки. Реализовать это можно так:

 public void twoLocks(Lock A, Lock B) < while(true)< if(A.tryLock())< if(B.tryLock()) < try< //do something >finally < B.unlock(); A.unlock(); >> else < A.unlock(); >> > > 

Как видно в этой программе мы занимаем два монитора, при этом, исключая возможность взаимной блокировки. Обратите внимание, блок try- finally необходим, поскольку классы из пакета java.util.concurrent.locks автоматически не освобождают монитор, и если в процессе выполнения вашей задачи возникло какое-то исключение, то монитор зависнет в заблокированном состоянии. Как диагностировать взаимные блокировки? JVM позволяет диагностировать взаимные блокировки отображая их в дампах потоков. Такие дампы включают информацию о том, в каком состоянии находится поток. Если он заблокирован, то дамп содержит информацию о мониторе, освобождения которого поток ожидает. Прежде чем вывести дамп потоков JVM просматривает граф ожидаемых (занятых) мониторов, и если находит циклы – добавляет информацию о взаимной блокировке, указывая участвующие мониторы и потоки. Дамп потоков с взаимной блокировкой выглядит так:

 Found one Java-level deadlock: ============================= "ApplicationServerThread": waiting to lock monitor 0x0f0d80cc (a MyDBConnection), which is held by "ApplicationServerThread" "ApplicationServerThread": waiting to lock monitor 0x0f0d8fed (a MyDBCallableStatement), which is held by "ApplicationServerThread" Java stack information for the threads listed above: "ApplicationServerThread": at MyDBConnection.remove_statement - waiting to lock (a MyDBConnection) at MyDBStatement.close - locked (a MyDBCallableStatement) . "ApplicationServerThread": at MyDBCallableStatement.sendBatch - waiting to lock (a MyDBCallableStatement) at MyDBConnection.commit - locked (a MyDBConnection) 

Приведенный выше дамп явно показывает, что два потока, работающие с базой данных заблокировали друг друга. Для того чтоб диагностировать взаимные блокировки с помощью этой особенности JVM необходимо разместить вызовы операции дампа потоков в различных местах программы и провести тестирование приложения. Далее следует проанализировать полученные логи. В случаи если в них будет указано, что произошла взаимная блокировка, информация из дампа поможет обнаружить условия ее возникновения. В целом, следует не допускать ситуаций, приведенных в примерах взаимных блокировок. В таком случаи приложение, скорее всего, будет работать стабильно. Но не забывайте о тестировании и код ревью. Это поможет выявить неполадки, если они все же возникнут. В случаи, если вы разрабатываете систему, для которой критично восстановление поле взаимных блокировок, можно использовать метод, описанный в разделе «Как избегать взаимных блокировок?». В этом случаи может так же оказаться полезным метод lockInterruptibly интерфейса Lock из пакета java.util.concurrent.locks . Он позволяет прервать поток занявший монитор этим методом(и таким образом освободить монитор).