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 are touched by multiple threads, as it is described in detail in rule CON30-J. Synchronize access to shared mutable variables. This can be done at an object level and protect the data in the synchronized block (coarse-grained locking) locking thus out any other thread from accessing them. The locking that is achieved in this way has no danger of deadlocks.

But in the case 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 array balances.

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 is always acquiring the locks in number 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);
    }
}