Хороший пример динамической взаимоблокировки?

Flippant comments aside, one example which is known to come up is in code which tries to detect and handle deadlock situations. If two threads detect a deadlock, and try to "step aside" for each other, without care they will end up being stuck in a loop always "stepping aside" and never managing to move forwards.

By "step aside" I mean that they would release the lock and attempt to let the other one acquire it. We might imagine the situation with two threads doing this (pseudocode):

// thread 1
getLocks12(lock1, lock2)
{
  lock1.lock();
  while (lock2.locked())
  {
    // attempt to step aside for the other thread
    lock1.unlock();
    wait();
    lock1.lock();
  }
  lock2.lock();
}

// thread 2
getLocks21(lock1, lock2)
{
  lock2.lock();
  while (lock1.locked())
  {
    // attempt to step aside for the other thread
    lock2.unlock();
    wait();
    lock2.lock();
  }
  lock1.lock();
}

Race conditions aside, what we have here is a situation where both threads, if they enter at the same time will end up running in the inner loop without proceeding. Obviously this is a simplified example. A naiive fix would be to put some kind of randomness in the amount of time the threads would wait.

The proper fix is to always respect the lock heirarchy. Pick an order in which you acquire the locks and stick to that. For example if both threads always acquire lock1 before lock2, then there is no possibility of deadlock.

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

boolean tryLockAll(Collection<Lock> locks) {
  boolean grabbedAllLocks = false;
  for(int i=0; i<locks.size(); i++) {
    Lock lock = locks.get(i);
    if(!lock.tryLock(5, TimeUnit.SECONDS)) {
      grabbedAllLocks = false;

      // undo the locks I already took in reverse order
      for(int j=i-1; j >= 0; j--) {
        lock.unlock();
      }
    }
  }
}

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

Настоящим (хотя и без точного кода) примером является блокировка в реальном времени двух конкурирующих процессов в попытке исправить тупик SQL-сервера, при этом каждый процесс использует один и тот же алгоритм ожидания-повтора для повторная попытка. Хотя это удача по времени, я видел, как это происходило на разных машинах с аналогичными характеристиками производительности в ответ на сообщение, добавленное в тему EMS (например, сохранение обновления одного графа объекта более одного раза), и невозможность управления порядок блокировки.

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

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

Еще одно решение (по крайней мере, для SQL Server) - попробовать другой уровень изоляции (например, моментальный снимок).