[解決済み] ロックフリーのマルチスレッドは真のスレッドエキスパートのためにある

しかし、データ構造で得られるのは、ロックが非常に細かいということです。 . これにより、2 つの同時実行スレッドが同じロック (メモリ位置) にアクセスする可能性を低くすることができます。

その代わりに、例えば配列のすべての要素やリンクリストのすべてのノードをスピンロックとして扱います。読み込み、変更、そして最後の読み込み以降に更新がなければ更新を試みます。更新があった場合、再試行します。

これにより、追加のメモリやリソースを必要とすることなく、非常にきめ細かいロック（あ、すみません、非ロックです）を行うことができます。

より細かくすることで、待ち時間が発生する確率が下がります。追加のリソース要件を導入することなく、可能な限りきめ細かくすることは素晴らしいことだと思いませんか？

しかし、ほとんどの楽しみは 正しいロード/ストアの順序を保証する .

直感に反して、CPUはメモリの読み書きを自由に並べ替えることができます - ちなみに彼らは非常に賢いので、シングルスレッドからこれを観察するのは難しいでしょう。しかし、マルチコアでマルチスレッドを行うようになると、問題にぶつかることになります。ある命令がコードの中で早く出てきたからと言って、それが実際に早く起こるとは限りません。CPU は命令を順番通りに処理できません。特に、メモリ アクセスを伴う命令では、メイン メモリのレイテンシを隠してキャッシュを有効に活用するために、この処理を好んで行います。

さて、一連のコードがトップダウンで流れるのではなく、まるで何もないかのように実行されるのは、直感に反していることは確かです。どのようなロード/ストアの再順序付けが行われるかについて、正確な答えを出すことは不可能だと思います。その代わりに、常に次のような言葉で語られます。 メイズ と かもしれない と 缶 で、最悪の事態に備えます。 があるかもしれない はこの読み取りをその書き込みの前に並べ替えるかもしれないので、ちょうどこの場所にメモリ バリアを置くのが最善です。

問題が複雑なのは、これらの メイズ と かもしれない は CPU アーキテクチャによって異なる可能性があります。それは は であるものが、たとえば 起きないことが保証されている あるアーキテクチャでは 起こるかもしれない が別のアーキテクチャで起こるかもしれません。

ロックフリーなマルチスレッドを正しく理解するためには、メモリモデルを理解する必要があります。

しかし、メモリモデルと保証を正しくすることは、次のように簡単なことではありません。 のドキュメントを修正したことで、Intel と AMD がこのストーリーを実証しました。 MFENCE のドキュメントを修正し、JVM 開発者の間にいくつかの動揺を引き起こしました。 . 結局のところ、開発者が当初から頼りにしていたドキュメントは、そもそもそれほど正確ではなかったということです。

.NETにおけるロックは暗黙のメモリバリアとなるため、安全に使用できます (ほとんどの場合、ですが...たとえば次のようなものがあります)。 Joe Duffy - Brad Abrams - Vance Morrison の偉大さ 遅延初期化、ロック、揮発性、メモリバリアーについてです)。 (そのページにあるリンクを必ずたどってください)。

おまけとして、あなたは サイドクエストで.NETのメモリモデルについて紹介されます。 . :)

Vance Morrison による "oldie but goldie" もあります。 マルチスレッド アプリケーションについてすべての開発者が知っておくべきこと .

...そして、もちろん エリック は言及しました。 ジョー ダフィー は、このテーマに関する決定的な読み物です。

優れたSTMは、きめ細かいロックに限りなく近づくことができ、おそらく手作りの実装に近い、あるいは同等のパフォーマンスを提供することができるでしょう。 その 1 つが STM.NET から提供されています。 DevLabs プロジェクト からのものです。

.NETオンリーの狂信者でないなら Doug Lea は JSR-166 で素晴らしい仕事をしました。 .

クリフクリック は、Java や .NET の並列ハッシュ テーブルのようなロック ストライピングに依存しない、ハッシュ テーブルに関する興味深い見解を示しています。

Linux の領域に踏み込むことを恐れないのであれば、次の記事は、現在のメモリ アーキテクチャの内部と、キャッシュ ラインの共有がどのようにパフォーマンスを破壊するかについて、より深い洞察を与えてくれます。 すべてのプログラマーがメモリについて知っておくべきこと .

@BenはMPIについて多くのコメントをしました。私は、MPI がいくつかの領域で輝いているかもしれないことに心から同意します。MPI ベースのソリューションは、スマートであろうとする中途半端なロック実装よりも、推論しやすく、実装しやすく、エラーを起こしにくいものです (これは主観的ですが、STM ベースのソリューションにも当てはまります)。(これは主観的ですが、STMベースのソリューションにも当てはまります。) また、まともな 分散型 アプリケーションを正しく書くのは、例えばErlangのようなもので、多くの成功例が示唆しています。

MPIは、しかし、それ自身のコストがあり、また シングル、マルチコアシステム . 例えばErlangの場合は プロセススケジューリングとメッセージキューの同期 .

また、MPIシステムの中核には、通常、一種の協調的な N:Mスケジューリング を実装しています。これは例えば、軽量プロセス間のコンテキストスイッチが不可避であることを意味します。確かに、これは古典的なコンテキスト スイッチではなく、ほとんどがユーザー空間の操作であり、高速化することができます。 連動した操作にかかる 20 ～ 200 サイクル . ユーザー モードのコンテキスト スイッチは よりも確実に遅く でさえも遅いのです。 軽量プロセスによる N:M スケジューリングは新しいものではありません。LWP は Solaris に長い間存在していました。しかし、それらは放棄されました。NTにはファイバーがありました。今ではほとんど遺物になっています。NetBSDにはquot;activation"がありました。それらは放棄されました。LinuxにはN:Mスレッディングという題材で独自の取り組みがありました。それは今となってはやや死語になっているようです。

時々、新しい候補があります: 例えば インテルからの McRT や、最近では ユーザーモード・スケジューリング と共に コンカレント をマイクロソフト社から導入しました。

最も低いレベルでは、N:M MPIスケジューラが行うことを行います。Erlang、あるいはどんなMPIシステムでも、SMPシステムで新しい UMS .

OP の質問は、どのソリューションのメリットや主観的な主張についてではないのでしょうが、もし私がそれに答えるとしたら、タスクによると思います: 低レベルで高性能な基本データ構造を構築し、それを実行するために 単一システム と メニーコア の場合、低ロック/ロックフリー技術かSTMが性能面で最良の結果をもたらし、たとえErlangなどで上記のしわ寄せがあったとしても、おそらく性能面ではMPIソリューションに勝てるでしょう。

単一システム上で動作する中程度の複雑なものを構築する場合、私はおそらく古典的な粗視化ロックか、パフォーマンスが非常に重要であればSTMを選択するでしょう。

分散システムを構築するために、MPIシステムはおそらく自然な選択でしょう。

があることに注意してください。 MPI の実装 には .NETでも (にも対応しています（ただし、それほど活発ではないようです）。