《並行プログラミングの芸術》-読書ノート02：Javaの並行メカニズムの底層実装原理

『並行プログラミングの技術』読書ノート第 2 章。主に volatile と synchronized についてまとめました。

一、volatile の応用#

もし volatile 変数修飾子が適切に使用されれば、synchronized の使用と実行コストよりも低くなります。
なぜなら、スレッドのコンテキストスイッチやスケジューリングを引き起こさないからです。

1. volatile の定義と実装原理#

volatile 変数修飾子を持つ共有変数に対して書き込み操作を行うと、lock プレフィックスの命令が追加されます。

lock プレフィックスの命令はマルチコアプロセッサで 2 つのことを引き起こします。

（1）現在のプロセッサのキャッシュラインのデータをメモリに書き戻す

しかし、ロックバスのオーバーヘッドは大きいため、現在の LOCK 信号は基本的にキャッシュをロックし、キャッシュの一貫性メカニズムを使用して変更の原子性を確保します（キャッシュロック）。

（2）このメモリへの書き戻し操作は、他の CPU でそのメモリアドレスをキャッシュしているデータを無効にします。

MESI（修正、独占、共有、無効）制御プロトコルは、メモリと他のプロセッサのキャッシュの一貫性を維持します。
スニッフィング技術は、内部キャッシュ、システムメモリ、および他のデータキャッシュがバス上で一貫性を保つことを保証します。

処理速度を向上させるために、プロセッサはメモリと直接通信せず、まずメモリからデータをキャッシュに読み込んでから操作を行いますが、操作はいつメモリに書き込まれるか全く分かりません。もし volatile 変数に対して書き込み操作を行うと、JVM はプロセッサに Lock プレフィックスの命令を送信し、この変数が所在するキャッシュラインのデータをシステムメモリに書き戻します。しかし、メモリに書き戻されたとしても、他のプロセッサのキャッシュの値がまだ古い場合、計算操作を行うと問題が発生します。したがって、マルチプロセッサ環境では、キャッシュの一貫性プロトコルを実施し、各プロセッサはスニッフィングを通じてバス上で伝播するデータをチェックし、自分のキャッシュの値が期限切れでないかを確認します。もし期限切れであれば、現在のプロセッサのキャッシュラインを無効状態に設定し、プロセッサがこのデータに対して変更操作を行うときには、再びシステムメモリからデータをプロセッサのキャッシュに読み込みます。

2. volatile 使用の最適化#

共有変数を 64 バイトに追加します（ソースコードには見当たらないようです）。

LinkedTransferQueue

一部のプロセッサのキャッシュのキャッシュラインは 64 バイトであり、部分的にキャッシュラインを埋めることをサポートしていません。64 バイトに追加することで、高速バッファのキャッシュラインを満たし、ヘッダーノードとテールノードが同じキャッシュラインにロードされないようにし、ヘッダーノードとテールノードが変更時に互いにロックされないようにします。

すべての volatile 変数を使用する場合に 64 バイトに追加する必要はありません。

キャッシュラインが 64 バイトでないプロセッサには適用されません。
共有変数が頻繁に読み書きされない場合には適用されず、逆に追加バイトによってパフォーマンス消費が増加します。

二、synchronized の実装原理と応用（重量級ロック）#

synchronize の基本：Java の各オブジェクトはロックとして使用できます。具体的には 3 つの形式があります。

通常の同期メソッドの場合、ロックは現在のインスタンスオブジェクトです。
静的同期メソッドの場合、ロックは現在のクラスの class オブジェクトです。
同期メソッドブロックの場合、ロックは synchronize の括弧内のオブジェクトです。

ロックは一体どこに保存されているのか？ロックの中にはどんな情報が保存されているのか？・

Synchronized の JVM における実装原理#

JVM はMonitorオブジェクトの入出力に基づいてメソッド同期とコードブロック同期を実現しますが、両者の表現の詳細は異なります。

コードブロック同期はmonitorenterとmonitorexit命令を使用して実現され、メソッド同期は別の実装方法を使用して実現されますが、詳細は JVM には記載されていません。しかし、メソッド同期も上記の 2 つの命令を使用して実現できます。

monitorenter命令は、コンパイル後に同期コードブロックの開始位置に挿入され、monitorexitはメソッドの終了位置と例外位置に挿入されます。JVM は各monitorenterに対して対応するmonitorexitがペアで存在することを保証する必要があります。
どのオブジェクトにも関連付けられたmonitorがあり、monitorが保持されると、それはロック状態になります。スレッドがmonitorenter命令に到達すると、オブジェクトに対応するmonitorの所有権を取得しようとします。つまり、オブジェクトのロックを取得しようとします。

同期メソッド：JVM はACC_SYNCHRONIZEDフラグを使用して実現します。つまり、JVM はメソッドアクセス識別子（flags）に **ACC_SYNCHRONIZEDを追加することで同期機能を実現します。同期メソッドは class ファイルのaccess_flagsにACC_SYNCHRONIZED** を保存し、access_flagsは定数プールに保存されます。

同期メソッドは暗黙的です。同期メソッドは実行時定数プールのmethod_info構造体にACC_SYNCHRONIZED識別子を保存します。スレッドがメソッドにアクセスすると、ACC_SYNCHRONIZED識別子が存在するかどうかを確認します。存在する場合は、対応するmonitorロックを取得し、その後メソッドを実行します。メソッドの実行が終了すると（正常にreturnするか、例外をスローするかにかかわらず）、対応するmonitorロックが解放されます。この時、他のスレッドがこのメソッドにアクセスしようとすると、monitorロックを取得できずにブロックされます。同期メソッド内で例外がスローされ、メソッド内でキャッチされない場合、外にスローする際には、まず取得したmonitorロックを解放します。

monitor#

モニタ（英語：Monitors、または監視器）は、プログラム構造の一種で、構造内の複数のサブプログラム（オブジェクトまたはモジュール）が形成する複数の作業スレッドが共有リソースに対して排他的にアクセスします。

これは概念であり、同期呼び出しのプロセスを簡素化することを目的としており、同期操作をカプセル化し、PV セマフォの直接使用を避けます。Java における具体的な実装はObjectMonitorです。

ObjcetMonitorの重要なフィールド

_count：オーナースレッドがロックを取得した回数を記録します。この文は非常に理解しやすく、これが synchronized が再入可能であることを決定します。
_owner：このオブジェクトを所有するスレッドを指します。
_WaitSet：待機状態にあるスレッドのキューを保存します。
_EntryList：ロックを待っているためにブロックされているスレッドのキューを保存します。

8694380-509ad307903635af

8694380-0d3b09e6c73f8892

monitor を取得したいスレッドは、まず monitor の__EntryList キューに入ってブロックされて待機します。
プログラム内で wait () メソッドが呼び出されると、そのスレッドは_WaitSet キューに入ります。wait () は monitor ロックを解放し、_owner を null に設定し、_WaitSet キューに入ってブロックされます。
プログラム内の他のスレッドが notify/notifyAll メソッドを呼び出すと、_WaitSet 内のあるスレッドが起こされ、そのスレッドは再び monitor ロックを取得しようとします。成功すれば、そのスレッドは monitor のオーナーになります。

具体的な実装

8694380-c4a60ba68bcc7704

この実装方法に関する情報はインターネット上にたくさんあります。

1、Java オブジェクトヘッダー#

synchronizedで使用されるロックは Java オブジェクトヘッダーに存在します。

配列タイプは 3 ワード幅（3*4 バイト）

非数値タイプは 2 ワード幅（2*4 バイト）

mark word に保存されるデータはロックフラグの変化に応じて変わります。

64 ビット仮想マシン下のストレージ構造

2、ロックのアップグレードと比較#

from JDK1.6

ロックには 4 つの状態があり、低いものから高いものへ：無ロック、偏向ロック、軽量ロック、重量ロック。これらの状態は競争状況に応じて徐々にアップグレードされます。
ロックはアップグレードできますが、ダウングレードはできません（ロックの取得と解放の効率を向上させます）。

偏向ロック：#

ほとんどの場合、ロックはマルチスレッド競争が存在せず、常に同じスレッドによって複数回取得されるため、スレッドがロックを取得するコストを低くするために偏向ロックが導入されます。

スレッドが同期ブロックにアクセスし、ロックを取得すると、オブジェクトヘッダーとスタックフレームのロック記録にロックの偏向を示すスレッドIDが保存されます。以降、そのスレッドが同期ブロックに入るときと出るときには、CAS 操作を行う必要がなく、オブジェクトヘッダーのmark wordに現在のスレッドを指す偏向ロックが保存されているかどうかを単純にテストするだけで済みます。

テストが成功すれば、スレッドはロックを取得したことを示します。テストが失敗した場合は、mark wordに偏向ロックの識別子が 1 に設定されているかどうかを再度テストします。設定されていなければ、CAS競争ロックを使用します。設定されていれば、CAS を使用してオブジェクトヘッダーの偏向ロックを現在のスレッドに指向させようとします。

（1）偏向ロックの撤回

偏向ロックは、競争が発生するまでロックを保持するメカニズムを使用しているため、他のスレッドが偏向ロックを競争しようとすると、偏向ロックを保持しているスレッドがロックを解放します。偏向ロックの撤回には、グローバルセーフポイント（この時間に実行中のバイトコードがない）を待つ必要があります。

まず == 一時停止 == 偏向ロックを保持しているスレッドを停止し、偏向ロックを保持しているスレッドが生きているかどうかを確認します。もしスレッドがアクティブでない場合、オブジェクトヘッダーを無ロック状態に設定します。もしスレッドがまだ生きている場合、偏向ロックを保持しているスタックが実行され、偏向オブジェクトのロック記録を走査します。スタック内のロック記録とオブジェクトヘッダーのmark wordは、他のスレッドに再偏向されるか、無ロックに戻されるか、偏向ロックとして不適切であるとマークされます。

ここはまだ不明確で、ネットで再度確認する必要があります。
他のスレッドと既存のスレッドが偏向ロックを競争する場合、どのようにして偏向を続けるかを判断するのでしょうか？

（2）偏向ロックの無効化

Java6、7 ではデフォルトで偏向ロックが有効ですが、プログラム起動後に数秒の遅延が発生します。必要に応じて遅延を無効にすることができます。
-XX:BiasedLockingStartupDelay=0、プログラム内のすべてのロックが通常競争状態にあることが確実であれば、JVM パラメータを使用して偏向ロックを無効にできます：-XX:UseBaisedLocking=false、この場合、プログラムはデフォルトで軽量ロック状態に入ります。

軽量ロック#

（1）ロック

スレッドが同期ブロックを実行する前に、JVM はまず現在のスレッドのスタックフレーム内にロック記録を保存するためのスペースを作成し、オブジェクトヘッダーのMark wordをロック記録にコピーします（Displaced Mark World）。その後、スレッドは CAS を使用してオブジェクトヘッダーのMark wordをロック記録へのポインタに置き換えようとします。成功すれば、現在のスレッドはロックを取得し、失敗すれば、他のスレッドがロックを競争していることを示し、現在のスレッドはスピンを使用してロックを取得しようとします。

（2）ロック解除

ロック解除時には、原子的な CAS 操作を使用してDisplaced Mark Wordをオブジェクトヘッダーに戻します。成功すれば、競争が発生しなかったことを示します。失敗すれば、現在のロックに競争が存在することを示し、ロックは重量級ロックに膨張します。

スピンは CPU を消費するため、無駄なスピンを避けるために、一度重量級ロックにアップグレードされると、軽量ロック状態には戻りません。この状態にあるロックでは、他のスレッドがロックを取得しようとすると、すべてブロックされます。ロックを保持しているスレッドがロックを解放すると、これらのスレッドが起こされ、起こされたスレッドは新たなロック争奪戦を行います。

3、ロックの長所と短所の比較#

偏向ロック：
長所：ロックと解放に追加の消費が必要ない
短所：スレッド間にロック競争が存在する場合、ロック撤回に追加の消費が発生する

適用シーン：同期ブロックにアクセスするのが 1 つのスレッドのみの場合に適しています
軽量ロック：
長所：競争するスレッドはブロックされないため、プログラムの応答速度が向上する
短所：ロックを取得できないスレッドが常に存在する場合、スピンが CPU を消費する
使用シーン：応答時間を重視し、同期実行速度が非常に速い
重量級ロック：
長所：スレッド競争はスピンを使用せず、CPU を消費しない
短所：スレッドがブロックされ、応答時間が遅くなる
適用シーン：スループットを重視し、同期ブロックの実行時間が長い

自己理解#

偏向ロックは最初にロックを保持しているスレッドを指し、その後ロック競争が発生すると偏向ロックが撤回されます。偏向ロックが軽量ロックに進化するかどうかは疑問です。
軽量ロックは最初に markworld の内容（すなわち hashcode または他のロック情報）をローカルスレッドスタックフレームにコピーし、その後 markworld をスレッドのポインタに指向させます。
ロック競争が発生すると、markworld は重量級ロックに膨張します。

三、原子操作の実装原理#

1、用語#

CAS：比較と交換
キャッシュライン：キャッシュの最小操作単位
メモリ順序競合：一般的に偽共有によって引き起こされ、メモリ順序競合が発生すると、CPUはパイプラインをクリアする必要があります。
偽共有：複数のCPUが同じキャッシュラインの異なる部分を同時に変更し、その結果、1つのCPUの操作が無効になること。

2、プロセッサによる原子操作の実装#

（1）バスロックによる原子性の保証

複数のプロセッサが同時に共有変数に対して読み書き操作（i++）を行うと、共有変数は複数のプロセッサによって同時に操作されるため、読み書き操作は原子的ではなくなります。操作が完了した後、共有変数の値は期待されるものと一致しません。

バスロック：あるプロセッサがバス上でLOCK#信号を出力すると、他のプロセッサの要求はブロックされ、そのプロセッサは共有メモリを独占できます。

（2）キャッシュロックによる原子性の保証

バスロックは CPU とメモリ間の通信をロックし、ロック中は他のプロセッサが他のメモリアドレスのデータを操作できないため、バスロックのオーバーヘッドは大きいです。

キャッシュロック：メモリ領域がプロセッサのキャッシュラインにキャッシュされ、LOCK期間中にロックされている場合、ロック操作を実行するとき、プロセッサはバス上でLOCK #信号を主張するのではなく、内部のメモリアドレスを変更し、キャッシュの一貫性メカニズムを使用して操作の原子性を保証します。キャッシュの一貫性メカニズムは、2 つ以上のプロセッサがキャッシュしているメモリ領域のデータを同時に変更することを防ぎ、他のプロセッサがロックされたキャッシュラインのデータを書き戻すと、そのキャッシュラインを無効にします。

キャッシュロックが使用されない2つの状況：
    1、データがプロセッサ内部にキャッシュできない、または操作するデータが複数のキャッシュラインにまたがる場合、この場合はバスロックを使用します。
    2、一部のプロセッサがキャッシュロックをサポートしていない。

3、Java による原子操作の実装（ロックとループ CAS）#

（1）ループ CAS メカニズム

プロセッサのCMPXCHG命令

スピン CAS：成功するまでループで CAS 操作を行います。

CAS による原子操作の 3 つの主要な問題：

ABA 問題：A から B、再び A に戻ると、CAS が値をチェックする際に変化がないと見なされますが、実際には変化が発生しています。解決方法は、変数の前にバージョン番号を追加することです：1A から 2B、3C へ。

AtomicStampedReference クラスによる解決方法：

ループ時間が長くなるとオーバーヘッドが大きくなる：スピン CAS が長時間成功しない場合、CPU に非常に大きな実行オーバーヘッドが発生します。
1 つの共有変数の原子操作しか保証できない：この場合はロックを使用するか、いくつかの共有変数を統合します。

（2）ロックメカニズム

偏向ロックを除く他の 2 つのロックは、ループ CAS メカニズムを使用しています。つまり、スレッドが同期ブロックに入るときにループ CAS の方法でロックを取得し、同期ブロックを退出するときにループ CAS を使用してロックを解放します。