为什么 CLH Lock 需要 java 中的 prev-Node

Question

这是java中典型的CLH锁：

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

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

this.prev.set(pred);
列表项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 的同一个节点，现在已被锁定！死锁。

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

Answer 2

第二次实施无效。假设线程一先拥有锁，然后释放 lock.The tail 是线程一的节点 Now.But 线程一再次获取锁，会发现线程一正在自旋 forever.Anyway 刚刚稍微改变一下解锁方式，pred节点就不需要了。

public void unlock() {  
    QNode node = myNode.get();  
    node.locked = false;  

    // this.myNode == this.myPred
    myNode.set(new Node());  
}

它也会起作用。

为什么 CLH Lock 需要 java 中的 prev-Node

Why CLH Lock need prev-Node in java

java

multithreading

concurrency

synchronized

spinlock