2

以下は私がインタビューで尋ねられた質問であり、この質問には多くの解決策があると思いますが、何が最善の解決策になるか知りたいです（そしてstackoverflowはこれに最適です:)）。

Q：ツリーのような構造で、3つのスレッドがあります。次に、挿入、削除、ルックアップの3つの操作を実行する必要があります。これをどのように設計しますか？

私のアプローチ：挿入または削除で一度に1つのスレッドのみを実行したいので、挿入および削除操作にミューテックスを使用します。ルックアップの場合、3つのスレッドすべてが関数に入るのを許可しますが、今回は挿入および削除操作を実行できないように、カウント（セマフォのカウント）を保持します。同様に、挿入または削除操作が実行されている場合、挿入および削除の場合と同様に、スレッドはルックアップを実行できません。

今、彼は私に一度に1つのスレッドしか挿入できないので、異なるリーフ上の2つのノードを挿入する必要がある場合でも、私のアプローチでは一度に1つのスレッドを許可するので、これは行き詰まっていると私に質問しました。

私のアプローチは大丈夫ですか？他のアプローチは何でしょうか？

4

1 に答える 1

3

こんな感じでいかがですか？通行止め（壊れた道）に似ています。

  • 各ノードには 2 つのフラグがあり、前方leftClear_fをrightClear_f示しますclear-path
  • ツリーの MutEx は 1 つだけです。

ルックアップ操作:

  • パス アヘッドが変更中であることを示すフラグが設定されている場合はconditional_wait、信号に到達して待機します。
  • 信号を取得したら、フラグを確認して続行します。

挿入操作

  • Lookup挿入位置までたどります。
  • MutEx を取得し、状態を確認した後、parent_nodeと 両方の関連するフラグを設定します。child_node
  • MutEx を解放して、他の有効な切れ目のないパスで並列Delete/が発生できるようにしますInsert
  • 挿入操作後に MutEx を取得し、parent_nodeおよびで関連するフラグを更新しますchild_node。

ノードを削除することを除いて、挿入操作 と同じ操作を削除します。

PS: ノードの詳細を維持したり、別の場所で処理しInsertたりすることもできDeleteます。必要に応じて、他の操作で壊れたパスをジャンプできます。複雑に聞こえますが、実行可能です。

于 2013-01-28T09:27:08.263 に答える