Pourquoi CLH verrouillage besoin prev-nœud en java

Question

Ceci est un CLH-Lock en Java typique:

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

Pourquoi nous avons besoin myPred Noeud, seulement deux endroits utilisé cette variable:

1. this.prev.set(pred);
2. Liste item this.node.set(this.prev.get());

quand nous avons fait, this.prev == this.node == pred?

Peut-être que nous pouvons en œuvre comme ceci:

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

Quelle est la différence entre les deux ci-dessus?

Answer 1

La deuxième implémentation est susceptible d'être bloquée.

Supposons que vous avez deux threads, T1 et T2. T1 possède le verrou et T2 attend T1 pour le libérer.

T1.node.locked est vrai, T2.node.locked est vrai, des points de queue à T2.node et T2 patine sur pre.locked, qui est le noeud T1.

Maintenant, T1 libère le verrou (définissant T1.node.locked sur false) et juste après cela essaye de l'acquérir à nouveau tandis que T2 est préempté. T1.node.locked redevient true, mais queue est T2.node, donc T1 attend T2. Et T2 attend toujours le même noeud de T1 qui est maintenant verrouillé! Impasse.

La première implémentation vous protège contre ce problème en réutilisant le nœud précédent (prédécesseur), donc de telles situations ne sont pas possibles: soit le prédécesseur était nul (il n'y a rien à réutiliser), soit le nœud est réutilisé il devient déverrouillé.