🙏

জয়  শ্রী  রাম

🕉

---

There are two types of Deadlocks:

• Lock-ordering deadlocks:
  We use locking to ensure thread safety, but indiscriminate use of locking can cause lock-ordering deadlocks.
• Resource Deadlocks:
  We use thread pools and semaphores to bound resource consumption, but failure to understand the activities being bounded can cause resource deadlocks

In this chapter, our focus is on preventing lock-ordering deadlocks.

Deadlock causes tension between safety and liveness. In most programming languages including Java and C#, applications do not recover from deadlock, so it is worthwhile to ensure that your design precludes the conditions that could cause it.

Deadlock is illustrated by the classic “dining philosophers” problem. Five philosophers go out for Chinese food and are seated at a circular table. There are five chopsticks (not five pairs), one placed between each pair of diners. The philosophers alternate between thinking and eating. Each needs to acquire two chopsticks for long enough to eat, but can then put the chopsticks back and return to thinking.

There are two kinds of chopstick-management algorithms:

• One that let everyone eat on a more or less timely basis. A hungry philosopher tries to grab both adjacent chopsticks, but if one is not available, puts down the one that is available and waits a minute or so before trying again.
• And second one can result in some or all of the philosophers dying of hunger. Each philosopher immediately grabs the chopstick to his left and waits for the chopstick to his right to be available before putting down the left.
  This situation where each has a resource needed by another and is waiting for a resource held by another, and will not release the one they hold until they acquire the one they don’t, illustrates deadlock.

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, 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.

Database systems are designed to detect and recover from deadlock. A transaction may acquire many locks, and locks are held until the transaction commits. So it is quite possible, and in fact not uncommon, for two transactions to deadlock. Without intervention, they would wait forever (holding locks that are probably required by other transactions as well). But the database server is not going to let this happen. When it detects that a set of transactions is deadlocked (which it does by searching the is-waiting-for graph for cycles), it picks a victim and aborts that transaction. This releases the locks held by the victim, allowing the other transactions to proceed. The application can then retry the aborted transaction, which may be able to complete now that any competing transactions have completed.

The JVM is not nearly as helpful in resolving deadlocks as database servers are. When a set of Java threads deadlock, that’s the end of the game—those threads are permanently out of commission. Depending on what those threads do, the application may stall completely, or a particular subsystem may stall, or performance may suffer. The only way to restore the application to health is to abort and restart it—and hope the same thing doesn’t happen again. Like many other concurrency hazards, deadlocks rarely manifest themselves immediately. The fact that a class has a potential deadlock doesn’t mean that it ever will deadlock, just that it can. When deadlocks do manifest themselves, it is often at the worst possible time—under heavy production load .

Let's look at the code below:

public class LeftRightDeadlock {
    private final Object left = new Object();
    private final Object right = new Object();
    public void leftRight() {
        synchronized (left) {
            synchronized (right) {
                doSomething();
            }
        }
    }

    public void rightLeft() {
        synchronized (right) {
            synchronized (left) {
                doSomethingElse();
            }
        }
    }
}

The code we saw is highly deadlock prone, because there is no global rule set for the order in which the locks should be acquired. Look how in leftRight() and rightLeft() methods the locks are acquired in two different orders. In leftRight() method we first acquire lock on left followed by on right. However, in rightLeft() method we do the complete opposite: first acquires right lock followed by left lock.

Let's look at another real-world example where deadlock might occur:

public void transferMoney(Account fromAccount, Account toAccount, DollarAmount amount) throws InsufficientFundsException {
    synchronized (fromAccount) {
        synchronized (toAccount) {
            if (fromAccount.getBalance().compareTo(amount) < 0) {
                throw new InsufficientFundsException();
            }
            else {
                fromAccount.debit(amount);
                toAccount.credit(amount);
            }
        }
    }
}

The code above transfers funds from one account to another. It acquires the locks on both Account objects before executing the transfer, ensuring that the balances are updated atomically and without violating invariants such as “an account cannot have a negative balance”.

How can transferMoney deadlock? It may appear as if all the threads acquire their locks in the same order, but in fact the lock order depends on the order of arguments passed to transferMoney, and these in turn might depend on external inputs. Deadlock can occur if two threads call transferMoney at the same time, one transferring from X to Y, and the other doing the opposite:

A: transferMoney(myAccount, yourAccount, 10);
B: transferMoney(yourAccount, myAccount, 20);

With unlucky timing, A will acquire the lock on myAccount and wait for the lock on yourAccount, while B is holding the lock on yourAccount and waiting for the lock on myAccount.

Mitigation:

The mitigation to solve any deadlock problem is to have a globally defined rule for order in which locks should be acquired anywhere in the entire application, and then sticking to the rule without any failure. Now defining the order can be tricky depending on the problem at hand, and would vary from problem to problem. If the object on which we acquire locks have their own ID then it definitely makes life easier as we can set the rule based on the ID that objects qith lower ID should be acquired lock on before acquiring lock on an object with higher ID. If there is no ID then we can take resort to using hashcode.

Let's take a look at how we can avoid deadlock in the code we see above:

To fix the problem in the above code, we must induce an ordering on the locks and acquire them according to the induced ordering consistently throughout the application.
One way to induce an ordering on objects is to use System.identityHashCode, which returns the value that would be returned by Object.hashCode. The code we will see now (code below) shows a version of transferMoney that uses System.identityHashCode to induce a lock ordering. It involves a few extra lines of code, but eliminates the possibility of deadlock.

In the rare case that two objects have the same hash code, we must use an arbitrary means of ordering the lock acquisitions, and this reintroduces the possibility of deadlock. To prevent inconsistent lock ordering in this case, a third “tie breaking” lock is used. By acquiring the tie-breaking lock before acquiring either Account lock, we ensure that only one thread at a time performs the risky task of acquiring two locks in an arbitrary order, eliminating the possibility of deadlock (so long as this mechanism is used consistently). If hash collisions were common, this technique might become a concurrency bottleneck (just as having a single, program-wide lock would), but because hash collisions with System.identityHashCode are vanishingly infrequent, this technique provides that last bit of safety at little cost.

private static final Object tieLock = new Object();

public void transferMoney(final Account fromAcct, final Account toAcct, final DollarAmount amount) throws InsufficientFundsException {
    class Helper {
        public void transfer() throws InsufficientFundsException {
            if (fromAcct.getBalance().compareTo(amount) < 0) {
                throw new InsufficientFundsException();
            }
            else {
                fromAcct.debit(amount);
                toAcct.credit(amount);
            }
        }
    }
    int fromHash = System.identityHashCode(fromAcct);
    int toHash = System.identityHashCode(toAcct);
    if (fromHash < toHash) { // lock-order is being maintained
        synchronized (fromAcct) {
            synchronized (toAcct) {
                new Helper().transfer();
            }
        }
    } else if (fromHash > toHash) { // lock-order is being maintained
        synchronized (toAcct) { 
            synchronized (fromAcct) {
                new Helper().transfer();
            }
        }
    } else {
        synchronized (tieLock) {
            synchronized (fromAcct) {
                synchronized (toAcct) {
                    new Helper().transfer();
                }
            }
        }
    }
}

If Account has a unique, immutable, comparable key such as an account number, inducing a lock ordering is even easier: order objects by their key, thus eliminating the need for the tie-breaking lock.

A Very Important Thing To Keep In Mind While Calling Other Methods:

A very important thing to remember here is that when we call a method about which we have little knowledge about (black-box or abstraction; let's call this type of methods outside methods), we should make sure that we are not calling the outside method while we have one or more lock acquired. Because, since we do not know anything about the implementation of the outside method we cannot guarantee that the outside method does not try to acquire a lock on the same object as the one we already hold from calling method.

Must Read:

• How to Write Production Grade Concurrent Program ?
• Multithreaded Web Crawler
• Synchronizers
• How to Test Concurrent Program ?

Recommended Read:

Instructor: