これは並行リフレッシャーの一種のためのものです...共有ツリーデータ構造のスレッド同期をどのように処理すればよいですか？
私はメモリ内に複数のアイテムがあり、リーフノードだけがアイテムを含み、リーフノードも簡単なシーケンシャルのリンクリストを形成すると想像します。アクセス。挿入と削除はほとんどの場合リーフノードにのみ影響しますが、ルートに伝播する可能性のあるプロセスでノードを分割またはマージする可能性があります。
私はシングルスレッドの実装をしています。このアップデートは、一種の事前計画アプローチに従っています。再帰は、ノードが変更する必要がある限り、リーフレベルからツリーをステップアップし、必要な変更を記述するリンクリスト（別の再帰でローカル変数をリンクする）を構築します。何が必要なのかを知ると、必要なすべてのノードを割り当てることができるかどうかをチェックし、再帰から脱落する前にこのプランを参照して必要な変更を適用するかどうかを確認できます。
この実装では、イテレータの更新を「維持」するため、イテレータは挿入/削除によって無効になりません。指定された項目が削除されていない限りです。同じノード内に挿入/削除すると、そのノードを指すイテレータが更新されます。
問題は、マルチスレッド化する必要があります。潜在的に多くの読者とライターを同時にサポートする必要があります。
結果として破損の恐れがない限り、複数の読者が同時に読み書きすることができます。だから、私は読んでも、単一のノードであっても、相互に排他的なアクセスを全く望んでいません。書くために、私は変更に必要なノードの最小数をロックしたい。もちろん、私はデッドロックを避けたい。
ありがたいことに、私が実際に行う必要があるものではありませんが、私は同時実行スキルを無視しているので、これは良い考えの実験のように思えます。
これは明らかにデータベースとファイルシステムが処理しなければならない問題の種類に似ているので、私はそのようなことについていくつか参考になるかもしれないと推測しています。
どうすればこのためのスレッド同期を処理できますか？私は、ノード上のミューテックスやセマフォの役割を漠然と見ることができますが、それらを扱うためにどのような戦略を使用しますか？
video
乾杯：
もう一つの戦略は、クリフをクリックして、（対象となるすべてのケースで、ステートマシン）ブロック解除ハッシュマップを実装する方法と同様の方法でブロック解除ツリー構造を実装することです更新での読み書きノードの混在。純粋に書いている意味では、トップダウン・ロックはデッドロック・センスにはなりませんが、ポジション（キーだけでなく）への挿入や削除では、最初にどのノードが影響を受けているかを調べ、リーフの項目からステップアップしますしたがって、読み取りロックはボトムアップ）。キー挿入物は、最初にトップダウン検索があります。一貫性があればボトムアップのロックが可能かもしれません。 – Steve314
ReadWriteLockについて - C++には標準の同期プリミティブはありませんが、多くの人が毎日非標準のものを使用しています。しかし、私が探しているのは、ReadWriteLockの実装方法です。私はちょうどそれを見てきました、そして、根底にある2つのロックは理にかなっています。 – Steve314
整合性のあるロック方向では、ロックを解除して正しい順序で再ロックし、次に確認、修復、または削除するために、実際には（実際には誤った順序でロックを取得する必要がある場合）ノードのロックが解除されたときに重要な変更があった場合は、更新計画を再実行します。ソフトウェアトランザクションメモリからアイデアを盗み出す何かが間違っていても、必ずしもあなたがそれを防ぐためにフープを飛び越えて行くという意味ではありません。確率が十分に低い場合は、それが起こったときに検出して修復/やり直すことができる限り、大きな問題ではありません。 – Steve314