Raymond Chenは、ロックフリーアルゴリズムに関する膨大な 連載 を行っています。関数の単純なケースを超えて、これらすべての一般的なパターンは、独自のロックを実装することです。もちろん、プロセッサ ロックはありませんが、一貫性を確保するために各 CPU で何度もループするという概念は、スピンロックに非常によく似ています。また、スピンロックであるため、他のスレッドを待機している間は量子の制御を譲らないため、オペレーティング システムに付属する一般的なロックよりも効率が低くなります。したがって、誰かが私のところに来て「でも私のアルゴリズムはロックフリーです」と言うときはいつでも、私の一般的な反応は「そうです」でしょうか? InterlockedXxx
興味があります-ロックフリーアルゴリズムがロックフルアルゴリズムよりも優れていることを示すベンチマークはありますか?
InterlockedXxx 関数の単純なケースを超えて、これらすべての一般的なパターンは、独自のロックを実装することです。
ここでの答えはどれも、「ロックフリー」のCASループとミューテックスまたはスピン ロックの違いの核心に到達しているようには見えません。
重要な違いは、ロックフリーアルゴリズムは、他のスレッドの支援なしに、独自に進行することが保証されていることです。ロックまたはスピン ロックでは、ロックを取得できない貧弱なスレッドは、ロックを所有するスレッドに完全に翻弄されます。ロックを取得できない貧弱なスレッドは、待機以外のことはできません(ビジー待機または OS 支援スリープのいずれかを介して)。
CAS でループするロックフリー アルゴリズムにより、競合する他のスレッドが何を行っているかに関係なく、各スレッドが確実に進行します。各スレッドは、本質的に、独自の運命を制御しています。はい、それでも何度もループする必要がありますが、ループの回数は競合するスレッドの数によって制限されます。ほとんどの場合、無限にループすることはできません。(実際には、たとえば、偽の共有が原因で失敗し続けるLL/SCループが原因でライブロックが発生する可能性があります) - ただし、これに対処するためにスレッド自体が対策を講じることができます - それは意のままではありませんロックを保持している別のスレッドの。
パフォーマンスに関しては、依存します。私は、スレッドの競合が激しい場合でも、ロックフリー アルゴリズムが対応するロック機能よりも完全にパフォーマンスが優れているという目に余る例を見てきました。Debian 7 を実行している x86-64 マシンで、C++ Boost.Lockfree キュー (Michael/Scott アルゴリズムに基づく) とstd::queue、std::mutex. スレッドの競合が多い状況では、ロックフリー バージョンはほぼ 2 倍遅くなりました。
では、それはなぜでしょうか。ロックフリー アルゴリズムのパフォーマンスは、最終的には実装の詳細に依存します。アルゴリズムはどのように ABA を回避しますか? 安全なメモリ再利用をどのように達成しますか? 非常に多くのバリアントがあります...タグ付きポインター、エポックベースの再生、RCU/静止状態、ハザードポインター、一般的なプロセス全体のガベージコレクションなど。これらすべての戦略にはパフォーマンスへの影響があり、アプリケーションの一般的な方法に制限を課すものもあります設計することができます。一般に、私の経験では、参照カウント アプローチ (またはタグ付きポインター アプローチ) はパフォーマンスが低下する傾向があります。ただし、代替手段は実装がはるかに複雑になる可能性があり、スレッドローカル ストレージまたは一般化されたガベージ コレクションに基づく、より多くのメモリ再利用インフラストラクチャが必要になります。
一般に、ロックフリーアルゴリズムはスレッドごとの効率が低くなります。前述のように、単純なロックよりもロックフリーアルゴリズムを実装するために、より多くの作業を行っています。
ただし、競合に直面した場合、アルゴリズム全体の全体的なスループットが劇的に向上する傾向があります。 スレッド切り替えの待ち時間とコンテキスト切り替えは、多くのスレッドで高速に行われるため、アプリケーションのスループットが大幅に低下します。ロックフリーアルゴリズムは効果的に独自の「ロック」を実装していますが、コンテキストスイッチの数を防止または削減する方法で実装しているため、対応するロックよりもパフォーマンスが高くなる傾向があります。
そうは言っても、これのほとんどは問題のアルゴリズム（および実装）に依存します。たとえば、以前のロック メカニズムを使用する代わりに .NET 4 の新しい同時実行コレクションに切り替えることができたいくつかのルーチンがあり、アルゴリズムの合計速度が 30% 近く向上したことが測定されました。そうは言っても、これらの同じコレクションのいくつかを使用すると、基本的なロックと比較してパフォーマンスが低下することを示す多くのベンチマークが見つかります。すべてのパフォーマンスの最適化と同様に、実際に測定するまでわかりません。
ロックフリーは必ずしも高速ではありませんが、デッドロックやライブロックの可能性を排除できるため、プログラムが常に終了に向けて進行することを保証できます。ロックでは、そのような保証を行うことは困難です。デッドロックにつながる可能性のある実行シーケンスを見逃すのは非常に簡単です。
それを過ぎると、それはすべて依存します。少なくとも私の経験では、速度の違いは、ロックを使用するかどうかよりも、実装にデプロイされたスキル レベルに大きく依存する傾向があります。
x64 上の Windows では、単純な (フリーリストの前に結合配列がない) ロックフリー フリーリストは、mutex ベースのフリーリストよりも約 1 桁高速です。
私のラップトップ (Core i5) では、シングル スレッドでロックフリーの場合、1 秒あたり約 3,100 万回のフリーリスト操作が行われますが、ミューテックスでは 1 秒あたり約 230 万回の操作が行われます。
2 つのスレッド (別々の物理コア上) の場合、ロックフリーでは、スレッドごとに約 1,240 万回のフリーリスト操作が行われます。ミューテックスを使用すると、1 秒あたり約80,000回の操作が行われます。
真にロックフリーのアルゴリズムの主な利点は、タスクが失敗した場合でも堅牢であるということです（ロックフリーは「ロックを使用しない」（*）よりも厳しい条件であることに注意してください）。不要なロックを回避することにはパフォーマンス上の利点がありますが、最もパフォーマンスの高いデータ構造は、多くの場合、ロックを操作できるものですが、スラッシングを最小限に抑えるためにロックを使用できます。
（*）「ロックフリー」のマルチプロデューサーキューで、間違ったタイミングでウェイレイドされたプロデューサーが、作業が完了するまで消費者が新しいアイテムを見ることができないという試みをいくつか見ました。このようなデータ構造は、実際には「ロックフリー」と呼ばれるべきではありません。ブロックされた1つのプロデューサーは、他のプロデューサーの進行をブロックしませんが、任意にコンシューマーをブロックする可能性があります。
最近 [JavaOne Russia] [1] で、Oracle の従業員 (Java のパフォーマンスとベンチマークを専門とする) が、単純なintカウンターへの並列アクセス内での 1 秒あたりの操作についていくつかの測定値を示しました。古典的なロック ( java.util.concurrent.locks.ReentrantLock)。
これによると、スピンロックは、少数のスレッドがモニターにアクセスしようとするまでのみ、パフォーマンスが向上します。
ロックフリー アルゴリズムは、ブロックするアルゴリズムよりも絶対に高速です。しかし、もちろん逆もまた真です。実装がロック カウンター パーツよりも優れていると仮定すると、唯一の制限要因は競合です。
ConcurrentLinkedQueue と LinkedBlockingQueue の 2 つの Java クラスを取り上げます。中程度の現実世界の競合の下では、CLQ は LBQ よりもかなり優れています。競合が激しい場合、サスペンド スレッドを使用すると、LBQ のパフォーマンスが向上します。
user237815 には同意しません。synchronized キーワードは、以前ほど多くのオーバーヘッドを必要としませんが、ロックフリー アルゴリズムと比較すると、単一の CAS と比較してかなりの量のオーバーヘッドが関連付けられています。
少なくとも Java では、ロック自体は非常に高速です。synchronized キーワードは、多くのオーバーヘッドを追加しません。ループ内で同期メソッドを呼び出すだけで、自分でベンチマークできます。
ロックは競合が発生した場合にのみ遅くなり、ロックされるプロセスは瞬時ではありません。
ロックフリーはスリープしないという利点もあります。カーネルには、スリープを許可されていない場所があり、Windows カーネルにはそれらの場所がたくさんあり、データ構造を使用する能力が非常に制限されます。