Is repeatedly trying to get locks a good solution to prevent deadlocks?

Question

my question is about synchronisation and preventing deadlocks when using threads. In this example an object simply holds an integer variable and multiple threads call swapValue on those objects.

public class Data {

    private long value;

    public Data(long value) {
        this.value = value;
    }
    public synchronized long getValue() {
        return value;
    }
    public synchronized void setValue(long value) {
        this.value = value;
    }

    public void swapValue(Data other) {
        long temp = getValue();
        long newValue = other.getValue();
        setValue(newValue);
        other.setValue(temp);
    }
}

The swapValue method should be thread safe and should not skip swapping the values if the resources are not available. Simply using the synchronized keyword on the method signature will result in a deadlock. I came up with this (apparently) working solution, which is only based on the probability that one thread unlocks its resource and the other tries to claim it while the resource is still unlocked.

private Lock lock = new ReentrantLock();

...

public void swapValue(Data other) {
    lock.lock();
    while(!other.lock.tryLock())
    {
        lock.unlock();
        lock.lock();
    }

    long temp = getValue();
    long newValue = other.getValue();
    setValue(newValue);
    other.setValue(temp);
    
    other.lock.unlock();
    lock.unlock();

}

To me this looks like a hack. Is this a common solution for these kind of problems? Are there solutions that are "more deterministic" in their behaviour and also applicable in practice?

Answer 1

There are two issues at play here:

• First, mixing Data.lock with the built-in lock used by the synchronized keyword
• Second, inconsistent locking order among four (!) locks - this.lock, other.lock, the built-in lock of this, and the built-in lock of other

Even without synchronized, a.swapValue(b) and b.swapValue(a) can deadlock unless you use your approach to try to spin while locking and unlocking, which is inefficient.

One approach that you could take is add a field with some kind of final unique ID to each Data object - when swapping data of two objects, lock the one with a lower ID before the one with the higher ID, regardless of which is this and which is other. Note that System.identityHashCode is unfortunately not unique so it can't be easily used here.

The unlock ordering isn't critical here, but unlocking in the reverse order of locking is generally a good practice to follow where possible.

Answer 2

@Nanofarad has the right idea: Give every Data instance a unique, permanent numeric ID, and then use those IDs to decide which object to lock first. Here's what that might look like in practice:

private static void lockBoth(Data a, Data b) {
    Lock first = a.lock;
    Lock second = b.lock;
    if (a.getID() < b.getID()) {
        first = b.lock;
        second = a.lock;
    }
    first.lock();
    second.lock();
}

private static void unlockBoth(Data a, Data b) {
    a.lock.unlock();
    b.lock.unlock();

    // Note: @Queeg suggests in comments below that in the general case,
    // it would be good practice to make this routine always unlock the
    // two locks in the order opposite to which `lockBoth()` locked them.
    // See https://stackoverflow.com/a/8949355/801894 for an explanation.
}

public void swapValue(Data other) {
    lockBoth(this, other);
    ...swap 'em...
    unlockBoth(this, other);
}

Answer 3

In your case, just use AtomicInteger or AtomicLong instead inventing the wheel again. About the synchronization and deadlocks part of your question in general - DO NOT RELY ON PROBABILITY -- it is way too tricky and too easy to get it wrong, unless you're experienced mathematician knowing exactly what youre doing - but even then it is risky. One example when probability is used is UUID, but if computers will get fast enough then the code that shouldn't reasonably break till the end of universe can break in matter of milliseconds or faster, it is better to write code that do not rely on probability, especially concurrent code.