私はジョン・スキートが質問に対して出した答えを読んでいて、その中で彼は次のように述べていました：
私に関する限り、ロックフリー マルチスレッディングは真のスレッディング エキスパート向けであり、私はその 1 人ではありません。
これを聞いたのは初めてではありませんが、ロックフリーのマルチスレッド コードの書き方を学ぶことに興味がある場合、実際にどのようにそれを行うかについて話している人はほとんどいません。
だから私の質問は、スレッドなどについてできることをすべて学ぶことに加えて、ロックフリーのマルチスレッドコードを具体的に書くことをどこから学び始めますか、そしていくつかの良いリソースは何ですか.
乾杯
現在の「ロックフリー」の実装は、ほとんどの場合、同じパターンに従います。
(*オプション: データ構造/アルゴリズムに依存)
最後のビットは、不気味なほどスピンロックに似ています。実際、これは基本的なスピンロックです。:)
これについては @nobugz に同意します。ロックフリー マルチスレッドで使用されるインターロック操作のコストは、実行する必要があるキャッシュとメモリ コヒーレンシ タスクによって支配されます。
ただし、「ロックフリー」のデータ構造で得られるのは、「ロック」が非常に細かいことです。これにより、2 つの同時スレッドが同じ「ロック」(メモリ位置) にアクセスする可能性が減少します。
ほとんどの場合の秘訣は、専用のロックを持たないことです。代わりに、たとえば、配列内のすべての要素またはリンクされたリスト内のすべてのノードを「スピンロック」として扱います。最後に読んでから更新がない場合は、読んで、変更して、更新しようとします。あった場合は、再試行します。
これにより、追加のメモリやリソースの要件を導入することなく、「ロック」(申し訳ありませんが、ロックなし:) が非常にきめ細かくなります。
よりきめ細かくすると、待機の可能性が減少します。追加のリソース要件を導入することなく、可能な限りきめ細かくすることは素晴らしいことだと思いませんか?
ただし、楽しみのほとんどは、正しいロード/ストア順序を確保することから得られます。
直感に反して、CPU はメモリの読み取り/書き込みを自由に並べ替えることができます。ちなみに、CPU は非常にスマートです。単一のスレッドからこれを観察するのは難しいでしょう。ただし、複数のコアでマルチスレッドを開始すると、問題が発生します。直観は崩壊します。命令がコードの前にあるからといって、それが実際に早く起こるとは限りません。CPU は順不同で命令を処理できます。特に、メイン メモリのレイテンシを隠してキャッシュをより有効に利用するために、メモリ アクセスを伴う命令に対してこれを行うことを好みます。
さて、直感に反して、コードのシーケンスが「トップダウン」に流れるのではなく、シーケンスがまったくないかのように実行され、「悪魔の遊び場」と呼ばれることがあります。どのようなロード/ストアの再注文が行われるかについて、正確な答えを出すことは不可能だと思います。代わりに、常に5月と5月と缶の観点から話し、最悪の事態に備えます。「ああ、CPUはこの読み取りをその書き込みの前に並べ替える可能性があるため、ここ、この場所にメモリ バリアを配置するのが最善です。」
これらの能力でさえ、CPU アーキテクチャ間で異なる可能性があるという事実によって、問題は複雑になります。たとえば、あるアーキテクチャで は発生しないことが保証されていることが、別のアーキテクチャでは発生する可能性があります。
「ロックのない」マルチスレッドを正しく行うには、メモリ モデルを理解する必要があります。
ただし、この記事で示されているように、メモリ モデルと保証を正しく取得することは簡単ではありません。Intel と AMD は、MFENCEJVM 開発者の間で騒ぎを引き起こしたというドキュメントにいくつかの修正を加えました。結局のところ、開発者が最初から信頼していたドキュメントは、そもそもそれほど正確ではありませんでした。
.NET のロックは暗黙的なメモリ バリアをもたらすため、安全に使用できます (ほとんどの場合、つまり... たとえば、このJoe Duffy - Brad Abrams - Vance Morrisonの遅延初期化、ロック、揮発性およびメモリに関する偉大さを参照してください)。 :) (必ずそのページのリンクをたどってください。)
追加のボーナスとして、サイド クエストで .NET メモリ モデルを紹介します。:)
また、Vance Morrison の「oldie but goldie」: What Every Dev Must Know About Multithreaded Appsもあります。
...そしてもちろん、@Ericが述べたように、Joe Duffyはこの件に関する決定的な読み物です。
優れた STM は、可能な限りきめ細かなロックに近づけることができ、おそらく手作りの実装に近い、または同等のパフォーマンスを提供します。それらの 1 つは、MSのDevLabsプロジェクトのSTM.NETです。
あなたが .NET のみの熱狂者ではない場合、Doug Lea は JSR-166 で素晴らしい仕事をしました。
Cliff Clickは、Java や .NET の同時ハッシュ テーブルのようにロック ストライピングに依存しない興味深いハッシュ テーブルを採用しており、750 CPU まで十分に拡張できるようです。
Linux の領域に足を踏み入れることを恐れていない場合は、次の記事で、現在のメモリ アーキテクチャの内部構造と、キャッシュ ラインの共有がパフォーマンスをどのように損なうかについての洞察を提供します:すべてのプログラマがメモリについて知っておくべきこと.
@Ben は MPI について多くのコメントをしました。MPI ベースのソリューションは、スマートにしようとする中途半端なロックの実装よりも、推論が容易で、実装が容易で、エラーが発生しにくい可能性があります。(ただし、主観的には、STM ベースのソリューションにも当てはまります。) また、多くの成功例が示唆するように、Erlang などで適切な分散アプリケーションを正しく作成する方が何光年も簡単だと思います。
ただし、MPI には、単一のマルチコア システムで実行する場合のコストと問題があります。たとえば、Erlang では、プロセス スケジューリングとメッセージ キューの同期に関して解決すべき問題があります。
また、MPI システムは通常、"軽量プロセス" のために一種の協調的なN:M スケジューリングを実装します。これは、たとえば、軽量プロセス間で避けられないコンテキストの切り替えがあることを意味します。確かに、これは「従来のコンテキスト スイッチ」ではなく、ほとんどがユーザー空間操作であり、高速化できますが、インターロック操作にかかる 20 ～ 200 サイクル以下にできるとは思えません。ユーザーモードのコンテキスト切り替えは確かに遅いIntel McRT ライブラリーでも。軽量プロセスによる N:M スケジューリングは新しいものではありません。LWP は Solaris に長い間存在していました。彼らは見捨てられました。NTには繊維があった。それらは現在、ほとんどが遺物です。NetBSD には「アクティベーション」がありました。彼らは見捨てられました。Linux は、N:M スレッド化というテーマについて独自の見解を持っていました。今では少し死んでいるようです。
時々、新しい候補があります。たとえば、Intelの McRT や、最近では MicrosoftのConCRTと組み合わせたUser-Mode Schedulingなどです。
最低レベルでは、N:M MPI スケジューラと同じことを行います。Erlang (または任意の MPI システム) は、新しいUMSを活用することで、SMP システムで大きな利益を得る可能性があります。
OPの質問は、ソリューションのメリットや主観的な議論に関するものではないと思いますが、それに答えなければならない場合は、タスクに依存すると思います。多くのコアを備えた単一システム、ローロック/「ロックフリー」技術または STM のいずれかが、パフォーマンスの点で最良の結果をもたらし、上記のしわが解消されたとしても、パフォーマンスの点で常に MPI ソリューションを打ち負かすでしょう。例えばErlangで。
単一のシステムで動作するやや複雑なものを構築する場合は、従来の粗粒度ロックを選択するか、パフォーマンスが重要な場合は STM を選択します。
分散システムを構築する場合、MPI システムはおそらく自然な選択になるでしょう。
.NET用のMPI 実装
もあることに注意してください(ただし、それほどアクティブではないようです)。
ジョー・ダフィーの本:
http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html
彼はこれらのトピックに関するブログも書いています。
ローロック プログラムを正しく作成する秘訣は、ハードウェア、オペレーティング システム、およびランタイム環境の特定の組み合わせにおけるメモリ モデルのルールを深いレベルで正確に理解することです。
私は個人的に、InterlockedIncrement を超える正しいローロック プログラミングを行うほど賢くはありませんが、もしそうなら、それを試してみてください。コードに多くのドキュメントを残すようにしてください。そうすれば、あなたほど賢くない人がメモリ モデルの不変条件の 1 つを誤って壊して、見つけられないバグを導入することはありません。
最近は「ロックフリースレッディング」のようなものはありません。コンピュータハードウェアが遅くて高価だった前世紀の終わりに、それは学界などにとって興味深い遊び場でした。 デッカーのアルゴリズムは常に私のお気に入りであり、最新のハードウェアはそれを放牧しました。もう動作しません。
2つの開発がこれを終わらせました：RAMとCPUの速度の間の増大する格差。また、チップに複数のCPUコアを搭載するチップメーカーの能力。
RAM速度の問題により、チップ設計者はCPUチップにバッファを配置する必要がありました。バッファにはコードとデータが格納されており、CPUコアからすばやくアクセスできます。また、RAMとの間ではるかに遅い速度で読み書きできます。このバッファはCPUキャッシュと呼ばれ、ほとんどのCPUには少なくとも2つあります。第1レベルのキャッシュは小さくて高速で、第2レベルのキャッシュは大きくて低速です。CPUが第1レベルのキャッシュからデータと命令を読み取ることができる限り、CPUは高速で実行されます。キャッシュミスは非常にコストがかかります。データが1番目のキャッシュにない場合は最大10サイクル、2番目のキャッシュにない場合は最大200サイクル、CPUをスリープ状態にします。羊。
すべてのCPUコアには独自のキャッシュがあり、RAMの独自の「ビュー」を格納します。CPUがデータを書き込むと、書き込みはキャッシュに行われ、キャッシュはゆっくりとRAMにフラッシュされます。必然的に、各コアはRAMの内容について異なるビューを持つようになります。つまり、あるCPUは、そのRAM書き込みサイクルが完了してCPUが自身のビューを更新するまで、別のCPUが何を書き込んだかを知りません。
これは、スレッド化とは劇的に互換性がありません。別のスレッドによって書き込まれたデータを読み取る必要がある場合は、常に別のスレッドの状態を気にします。これを確実にするには、いわゆるメモリバリアを明示的にプログラムする必要があります。これは、すべてのCPUキャッシュが一貫した状態にあり、RAMの最新のビューを持つことを保証する低レベルのCPUプリミティブです。保留中の書き込みはすべてRAMにフラッシュする必要があり、キャッシュを更新する必要があります。
これは.NETで利用可能であり、Thread.MemoryBarrier（）メソッドが実装します。これがlockステートメントが実行するジョブの90％（および実行時間の95％以上）であることを考えると、.NETが提供するツールを回避し、独自のツールを実装しようとすることで、先に進むことはできません。
ロックのないデータ構造とソフトウェア トランザクション メモリについては Google を参照してください。
これについては、John Skeet に同意します。ロックフリースレッドは悪魔の遊び場であり、知る必要があることを知っていることを知っている人々に任せるのが最善です.
マルチスレッドに関しては、自分が何をしているのかを正確に知る必要があります。つまり、マルチスレッド環境で作業しているときに発生する可能性のあるすべてのシナリオ/ケースを調査するということです。ロックフリー マルチスレッドは、私たちが組み込むライブラリやクラスではなく、スレッドの旅で得た知識/経験です。
.NET ではロックのないスレッド化は難しいかもしれませんが、ロックする必要があるものを正確に調査し、ロックされたセクションを最小限に抑えることで、ロックを使用するときに大幅な改善を行うことができます。これは、ロックの粒度の最小化とも呼ばれます。
例として、コレクションをスレッドセーフにする必要があるとします。コレクションを反復処理するメソッドが各項目で CPU を集中的に使用するタスクを実行する場合、やみくもにロックをスローしないでください。コレクションの浅いコピーを作成する際にロックを設定するだけでよい場合があります。コピーを繰り返し処理すると、ロックなしで機能する可能性があります。もちろん、これはコードの詳細に大きく依存しますが、このアプローチでロック コンボイの問題を修正できました。
