为什么 CLH Lock 在 Java 中需要 prev-Node

Question

这是java中典型的CLH-Lock：

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;  
    }  
}

为什么我们需要myPredNode，只有两个地方使用了这个变量：

1. this.prev.set(pred);
2. 项目清单 this.node.set(this.prev.get());

当我们完成时，this.prev == this.node == pred？

也许我们可以这样实现：

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;
    }
}

以上两者有什么区别？

Answer 1

第二个实现容易死锁。

假设您有两个线程，T1 和 T2。T1 拥有锁，T2 等待 T1 释放它。

T1.node.locked为真，T2.node.locked为真，tail 指向T2.node并且 T2 在 上旋转pre.locked，这是 T1 的节点。

现在 T1 释放锁（设置T1.node.locked为 false），然后在 T2 被抢占时再次尝试获取它。 T1.node.locked再次变为真，但 tail 为T2.node，因此 T1 现在正在等待 T2。而 T2 还在等待 T1 的同一个节点，这个节点现在被锁定了！僵局。

第一个实现通过重用不是当前的，而是前一个（前任）节点来保护您免受它的侵害，因此这种情况是不可能的：前任为空（然后没有什么可重用）或不是，然后它的节点在解锁时被重用。