'. '

Deadlock

From APIDesign

(Difference between revisions)
Jump to: navigation, search
Line 5: Line 5:
What is a foreign code in this context? Anything written by users of your [[API]]. E.g. callbacks, listeners, etc. must not be called under any lock used in your [[API]]. The rule is that simple.
What is a foreign code in this context? Anything written by users of your [[API]]. E.g. callbacks, listeners, etc. must not be called under any lock used in your [[API]]. The rule is that simple.
-
It is easy to follow the rule when dealing with listeners - they are just simple callbacks that notify a change - they don't return any value and as such they can be called asynchronously. which is exactly what [[UI]] frameworks like [[AWT]] or [[Swing]] do: they notify the callbacks ''later''. Of course, without holding any locks and thus avoiding [[deadlock]]s.
+
It is easy to follow the rule when dealing with listeners - they are just simple callbacks that notify a change - they don't return any value and as such they can be called asynchronously. which is exactly what [[UI]] frameworks like [[AWT]] or [[Swing]] do: they notify the callbacks ''later''. Of course, without holding any locks and thus avoiding [[deadlock]]s.
 +
 
 +
However what shall one do if the foreign code needs to be called synchronously, in a critical section? Imagine:
 +
 
 +
<source lang="java">
 +
public abstract class Helper {
 +
private int value1;
 +
private int value2;
 +
private int value3;
 +
 
 +
protected abstract int combine(int x, int y);
 +
 
 +
public final void update() {
 +
synchronized (this) {
 +
int v1 = value1;
 +
value1 = combine(value1, value2);
 +
value2 = combine(value2, value3);
 +
value3 = combine(value3, v1);
 +
}
 +
}
 +
}
 +
</source>
 +
 
 +
Placing such class into an [[API]] is directly asking for troubles. First of all one synchronizes on a publicly reachable object - e.g. '''this''' - see [[Java_Monitor]] page for details. However, the biggest problem is the call to a unknown code while holding the lock. The unknown code is represented by abstract ''combine'' method - it can do anything wild. For example ask for another lock - and that is just a step away for creating [[deadlock]].
 +
 
 +
How can one prevent that? Of course, the easiest solution is to blame the user of the [[API]] and possibly put a note to [[javadoc]] of the ''combine'' method to ask users to not [[deadlock]]. While possible, it is not a solution [[TheAPIBook]] would recommend - we know users of our [[API]]s are [[clueless]], they don't read [[javadoc]] unless inevitable and they don't like to be blamed. It is the [[API]] writer that shall be blamed and shall work hard on allowing [[clueless]] usage of the [[API]] by its users. As such let's rewrite the code to take all the pain:
 +
 
 +
 
 +
<source lang="java">
 +
 
 +
public abstract class Helper {
 +
 
 +
private int value1;
 +
private int value2;
 +
private int value3;
 +
 
 +
protected abstract int combine(int x, int y);
 +
 
 +
public final void update() {
 +
int v1;
 +
int v2;
 +
int v3;
 +
while (true) {
 +
synchronized (this) {
 +
v1 = value1;
 +
v2 = value2;
 +
v3 = value3;
 +
}
 +
 
 +
int r1 = combine(v1, v2);
 +
int r2 = combine(v2, v3);
 +
int r3 = combine(v3, v1);
 +
 
 +
synchronized (this) {
 +
if (v1 == value1 && v2 == value2 && v3 == value3) {
 +
value1 = r1;
 +
value2 = r2;
 +
value3 = r3;
 +
return;
 +
}
 +
}
 +
}
 +
}
 +
}
 +
 
 +
</source>
 +
 
 +
This is the correct code which removes the [[deadlock]] danger and still keeps consistency. A kind of manually written [[TransactionalMemory]]. First of all atomically read the values needed for the computation. Then release the lock and call the unknown code. Then obtain the lock again, make sure nobody else modified the internal state and if so, modify the state of the object. If the state of the object has been modified meanwhile, repeat the computation with new values.
 +
 
 +
The code can be made even cleaner, if the internal data are kept in a special immutable object:
 +
 
 +
<source lang="java">
 +
 
 +
public abstract class Helper {
 +
 
 +
private static final class Data {
 +
 
 +
final int value1;
 +
final int value2;
 +
final int value3;
 +
 
 +
Data(int value1, int value2, int value3) {
 +
this.value1 = value1;
 +
this.value2 = value2;
 +
this.value3 = value3;
 +
}
 +
}
 +
 
 +
private Data data = new Data(0, 0, 0);
 +
 
 +
protected abstract int combine(int x, int y);
 +
 
 +
public final void update() {
 +
Data current;
 +
while (true) {
 +
synchronized (this) {
 +
current = this.data;
 +
}
 +
 
 +
int r1 = combine(current.value1, current.value2);
 +
int r2 = combine(current.value2, current.value3);
 +
int r3 = combine(current.value3, current.value1);
 +
 
 +
synchronized (this) {
 +
if (current == this.data) {
 +
this.data = new Data(r1, r2, r3);
 +
return;
 +
}
 +
}
 +
}
 +
}
 +
}
 +
</source>

Revision as of 15:12, 1 August 2018

Deadlock can only happen when all four deadlock conditions are satisfied. Yet, deadlocks happen. As a paradox of APIDesign there is just a single solution to avoid them when designing an API:

Never hold a lock when calling a foreign code!

What is a foreign code in this context? Anything written by users of your API. E.g. callbacks, listeners, etc. must not be called under any lock used in your API. The rule is that simple.

It is easy to follow the rule when dealing with listeners - they are just simple callbacks that notify a change - they don't return any value and as such they can be called asynchronously. which is exactly what UI frameworks like AWT or Swing do: they notify the callbacks later. Of course, without holding any locks and thus avoiding deadlocks.

However what shall one do if the foreign code needs to be called synchronously, in a critical section? Imagine:

public abstract class Helper {
    private int value1;
    private int value2;
    private int value3;
 
    protected abstract int combine(int x, int y);
 
    public final void update() {
        synchronized (this) {
            int v1 = value1;
            value1 = combine(value1, value2);
            value2 = combine(value2, value3);
            value3 = combine(value3, v1);
        }
    }
}

Placing such class into an API is directly asking for troubles. First of all one synchronizes on a publicly reachable object - e.g. this - see Java_Monitor page for details. However, the biggest problem is the call to a unknown code while holding the lock. The unknown code is represented by abstract combine method - it can do anything wild. For example ask for another lock - and that is just a step away for creating deadlock.

How can one prevent that? Of course, the easiest solution is to blame the user of the API and possibly put a note to javadoc of the combine method to ask users to not deadlock. While possible, it is not a solution TheAPIBook would recommend - we know users of our APIs are clueless, they don't read javadoc unless inevitable and they don't like to be blamed. It is the API writer that shall be blamed and shall work hard on allowing clueless usage of the API by its users. As such let's rewrite the code to take all the pain:


public abstract class Helper {
 
    private int value1;
    private int value2;
    private int value3;
 
    protected abstract int combine(int x, int y);
 
    public final void update() {
        int v1;
        int v2;
        int v3;
        while (true) {
            synchronized (this) {
                v1 = value1;
                v2 = value2;
                v3 = value3;
            }
 
            int r1 = combine(v1, v2);
            int r2 = combine(v2, v3);
            int r3 = combine(v3, v1);
 
            synchronized (this) {
                if (v1 == value1 && v2 == value2 && v3 == value3) {
                    value1 = r1;
                    value2 = r2;
                    value3 = r3;
                    return;
                }
            }
        }
    }
}

This is the correct code which removes the deadlock danger and still keeps consistency. A kind of manually written TransactionalMemory. First of all atomically read the values needed for the computation. Then release the lock and call the unknown code. Then obtain the lock again, make sure nobody else modified the internal state and if so, modify the state of the object. If the state of the object has been modified meanwhile, repeat the computation with new values.

The code can be made even cleaner, if the internal data are kept in a special immutable object:

public abstract class Helper {
 
    private static final class Data {
 
        final int value1;
        final int value2;
        final int value3;
 
        Data(int value1, int value2, int value3) {
            this.value1 = value1;
            this.value2 = value2;
            this.value3 = value3;
        }
    }
 
    private Data data = new Data(0, 0, 0);
 
    protected abstract int combine(int x, int y);
 
    public final void update() {
        Data current;
        while (true) {
            synchronized (this) {
                current = this.data;
            }
 
            int r1 = combine(current.value1, current.value2);
            int r2 = combine(current.value2, current.value3);
            int r3 = combine(current.value3, current.value1);
 
            synchronized (this) {
                if (current == this.data) {
                    this.data = new Data(r1, r2, r3);
                    return;
                }
            }
        }
    }
}
Personal tools
buy