multithreading - 相互排除なしでデッドロックが発生する可能性はありますか?

Question

デッドロックに必要な条件の 1 つは相互排除であり、一度に 1 つのスレッドだけがロックを保持できるという話をよく耳にします。

しかし、ミューテックス以外のロックがデッドロックを引き起こす可能性があると考えるのは間違っていますか?

最大 2 つのスレッドが保持できるセマフォの単純なケースを考えてみましょう。A と B という 2 つの 2 セマフォがあるとします。プロセス A1、A2、B1、B2 の 4 つのプロセスがあるとします。

プロセス A1 と A2 がそれぞれセマフォ A をグラブし、プロセス B1 と B2 がセマフォ B をグラブするとします。A1 と A2 の両方がセマフォ B を必要とし、プロセス B1 と B2 の両方がセマフォ A を必要とするポイントに達した場合、それぞれが現在のロックを放棄することはありません。 、セマフォは 2 つのプロセスでしか保持できないため、デッドロックが発生します。しかし、セマフォでは 2 つのプロセスがそれを保持できるため、相互に排他的ではありません!

これが間違った推論なのか、それとも相互排除の私の解釈が間違っているのか、誰か説明してもらえますか?

Answer 1

あなたが説明したシナリオが、セマフォのカウントを使用してデッドロックにつながることは正しいです。から取られた相互排除条件

エイブラハム・シルバーシャッツ、ピーター・ベア・ガルビン、グレッグ・ガニア。2008. オペレーティング システムの概念 (第 7 版)。ワイリー出版。

言います:

少なくとも 1 つのリソースを非共有モードで保持する必要があります。つまり、一度に 1 つのプロセスだけがリソースを使用できます。別のプロセスがそのリソースを要求した場合、リソースが解放されるまで、要求しているプロセスを遅らせる必要があります。

矛盾しているように見えるものの解決策は、カウンティング セマフォが value1に達すると、セマフォ (またはセマフォが保護するリソース) が事実上共有不可になるため、その瞬間から既知の条件が適用されることです。別の言い方をすれば、システムの調査を開始するのが少し早すぎました。