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

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

Кратко

• Взаимная блокировка возникает, когда потоки захватывают одни и те же блокировки в разном порядке и начинают ждать друг друга.
• Главное лекарство это единый порядок захвата. Сортировать блокировки можно по естественному идентификатору, а если его нет, по System.identityHashCode.
• Второй источник проблем это вызов чужого синхронизированного метода изнутри своего синхронизированного блока. Спасают открытые вызовы: наружу выходим до вызова.
• Блокировка бывает и ресурсной, когда потоки в разном порядке берут соединения из пула или другие ограниченные ресурсы.
• Если гарантий дать нельзя, помогает tryLock() из java.util.concurrent.locks: поток не зависает, а откатывается и пробует снова.
• Готовую блокировку видно в дампе потоков: JVM сама пишет «Found one Java-level deadlock» и показывает, кто кого ждет.

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

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

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 = toAcct.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 Set<Plane> planes;
	private final Set<Plane> planesPendingLanding;

	public Dispatcher() {
		planes = new HashSet<Plane>();
		planesPendingLanding = new HashSet<Plane>();
	}
	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() {
	Set<Plane> copy;
	synchronized(this){
		copy = new HashSet<Plane>( planes);
	}
	Image image = new Image();
	for (Plane plane : copy)
		image.drawMarker(plane.getLocation());
	return image;
}

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

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

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

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

public void twoLocks(Lock A, Lock B) {
	while (true) {
		if (A.tryLock()) {
			try {
				if (B.tryLock()) {
					try {
						//do something
						return;
					} finally {
						B.unlock();
					}
				}
			} finally {
				A.unlock();
			}
		}
	}
}

Как видно в этой программе мы занимаем два монитора, при этом, исключая возможность взаимной блокировки. Обратите внимание, блок try-finally необходим, поскольку классы из пакета java.util.concurrent.locks автоматически не освобождают монитор, и если в процессе выполнения вашей задачи возникло какое-то исключение, то монитор зависнет в заблокированном состоянии. Блоков try-finally здесь два, и вложены они не для красоты. Внешний освобождает A в любом случае, даже если B.tryLock() сам бросит исключение: иначе код, который защищает от вечного зависания, сам бы его и устроил. Ровно так этот прием показан в документации к методу tryLock(). Второе, без чего пример не работает, это return после выполненной задачи. Без него while (true) пойдет на второй круг и сделает ту же работу заново, и так до бесконечности. Осталась одна шероховатость. Если два потока промахиваются синхронно, цикл может долго крутиться вхолостую и жечь процессор. На этот случай у интерфейса есть версия с таймаутом, tryLock(long time, TimeUnit unit): она ждет заданное время, а не возвращает false сразу.

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

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 <0x6f50f730> (a MyDBConnection)
at MyDBStatement.close
- locked <0x604ffbb0> (a MyDBCallableStatement)
...
"ApplicationServerThread":
at MyDBCallableStatement.sendBatch
- waiting to lock <0x604ffbb0> (a MyDBCallableStatement)
at MyDBConnection.commit
- locked <0x6f50f730> (a MyDBConnection)

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

1. разместить вызовы операции дампа потоков в различных местах программы;
2. провести тестирование приложения;
3. проанализировать полученные логи.

В случае если в них будет указано, что произошла взаимная блокировка, информация из дампа поможет обнаружить условия ее возникновения. Снять дамп у уже запущенного процесса можно и снаружи, утилитой jstack из состава JDK. Три разобранных типа блокировок и способы их лечения удобно держать перед глазами одним списком. В целом, следует не допускать ситуаций, приведенных в примерах взаимных блокировок. В таком случае приложение, скорее всего, будет работать стабильно. Но не забывайте о тестировании и код ревью. Это поможет выявить неполадки, если они все же возникнут. В случае, если вы разрабатываете систему, для которой критично восстановление после взаимных блокировок, можно использовать метод, описанный в разделе «Как избегать взаимных блокировок?». В этом случае может так же оказаться полезным метод lockInterruptibly интерфейса Lock из пакета java.util.concurrent.locks. Работает он не так, как иногда думают: чужой поток он не трогает. В документации сказано «Acquires the lock unless the current thread is interrupted», то есть поток, который ждет блокировку через этот метод, можно прервать снаружи вызовом interrupt(), и он выйдет из ожидания с InterruptedException вместо того, чтобы висеть вечно. Обычный synchronized так прервать нельзя.

Вопросы и ответы

Что такое deadlock в Java простыми словами?

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

Из-за чего чаще всего возникает взаимная блокировка?

Из-за разного порядка захвата блокировок. Классический пример это перевод денег между двумя счетами: одна транзакция берет сначала счет A, потом B, а встречная наоборот, и если они стартуют одновременно, каждая занимает половину нужного и ждет вторую.

Как избежать взаимной блокировки?

Захватывать блокировки всегда в одном и том же порядке. Если у объектов есть естественный идентификатор, сортируйте по нему, если нет, подойдет System.identityHashCode с запасным общим объектом на случай совпадения. И не вызывайте чужие синхронизированные методы изнутри своего синхронизированного блока.

Что такое открытые вызовы?

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

Почему deadlock так трудно поймать тестами?

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

Как понять, что приложение попало в deadlock?

По дампу потоков. Перед выводом дампа JVM сама обходит граф занятых мониторов и, если находит цикл, печатает строку Found one Java-level deadlock и показывает, какой поток какой монитор ждет. Снять дамп у работающего процесса можно утилитой jstack из состава JDK.

Читайте также

• Что такое Deadlock в Java?
• Synchronized в Java, синхронизация потоков
• Синхронизация потоков, блокировка объекта и блокировка класса
• Thread в Java: Часть I, потоки