[解決済み] Re-entrantロックとは何ですか？

質問

いつも混乱します。どなたか 再入可能 の意味を説明してもらえませんか？また、なぜリエントラントと非リエントラントを使い分けたいのでしょうか？

pthread (posix) のロックプリミティブはリエントラントですか、そうではありませんか？それらを使用するとき、どのような落とし穴を避けるべきですか？

mutex はリエントラントですか？

どのように解決するのですか？

再入可能なロック

リエントラントロックとは、あるプロセスが自分自身をブロックすることなく何度もロックを要求できるものです。 これは、すでにロックを取得したかどうかを追跡するのが容易でない状況で便利です。 ロックがリエントラントでない場合、ロックを取得し、再度取得しようとするとブロックされ、事実上自分のプロセスがデッドロックになる可能性があります。

一般に、リエントランシーは、コードが実行中に呼び出された場合に破損する可能性のある、中央で変更可能な状態を持たないコードの特性です。 そのような呼び出しは別のスレッドによって行われる可能性があり、また、コード自体の内部から発生する実行パスによって再帰的に行われる可能性もあります。

コードが実行の途中で更新される可能性のある共有状態に依存している場合、少なくともその更新がそれを破壊する可能性がある場合は、それは再入可能ではありません。

リエントラントロックのユースケース

リエントラントロックのアプリケーションの（やや一般的で作為的な）例としては、次のようなものが考えられます。

• グラフ (おそらくサイクルがある) を走査するアルゴリズムを含むいくつかの計算があります。 探索は、サイクルのため、または同じノードへの複数のパスのために、同じノードを複数回訪れるかもしれません。

• データ構造は同時アクセスの対象となり、おそらく別のスレッドによって、何らかの理由で更新される可能性があります。 競合状態による潜在的なデータ破損に対処するために、個々のノードをロックできる必要があります。 何らかの理由 (おそらくパフォーマンス) で、データ構造全体をグローバルにロックしたくありません。

• 計算が、どのノードに行ったかについての完全な情報を保持できない、または、「前にここに来たことがあるか」という質問に素早く答えられないようなデータ構造を使用している。
  
  
  
  この状況の例としては、バイナリ ヒープとして実装された優先順位キューを使用したダイクストラ アルゴリズムの単純な実装や、キューとして単純なリンク リストを使用した幅優先探索が挙げられます。 これらのケースでは、既存の挿入のためにキューをスキャンすることはO(N)であり、すべての反復でそれを行うことは望まないかもしれません。

このような状況では、すでに取得したロックを追跡することは高価です。 ノード レベルでロックを行いたいと仮定すると、リエントラント ロック機構により、以前にノードを訪問したかどうかを判断する必要性が軽減されます。 ただやみくもにノードをロックし、おそらくキューからそれをポップした後にロックを解除することができます。

リエントラントミュテックス

単純なミューテックスはリエントラントではありません。なぜなら、ある時点で1つのスレッドだけがクリティカルセクションに存在できるからです。 Mutex を取得し、それを再び取得しようとした場合、単純な Mutex は誰が以前それを保持していたかを知るのに十分な情報を持っていません。 これを再帰的に行うには、各スレッドがトークンを持ち、誰がミューテックスを取得したかを知ることができる仕組みが必要です。 このため、ミューテックス機構はやや高価になり、すべての状況でこれを実行したいとは思わないかもしれません。

POSIXスレッドAPIは、リエントラントおよび非リエントラントのミューテックスのオプションを提供しています。