// 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;
}
Last active
October 11, 2015 00:08
-
-
Save sile/3771765 to your computer and use it in GitHub Desktop.
Composit Lock
// CompositeLock::spliceQNode の実装
// キューの末尾に node を追加するだけ。
// nodeを末尾に追加して、その前に末尾要素だったノードを、返り値として返す。
private QNode spliceQNode(QNode node, long startTime, long patience) {
// 実装に変更はないので省略
}
// 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();
}
}
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment