3

R1という名前の5つの個別のリソースを持つコンピューターを考えてみましょう…。R5。5つのプロセスP1、…をしましょう。P5は、次のように順番にリクエストを行います。

i. P1 requests R2
ii. P4 requests R3
iii. P3 requests R1
iv. P2 requests R4
v. P5 requests R5
vi. P4 requests R2
vii. P5 requests R3
viii. P3 requests R5

R_iが現在使用可能な場合、プロセスP_iがR_iを取得するとします。

デッドロックはありますか？もしそうなら、それはどの時点で発生し、どのプロセスが関与しましたか？

誰か助けてくれませんか？最初のものについては、デッドロックはないと思っていましたが、証明する方法がわかりません。

ありがとう！

4

1 に答える 1

0

これが実際の一連のイベントであると仮定すると、そこにはデッドロックはありません。最初は、すべてのリソースが無料で、そのコードを順番に実行します。

1. P1 requests R2: p1 has r2.
2. P4 requests R3: p4 has r3.
3. P3 requests R1: p3 has r1.
4. P2 requests R4: p2 has r4.
5. P5 requests R5: p5 has r5.
6. P4 requests R2: p4 has r3, awaiting r2(p1).
7. P5 requests R3: p5 has r5, awaiting r3(p4).
8. P3 requests R5: p3 has r1, awaiting r5(p5).

したがって、現在の状態は次のとおりです。

p1 has r2.
p2 has r4.
p3 has r1, awaiting r5(p5).
p4 has r3, awaiting r2(p1).
p5 has r5, awaiting r3(p4).

待機のチェーンは (待機者 -> ブロッカー) です。

p4 -> p1, p5 -> p4, p3 -> p5

また：

p3 -> p5 -> p4 -> p1

そこにはサイクルがないため、デッドロックは発生していません。

非待機者にリソースを解放させ、一連のイベントに従うだけで、さらなる証拠を得ることができます。

 9. p1 releases r2, frees it up for p4 (p3 and p5 blocked, p4 has r3/r2).
10. p4 releases r3, frees it up for p5 (p3 blocked, p5 has r5/r3).
11. p5 releases r5, frees it up for p3 (nobody is blocked, p3 has r5).

これらの手順の後の最終的な状態は次のとおりです。

p1 has nothing.
p2 has r4.
p3 has r1/r5.
p4 has r2.
p5 has r3.

これでブロックはなくなり、各スレッドはまだ割り当てられているリソースを簡単に解放できます。

ここで、これらの操作が任意の順序で (各スレッド内の順序を維持しながら) 発生する可能性がある場合にデッドロックが発生する可能性があるかどうかを質問するように質問を拡張した場合、答えはまだノーです。

すべてのリソースがすべてのスレッドで同じ順序で割り当てられるようにすることで、デッドロックを回避できるというのがマルチスレッドの基本原則です。指定した操作から、個々のスレッドは次のようにリソースを割り当てます (スレッド内で順序を維持する必要があります)。

P1: R2
P2: R4
P3: R1 R5
P4: R3 R2
P5: R5 R3

では、それらがすべて同じ順序で割り当てられていることを確認するにはどうすればよいでしょうか? 一致するシーケンスを見つけるだけです。まず、上記のリストから始めますが、スペースを追加して、同様のリソースを並べ、別のリソースの両側にリソースがないようにします。

P1:             R2
P2: R4
P3:    R1 R5
P4:          R3 R2
P5:       R5 R3

    R4 R1 R5 R3 R2  <==

そして、あなたのシーケンスがあります。すべてのスレッドは、4、1、5、3、2 の順序でリソースを割り当てています。すべてのスレッドがすべてのリソースを割り当てるわけではありませんが、ここでは関係ありません。

また、これが唯一の解決策ではありません (R4 はスタンドアロンであるため、リストのどこにでも配置できます。他のすべてのリソースは単一の依存関係チェーン (1、5、3、2) に含まれているため、それらの相対位置は固定されています)。

ただし、すべてのスレッドが特定の順序でリソースを割り当てていることを証明するだけで十分であるため、デッドロックは発生しません。

于 2012-06-13T04:44:10.530 に答える