ロックの下位実装原理を深く理解する
9086 ワード
lockの実装はjavaによって完全に書かれており、オペレーティングシステムやJVM仮想マシンとは何の関係もありません.全体的にロックは主にCASとASQ(AbstractQueuedSynchronizer)の2つのものによって実現される.ロックの実装は、ロックの追加とロック解除のプロセスによって分析される.
錠をかける
一、全体概説プロセス
1.ロック状態を示す変数の読み出し
2.ステータスを表す変数の値が0の場合、現在のスレッドは変数値を1に設定しようとします(CAS操作で完了します).複数のスレッドがステータスを表す変数値を0から1に同時に設定すると、1つのスレッドだけが成功し、他のスレッドは失敗します.失敗した後、キューに入ってスピンし、現在のスレッドをブロックします.
2.1成功すると、ロックを取得したことを示します.
2.1.1スレッド(またはノード)がキュー内に存在する場合は、そのスレッドを列に出します(次のノードをキューのヘッダノードにします).
2.1.2スレッドが列に含まれていない場合は、キューのメンテナンスは不要です.
2.1.3次に、現在のスレッドがlockメソッドから返され、共有リソースにアクセスします.
2.2失敗した場合、現在のスレッドは自身を待機(ロックされた)キューに入れ、自身をブロックします.このとき、スレッドはlockメソッドにブロックされ続け、そのメソッドから返されません(起動後もlockメソッドにあり、次の文から実行されます.ここでは第1ステップに戻って再開します).
3.ステータスを表す変数の値が1の場合、現在のスレッドを待機キューに入れ、それ自体をブロックします.
注意:起動は、スレッドがすぐに実行できることを示すのではなく、スレッドが準備完了していることを示し、実行できるだけです.
二、具体的な実現詳細(非公平ロック)
簡単に言えば、AbstractQueuedSynchronizerはすべてのリクエストスレッドを1つのCLHキューに構成し、1つのスレッドが実行済み(lock.unlock()の場合)には自分の後継ノードをアクティブにするが、実行中のスレッドはキューにない、実行待ちのスレッドはすべてブロック状態にあり、調査スレッドの明示的なブロックはLockSupportを呼び出すことによって行われる.パーク()が完了し、LockSupport.park()はsunを呼び出す.misc.Unsafe.park()ローカルメソッド、さらに、HotSpotはLinuxでpthread_を呼び出すことによってmutex_lock関数はスレッドをシステムカーネルに渡してブロックする.
1、lock方法実現(公正ロックと非公平ロックの由来)
スレッド競合ロックがある場合、現在のスレッドは、キュー内でキュー待ちを行うのではなく、まずロックを取得しようとします.これは、キュー内でキューに並んでいるスレッドにとって不公平に見えます.これも非公平ロックの由来です.ソースコードは次のとおりです.
2、解析acquire(1)方法
2.1 nonfairTryAcquire同期状態の取得
1、この方法はまず現在の状態を判断し、c=0がスレッドがロックを競合していないことを示している場合、c!=0スレッドがロックを所有していることを示します.
2、c=0が見つかった場合、CASで状態値をacquires、acquiresの初期呼び出し値を1に設定し、スレッドがロックに再入力するたびに+1となり、unlockのたびに
-1になりますが、0の場合はロックが解放されます.これは、lockがこのunlockに対応する理由です.
3、CAS設定が成功した場合、他のどのスレッドもCAS呼び出しが成功しないと予想でき、現在のスレッドがロックされていると考えられ、Runningスレッドとしても、このRunningスレッドが待機キューに入っていないことは明らかである.
4、もしc!=0しかし、自分がすでにロックを持っていることに気づき、簡単に++acquiresし、status値を変更しただけだが、競合していないため、CASではなくsetStatusで修正した.つまり、このコードはバイアスロックの機能を実現した.
2.2 addWaiterエンキューノードの構築
addWaiterメソッドは、現在ロックが取得できないスレッドをNodeとしてキューの最後に追加する責任を負います.
パラメータmodeが排他ロックか共有ロックか、デフォルトはnull、排他ロックです.キューの最後に追加する動作は2つのステップに分けられます:1、現在のキューの最後がすでに存在する場合(tail!=null)、CASを使用して現在のスレッドをTailに更新します
2、現在のTailがnullである場合、またはスレッド呼び出しCASがキューの設定に失敗した場合、enqメソッドでTailの設定を続行します.次はenqメソッドです.
この方法は、CASをループ呼び出し、高同時のシーンがあっても無限ループが最終的に現在のスレッドをキューテール(またはキューヘッダの設定)に追加することに成功します.要するに、addWaiterの目的は、CASによって現在のスレッドをキューテールに追加し、パッケージされたNodeインスタンスに戻ることです.
2.3 acquireQueuedスレッドの外部挙動の閉塞,内部スピン
acquireQueuedの主な役割は,キューに追加されたスレッドノード(addWaiterメソッド戻り値)をブロックすることであるが,ブロック前にtryAccquireで再試行してロックが得られるかどうか,再試行に成功すればブロックする必要がなく,直接戻る.
この方法は無限ループであることをよく見ると,p==head&&tryAcquire(arg)条件が満たされなければループは永遠に終了せず,もちろんデッドループは現れず,12行目のparkAndCheckInterruptが現在のスレッドを掛け,スレッドの呼び出しスタックをブロックする奥義があると感じられる.
shouldParkAfterFailedAcquireは、現在のスレッドがブロックされるべきかどうかを前継ノードで判断し、前継ノードがCANCELELED状態にある場合は、これらのノードを削除してキューを再構築します.
ロック解除
要求ロックが成功しないスレッドはacquireQueuedメソッドの12行目に掛けられ、12行以降のコードはスレッドがロック解除されてから実行されなければならず、ブロックされたスレッドがロック解除されると13行目、すなわちinterrupted=trueを設定し、その後無限ループに入る.無限ループのコードから分かるように、ロックを解除したスレッドが必ずロックを取得できるわけではなく、6行目でtryAccquireを呼び出して再競争しなければならない.ロックは非公平であり、新しく追加されたスレッドに獲得される可能性があるため、呼び覚ましたばかりのスレッドが再びブロックされる可能性がある.この詳細は「非公平」の真髄を十分に体現している.後述するロック解除機構により,最初に解放されたスレッドがHeadであるため,p==headの判断は基本的に成功することが分かった.ロック解除コードは比較的簡単で、主にAbstractQueuedSynchronizerに現れている.releaseとSync.tryReleaseメソッドのclass AbstractQueuedSynchronizer
1、実行中のスレッドノードはキューにありません
2、最初のノードが起動した後、ブロック状態ではないと言っているだけで、必ず実行できるわけではありません.また、実行するか、再びブロックされるかを競争するために同期状態を取得する必要があります(運命は多岐にわたるでしょう).
概要:
全体的に、スレッドがロックを取得するには、次の手順に従います(非公平).
1、lockメソッドを呼び出すと、まずcas操作を行い、同期状態1を設定できるかどうかを確認します.
2、同期状態の取得に失敗した場合、状態が0の場合、casは1に設定.
3、同期状態が0でも自己スレッドでもない場合は、現在のスレッドをノードとして構築します.
4、現在のスレッドノードCAS方式をキューに入れ、挙動上のスレッドがブロックされ、内部スピン取得状態となる.
5、スレッドはロックを解除し、キューの最初のノードを起動し、競争に参加する.上記を繰り返します.
錠をかける
一、全体概説プロセス
1.ロック状態を示す変数の読み出し
2.ステータスを表す変数の値が0の場合、現在のスレッドは変数値を1に設定しようとします(CAS操作で完了します).複数のスレッドがステータスを表す変数値を0から1に同時に設定すると、1つのスレッドだけが成功し、他のスレッドは失敗します.失敗した後、キューに入ってスピンし、現在のスレッドをブロックします.
2.1成功すると、ロックを取得したことを示します.
2.1.1スレッド(またはノード)がキュー内に存在する場合は、そのスレッドを列に出します(次のノードをキューのヘッダノードにします).
2.1.2スレッドが列に含まれていない場合は、キューのメンテナンスは不要です.
2.1.3次に、現在のスレッドがlockメソッドから返され、共有リソースにアクセスします.
2.2失敗した場合、現在のスレッドは自身を待機(ロックされた)キューに入れ、自身をブロックします.このとき、スレッドはlockメソッドにブロックされ続け、そのメソッドから返されません(起動後もlockメソッドにあり、次の文から実行されます.ここでは第1ステップに戻って再開します).
3.ステータスを表す変数の値が1の場合、現在のスレッドを待機キューに入れ、それ自体をブロックします.
注意:起動は、スレッドがすぐに実行できることを示すのではなく、スレッドが準備完了していることを示し、実行できるだけです.
二、具体的な実現詳細(非公平ロック)
簡単に言えば、AbstractQueuedSynchronizerはすべてのリクエストスレッドを1つのCLHキューに構成し、1つのスレッドが実行済み(lock.unlock()の場合)には自分の後継ノードをアクティブにするが、実行中のスレッドはキューにない、実行待ちのスレッドはすべてブロック状態にあり、調査スレッドの明示的なブロックはLockSupportを呼び出すことによって行われる.パーク()が完了し、LockSupport.park()はsunを呼び出す.misc.Unsafe.park()ローカルメソッド、さらに、HotSpotはLinuxでpthread_を呼び出すことによってmutex_lock関数はスレッドをシステムカーネルに渡してブロックする.
1、lock方法実現(公正ロックと非公平ロックの由来)
スレッド競合ロックがある場合、現在のスレッドは、キュー内でキュー待ちを行うのではなく、まずロックを取得しようとします.これは、キュー内でキューに並んでいるスレッドにとって不公平に見えます.これも非公平ロックの由来です.ソースコードは次のとおりです.
final void lock() {
if (compareAndSetState(0, 1))
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1);
}2、解析acquire(1)方法
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}2.1 nonfairTryAcquire同期状態の取得
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
if (compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
}
else if (current == getExclusiveOwnerThread()) {// ， ++
int nextc = c + acquires;
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
} 1、この方法はまず現在の状態を判断し、c=0がスレッドがロックを競合していないことを示している場合、c!=0スレッドがロックを所有していることを示します.
2、c=0が見つかった場合、CASで状態値をacquires、acquiresの初期呼び出し値を1に設定し、スレッドがロックに再入力するたびに+1となり、unlockのたびに
-1になりますが、0の場合はロックが解放されます.これは、lockがこのunlockに対応する理由です.
3、CAS設定が成功した場合、他のどのスレッドもCAS呼び出しが成功しないと予想でき、現在のスレッドがロックされていると考えられ、Runningスレッドとしても、このRunningスレッドが待機キューに入っていないことは明らかである.
4、もしc!=0しかし、自分がすでにロックを持っていることに気づき、簡単に++acquiresし、status値を変更しただけだが、競合していないため、CASではなくsetStatusで修正した.つまり、このコードはバイアスロックの機能を実現した.
2.2 addWaiterエンキューノードの構築
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;
} addWaiterメソッドは、現在ロックが取得できないスレッドをNodeとしてキューの最後に追加する責任を負います.
パラメータmodeが排他ロックか共有ロックか、デフォルトはnull、排他ロックです.キューの最後に追加する動作は2つのステップに分けられます:1、現在のキューの最後がすでに存在する場合(tail!=null)、CASを使用して現在のスレッドをTailに更新します
2、現在のTailがnullである場合、またはスレッド呼び出しCASがキューの設定に失敗した場合、enqメソッドでTailの設定を続行します.次はenqメソッドです.
private Node enq(final Node node) {
for (;;) {
Node t = tail;
if (t == null) { // Must initialize
Node h = new Node(); // Dummy header
h.next = node;
node.prev = h;
if (compareAndSetHead(h)) {
tail = node;
return h;
}
}
else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
} この方法は、CASをループ呼び出し、高同時のシーンがあっても無限ループが最終的に現在のスレッドをキューテール(またはキューヘッダの設定)に追加することに成功します.要するに、addWaiterの目的は、CASによって現在のスレッドをキューテールに追加し、パッケージされたNodeインスタンスに戻ることです.
2.3 acquireQueuedスレッドの外部挙動の閉塞,内部スピン
final boolean acquireQueued(final Node node, int arg) {
try {
boolean interrupted = false;
for (;;) {
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {// ，
setHead(node);
p.next = null; // help GC
return interrupted;
}
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} catch (RuntimeException ex) {
cancelAcquire(node);
throw ex;
}
} acquireQueuedの主な役割は,キューに追加されたスレッドノード(addWaiterメソッド戻り値)をブロックすることであるが,ブロック前にtryAccquireで再試行してロックが得られるかどうか,再試行に成功すればブロックする必要がなく,直接戻る.
この方法は無限ループであることをよく見ると,p==head&&tryAcquire(arg)条件が満たされなければループは永遠に終了せず,もちろんデッドループは現れず,12行目のparkAndCheckInterruptが現在のスレッドを掛け,スレッドの呼び出しスタックをブロックする奥義があると感じられる.
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
} shouldParkAfterFailedAcquireは、現在のスレッドがブロックされるべきかどうかを前継ノードで判断し、前継ノードがCANCELELED状態にある場合は、これらのノードを削除してキューを再構築します.
ロック解除
要求ロックが成功しないスレッドはacquireQueuedメソッドの12行目に掛けられ、12行以降のコードはスレッドがロック解除されてから実行されなければならず、ブロックされたスレッドがロック解除されると13行目、すなわちinterrupted=trueを設定し、その後無限ループに入る.無限ループのコードから分かるように、ロックを解除したスレッドが必ずロックを取得できるわけではなく、6行目でtryAccquireを呼び出して再競争しなければならない.ロックは非公平であり、新しく追加されたスレッドに獲得される可能性があるため、呼び覚ましたばかりのスレッドが再びブロックされる可能性がある.この詳細は「非公平」の真髄を十分に体現している.後述するロック解除機構により,最初に解放されたスレッドがHeadであるため,p==headの判断は基本的に成功することが分かった.ロック解除コードは比較的簡単で、主にAbstractQueuedSynchronizerに現れている.releaseとSync.tryReleaseメソッドのclass AbstractQueuedSynchronizer
public final boolean release(int arg) {
if (tryRelease(arg)) {
Node h = head;
if (h != null && h.waitStatus != 0)
unparkSuccessor(h);
return true;
}
return false;
} protected final boolean tryRelease(int releases) {
int c = getState() - releases;
if (Thread.currentThread() != getExclusiveOwnerThread())
throw new IllegalMonitorStateException();
boolean free = false;
if (c == 0) {
free = true;
setExclusiveOwnerThread(null);
}
setState(c);
return free;
} private void unparkSuccessor(Node node) {
/*
* If status is negative (i.e., possibly needing signal) try
* to clear in anticipation of signalling. It is OK if this
* fails or if status is changed by waiting thread.
*/
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
/*
* Thread to unpark is held in successor, which is normally
* just the next node. But if cancelled or apparently null,
* traverse backwards from tail to find the actual
* non-cancelled successor.
*/
Node s = node.next;
if (s == null || s.waitStatus > 0) {
s = null;
for (Node t = tail; t != null && t != node; t = t.prev)
if (t.waitStatus <= 0)
s = t;
}
if (s != null)
LockSupport.unpark(s.thread);
}1、実行中のスレッドノードはキューにありません
2、最初のノードが起動した後、ブロック状態ではないと言っているだけで、必ず実行できるわけではありません.また、実行するか、再びブロックされるかを競争するために同期状態を取得する必要があります(運命は多岐にわたるでしょう).
概要:
全体的に、スレッドがロックを取得するには、次の手順に従います(非公平).
1、lockメソッドを呼び出すと、まずcas操作を行い、同期状態1を設定できるかどうかを確認します.
2、同期状態の取得に失敗した場合、状態が0の場合、casは1に設定.
3、同期状態が0でも自己スレッドでもない場合は、現在のスレッドをノードとして構築します.
4、現在のスレッドノードCAS方式をキューに入れ、挙動上のスレッドがブロックされ、内部スピン取得状態となる.
5、スレッドはロックを解除し、キューの最初のノードを起動し、競争に参加する.上記を繰り返します.