ロックフリーのデータ構造が「特定のワークロードに対して」より効率的であることをどこかで読みました（もうページが見つかりません）。アトミック操作を実行するためのロック命令の約 100 サイクルのヒットは、スリープしてスケジューラがプロセスを復帰させるのを待つよりもはるかに高速に聞こえるため、ロックフリーのデータ構造がどのような状況下にあるかは明らかではありません。昔ながらのミューテックスよりも好ましくないでしょう。ロックが 99% の時間利用可能で、プロセスがスリープ状態になる必要がない場合、ミューテックスの方が高速ですか? 適切なロックのないデータ構造が利用可能であると仮定して、どちらに進むべきかを知るための良い経験則はありますか?
8014 次
6 に答える
54
ロックフリーのデータ構造を実装するための一般的なアプローチは、不変オブジェクトへの可変参照を持ち、構造を変更したいものはすべて参照を取得し、適切な変更が適用された新しいバージョンのオブジェクトを生成してから、CompareExchange を行うことです。新しいオブジェクトを指す参照。CompareExchange が機能する場合は、すばらしいことです。そうでない場合は、新しいオブジェクトを破棄し、参照を再度取得して、最初からやり直してください。
これは、新しいオブジェクトの作成が安価であり、競合のレベルが十分に低く、CompareExchange が通常機能する場合にうまく機能します。かなりの競合があり、新しいオブジェクトの作成が遅い場合、N 個のスレッドによる同時更新の試みが完了するまでに N^2 の時間がかかる場合があります。極端な例として、CPU で 100 のスレッドが実行されており、更新に 100 ミリ秒の CPU 時間がかかり (タイム スライスをわずかに超える)、100 のスレッドすべてがオブジェクトを一度に更新しようとするとします。最初の 10 秒間、各スレッドは元のオブジェクトに基づいて新しいオブジェクトを生成します。スレッドの 1 つは CompareExchange を正常に実行しますが、他のスレッドはすべて失敗します。次の 9.9 秒間で、99 のスレッドがオブジェクトの新しいバージョンを生成し、その後、1 つのスレッドが更新を正常に送信し、98 のスレッドが失敗します。
于 2010-10-28T15:48:12.367 に答える
7
ロックレス データ構造は、何らかの形で、アーキテクチャのアトミック セマンティクスを使用してコア操作を実行します。これを行うと、マシン全体の内部除外メカニズムを使用して、データの正しい順序付けまたはフェンシングを確保できます。ミューテックスまたはクリティカル セクションもこれを行いますが、1 つのフラグに対して 1 回しか行いません。ミューテックスまたはクリティカル セクションが遅いのは、ロックの取得が失敗したときです (競合があります)。この場合、OS はスケジューラーも呼び出して、除外オブジェクトが解放されるまでスレッドを中断します。
したがって、ロックのないデータ構造がコア メソッドごとに複数のアトミック操作を使用する場合は常に、クリティカル セクションを保護する単一のロックが同じセマンティクスを提供でき、問題のデータ構造に対して実際には競合がほとんどない傾向があることは論理的に思えます。実際、独自のロック機構を構築するよりも、OS が提供するロック機構を使用する方が理にかなっています。
于 2009-10-18T21:41:27.930 に答える
1
答えのこの部分に1つのポイントを追加したいと思います。「ミューテックスまたはクリティカルセクションが遅いのは、ロックの取得が失敗したときです（競合があります）。この場合、OSはスケジューラーを呼び出して、除外オブジェクトが解放されるまでスレッドします。」
ロックの取得が失敗した場合の対処方法については、オペレーティングシステムが異なればアプローチも異なるようです。私はHP-UXを使用していますが、たとえば、ミューテックスをロックするためのより洗練されたアプローチがあります。説明は次のとおりです。
...一方、コンテキストの変更はコストのかかるプロセスです。待機時間が短くなる場合は、コンテキストスイッチを実行しないでください。これらの要件のバランスを取るために、セマフォを取得してロックされていることを確認する場合、最初に行うことは短いスピン待機です。ルーチンpsema_spin_1（）は、ロックを取得しようとして最大50,000クロックサイクルの間スピンするために呼び出されます。50,000サイクル後にロックを取得できない場合は、psema_switch_1（）を呼び出してプロセッサを放棄し、別のプロセスに引き継がせます。
于 2009-10-19T13:23:04.337 に答える
1
ミューテックスは、その状態を表すために 1 つまたはいくつかのアトミック オブジェクトを使用するという意味で、ロックのないデータ構造として実装される可能性があることに注意してください。それは誤った二分法です。
複数のスレッドが一連の操作へのアクセスを待機できるようにする必要があるかどうか、またはシグナルが送信されるまでブロックする必要があるかどうかを検討することをお勧めします。それぞれに、待機中のスレッドのキューが必要です。前者は同期領域へのアクセスを待っているスレッドをキューに入れ、後者はシグナルを待っているスレッドをキューに入れます。Java クラスAbstractQueuedSynchronizerとAbstractQueuedLongSynchronizerはそのようなキュー (特にCLH キュー) を提供し、このキュー上でミューテックス、条件、およびその他のキューベースのプリミティブを構築できます。
1 つのスレッドだけが排他的な一連の作業を実行し、他のスレッドが他の作業を自由に実行できるようになるまで待機するのではなく、他のスレッドが同じ作業を実行できるようになるまで待つのではなく、1 つのスレッドのみを優先するという要件がある場合は、ロックフリーの手法を使用できます。そうすることで実行時間が短縮されるかどうかは、ベンチマークに依存し、これらの同期制御をめぐって競合するスレッドの頻度と数、およびスレッドが独立して実行する他の作業があるかどうかに左右されます。
于 2009-11-07T22:49:33.363 に答える
0
効率はメトリックに依存します。プリエンプションによってデッドロックが発生したり、スケジュールの締め切りに影響を与えたりする可能性があるシステムでは、ロックまたは待機のないアルゴリズムが重要です。そのような場合、処理は正確さほど重要ではありません。
OP は、ロックをミューテックスの代替手段と見なしています。一部のアルゴリズムでは、どちらも共有データ構造にアクセスする必要はありません。このような場合、プロデューサーとコンシューマーの両方が、他方に関係なく同じデータ構造に同時にアクセスできます。共有キューの例では、1 つのリーダーと 1 つのライターが共有インスタンスで同時に動作することを許可します。これは、コンシューマー プロセスがオンデマンドでアクセスできるデータを書き込むデバイス ドライバーの一般的なニーズを満たします。
さまざまなレベルのハードウェア サポートにより、プロセス間のより複雑な関係を許容できます(分析については、Herlihy (1991) を参照) 。彼は、Wait-free 同期は、並行オブジェクトを実装するための従来のロックベースの手法との質的な違いを表していると結論付けています。
これが意味することは、トレードオフが残っているということですが、ミューテックスとスピンロックのどちらかを選択するだけではありません。
経験則は、パフォーマンスよりも正確さに焦点を当てることに変わりはありません。通常、パフォーマンスは問題にお金を投じることで達成できますが、要件を満たすことは通常より困難です。
于 2016-07-26T00:19:23.913 に答える