tryLock() の実装をしたい
- BackoffLock では簡単
- queue lock での実装は難しい
タイムアウト付 CLHLock (図7.15、7.16)
- 構成
- QNode#pred フィールド
- static final QNode AVAILABLE
- QNode#pred
- tail -> (tryLockに失敗したノード) -> … -> (AVAILABLE or null)
- AVAILABLE なら unlock 後
- null なら lock 中。他の値に変更される可能性あり
- tryLock()
- 5〜11 … queue に自分の QNode() を追加した上で既にロック中かチェック。オリジナルと同じ
- 12〜19 … タイムアウトになるまで前の QNode が終了したかチェック
- 20〜22 … 失敗時の処理
- 20 … tail が myNode (=他のノードが待っていない)場合は tail を myPred に戻す
- 21 … その他の場合は myNode.pred を myPred にする
- unlock()
- tail が myNode (=他のノードが待っていない)場合は tail を null
- その他の場合は myNode.pred を AVAILABLE に
- オリジナルと違い、QNodeはリサイクルできない
(図7.17はよく分からない??)
- queue lock … fairness、競合の少なさ、ただしノードのリサイクルが複雑
- backoff lock … スケールしない、アンロックが遅い
二つを組み合わせていいとこ取りを考える
- queue lock を使用できる数を制限する
- 残りは backoff を使って待つ 構成 (図7.18)
- waiting … 0〜(SIZE - 1)までの
- tail … AtomicStampedReference (ABA問題の対策。詳細は10章と11章)
- QNode#state
- FREE … キューに入っていない
- WAITING … ロック取得中かクリティカルセクション
- RELEASED … unlock() 後、キューにはある
- ABORTED … タイムアウト後、キューにはある
tryLock()
- acquireQNode … FREE な QNode を探して WAITING 状態で取得
- ランダムに waiting からQNodeを選ぶ
- 選んだQNodeが解放されるまで待つ
- 取得完了する際、stateをWAITINGにする
- 選んだQNodeが解放されていない場合に、QNodeのクリーンアップ処理を試みる
- ABORTED か RELEASED の時のみ
- (19,20がよく分からない)
- tail の書き換え
- spliceQNode … キューに enqueue
- getAndSet するだけではなく、一旦タイムアウトチェックをして compareAndSet している
- (理由がよく分からない??)
- 前の tail を返す
- getAndSet するだけではなく、一旦タイムアウトチェックをして compareAndSet している
- waitForPredecessor … ロック取得待ち
- 事前条件として pred が null でないなら FREE 以外の状態である、というのがある模様
- 5〜8 … pred が null の場合は queue が空なので終了
- 11〜14 … pred が ABORTED なら FREE にしてクリーンアップ
- このスレッドが tail を更新しているので pred が誰にも参照されていない事を知っているから??
- pred のさらに pred を辿ってそれを pred として使用
- 16〜19 … タイムアウト処理
- 23 … RELEASED な pred をクリーンアップ
- unlock … state を RELEASED にする
- キューには残っている
(例によって図7.24の例がよく分からない??)
特徴
- backoff での競合が起きにくい(らしい)
- CLHLock 並に速い(らしい)
- backoff ステージのタイムアウトも難しくない(らしい)、その後のステージでも比較的ストレート(らしい)
- スペースがO(L)
- first-come-first-served ではない
- 競合が無い場合のロック取得の高速化
- 通常の Composite Lock の処理とは異なる fast-path を用意する
構成
- fastPathLock
- 9〜11 … tail がある時は使えない
- 12〜14 … fast-path を誰かが使っている時は使えない
- 15〜16 … fast-path を使用中であるフラグを付けて tail に設定
- tryLock
- 20〜22 … fastPathLock() を試みる
- 23〜26 … 通常のロックを取得し、 fastPath が終了するのを待つ
- fastPathUnlock
- 4〜6 … fast-path によるlockをしていないなら処理を中断
- 7〜13 … fast-path によるlockのunlock。tail の FASTPATH フラグを落とす
- unlock … fastPathUnlock と通常の unlock を適宜行う
プロセッサにおけるクラスタという仕組み
- クラスタ内のアクセスは外よりも速い
- このクラスタに最適化されたロックを考える
- 今回はクラスタは1段しか無いと仮定
- Thread から clusterIDを取得できる
- state フィールドにロックしているスレッドのクラスタIDを保存する
- ロックしているスレッドのクラスタが自分のスレッドのクラスタと同じであれば短い backoff を使う
欠点
- 同じクラスタが優先され過ぎてしまう可能性がある
- lock/unlock 時に別クラスタのキャッシュの削除が生じる
- local queue と global queue の二段階
QNode
- ClusterId
- successorMustWait … キューに入っているかどうか
- tailWhenSpliced … global queue の tail に属しているか
- これらは同時に更新されるため、一つの int に含めている
localQueues(クラスタID) globalQueue … 各クラスタの(待ち状態になっている) head
lock
- localQueue に追加
- localQueue の predecessor がいれば、以下のどちらかを満たすまで待ち
- myPred が同じクラスタなら tailWhenSpliced と successorMustWait が false
- myPred が違うクラスタなら tailWhenSpliced が true
- 前者なら global queue の head にいるのでロック完了
- 後者なら global queue を追加しないといけない
そんなものはない!