This is a typical CLH-Lock in java:
public class CLHLock{
private final AtomicReference tail;
// why we need this node?
private final ThreadLocal myPred;
private final ThreadLocal myNode;
public CLHLock() {
tail = new AtomicReference(new QNode());
myNode = new ThreadLocal() {
protected QNode initialValue() {
return new QNode();
}
};
myPred = new ThreadLocal();
}
public void lock() {
QNode node = myNode.get();
node.locked = true;
QNode pred = tail.getAndSet(node);
// this.myPred == pred
myPred.set(pred);
while (pred.locked) {
}
}
public void unlock() {
QNode node = myNode.get();
node.locked = false;
// this.myNode == this.myPred
myNode.set(myPred.get());
}
private static class QNode {
volatile boolean locked;
}
}
Why we need myPred
Node, only two places used this variable:
this.prev.set(pred);
this.node.set(this.prev.get());
when we done, this.prev == this.node == pred
?
Maybe we can implements like this:
public class CLHLock {
// Node tail
private final AtomicReference<QNode> tail = new AtomicReference<>(new QNode());
// ThreadLocal
private final ThreadLocal<QNode> node = ThreadLocal.withInitial(QNode::new);
public void lock() {
QNode now = node.get();
now.locked = true;
// spin on pre-node
QNode pre = tail.getAndSet(now);
while (pre.locked) {
}
}
public void unlock() {
QNode now = node.get();
now.locked = false;
}
class QNode {
volatile boolean locked = false;
}
}
What is the difference between the above two?
Second implementation is deadlock-prone.
Assume you have two threads, T1 and T2. T1 owns the lock and T2 waits for T1 to release it.
T1.node.locked
is true, T2.node.locked
is true, tail points to T2.node
and T2 is spinning on pre.locked
, which is T1's node.
Now T1 releases the lock (setting T1.node.locked
to false) and right after this tries to acquire it again while T2 is preempted.
T1.node.locked
becomes true again, but tail is T2.node
, so T1 now is waiting for T2. And T2 is still waiting for the same node of T1 which is now locked! Deadlock.
First implementation protects you against it by reusing not current, but previous (predecessor) node, so such situations are not possible: either predecessor was null (then there is nothing to reuse) or not, then it's node is reused when it becomes unlocked.