multithreading - 一般的な再入可能ロックと概念とは何ですか?

Question

私はいつも混乱します。Reentrantがさまざまなコンテキストで何を意味するのか、誰か説明してくれませんか? そして、なぜ再入可能と非再入可能を使いたいのでしょうか?

pthread (posix) ロック プリミティブと言うと、それらは再入可能かどうか? それらを使用するときに避けるべき落とし穴は何ですか？

ミューテックスは再入可能ですか?

Answer 1

再入可能ロック

再入可能ロックは、プロセスがそれ自体をブロックすることなく、複数回ロックを要求できるロックです。すでにロックを取得しているかどうかを追跡するのが容易ではない状況で役立ちます。ロックが再入可能でない場合は、ロックを取得してから、再度取得しようとするとブロックされ、独自のプロセスが効果的にデッドロックされます。

一般に、再入可能性は、実行中にコードが呼び出された場合に破損する可能性がある中央の可変状態がないコードのプロパティです。このような呼び出しは、別のスレッドによって行われるか、コード自体からの実行パスによって再帰的に行われる可能性があります。

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

再入可能ロックの使用例

再入可能ロックのアプリケーションの (やや一般的で不自然な) 例は、次のようになります。

• グラフをトラバースするアルゴリズムを含む計算があります (おそらくサイクルを含む)。トラバーサルは、サイクルまたは同じノードへの複数のパスが原因で、同じノードを複数回訪問する場合があります。

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

• どのノードにアクセスしたかについての完全な情報を計算で保持できないか、「以前にここにいたことがあるか」という質問にすばやく答えることができないデータ構造を使用しています。
  
  この状況の例としては、バイナリ ヒープとして実装されたプライオリティ キューを使用したダイクストラのアルゴリズムの単純な実装、または単純なリンク リストをキューとして使用する幅優先検索があります。このような場合、既存の挿入のキューをスキャンするのは O(N) であり、反復ごとに実行したくない場合があります。

この状況では、既に取得したロックを追跡するのはコストがかかります。ノード レベルでロックを行いたい場合、再入可能なロック メカニズムにより、以前にノードにアクセスしたことがあるかどうかを確認する必要がなくなります。ノードをやみくもにロックできます。おそらく、ノードをキューからポップした後にロックを解除します。

再入可能ミューテックス

単純なミューテックスは、一度に 1 つのスレッドしかクリティカル セクションに存在できないため、再入可能ではありません。ミューテックスを取得してからもう一度取得しようとすると、単純なミューテックスには、以前に誰がそれを保持していたかを判断するのに十分な情報がありません。これを再帰的に行うには、各スレッドにトークンがあり、誰がミューテックスを取得したかがわかるようにするメカニズムが必要です。これにより、mutex メカニズムのコストがいくらか高くなるため、すべての状況で使用したくない場合があります。

IIRC POSIX スレッド API は、再入可能および非再入可能ミューテックスのオプションを提供します。

Answer 2

再入可能ロックを使用するとM、リソースにロックを設定し、再帰的に、または既にロックを保持しているコードからA呼び出すメソッドを作成できます。MA

非再入可能ロックでは、ロックするバージョンとMロックしないバージョンの の 2 つのバージョンと、正しいバージョンを呼び出すための追加のロジックが必要になります。

Answer 3

リエントラント ロックについては、このチュートリアルで詳しく説明しています。

チュートリアルの例は、グラフのトラバースに関する回答よりもはるかに工夫されていません。再入可能ロックは、非常に単純な場合に役立ちます。