AbstraactQueuedSynchronizer(8)-ヘッダノードとテールノード

1.ヘッダノードと取得ロック
ヘッダ・ノードは、Exclusiveモードでロックを取得する鍵です.

/**
     * Acquires in exclusive uninterruptible mode for thread already in
     * queue. Used by condition wait methods as well as acquire.
     *
     * @param node the node
     * @param arg the acquire argument
     * @return {@code true} if interrupted while waiting
     */
    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

現在のノードがロックを取得する条件は2つあります.
1.現在のノードの前駆体はヘッドノード
2.現在のノードがロックを正常に取得しました
本当は
非公平ロックでは、コードシートに表示される論理のほかに
fast pathとは、老二の位置にあるノード(ここでは前駆体がヘッドノードであるノードを老二ノードと呼ぶ)でロックを取得できるかどうか、fastpathでtryAcquireを行うノードができるかどうかを見て、ReentrantLock(再入ロック)および公平性を詳しく見て、後で公平性ロックを言うときに詳しく述べる.
2.ヘッド接点とsetHead

/**
     * Sets head of queue to be node, thus dequeuing. Called only by
     * acquire methods.  Also nulls out unused fields for sake of GC
     * and to suppress unnecessary signals and traversals.
     *
     * @param node the node
     */
    private void setHead(Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }

注釈によれば、この方法はacquireメソッドでのみ呼び出され、acquireQueued、doAcquireInterruptibly、doAcquireNanosの3つのスピンがロックを取得する方法で呼び出されることが知られている.
shareモードの場合、doAcquireShared、doAcquireSharedInterruptiblyおよびdoAcquireSharedNanosは、そのバリエーションsetHeadAndPropagateメソッドを呼び出し、次の段落でこのメソッドを説明します.
setHeadメソッドは、現在のノードをヘッダノードに設定し、thread変数とprev変数を空にします(help gc).
setHeadメソッドはacquireメソッドでロックが正常に取得された場合にのみ呼び出されるのでracingは存在しないので原子操作は採用されず、set tailの操作はしたくない.
3.ヘッダ・ノード宣言サイクル:エンキュー(現在のスレッドでロックを取得できない)初期化

/**
     * Creates and enqueues node for current thread and given mode.
     *
     * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
     * @return the new node
     */
    private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }

現在のスレッドがロックを取得できない場合、現在のスレッドでノードが同時にキューに入るように構築されます.ここにもfast path(キュー全体が初期化されたかどうか、ヘッダノードがあるかどうかを考慮せずに原子設定を試み、失敗した場合はキューに入る操作を実行します.

/**
     * Inserts node into queue, initializing if necessary. See picture above.
     * @param node the node to insert
     * @return node's predecessor
     */
    private Node enq(final Node node) {
        for (;;) {
            Node t = tail;
            if (t == null) { // Must initialize
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

tail=null(説明headもnull)が見つかった場合、説明キューは初期化されていません.ここでは初期化し、原子は空のヘッダノード(compareAndSetHead)を設定し、tailもそのノードを指します.次に、現在のノード原子をtail(compareAndSetTail)に設定します.
4.ヘッドノードの設定状態:前駆体がヘッドノードであり、現在のノードtryAcquireが失敗した場合

final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

は、2つのスレッドしかないと仮定し、第1のスレッドT 1がロックを取得してロックを占有すると、第2のスレッドT 2がロックにアクセスする場合、2つのケースがある.
1.1つ目はT 2がacquireQueuedでtryAcquire成功
これは、スレッドがtryAcquireのときに、最初のスレッドT 1がロックを解除したことを示す.
このときshouldParkAfterFailedAcquireは実行されません.つまり、ノードがロックを正常に取得したため、T 1がT 2を起動する必要はありません.
T 1 releaseの場合,ヘッダノードの状態は初期化されていないため,unparkSuccessorメソッドは呼び出されない.

/**
     * Releases in exclusive mode.  Implemented by unblocking one or
     * more threads if {@link #tryRelease} returns true.
     * This method can be used to implement method {@link Lock#unlock}.
     *
     * @param arg the release argument.  This value is conveyed to
     *        {@link #tryRelease} but is otherwise uninterpreted and
     *        can represent anything you like.
     * @return the value returned from {@link #tryRelease}
     */
    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }

2.2つ目はT 2がacquireQueuedでtryAcquire失敗
このときshouldParkAfterFailedAcquire初期化ヘッダノードが呼び出され、release時にT 1がT 2を起動する必要があることを示します.
T 1はreleaseの場合,ヘッダノードの状態が初期化されていると判断し,unparkSuccessorメソッドを呼び出す.
unparkSuccessorメソッドではヘッダノードの状態が取り除かれます.
5.ヘッダノードの再会は先ほどのシナリオに続き、T 2はT 2でunparkSuccessorが成功した後、acquireQueuedで動作し続け、このときT 2の前駆ノードはheadであり、tryAcquireは成功する.
T 2に対応するノードをsetHeadでヘッダノードに設定し、predとthreadフィールドをクリアし、そのノードもtailノードであり、headとtailは同じノードであり、初期化状態に戻った.
この場合、「非公平ロック」の場合、fast pathが発生する現象がある可能性があります.この場合もパーク操作が行われます.
6.まとめ
キュー内のノードに対してロック解除ロックを取得するプロセスは、(ここでは、3つのスレッド競合リソースしかないと仮定する):
1.初期状態、syncキューは初期化されておらず、現在のスレッドはロックを取得できず、キューに入り、空のノードをヘッダノードとし、現在のノードをヘッダノードの後継である次男ノードとし、ヘッダノードの状態をSIGNALとする.
2.ロックを取得するスレッドが追加され、取得されずにキューに入り、老三ノード(老二ノードの後継)となり、老二ノード状態をSINGALに設定するが、このときshouldParkAfterFailedAcquireはfalse、すなわち
パーク操作を行わずに、headとtryAcquireを判断する機会をもう一度与えます.
3.キュー外のスレッドはロックを解放し、現在のヘッダノードの状態がSIGNALであると判断し、unparkSuccessorはその後継ノードである次男ノードを解放する.
4.老二ノードはロックを取得し、自分をヘッダノードに設定し、老三ノードは老二ノードになり、関連業務操作を実行する.
5.ヘッダノード(元の次男ノード)が業務操作を行った後、ロックを解除する(
unlockを呼び出し,ヘッダノード(自身)の状態がSIGNALであると判断し,その後継ノードである次男ノード(元の次男ノード)を解放する.
6.2番目のノード(元の3番目のノード)はロックを取得し、自分をヘッダノードに設定し、ビジネス操作を実行します.
7.ヘッダノード(元の3番目のノード、後の2番目のノード)はロックを解除し、自分の状態が0であることに気づき、起動操作を実行しなくなった.
7.ノード状態の意味
フェアロックにとって、競争がなければノードはありません.競合があるとノードがキューに入り、その後は毎回キュー内のノードにロックを先に持たせます.
非公平ロックにとって、競争がなければノードはありません.競合がある場合はキューのようなノードがありますが、その後、キュー内のノードが先にロックを取得するとは限らず、新しく来たスレッドが先にロックを奪う可能性があります.
ノードのステータスは、後続ノードがロックを取得するかどうかを示します.ノードステータスが0(初期化されていない)の場合は、後続ノードがないことを示します.逆に、後続ノードがあり、後続ノードはロックを取得します.