私のマルチスレッド アプリケーションでは、ロックの競合が激しく、複数のコアにまたがる優れたスケーラビリティが妨げられています。これを解決するために、ロックフリープログラミングを使用することにしました。
ロックのない構造を書くにはどうすればよいですか?
Suma
質問する
10671 次
21 に答える
45
簡単な答えは次のとおりです。
それはいけません。
長い答えは次のとおりです。
この質問をしている場合、ロックのない構造を作成できるほど十分に理解していない可能性があります。ロックのない構造を作成することは非常に難しく、この分野の専門家だけがそれを行うことができます。独自の実装を作成する代わりに、既存の実装を検索してください。それを見つけたら、それがどれだけ広く使われているか、どれだけ文書化されているか、十分に証明されているか、どのような制限があるかを確認してください。
現在使用している構造に対応するロックフリー構造が見つからない場合は、既存のものを使用できるようにアルゴリズムを調整してください。
それでも独自のロックフリー構造を作成することに固執する場合は、次のことを確認してください。
- 非常に簡単なことから始める
- ターゲット プラットフォームのメモリ モデルを理解する (読み取り/書き込みの並べ替えの制約、アトミックな操作を含む)
- ロックフリー構造を実装する際に他の人が遭遇した問題について多くのことを研究する
- うまくいくかどうかを推測するだけでなく、証明してください
- 結果を徹底的にテストする
もっと読む：
于 2008-09-18T13:36:31.990 に答える
16
Intel の Threading Building Blocksなどのライブラリを使用してください。これには、かなりの数のロックフリーの構造とアルゴリズムが含まれています。ロックフリーのコードを自分で書こうとすることは本当にお勧めしません。非常にエラーが発生しやすく、正しくするのが難しいからです。
于 2008-09-18T13:25:50.240 に答える
12
スレッド セーフなロック フリー コードを記述するのは困難です。しかし、Herb Sutter のこの記事から始めることができます。
于 2008-09-18T13:23:14.380 に答える
12
sblundyが指摘したように、すべてのオブジェクトが不変で読み取り専用であれば、ロックについて心配する必要はありませんが、これはオブジェクトをたくさんコピーする必要があることを意味します。通常、コピーには malloc が含まれ、malloc はロックを使用してスレッド間でメモリ割り当てを同期するため、不変オブジェクトはあなたが思っているよりも購入しないかもしれません (malloc 自体のスケーリングはかなり悪く、malloc は遅いです。パフォーマンスが重要なセクションで多くの malloc を実行する場合は、ドン良いパフォーマンスを期待しないでください）。
単純な変数 (32 ビットまたは 64 ビットの int またはポインターなど) を更新する必要がある場合、単純に加算または減算演算を実行するか、2 つの変数の値を交換するだけの場合、ほとんどのプラットフォームはそのための「アトミック演算」を提供します (さらに GCC はこれらを提供します)。同じように）。Atomic は thread-safe と同じではありません。ただし、アトミックでは、たとえば、あるスレッドが 64 ビット値をメモリ ロケーションに書き込み、別のスレッドがそこから読み取る場合、読み取り操作は書き込み操作の前または書き込み操作の後に値を取得しますが、壊れた値は取得しません。書き込み操作の間 (たとえば、最初の 32 ビットが既に新しい値であり、最後の 32 ビットがまだ古い値である場合! これは、そのような変数でアトミック アクセスを使用しない場合に発生する可能性があります)。
ただし、更新したい 3 つの値を持つ C 構造体がある場合、アトミック操作で 3 つすべてを更新したとしても、これらは 3 つの独立した操作です。更新しました。ここで、保証する必要がある場合は、ロックが必要になります。リーダーは、構造体のすべての値が古い値または新しい値のいずれかであると認識します。
ロックのスケーリングを大幅に改善する 1 つの方法は、R/W ロックを使用することです。多くの場合、データの更新はあまり頻繁ではありませんが (書き込み操作)、データへのアクセス (データの読み取り) は非常に頻繁に行われます。コレクション (ハッシュテーブル、ツリー) について考えてみてください。その場合、多くのスレッドが同時に読み取りロックを保持でき (相互にブロックされない)、1 つのスレッドが書き込みロックを必要とする場合にのみ、他のすべてのスレッドが書き込みロックを必要とするため、R/W ロックによってパフォーマンスが大幅に向上します。更新の実行中はブロックされます。
スレッドの問題を回避する最善の方法は、スレッド間でデータを共有しないことです。すべてのスレッドがほとんどの場合、他のスレッドがアクセスできないデータを処理する場合、そのデータをロックする必要はまったくありません (アトミック操作もありません)。そのため、スレッド間で共有するデータはできるだけ少なくしてください。次に、本当に必要な場合にのみ、スレッド間でデータを高速に移動する方法が必要です (ITC、スレッド間通信)。オペレーティング システム、プラットフォーム、およびプログラミング言語 (残念ながら、これらのいずれも教えてくれませんでした) によっては、ITC のためのさまざまな強力な方法が存在する可能性があります。
最後に、共有データをロックせずに操作するもう 1 つの方法は、スレッドが共有データの同じ部分にアクセスしないようにすることです。たとえば、2 つのスレッドが配列を共有しているが、一方が偶数インデックスにのみアクセスし、もう一方が奇数インデックスにのみアクセスする場合、ロックは必要ありません。または、両方が同じメモリ ブロックを共有し、一方がその上半分のみを使用し、もう一方が下半分のみを使用する場合、ロックは必要ありません。これが良いパフォーマンスにつながるとは言われていませんが。特にマルチコア CPU ではそうではありません。この共有データ (1 つのコアで実行中) への 1 つのスレッドの書き込み操作により、別のスレッド (別のコアで実行中) のためにキャッシュが強制的にフラッシュされる可能性があり、これらのキャッシュ フラッシュは、最新のマルチコア CPU で実行されるマルチスレッド アプリケーションのボトルネックになることがよくあります。
于 2008-09-18T13:42:31.570 に答える
10
私の教授 (「The Art of Multiprocessor Programming」の Nir Shavit) がクラスに言ったように: やめてください。主な理由はテスト容易性です。同期コードをテストすることはできません。シミュレーションを実行したり、ストレス テストを実行したりできます。しかし、それはせいぜい大まかな概算です。本当に必要なのは、数学的な正しさの証明です。そして、それらを書くどころか、それらを理解できる人はほとんどいません。したがって、他の人が言ったように、既存のライブラリを使用してください。Joe Duffy のブログでは、いくつかの手法について調査しています (セクション 28)。最初に試す必要があるのはツリー分割です。小さなタスクに分割して結合します。
于 2009-04-09T08:47:46.387 に答える
7
不変性は、ロックを回避するための 1 つのアプローチです。不変のスタックやキューなどに関する Eric Lippert の議論と実装を参照してください。
于 2008-09-18T13:24:32.987 に答える
6
で。Suma の答えである Maurice Herlithy は、The Art of Multiprocessor Programming で、実際にはロックなしで何でも記述できることを示しています (第 6 章を参照)。iirc、これには基本的に、タスクを処理ノード要素 (関数クロージャーなど) に分割し、それぞれをキューに入れることが含まれます。スレッドは、キャッシュされた最新のノードからすべてのノードをたどって状態を計算します。明らかに、これは最悪の場合、シーケンシャル パフォーマンスをもたらす可能性がありますが、重要なロックレス プロパティを備えているため、スレッドがロックを保持しているときに、スレッドが長期間スケジュール アウトされるシナリオを防止できます。Herlithy はまた、理論上の待機なしのパフォーマンスを実現します。つまり、1 つのスレッドがアトミック エンキューを獲得するために永遠に待機することはありません (これは多くの複雑なコードです)。
マルチスレッド化されたキュー/スタックは驚くほど難しいです ( ABA 問題を確認してください)。他のことは非常に単純かもしれません。while(true) { atomicCAS をスワップするまで } ブロックに慣れてください。彼らは信じられないほど強力です。CAS の何が正しいかの直感は開発に役立ちますが、単純な構造に減らすことができる場合は、適切なテストとより強力なツール (おそらくSKETCH、今後の MIT Kendo、またはspin ?) を使用して正確さを確認する必要があります。
あなたの問題についてもっと投稿してください。詳細なしで良い答えを出すのは難しいです。
編集の不変性は素晴らしいですが、私が正しく理解していれば、その適用性は限られています。読み取り後の書き込みの危険性を実際に克服することはできません。「mem = NewNode(mem)」を実行している 2 つのスレッドを考えてみましょう。彼らは両方とも私を読んで、それから両方ともそれを書くことができました。古典的なインクリメント関数には正しくありません。また、ヒープ割り当て (スレッド間で同期する必要がある) が原因で、おそらく遅くなります。
于 2009-04-09T07:50:45.277 に答える
5
不変性にはこの効果があります。オブジェクトを変更すると、新しいオブジェクトが作成されます。Lisp は裏でこのように動作します。
この手法については、 Effective Javaの項目 13 で説明されています。
于 2008-09-18T13:21:51.480 に答える
4
Cliff Click は、有限状態マシンを利用することによるロックフリーのデータ構造に関するいくつかの主要な研究を行い、Java の実装も多数投稿しました。彼の論文、スライド、および実装は、彼のブログ ( http://blogs.azulsystems.com/cliff/ ) で見つけることができます。
于 2008-09-18T13:37:33.423 に答える
2
この作業領域はドメインの専門家と博士号の領域であるため、既存の実装を使用します (適切に実行したい場合)。
たとえば、ここにコードのライブラリがあります。
于 2008-09-18T15:30:25.057 に答える
1
マルチコア CPU 用に独自のロックフリー データ構造を作成している場合は、メモリ バリアを忘れないでください。また、ソフトウェア トランザクション メモリの手法を調べることも検討してください。
于 2008-09-18T15:24:40.187 に答える
1
ロックフリー同期の基本原則は次のとおりです。
構造を読んでいるときはいつでも、読み取りを開始してから構造が変更されたかどうかを確認するテストを使用して読み取りを追跡し、読み取り中に他の何かが発生して変更されずに読み取りに成功するまで再試行します。
構造を変更するときはいつでも、アルゴリズムとデータを調整して、実行された場合に変更全体が他のスレッドから見えるようになる単一のアトミックステップが存在するようにし、変更がない限り見えないように物事を調整します。そのステップが取られます。そのステップでは、プラットフォームに存在するロックフリーのアトミック メカニズムを使用します (たとえば、compare-and-set、load-linked+store-conditional など)。そのステップでは、変更操作が開始されてから他のスレッドがオブジェクトを変更したかどうかを確認し、変更していない場合はコミットし、変更している場合は最初からやり直す必要があります。
Web 上には、ロックのない構造の例がたくさんあります。何を実装しているか、どのプラットフォームで実装しているかについて詳しく知らなければ、より具体的にすることは困難です。
于 2008-09-18T13:28:31.497 に答える
1
ほとんどのロックフリー アルゴリズムまたは構造は、何らかのアトミック操作、つまり、スレッドによって開始されたメモリ位置への変更で始まり、他のスレッドが同じ操作を実行する前に完了します。あなたの環境でそのような操作はありませんか？
この主題に関する標準的な論文については、こちらを参照してください。
さらなるアイデアやリンクについては、このウィキペディアの記事もお試しください。
于 2008-09-18T13:32:44.607 に答える
0
このテーマに関するいくつかの実装と論文を読むと、次の共通のテーマがあることに気付くでしょう。
1）共有状態オブジェクトはlisp / clojureスタイルで不変です。つまり、すべての書き込み操作は、新しいオブジェクトの既存の状態をコピーして実装され、新しいオブジェクトに変更を加えてから、共有状態を更新しようとします（ CASプリミティブで更新できます）。つまり、現在のスレッドよりも多くの人が読み取る可能性のある既存のオブジェクトを変更することは絶対にしないでください。不変性は、大きくて複雑なオブジェクトのコピーオンライトセマンティクスを使用して最適化できますが、それは別のナッツのツリーです
2）現在の状態と次の状態の間で許可される遷移が有効であるかを明確に指定します。次に、アルゴリズムが有効であることの検証が桁違いに簡単になります。
3）スレッドごとのハザードポインタリストで破棄された参照を処理します。参照オブジェクトが安全になったら、可能であれば再利用します
セマフォとミューテックスで実装された一部のコードが（部分的に）ロックフリースタイルで再実装されている私の別の関連記事を参照してください： 相互排除とセマフォ
于 2010-11-11T18:38:30.107 に答える
0
構造の種類にもよりますが、衝突の可能性を慎重かつ黙って検出し、処理するように構造を作成する必要があります。
100% ロックのないものを作成できるとは思えませんが、これもまた、構築する必要がある構造の種類によって異なります。
また、複数のスレッドが個々のアイテムで動作するように構造を分割し、後で同期/再結合する必要がある場合もあります。
于 2008-09-18T13:22:27.017 に答える
0
ロックフリーのデータ構造を記述する方法の例については、私のリンク ConcurrentLinkedHashMapをご覧ください。学術論文に基づいたものではなく、他の人が暗示するように何年もの研究を必要としません. 慎重なエンジニアリングが必要です。
私の実装では、バケットごとのロック アルゴリズムである ConcurrentHashMap を使用していますが、その実装の詳細には依存していません。Cliff Click のロックフリー実装に簡単に置き換えることができます。私は Cliff からアイデアを借りましたが、より明示的に使用したのは、ステート マシンを使用してすべての CAS 操作をモデル化することです。これにより、モデルが大幅に簡素化されます。'ing 状態を介して疑似ロックがあることがわかります。もう 1 つの秘訣は、怠惰を許容し、必要に応じて解決することです。これは、後戻りしたり、他のスレッドにクリーンアップを「支援」させたりすることでよく見られます。私の場合、リストの途中からノードを削除する複雑さに対処するのではなく、リストのデッド ノードが先頭に到達したときに削除できるようにすることにしました。私はそれを変えるかもしれませんが、私はしませんでした」
「The Art of Multiprocessor Programming」という本は優れた入門書です。ただし、全体的には、アプリケーション コードでロックフリーの設計を避けることをお勧めします。多くの場合、エラーが発生しにくい他の手法が適しているのに、単純にやり過ぎです。
于 2008-09-20T02:26:12.280 に答える
0
前述のように、それは実際に話している構造のタイプによって異なります。たとえば、制限付きのロックフリー キューを作成できますが、ランダム アクセスを許可するキューは作成できません。
于 2008-09-18T13:24:03.613 に答える
0
Java では、独自のパッケージを作成する代わりに、JDK 5+ の java.util.concurrent パッケージを利用します。上で述べたように、これは実際には専門家の分野であり、1 年か 2 年余裕がない限り、自分で開発するという選択肢はありません。
于 2008-09-18T14:42:38.650 に答える
0
共有された変更可能な状態を削減または排除します。
于 2008-09-18T13:26:43.200 に答える
0
構造の意味を明確にできますか？
現時点では、全体的なアーキテクチャを意味していると思います。プロセス間でメモリを共有せず、プロセスにアクター モデルを使用することで、これを実現できます。
于 2008-09-18T16:06:30.180 に答える