3

だから、私は、複数のスレッドが同時に読み取りと書き込みの両方のアクセス権を持つバイナリツリーでローテーションするときにノードをロックするためのこのスキームを思いつきました。これには、ローテーションごとに4つのノードをロックすることが含まれますが、これは非常に多いようです。必要なロックを減らす方法を思いついたので、ある方法を賢く考えましたが、グーグルはあまり現れませんでした（とにかく間違った用語を使用している可能性があります）。

これは私の現在のスキームです。オレンジと赤のノードは回転によって移動または変更されるため、ロックする必要があります。緑のノードは、回転の影響を受けるがそれ自体の影響を受けないノードに隣接しています。

二分木の回転

これを行うにはもっと良い方法が必要だと思いました。影響を受ける4つのノードのスナップショットを取り、スナップショット内でそれらをローテーションしてから、現在のノードをスナップショットのノードに置き換えるというアイデアがあります（ローテーションを行っていました）-これにより、ほぼロックフリーになりますが、ローテーションがかなり迅速な操作（3つのポインターの再割り当て）であることを考えると、メモリのオーバーヘッドが非常に大きくなる可能性がありますか？

これを効率的に行う方法についての指針（しゃれなし）を探していると思います。

4

6 に答える 6

4

不変の二分木を見てください。もう少しノードを変更する必要があります (すべてのノードからルートまで) が、それはlog n双方向の挿入の複雑さを変更しません。実際、同期コードが必要ないため、パフォーマンスが向上する可能性さえあります。

たとえば、Eric Lippert は、C# での不変の avl ツリーに関するいくつかの投稿を書きました。最後の 1 つは次のとおりです。C# の不変性 第 9 部: アカデミック? さらに、私のAVLツリーの実装

于 2009-03-16T21:17:27.583 に答える
1

私が見る限り、ロックフリーアルゴリズムには参照カウントがないため、一般的な使用には問題があります。要素へのポインタが有効かどうかはわかりません。その要素がなくなった可能性があります。

Valoisは、実際には役に立たないエキゾチックなメモリ割り当ての配置でこれを回避します。

ロックフリーのバランスの取れたツリーを実行するために私が見ることができる唯一の方法は、変更されたMCASを使用することです。ここでは、インクリメント/デクリメントも実行できるため、参照カウントを維持できます。私はMCASがこのように変更できるかどうかを見ていません。

于 2009-03-24T21:17:08.330 に答える
0

書き込み時に部分コピーを使用して、バイナリツリーをロックなしで読み取り可能にすることを試しました。ここに不完全な実装を投稿しましたhttp://groups.google.com/group/comp.programming.threads/msg/6c0775e9882516a2?hl=en&

于 2009-03-17T10:08:51.113 に答える
0

John Valois の論文では、補助ノードを使用して二分探索木を実装する方法について簡単に説明しています。同時 LinkedHashMap の設計で補助ノード アプローチを使用しています。CiteSeerX (非常に貴重なリソース) で並行ツリーに関する他の多くの論文を見つけることができるでしょう。ツリーはリバランスのために同時実行特性が低下する傾向があるため、本当に必要な場合を除き、ツリーを同時データ収集として使用することは避けます。多くの場合、スキップ リストなどのより実用的なアプローチの方がうまくいきます。

于 2009-03-17T02:49:32.917 に答える
0

通常、ロック自体がかなりのリソースを占有するため、データ構造全体に対して 1 つのロックが存在します。あなたがそれを避けようとしていることを考えると、これは非常に特殊なシナリオであり、多くの CPU 集中型のワーカー スレッドがツリーを絶えず更新している必要があると思いますか?

N ノードごとに 1 つのロックを共有することでバランスを取ることができます。ローテーション操作に入るとき、影響を受けるノードによって使用される一意のロックのセットを見つけます。ほとんどの場合、ロックは 1 つだけです。

于 2009-03-16T21:18:37.567 に答える
0

最適なソリューションはアプリケーションによって異なります。しかし、メモリ内データベースのようなものを持っていて、それを同時に更新し、非常にきめの細かいロックを行いたい場合は、バイナリ ツリーほど頻繁にノード ローテーションを必要としない B ツリーを調べることもできます。 . また、バランスを維持するためにより多くのローテーションを必要とする二分木とは異なり、それらは自動的にバランス調整されます (例: Splay ツリーまたは AVL ツリー)。

ツリーにトランザクショナルな変更を加えたい場合は、機能的な B ツリー (Thomas Danecker はこれを不変ツリーと呼んでいます) を使用できます。これらは一種の「コピー オン ライト」バイナリ ツリーであり、ロックする必要があるのはルート ノードだけです。したがって、必要なロックは 1 つだけです。また、関数バイナリ ツリーのすべての操作は O(log n) であり、ツリーを下るたびに同じ対数時間を費やすため、操作は実際にはバイナリ ツリーと同じ複雑さを持ちます。

ノードごとに 1 つのロックを持つことは、おそらく正しい解決策ではありません。

于 2009-03-17T00:28:23.147 に答える