Deadlocks can only occur in concurrent (multithreaded) programs, where synchronous (using locks) threads access one or more shared resources (variables and objects) or instruction sets (critical areas).

When we try to avoid deadlocks during livelocks, asynchronous locking will be used. Multiple threads compete for write operations on the same set of locks. In order to avoid obtaining locks, other threads are allowed to obtain locks first and continue after the locks are finally released, which is easy to cause CPU cycle hunger caused by waiting for threads to retry obtaining locks. Asynchronous locking is just a strategy to prevent deadlocks from becoming livelocks.

Here are some theoretical solutions to deadlocks, and one (second) of them is the main reason for livelocks.

Theoretical method

1. Do not use locks

It is impossible when two operations need to be synchronized. For example, for a simple bank transfer, you can debit one account and then credit another account, and no other thread is allowed to touch the balance in the account until the current thread completes.

2. Don't block the lock. If a thread can't get the lock, it should release the previously obtained lock so that it can try again later

Implementation is cumbersome and can lead to starvation (livelock). Threads always try to obtain locks again. In addition, this method may cause switching overhead in frequent thread context switching, which reduces the overall performance of the system.

1. Let threads always request locks in strict order

Easier said than done. If we are writing A function to transfer the funds of account A to account B, we can write something similar:

// at compile time, we take lock on first arg then second
public void transfer(Account A, Account B, long money) {
  synchronized (A) {
    synchronized (B) {
      A.add(amount);
      B.subtract(amount);
    }
  }
}
// at runtime we cannot track how our methods will be called
public void run() {
  new Thread(()->this.transfer(X,Y, 10000)).start();
  new Thread(()->this.transfer(Y,X, 10000)).start();
}
// this run() will create a deadlock
// first thread locks on X, waits for Y
// second thread locks on Y, waits for X

Real world solutions

We can combine the locking sequence and timing locking method to get a real solution

1. Determine the order of locks through business

We can improve our method by distinguishing A and B according to account size.

// at run time, we take lock on account with smaller id first
public void transfer(Account A, Account B, long money) {
  final Account first = A.id < B.id ? A : B;
  final Account second = first == A? B: A;
  synchronized (first) {
    synchronized (second) {
      first.add(amount);
      second.subtract(amount);
    }
  }
}
// at runtime we cannot track how our methods will be called
public void run() {
  new Thread(()->this.transfer(X,Y, 10000)).start();
  new Thread(()->this.transfer(Y,X, 10000)).start();
}

If X.id = 1111 and Y.id = 2222, because the first account we take is a smaller account ID, the locking order is executed: transfer(Y, X, 10000) and transfer(X,Y, 10000) will be the same. If the account number of X is less than Y, the two threads will try to lock x before Y, and will continue to lock Y only after X succeeds.

2. The service determines the time of tryLock / async and waits for the lock request

The solution using the above business deterministic lock sequence is only applicable to the logical transfer in one place (...) For example, determine how to coordinate resources in our method.

We may eventually have other methods / logic, and eventually use the incompatible sorting logic transfer(...). In order to avoid deadlock in this case, it is recommended to use asynchronous locking. We try to lock the limited / actual time of resources (maximum transaction time) + small random waiting time, so that all threads will not try to obtain locks too early and avoid livelocks (starvation due to repeated attempts to obtain locks)

// assume Account#getLock() gives us account's Lock  (java.util.concurrent.locks.Lock)
// Account could encapsulate lock, provide lock() /unlock()
public long getWait() { 
/// returns moving average of transfer times for last n transfers + small-random-salt in millis so all threads waiting to lock do not wake up at the same time.
//////Returns the moving average of the transmission time of the last n transmissions + small random time, so all threads waiting for locking will not wake up at the same time.
}
public void transfer(Lock lockF, Lock lockS, int amount) {
  final Account first = A.id < B.id ? A : B;
  final Account second = first == A? B: A;
  final Lock lockF = first.getLock();
  final Lock lockS = second.getLock();
  boolean done = false;
  do {
    try {
      try {
        if (lockF.tryLock(getWait(), MILLISECONDS)) {
          try {
            if (lockS.tryLock(getWait(), MILLISECONDS)) {
              done = true;
            }
          } finally {
            lockS.unlock();
          }
        }
      } catch (InterruptedException e) {
        throw new RuntimeException("Cancelled");
      }
    } finally {
      lockF.unlock();
    }
  } while (!done);

}
// at runtime we cannot track how our methods will be called
public void run() {
    new Thread(()->this.transfer(X,Y, 10000)).start();
    new Thread(()->this.transfer(Y,X, 10000)).start();
}