ルート、私が持っているものの子供と複数のロック

Question

簡易構造は次のとおりです。

• いくつかの単一の根
• 各ルートには、多くの（例えば100S）を持つ子ども

のユーザーは、ルートを更新することができます。情報、およびその他の操作は許可されてはならない（根の変更がすべての情報に影響を及ぼす可能性があるため）。

また、ユーザーは子供を操作することもできます（ルートが使用されていない場合はもちろんです）。たとえば、ユーザーは2人の子供を同じ時間に変更することができます。これは、各子供が独立しているため許可されています。

• 子どもたちが使用している、子供をロック：

  は、私は破損がないことを確認するために、このような構造でロックを必要とします。これにより、同じ時間に同じ子供に対して2つの操作が許可されることはありません。

• ルートが使用されている場合は、ルートをロックし、すべての子を使用します。これにより、ルートが更新されている間、すべての子に対する操作が禁止されます。ここで私を悩ます何

すべて子供をロックする必要がある - 分散ロックに多くのリクエストを送ることを意味分散システムで。

表示されない解決策はありますか？

Answer 1

あなたには2つのものがありません。まず、複数のスレッドが誰にも書き込みをしていない限り、ノードから同時に読み取ることは安全です。第2に、子ノードは、より小さいツリーのそれ自身のルートとして見ることができるので、リーフノードを除くすべてのノードに同じアルゴリズム/ソリューションを適用することができる。最初のものが最も重要です。

ツリー内のすべてのノードで読み取り/書き込みミューテックスを使用します。これにより、任意の数のプロセスを同時に読み取ることができます。また、1つのプロセスでいつでもノードに書き込むことができます。

を読むには：

1. 読み取りロックノードとすべての親のすべての方法を根本まで。
2. を読んでください。
3. すべての読み取りロックを解放します。
   1. 変更するノードの最小上界書き込みロック：書き込むに

   。ノード（および場合によってはその子ノード）を変更する場合は、そのノードを書き込みロックします。

4. ご変更
5. これは2人の兄弟が同時に変更されてもよいし、任意の数が読み込むことは同時に実行できることを意味

書き込みロックを解除します。しかし、読み込みコストは、各レベルでおよそ100人の子供がいるツリーに対して、O（log100（tree_height））読み取りロックを取得する必要があることです。あなたのツリーが巨大で、同じリーフノードへの読み書きが非常に多い場合を除き、本当の問題になることはまずありません。

これは、子がその親を変更できないことを前提としています。