Java原子操作の実現原理
4802 ワード
原子操作の実現原理
引用する
原子(atom)は「さらに分割できない最小粒子」を意味し、原子操作(atomic operation)は「中断できない1つまたは一連の操作」を意味する.マルチプロセッサに原子操作を表示するのは少し複雑です.本文はintelプロセッサとjavaの中でどのように原子操作を実現したのかについて話します.
キャッシュコンシステンシ機構は全体として,あるCPUがキャッシュ中のデータを操作した後,他のCPUに内部に格納されているキャッシュを破棄するよう通知したり,メインメモリから読み直したりする.
用語定義キャッシュライン(Cache line):キャッシュの最小操作単位 比較・交換(Compare and Swap):CAS操作には2つの数値、1つの古い値(所望の操作前の値)と1つの新しい値を入力する必要があり、操作期間中に古い値が変化したかどうかを比較し、変化がなければ新しい値に交換しない. CPUパイプライン(CPU pipeline):CPUパイプラインの動作方式は工業生産上の組立パイプラインのようで、CPUの中で5~6個の異なる機能の回路ユニットから1本の指令処理パイプラインを構成し、1本のX 86指令を5~6ステップに分けてこれらの電気回路ユニットでそれぞれ実行することで、1つのCPUクロックサイクルで1本の指令を完了することができ、これによりCPUの演算速度が向上する. メモリ順序衝突(Memory order violation):メモリ順序衝突は一般的に偽共有によって引き起こされ、偽共有とは複数のCPUが同じキャッシュラインの異なる部分を同時に修正して1つのCPUの操作が無効になることを意味し、このメモリ順序衝突が発生した場合、CPUはフローラインを空にしなければならない.
プロセッサが原子操作を実現する方法
32ビットIA−32プロセッサは、キャッシュに対するロックまたはバスに対するロックに基づく方法を使用して、マルチプロセッサ間の原子動作を実現する.
プロセッサは、基本的なメモリ操作の原子性を自動的に保証します.
まず、プロセッサは基本的なメモリ操作の原子性を自動的に保証します.プロセッサは、システムメモリから1バイトの読み取りまたは書き込みが原子であることを保証します.これは、1つのプロセッサが1バイトの読み取りを行うと、他のプロセッサがこのバイトのメモリアドレスにアクセスできないことを意味します.Pentium 6と最新のプロセッサは、単一プロセッサが同じキャッシュラインで16/32/64ビットの操作を行うことを自動的に保証することができますが、複雑なメモリ操作プロセッサは、バス幅、複数のキャッシュライン、ページテーブル間のアクセスなどの原子性を自動的に保証することはできません.しかし、プロセッサは、複雑なメモリ操作の原子性を保証するために、バスロックとキャッシュロックの2つのメカニズムを提供します.
バスロックを使用して原子性を保証する
第1のメカニズムは,バスロックにより原子性を保証することである.複数のプロセッサが共有変数を同時に読み書きする場合(i++は古典的な読み書き操作である)操作を行うと、共有変数は複数のプロセッサによって同時に操作され、読み書き操作は原子ではなく、操作が完了すると共有変数の値が所望と一致しない.例えば、i=1の場合、i++操作を2回行い、所望の結果は3であるが、結果は2である可能性がある.
複数のプロセッサが同時にそれぞれのキャッシュから変数iを読み出し,それぞれに加算操作を行い,システムメモリにそれぞれ書き込む可能性があるためである.では、共有変数の読み書き操作が原子であることを保証するには、CPU 1が共有変数の読み書きを保証しなければならない場合、CPU 2は、その共有変数のメモリアドレスをキャッシュしたキャッシュを操作できない.
プロセッサがバスロックを使用することで、この問題を解決します.バスロックとは、プロセッサが提供するLOCK＃信号を使用し、1つのプロセッサがバス上でこの信号を出力すると、他のプロセッサの要求がブロックされ、共有メモリを独占的に使用することができる.
キャッシュ・ロックを使用して原子性を保証する
2つ目のメカニズムは,キャッシュロックにより原子性を保証することである.同じ時点であるメモリアドレスの動作が原子性であることを保証するだけでよいが、バスロックバーCPUとメモリとの間の通信がロックされ、ロック期間中に他のプロセッサが他のメモリアドレスのデータを操作できないため、バスロックのオーバーヘッドが大きい.最近のプロセッサは、バスロックの代わりにキャッシュロックを使用して最適化される場合があります.頻繁に使用されるメモリはプロセッサのL 1,L 2,L 3キャッシュにキャッシュされ、原子操作はプロセッサ内部のキャッシュで直接行うことができ、バスロックを宣言する必要はなく、Pentium 6や最近のプロセッサではキャッシュロックを使用して複雑な原子性を実現することができます.キャッシュロックとは、プロセッサのキャッシュラインにおけるメモリ領域がLOCK動作中にロックされている場合に、ロック動作を実行してメモリに書き込まれると、プロセッサがバス上でLOCK信号を言わずに内部のメモリアドレスを変更し、そのキャッシュ整合性機構が動作の原子性を保証することを可能にすることである.キャッシュ整合性機構は、2つ以上のプロセッサによってキャッシュされたメモリ領域データを同時に変更することを阻止するため、他のプロセッサがロックされたキャッシュ行のデータを書き込み返すとキャッシュ行が無効となり、上述の例では、CPU 1がキャッシュ行のiを変更する際にキャッシュロックを使用すると、CPU 2はiのキャッシュ行を同時にキャッシュすることができなくなる.
ただし、CPUがキャッシュロックを使用しない場合は2つあります.動作データがプロセッサ内にキャッシュできない場合、または動作データが複数のキャッシュラインにまたがる場合、プロセッサはバスロックを呼び出す. 一部のプロセッサではキャッシュロックがサポートされていません.intel 486およびPentiumプロセッサでは、ロックされたメモリ領域がプロセッサのキャッシュラインでもバスロックが呼び出されます.
Javaが原子操作を実現する方法
サイクルCASによる原子操作
CASには3つのオペランド、メモリ値V、古い予想値A、修正する新しい値Bがあります.また、期待値Aとメモリ値Vが同一である場合のみ、メモリ値VをBに変更し、そうでない場合は、新しい値をパラメータとして操作し、操作が完了した後もこのループを継続し、期待値がメモリ値と同一であることを知り、メモリ値を新しい値に変更して終了する.
Java並列発注には,LinkedTransferQueueクラスのXfer法のような原子操作を実現するためにスピンCASを用いたいくつかの同時フレームワークもある.CASは原子操作を効率的に解決するが,CASには依然として3つの大きな問題がある.ABA問題では,サイクル時間が長くオーバーヘッドが大きく,共有変数の原子操作が1つしか保証できない.
1.ABA問題:
ABA問題.CASは、操作値のときに値が変化しているかどうかをチェックする必要があるので、変化がなければ更新しますが、1つの値がAで、Bになって、Aになっていると、CASを使ってチェックすると値が変化していないことがわかりますが、実際には変化しています.ABA問題の解決策はバージョン番号を使うことです.変数の前にバージョン番号を追加し、変数が更新されるたびにバージョン番号を1つ追加すると、A-B-Aは1 A-2 B-3 Aになります.
Java 1から5からJDKのatomicパッケージにABA問題を解決するためのクラスAtomicStampedReferenceが提供された.このクラスのcompareAndSetメソッドは、まず、現在の参照が所望の参照に等しいかどうかを確認し、現在のフラグが所望のフラグに等しいかどうかを確認し、すべてが等しい場合、その参照とフラグの値を所定の更新値に原子的に設定することです.
2.サイクル時間が長くてコストが大きい:
スピンCASが長時間失敗すると、CPUに非常に大きな実行コストがかかります.JVMがプロセッサが提供するpause命令をサポートできる場合、効率は一定の向上があり、pause命令には2つの役割がある.第1に、流水ライン実行命令
3.共有変数の原子操作は1つしか保証できません.
1つの共有変数に対して操作を実行する場合、ループCASを使用して原子操作を保証することができますが、複数の共有変数に対して操作する場合、ループCASは操作の原子性を保証することはできません.この場合、ロックを使用することができます.あるいは、複数の共有変数を1つの共有変数に結合して操作する方法があります.例えば、2つの共有変数i=2,j=aがあり、ij=2 aをマージしてCASでijを操作する.Java 1から5からJDKはAtomicReferenceクラスを提供して参照オブジェクト間の原子性を保証し、複数の変数を1つのオブジェクトに配置してCAS操作を行うことができます.
ロックメカニズムを用いて原子操作を実現する
ロックメカニズムは、ロックを取得したスレッドのみがロックされたメモリ領域を操作できることを保証します.JVM内部には多くのロック機構が実現されており、偏向ロック、軽量ロック、反発ロックがあり、興味深いことに偏向ロックに加えて、JVMがロックを実現する方法で使用されるループCASは、1つのスレッドが同期ブロックに入りたい場合にループCASを使用してロックを取得し、同じステップブロックを終了する場合にループCASを使用してロックを解放する.詳細は記事Java SE 1を参照してください.6のSynchronized.
引用する
原子(atom)は「さらに分割できない最小粒子」を意味し、原子操作(atomic operation)は「中断できない1つまたは一連の操作」を意味する.マルチプロセッサに原子操作を表示するのは少し複雑です.本文はintelプロセッサとjavaの中でどのように原子操作を実現したのかについて話します.
キャッシュコンシステンシ機構は全体として,あるCPUがキャッシュ中のデータを操作した後,他のCPUに内部に格納されているキャッシュを破棄するよう通知したり,メインメモリから読み直したりする.
用語定義
プロセッサが原子操作を実現する方法
32ビットIA−32プロセッサは、キャッシュに対するロックまたはバスに対するロックに基づく方法を使用して、マルチプロセッサ間の原子動作を実現する.
プロセッサは、基本的なメモリ操作の原子性を自動的に保証します.
まず、プロセッサは基本的なメモリ操作の原子性を自動的に保証します.プロセッサは、システムメモリから1バイトの読み取りまたは書き込みが原子であることを保証します.これは、1つのプロセッサが1バイトの読み取りを行うと、他のプロセッサがこのバイトのメモリアドレスにアクセスできないことを意味します.Pentium 6と最新のプロセッサは、単一プロセッサが同じキャッシュラインで16/32/64ビットの操作を行うことを自動的に保証することができますが、複雑なメモリ操作プロセッサは、バス幅、複数のキャッシュライン、ページテーブル間のアクセスなどの原子性を自動的に保証することはできません.しかし、プロセッサは、複雑なメモリ操作の原子性を保証するために、バスロックとキャッシュロックの2つのメカニズムを提供します.
バスロックを使用して原子性を保証する
第1のメカニズムは,バスロックにより原子性を保証することである.複数のプロセッサが共有変数を同時に読み書きする場合(i++は古典的な読み書き操作である)操作を行うと、共有変数は複数のプロセッサによって同時に操作され、読み書き操作は原子ではなく、操作が完了すると共有変数の値が所望と一致しない.例えば、i=1の場合、i++操作を2回行い、所望の結果は3であるが、結果は2である可能性がある.
複数のプロセッサが同時にそれぞれのキャッシュから変数iを読み出し,それぞれに加算操作を行い,システムメモリにそれぞれ書き込む可能性があるためである.では、共有変数の読み書き操作が原子であることを保証するには、CPU 1が共有変数の読み書きを保証しなければならない場合、CPU 2は、その共有変数のメモリアドレスをキャッシュしたキャッシュを操作できない.
プロセッサがバスロックを使用することで、この問題を解決します.バスロックとは、プロセッサが提供するLOCK＃信号を使用し、1つのプロセッサがバス上でこの信号を出力すると、他のプロセッサの要求がブロックされ、共有メモリを独占的に使用することができる.
キャッシュ・ロックを使用して原子性を保証する
2つ目のメカニズムは,キャッシュロックにより原子性を保証することである.同じ時点であるメモリアドレスの動作が原子性であることを保証するだけでよいが、バスロックバーCPUとメモリとの間の通信がロックされ、ロック期間中に他のプロセッサが他のメモリアドレスのデータを操作できないため、バスロックのオーバーヘッドが大きい.最近のプロセッサは、バスロックの代わりにキャッシュロックを使用して最適化される場合があります.頻繁に使用されるメモリはプロセッサのL 1,L 2,L 3キャッシュにキャッシュされ、原子操作はプロセッサ内部のキャッシュで直接行うことができ、バスロックを宣言する必要はなく、Pentium 6や最近のプロセッサではキャッシュロックを使用して複雑な原子性を実現することができます.キャッシュロックとは、プロセッサのキャッシュラインにおけるメモリ領域がLOCK動作中にロックされている場合に、ロック動作を実行してメモリに書き込まれると、プロセッサがバス上でLOCK信号を言わずに内部のメモリアドレスを変更し、そのキャッシュ整合性機構が動作の原子性を保証することを可能にすることである.キャッシュ整合性機構は、2つ以上のプロセッサによってキャッシュされたメモリ領域データを同時に変更することを阻止するため、他のプロセッサがロックされたキャッシュ行のデータを書き込み返すとキャッシュ行が無効となり、上述の例では、CPU 1がキャッシュ行のiを変更する際にキャッシュロックを使用すると、CPU 2はiのキャッシュ行を同時にキャッシュすることができなくなる.
ただし、CPUがキャッシュロックを使用しない場合は2つあります.
Javaが原子操作を実現する方法
サイクルCASによる原子操作
CASには3つのオペランド、メモリ値V、古い予想値A、修正する新しい値Bがあります.また、期待値Aとメモリ値Vが同一である場合のみ、メモリ値VをBに変更し、そうでない場合は、新しい値をパラメータとして操作し、操作が完了した後もこのループを継続し、期待値がメモリ値と同一であることを知り、メモリ値を新しい値に変更して終了する.
Java並列発注には,LinkedTransferQueueクラスのXfer法のような原子操作を実現するためにスピンCASを用いたいくつかの同時フレームワークもある.CASは原子操作を効率的に解決するが,CASには依然として3つの大きな問題がある.ABA問題では,サイクル時間が長くオーバーヘッドが大きく,共有変数の原子操作が1つしか保証できない.
1.ABA問題:
ABA問題.CASは、操作値のときに値が変化しているかどうかをチェックする必要があるので、変化がなければ更新しますが、1つの値がAで、Bになって、Aになっていると、CASを使ってチェックすると値が変化していないことがわかりますが、実際には変化しています.ABA問題の解決策はバージョン番号を使うことです.変数の前にバージョン番号を追加し、変数が更新されるたびにバージョン番号を1つ追加すると、A-B-Aは1 A-2 B-3 Aになります.
Java 1から5からJDKのatomicパッケージにABA問題を解決するためのクラスAtomicStampedReferenceが提供された.このクラスのcompareAndSetメソッドは、まず、現在の参照が所望の参照に等しいかどうかを確認し、現在のフラグが所望のフラグに等しいかどうかを確認し、すべてが等しい場合、その参照とフラグの値を所定の更新値に原子的に設定することです.
public boolean compareAndSet
(V expectedReference,//
V newReference,//
int expectedStamp, //
int newStamp) //
2.サイクル時間が長くてコストが大きい:
スピンCASが長時間失敗すると、CPUに非常に大きな実行コストがかかります.JVMがプロセッサが提供するpause命令をサポートできる場合、効率は一定の向上があり、pause命令には2つの役割がある.第1に、流水ライン実行命令
(de-pipeline)を遅延させ、CPUが実行資源を消費しすぎないようにすることができる.遅延時間は具体的な実装バージョンに依存し、一部のプロセッサでは遅延時間はゼロである.第2に、サイクルを終了する際にメモリ順序の競合(memory order violation)によりCPUラインが(CPU pipeline flush)クリアされることを回避し、CPUの実行効率を向上させることができる.3.共有変数の原子操作は1つしか保証できません.
1つの共有変数に対して操作を実行する場合、ループCASを使用して原子操作を保証することができますが、複数の共有変数に対して操作する場合、ループCASは操作の原子性を保証することはできません.この場合、ロックを使用することができます.あるいは、複数の共有変数を1つの共有変数に結合して操作する方法があります.例えば、2つの共有変数i=2,j=aがあり、ij=2 aをマージしてCASでijを操作する.Java 1から5からJDKはAtomicReferenceクラスを提供して参照オブジェクト間の原子性を保証し、複数の変数を1つのオブジェクトに配置してCAS操作を行うことができます.
ロックメカニズムを用いて原子操作を実現する
ロックメカニズムは、ロックを取得したスレッドのみがロックされたメモリ領域を操作できることを保証します.JVM内部には多くのロック機構が実現されており、偏向ロック、軽量ロック、反発ロックがあり、興味深いことに偏向ロックに加えて、JVMがロックを実現する方法で使用されるループCASは、1つのスレッドが同期ブロックに入りたい場合にループCASを使用してロックを取得し、同じステップブロックを終了する場合にループCASを使用してロックを解放する.詳細は記事Java SE 1を参照してください.6のSynchronized.