2

この質問をできるだけ一般的なものにしようとしますが、実際の問題を簡単に紹介します-

プライオリティ キューに同時スキップリストを実装しようとしています。各「ノード」には、値と「転送」ノードの配列があります。ここで、node.forward[i] はスキップリストの i 番目のレベルの次のノードを表します。書き込みアクセス (つまり、挿入と削除) には、スピンロックを使用します (使用するのに最適なロックかどうかを判断するためです)。

私の質問は基本的に、トラバーサルに読み取りアクセスが必要な場合です。

node = node.forward[i]

このような状況では、どのようなスレッド セーフが必要ですか? 別のスレッドが node.forward[i] を読み取りとまったく同時に変更している場合 (読み取り用の現在のロック メカニズムがない場合)、ここで何が起こる可能性がありますか?

私が最初に考えたのは、Forward のインデクサーの getter と setter に ReaderWriterLockSLim を配置することです。このシナリオでは、不必要なロックが多すぎますか?

編集:または、代わりにすべての読み取りに Interlocked.Exchange を使用するのが最善でしょうか?

4

1 に答える 1

3

別のスレッドが（読み取り用の現在のロックメカニズムなしで）読み取りと同時にnode.forward [i]を変更している場合、ここで何が起こる可能性がありますか？

それは本当に実装に依存します。参照が無効になるのを防ぐ方法で「転送」を設定するときにInterlocked.Exchangeを使用することは可能ですが（「設定」をアトミックにすることができるため）、どの参照が読み取られるかは保証されません。ただし、単純な実装では、不良データの取得など、何でも発生する可能性があります。

私の最初の考えは、ForwardのインデクサーのゲッターとセッターにReaderWriterLockSLimを配置することです。

これは、開始するのに適した場所である可能性があります。を使用して適切に同期されたコレクションを作成するのはかなり簡単ReaderWriterLockSlimであり、機能は常に最優先事項です。

これはおそらく良い出発点になるでしょう。

このシナリオでは、不要なロックが多すぎますか？

それをどのように実装するか、そしてさらに重要なことに、それがどのように使用されるのかを見ずに知る方法はありません。使用法に応じて、その時点で必要に応じて最適化の機会をプロファイリングして探すことができます。

node.Forward[i]ちなみに、ここでは「リンクリスト」アプローチではなく、使用を再検討することをお勧めします。へのアクセスにForward[i]は、スキップリストの手順を繰り返すためにかなりの同期が必要になる可能性があります。とiの間のどこかに同時書き込みがあり、それ以降の要素がある場合は、エラーを防ぐためにすべての同期が必要になります。1つのステップだけ先を見越すと、必要な同期の量を（潜在的に）減らすことができます。 nodeinode

于 2012-10-02T16:14:56.403 に答える