はなぜCLHロックこれは、Javaでの典型的なCLH-ロックされているJava

Question

に前のノードを必要とする：

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ノードを必要とするなぜ、たった2つの場所は、この変数を使用：

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

上記の2つの違いは何ですか？

Answer 1

第2の実装はデッドロックを起こしやすい。

T1とT2の2つのスレッドがあるとします。 T1がロックを所有し、T2がT1を解放するのを待ちます。

T1.node.lockedが真である場合、尾はT2.nodeを指し、T2はT1のノードであるpre.lockedを旋回しています。

T1はロックを解除し（T1.node.lockedをfalseに設定します）、直ちにT2を優先して取得しようとすると、T1がロックを解除します。 T1.node.lockedが再びtrueになりますが、tailはT2.nodeであるため、T1はT2を待っています。そして、T2はまだロックされているT1の同じノードを待っています！デッドロック。

最初の実装では、現行ではなく以前の（前の）ノードを再利用することで、あなたを保護します。その場合、先行者はnull（再利用するものはありません）かどうか、ロックが解除されます。