16 апр. 2009 г.

Java: Классический dead lock

Классический dead lock (Java Concurrency In Practice, p.10.1):
When a thread holds a lock forever, other threads attempting to acquire that lock will block forever waiting. When thread A holds lock L and tries to acquire lock M, but at the same time thread B holds M and tries to acquire L, both threads will wait forever. This situation is the simplest case of deadlock (or deadly embrace), where multiple threads wait forever due to a cyclic locking dependency. (Think of the threads as the nodes of a directed graph whose edges represent the relation "Thread A is waiting for a resource held by thread B". If this graph is cyclical, there is a deadlock.)

Пример иллюстрирующий пробему:
Есть сущность типа счёт, необходимо реализовать сервис типа переводчика денег с одного счёта на другой.

Для определённости стоит уточнить, что счетов с системе очень много (скажем, несколько миллионов) и порядка несколько тысяч операций в секунду (всё многопоточно).
// ради простоты сущность счёт это такая простая структура:
public class Account {
public int id;
public int sum;
}
необходимо реализовать
public class MoneyTransfer {
/**
*
* @param sourceAccount счёт с которого надо снять сумму
* @param targetAccount счёт на который надо зачислить сумму
* @param sum сумма, которую необходимо перевести
*/
public void doTransfer(final Account sourceAccount,
final Account targetAccount, final int sum){
// TODO: реализовать
}
}


Ошибка №1. DeadLock:
synchronized(sourceAccount){
if (sourceAccount.sum > sum) {
synchronized(targetAccount) {
sourceAccount.sum -= sum;
targetAccount.sum += sum;
}
}
}

Если в момент, когда деньги переводятся со счёта1 на счёт2 будет произведён обратный перевод (т.е со счёта2 на счёт1) получим ситуацию т.н. dead lock'а :

Классическая схема dead lock

  • Первая нить (T1) блокирует счёт1 (используя монитор lock a) и в этот же самый момент вторая нить (Т2) блокирует счёт2 (используя соответствующий монитор lock b)
  • Т1 пытается получить блокировку счёта2 - но не может получить, т.к Т2 его держит и не может отпустить, т.к. он (Т2) пытается получить блокировку счёта1, который держит Т1 и так же не может отдать

Ошибка №2. BottleNeck:
synchronized(this) {
if (sourceAccount.sum > sum) {
sourceAccount.sum -= sum;
targetAccount.sum += sum;
}
}
В данном случае все запросы выстроятся в очередь - т.к. блокировка происходит по экземпляру MoneyTransfer - т.е пока каждый последующий трансфер независимо от счетов и потоков из которого происходит трансфер, вынужден дождаться окончания предыдущего трансфера.

Ошибка №3. Не атомарность:
boolean transfered = false;
synchronized(sourceAccount) {
if (sourceAccount.sum > sum) {
transfered = true;
sourceAccount.sum -= sum;
}
}
if (transfered) {
synchronized(targetAccount) {
targetAccount.sum += sum;
}
}


Правильное решение (респект Павлу Куракину): выстраивание строго определённой последовательности блокировок:
final Object lock1 = sourceAccount.id < targetAccount.id ? sourceAccount : targetAccount;
final Object lock2 = sourceAccount.id < targetAccount.id ? targetAccount : sourceAccount;
synchronized(lock1){
if (sourceAccount.sum > sum) {
synchronized(lock2) {
sourceAccount.sum -= sum;
targetAccount.sum += sum;
}
}
}
В данном случае не будет dead lock при "встречных" переводах - т.к. блокировка всегда будет происходить в одной и той же последовательности, в то же время нет bottle neck'а и операция трансфера атомарна с точки зрения обоих счетов.

P.S. Стоит так же посмотреть, хотя бы по диагонали статью
IBM developerWorks : Writing multithreaded Java applications.

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

.sid комментирует...

Стоит отметить, что подобная проверка работает до тех пор, пока счет не может учавствовать в транзакции и как эмиттер, и как приемник средств. В противном случае, можно ввести третий лок (глобальный для системы) при помощи которого будет сериализовыватся обработка счетов с одинаковыми номерами. То есть если номера счетов равны надо будет сначала взять глобальный лок (чтобы предотвратить deadlock), затем два лока счетов (в любом порядке).

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

artemv12 комментирует...

Камрад, а ведь можно еще так:
public class Account {
public int id;
public int sum;
public final Lock l_ = new ReentrantLock();
}

и операция становится такой:
if(sourceAccount.l_.tryLock()) {
try {
if (targetAccount.l_.tryLock()) {
try {
...
}
finally{
targetAccount.l_.unlock();
}
}
}
finally{
sourceAccount.l_.unlock();
}
}

Владимир Долженко комментирует...

@artemv12
как бы не хочется в сам доменный объект добавлять сущности не связанные с объектом.