CON34-J. Avoid deadlock by requesting fine-grained locks in the proper order

To avoid data corruption in multithreaded Java programs, you have to protect data that is touched by multiple threads as described in detail in CON30-J. Synchronize access to shared mutable variables. This can be done at an object level to protect the data in the synchronized block (coarse-grained locking), thus locking out any other thread from accessing it. Locking that is achieved in this way has no danger of deadlocks.

But if you follow a fine-grained locking, using member locks, you may end up in a deadlock unless you ensure that each thread always requests locks in the same order.

Compliant Solution

To implement a fine-grained strategy, take out a separate lock for each position in the balances array.

class Stocks implements FundConstants {
    static int[] balances =
                       new int[noOfStocks];
    static Object[] locks =
                    new Object[noOfStocks];
    static
    {
        for (int n=0; n<noOfStocks; n++) {
            balances[n] = 10000;
            locks[n] = new Object();
        }
    }

    static void transfer(Transfer t) {
        int lo, hi;
        if (t.fundFrom < t.fundTo) {
            lo = t.fundFrom;
            hi = t.fundTo;
        } else {
            lo = t.fundTo;
            hi = t.fundFrom;
        }
        synchronized (locks[lo]) {
            synchronized (locks[hi]) {
                balances[t.fundFrom] -= t.amount;
                balances[t.fundTo] += t.amount;
            }
        }
    }

    static int sumHelper (int next) {
        synchronized (locks[next]) {
            if (next == (noOfStocks-1)) {
                return balances[next];
            } else {
                return balances[next] +
                       sumHelper(next+1);
            }
        }
    }

    static void checkSystem() {
        int actual = 0;
        actual = sumHelper(0);
        System.out.println("Actual balance is
                                   " + actual);
    }
}

Since you cannot lock on primitive types, you cannot take a direct lock on the items in the balances array. Instead, you have to create an array of object (locks).

The code above avoids deadlock because every thread requests monitors in the same order, since it is always acquiring the locks in numeric order.

Noncompliant Code Example

Deadlock would occur if the transfer method acquired the monitors in decreasing numeric order, while the sumHelper method would still be using increasing numeric order.

class Stocks implements FundConstants {
    static int[] balances =
                       new int[noOfStocks];
    static Object[] locks =
                    new Object[noOfStocks];
    static
    {
        for (int n=0; n<noOfStocks; n++) {
            balances[n] = 10000;
            locks[n] = new Object();
        }
    }

    static void transfer(Transfer t) {
        int lo, hi;
        if (t.fundFrom > t.fundTo) {// acquires the monitors in decreasing numeric order
            lo = t.fundFrom;
            hi = t.fundTo;
        } else {
            lo = t.fundTo;
            hi = t.fundFrom;
        }
        synchronized (locks[lo]) {
            synchronized (locks[hi]) {
                balances[t.fundFrom] -= t.amount;
                balances[t.fundTo] += t.amount;
            }
        }
    }

    static int sumHelper (int next) {
        synchronized (locks[next]) {
            if (next == (noOfStocks-1)) {
                return balances[next];
            } else {
                return balances[next] +
                       sumHelper(next+1);
            }
        }
    }

    static void checkSystem() {
        int actual = 0;
        actual = sumHelper(0);
        System.out.println("Actual balance is
                                   " + actual);
    }
}