Взаємне блокування (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);
			}
		}
	}
}

На перший погляд, цей код синхронізований цілком нормально, ми маємо атомарну операцію перевірки та зміни стану рахунку-джерела та зміну рахунку-отримувача. Проте, за цієї стратегії синхронізації може виникнути ситуація взаємної блокування. Розгляньмо приклад того, як це відбувається. Необхідно зробити дві транзакції: з рахунку на рахунок B переказати x грошей, а з рахунку на рахунок A – y. Найчастіше ця ситуація не викличе взаємного блокування, однак, при невдалому збігу обставин, транзакція 1 займе монітор рахунку A, транзакція 2 займе монітор рахунку B. Результат - взаємне блокування: транзакція 1 чекає, поки транзакція 2 звільнить монітор 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. Він дозволяє перервати потік монітор, що зайняв цим методом (і таким чином звільнити монітор).