A Hierarchical CLH Queue Lock

HCLHLock_lock.md

//** 『The Art of Multiprocessor Programming』七章
//** A Hierarchical CLH Queue Lock **//
//
// HCLHLock::lock()の実装書き換え例
// (分かりやすさを重視しているため若干不正確な可能性がある)

public void lock() {
    QNode myNode = currNode.get();
    AtomicReference<QNode> localQueue = localQueues.get(ThreadId.getCluster());

    QNode myPred; // 一つ前のロック待ちノードへの参照
    
    // 1] ローカルキューにノードを追加し、一つ前のノードを取得
    QNode predLocalTail = replaceQueueTail(localQueue, myNode);

    // 2] 一つ前のノードが属するクラスタを判定し、それに応じて myPred を設定する
    if (predLocalTail != null && predLocalTail.isTailWhenSpliced() == false) {
        // 2-a] 一つ前の(ロック待ち)ノードがローカルキューに存在する場合
        //      ※ isTailWhenSpliced()がtrueの場合、ローカルキューの一つ前の要素と現在の要素の間に、
        //         別のクラスタのキューが挿入されていることを示している　※同じクラスタの場合もある
        //         (つまり isTailWhenSpliced() はクラスタの切り替えポイントを示すためのフラグ)
        myPred = predLocalTail;

    } else {
        // 2-b] 一つ前の(ロック待ち)ノードが別のクラスタに存在する場合
        Qnode localTail = localQueue.get();

        // 別のクラスタの末尾ノード と (それを指している)グローバルキューの間に、
        // myNode から localTail までの ローカルキューのノード群を差し込む。
        // ※ 実際にはotherClusterTailとlocalTailが同じクラスタに属している場合も(普通に)ある
        //    (そのケース -一つ前が同じクラスタでもグローバルキューに差し込む必要があるケース- を扱うために tailWhenSplicedフラグ が必要)
        //
        // [before] otherClusterTail <- globalQueue
        // [after]  otherClusterTail <- myPred ... localTail <- globalQueue
        otherClusterTail = replaceQueueTail(globalQueue, localTail);

        // クラスタ切り替えマークをセットする (挿入したキューの終端位置を示すマークでもある)
        localTail.setTailWhenSpliced(true); 

        myPred = otherClusterTail;
    }

    // 3] 一つ前のノードのロック解放を待機
    while(myPred.isSuccessorMustWait()) {};
    predNode.set(myPred);

    return;
}

private QNode replaceQueueTail(AtomicReference<QNode> queue, QNode node) {
    do {
        tail = queue.get();    
    } while(!queue.compareAndSet(tail, node));
    
    return tail;
}

May you offer the complete code? I have dig this problem without success and try in https://github.com/jiamo/HCLHlock

Thank you for your comment. But I cannot do that as now I don't have the complete code. And it's difficult to rewrite the code because I forget the detail.