Composit Lock

1_acquireQNode.md

// CompositeLock::acquireQNode の実装

// メソッドを二つに分割:
//  1] ノードの所有権の獲得を試みるメソッド (acquireQNodeOwnerShip)
//  2] バックオフとかリトライ処理を管理するメソッド (acquireQNode)

private QNode acquireQNode(Backoff backoff, long startTime, long patience) {
    QNode node = waiting[random.nextInt(SIZE)];
    while(true) {
        bool acquired = acquireQNodeOwnerShip(node);
        if(acquired) {
            return node;
        }

        boackoff.backoff();
        if(timeout(patience, startTime)) {
            throw new TimeoutException();
        }
    }
}

// ノードの所有権の確保を試みる。
// スレッドは、以下の二つの操作のいずれかによって、ノードの所有権を得ることができる。
//   1] 未使用(State.FREE)のノードのステートを、State.WAITING、に変更する
//   2] キューに入っていて回収可能(State.ABORTED or State.RELEASED)のノードを、キューから取り出す(回収する)
private boolean acquireQNodeOwnerShip(QNode node) {
    State state = node.state.get();
    switch(state) {
    case State.FREE:
        // a] ノードが未使用の場合 (キューにも入っていない)
        if(node.state.compareAndSet(State.FREE, State.WAITING)) {
            // 所有権を確保 (State.WAITINGを設定することで)
            return true;
        }
        break;
        
    case State.WAITING:
        // b] 別の誰かが使用中
        break;
        
    case State.RELEASED:
    case State.ABORTED:
        // c] ノードはキューに入っているけど、再利用(回収)可能
        {
            int[] currStamp = {0};
            QNode currTail = tail.get(currStamp);
            if(node != currTail) {
                // ノードがキューの末尾にないので、キューから取り出すことができない
                // ※ この場合、waitForPredecessorを実行する他のメソッドが存在するので、
                //    そのうち、このノードはキューか切り離されステートは State.FREE に変更される
                break;
            }
            
            // ノードがキューの末尾にあるので、取り出し可能
            QNode myPred = null;
            if(state == State.ABORTED) {
                myPred = node.pred; 
            }
            
            if(tail.compareAndSet(currTail, myPred, currStamp[0], currStamp[0]+1)) {
                // 取り出せたら、そのノードの所有権は自分に移る
                node.state.set(State.WAITING);
                return true;
            }           
        }
        break;
    }
    
    // d] 所有権確保に失敗 
    return false;
}

2_spliceQNode.md

// CompositeLock::spliceQNode の実装

// キューの末尾に node を追加するだけ。
// nodeを末尾に追加して、その前に末尾要素だったノードを、返り値として返す。
private QNode spliceQNode(QNode node, long startTime, long patience) {
    // 実装に変更はないので省略
}

3_waitForPredecessor.md

// CompositeLock::waitForPredecessor の実装


private void waitForPredecessor(QNode pred, QNode node, long startTime, long patience) {
    if (pred == null) {
        // 1] キューが空だったので(= ロック未使用)、ロック獲得済み
        myNode.set(node);
        return;
    }

    // 2] 誰かロックを保持している人がいるので、解放されるまで待機
    for (;;) {
        switch (pred.state.get()) {
        case State.WAITING:
            // 2-a] predecessor がロック獲得 or 獲得待機中
            break;
            
        case State.RELEASED:
            // 2-b] predecessor がロックを解放した
            // そのノードを回収して、クリティカルセクションへ
            pred.state.set(State.FREE);
            myNode.set(node);
            return;
        
        case State.ABORTED:
            // 2-c] predecessor がタイムアウトして、ロック獲得を放棄
            // predecessorが掴んでいるノードを回収し、
            // 監視対象を predecessor の一つ前のノードに移す
            QNode temp = pred;
            pred = pred.pred;
            temp.state.set(State.FREE);
            break;
            
        case State.FREE:
            // 2-d] ここに来ることは無い (pred.stateにFREEを設定する可能性があるのは自スレッドのみなので)
            break;
        }

        if (timeout(patience, startTime)) {
            // 2-d] タイムアウト時間を超過
            node.pred = pred;
            node.state.set(State.ABORTED);
            throw new TimeoutException();
        }
    }
}