再入可能ミューテックス

コンピュータサイエンス において、再入可能ミューテックス（再帰ミューテックス、再帰ロック）は、デッドロックを引き起こすことなく、同じプロセス/スレッドによって複数回ロックできる特定のタイプの相互排他（ミューテックス）デバイスです。

通常のミューテックス (ロック) で「ロック」操作を実行しようとすると、ミューテックスがすでにロックされている場合は失敗するかブロックされますが、再帰ミューテックスでは、ロックしているスレッドがすでにロックを保持している場合にのみ、この操作は成功します。通常、再帰ミューテックスはロックされた回数を追跡し、他のスレッドがロックする前に、同じ回数のロック解除操作を実行する必要があります。

再帰ミューテックスは、通常のミューテックスの再入不可能性の問題を解決します。ロックを取得してコールバックを実行する関数自体がコールバックによって呼び出されると、デッドロックが発生します。^[1]疑似コードでは、次の状況になります。

var m : Mutex // 非再帰ミューテックス。最初はロック解除されています。

関数lock_and_call(i: 整数)
    m.ロック()
    コールバック(i)
    m.ロック解除()

関数コールバック(i:Integer)
     i > 0の場合
        ロックアンドコール(i - 1)

lock_and_call(1) // 関数の呼び出し

これらの定義により、関数呼び出しlock_and_call(1)は次の一連のイベントを引き起こします。

• m.lock() — ミューテックスがロックされている
• コールバック(1)
• lock_and_call(0) — i > 0なので
• m.lock() — デッドロック。m はすでにロックされているため、実行中のスレッドはブロックされ、自分自身を待機します。

ミューテックスを再帰的なものに置き換えると、最終的なm.lock() がブロックされずに成功する ので、問題は解決します。

W.リチャード・スティーブンスは、再帰ロックを正しく使用するのは「難しい」と指摘し、 APIを変更せずにシングルスレッドコードを適応させるために再帰ロックを使用することを推奨しているが、「他の解決策が不可能な場合のみ」としている。^[2]

Java言語のネイティブ同期メカニズムであるmonitor は、再帰ロックを使用します。構文的には、ロックは、その前に 'synchronized' キーワードがあり、括弧で囲まれたオブジェクト参照がミューテックスとして使用されるコードブロックです。同期ブロック内では、指定されたオブジェクトに対して wait()、notify()、またはnotifyAll() を実行することで、そのオブジェクトを条件変数として使用できます。したがって、すべてのオブジェクトは再帰ミューテックスと条件変数の両方です。^[3]

1. スレッドAは関数Fを呼び出し、関数Fは処理を進める前に再入可能ロックを取得します。
2. スレッドBは関数Fを呼び出し、関数Fは再入可能ロックを取得しようとしますが、すでに未処理のロックがあるために取得できず、ブロック（待機）または要求された場合はタイムアウトが発生します。
3. スレッド A の F は自分自身を再帰的に呼び出します。すでにロックを所有しているため、自分自身をブロックすることはありません (デッドロックはありません)。これが再入可能ミューテックスの中心的な考え方であり、通常のロックと異なる点です。
4. スレッドBのFはまだ待機中、またはタイムアウトをキャッチして回避しました
5. スレッドAのFが終了し、ロックを解除する
6. スレッドBのFは、再入可能ロックを取得して、まだ待機中であれば続行できるようになりました。

ソフトウェアエミュレーションは、次の構造を使用して実現できます^{[説明が必要] 。 [引用が必要]}

• 通常のロックを使用した「制御」条件
• 各スレッドに固有の所有者識別子（デフォルトは空/未設定）
• 取得数（デフォルトはゼロ）

1. 制御条件を取得します。
2. 所有者が設定されていて、現在のスレッドではない場合は、制御条件が通知されるまで待機します (これにより条件も解放されます)。
3. 現在のスレッドに所有者を設定します。取得者がすでに所有者でない限り、この時点で所有者識別子はすでにクリアされているはずです。
4. 取得数を増やします (新しい所有者の場合は常に 1 になります)。
5. 制御条件を解除します。

1. 所有者が解放者であると主張して、制御条件を取得します。
2. 取得カウントを減分し、カウントがゼロ以上であることを確認します。
3. 取得回数が0の場合は、所有者情報をクリアし、制御条件を通知します。
4. 制御条件を解除します。