• ,

Взаимная блокировка(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 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, если удалось занять монитор). Пусть у нас есть пара объектов реализующих интерфейс 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 <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 необходимо разместить вызовы операции дампа потоков в различных местах программы и провести тестирование приложения. Далее следует проанализировать полученные логи. В случаи если в них будет указано, что произошла взаимная блокировка, информация из дампа поможет обнаружить условия ее возникновения.

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

3 комментария

tema_emelyan
что такое tieLock в первом последнем примере из первой секции?
driver
private static final Object tieLock = new Object();
Alvisid
По моему, во взаимной блокировке уровня синхронизации допущена небольшая неточность:
в случае если счета обладают ID(первый пример) в методе transferMoney должно быть не
int fromId = fromAcct.getId();
int toId = fromAcct.getId();


, а
int fromId = fromAcct.getId();
int toId = toAcct.getId();


Наверное, имеет место опечатка.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.