33

ミューテックスよりもアトミックを使用する主な理由は、ミューテックスが高価であるということですが、デフォルトのメモリモデルが でatomicsあるためmemory_order_seq_cst、これは同じくらい高価ではありませんか?

質問: ロックを使用する並行プログラムは、ロックのない並行プログラムと同じくらい高速にできますか?

memory_order_acq_relもしそうなら、アトミックに使いたくない限り、努力する価値はないかもしれません。

編集：私は何かが欠けているかもしれませんが、各ロックも完全なメモリバリアでなければならないため、ロックベースはロックフリーよりも高速ではありません。しかし、ロックフリーを使用すると、メモリ バリアよりも制限の少ない手法を使用できます。

私の質問に戻りますが、ロックフリーは新しい C++11 標準に基づくロックよりも高速memory_modelですか?

「パフォーマンスで測定するとロックフリー>=ロックベース」は本当ですか? 2 つのハードウェア スレッドがあるとします。

編集 2: 私の質問は、進行の保証に関するものではありません。おそらく、コンテキスト外で「ロックフリー」を使用している可能性があります。

基本的に、共有メモリを持つ2つのスレッドがあり、必要な唯一の保証は、一方のスレッドが書き込みを行っている場合、もう一方のスレッドが読み書きできないということです。私の仮定は、単純なアトミックcompare_and_swap操作の方がミューテックスをロックするよりもはるかに高速であるということです.

1 つのスレッドが共有メモリにまったく触れない場合、理由もなく何度もロックとロック解除を繰り返すことになりますが、アトミック操作では毎回 1 CPU サイクルしか使用しません。

コメントに関しては、競合がほとんどない場合、スピンロックとミューテックスロックは大きく異なります。

4

3 に答える 3

55

ロックフリー プログラミングは進行保証に関するものです。最も強いものから最も弱いものまで、それらはwait-free、lock-free、obstruction-free、blockingです。

保証は高価で、代償が伴います。より多くの保証が必要なほど、より多くの費用がかかります。一般に、ブロッキング アルゴリズムまたはデータ構造 (たとえばミューテックスを使用) には最大の自由度があり、潜在的に最速です。反対の極端な待機のないアルゴリズムは、すべてのステップでアトミック操作を使用する必要があり、これははるかに遅くなる可能性があります。

ロックを取得するのは実際にはかなり安いので、主題を深く理解していない限り、それについて心配する必要はありません. さらに、mutex を使用したブロッキング アルゴリズムは、読み取り、書き込み、および推論がはるかに簡単です。対照的に、最も単純なロックフリーのデータ構造でさえ、長期にわたる焦点を絞った研究の結果であり、それぞれが 1 人または複数の博士号を取得する価値があります。

簡単に言えば、ロックまたは待機のないアルゴリズムは、最悪のレイテンシーを平均的なレイテンシーとスループットと交換します。すべてが遅くなりますが、非常に遅いものはありません。これは、非常に特殊な状況 (リアルタイム システムなど) でのみ役立つ非常に特殊な特性です。

于 2013-04-30T20:32:13.257 に答える
1

ロックは、単純なアトミック操作よりも多くの操作を必要とする傾向があります。最も単純なケースでは、memory_order_seq_cst はロックの約 2 倍の速さになります。これは、ロックには実装で少なくとも 2 つのアトミック操作 (1 つはロック、もう 1 つはロック解除) が必要になる傾向があるためです。多くの場合、それ以上かかります。ただし、メモリ順序を活用し始めると、受け入れる同期が少なくなるため、はるかに高速になる可能性があります。

また、「ロック アルゴリズムは常にロック フリー アルゴリズムと同じくらい高速です」と表示されることもよくあります。これはある程度正しいです。基本的な考え方は、最速のアルゴリズムがたまたまロックフリーである場合、ロックフリーの保証がない最速のアルゴリズムも同じアルゴリズムであるということです! ただし、最速のアルゴリズムがロックを必要とする場合、ロックフリーの保証を要求するものは、より遅いアルゴリズムを見つける必要があります。

一般に、特殊なオペコードを活用するパフォーマンスが役立ついくつかの低レベル アルゴリズムで、ロックフリー アルゴリズムが見られます。他のほとんどすべてのコードでは、ロックは十分なパフォーマンス以上のものであり、読みやすくなっています。

于 2013-09-03T06:00:48.870 に答える
1

質問: ロックを使用する並行プログラムは、ロックのない並行プログラムと同じくらい高速にできますか?

より高速になる可能性があります。ロックフリーアルゴリズムは、グローバルな状態を常に一貫した状態に保つ必要があり、計算が完了したときに状態が変化した可能性があるため、生産的であるかどうかを知らずに計算を実行し、CPU が失われて無関係になります。サイクル。

ロック フリー戦略では、計算が完了したときに、プロセスの最後にシリアル化が行われます。異常なケースでは、多くのスレッドが作業を行うことができ、1 つの作業のみが生産的になり、他の作業は再試行されます。

ロックフリーは、優先度に関係なく、一部のスレッドの枯渇につながる可能性があり、それを回避する方法はありません。(ただし、異常な競合がない限り、スレッドが非常に長い間再試行を停止することはほとんどありません。)

一方、「シリアル化された計算と一連の副作用ベース」(別名ロックベース) アルゴリズムは、他のアクターによってその特定のロックされたリソースでの操作が妨げられないことを知る前に開始されません(保証は使用によって提供されます)。ミューテックスの)。複数のロックが取得された場合、別のリソースにアクセスする必要があるために終了できない可能性があることに注意してください。これにより、設計が不適切なプログラムで複数のロックが必要な場合にデッドロックが発生する可能性があります。

このデッド ロックの問題は、ロック フリー コードの範囲内ではないことに注意してください。ロック フリー コードは、複数のエンティティに対して動作することさえできません。通常、2 つの無関係なオブジェクトに基づいてアトミック コミットを行うことはできません(1)。

したがって、ロック フリー コードのデッド ロックの可能性がないことは、ロック フリー コードの弱点の兆候です。デッド ロックできないことは、ツールの限界です。一度にしかロックを保持できないシステムは、デッドロックすることもできません。

ロック フリー アルゴリズムの適用範囲は、ロック ベースのアルゴリズムの適用範囲に比べてごくわずかです。多くの問題では、ロックフリーは意味がありません。

ロックベースのアルゴリズムは礼儀正しく、スレッドは必要なことを実行する前に順番に待機する必要があります。これは、各スレッドによる計算ステップに関して最大​​限に効率的です。しかし、順番待ちリストにスレッドをキューイングしなければならないのは非効率的です: 多くの場合、スレッドはタイム スライスの最後を使用できないため、非常に非効率的です。彼の集中力は失われ、彼の作業時間は細分化するため、最大の効率に達することは決してありません。

（1）少なくともそのためには、ダブルCASを実行できる必要があります。これは、2つの任意のアドレスでアトミックな操作です（ダブルワードCASではなく、より多くのビットのCASであり、簡単に実装できます）キャッシュラインである自然なCPUメモリアクセス調停ユニットまで）。

于 2019-12-08T21:27:20.530 に答える