0

これは私の次の試験のために提案された演習です。下部は、これまでに収集したものです。すべての建設的な意見を歓迎します。

   P1, P2 and P3 share three semaphores (x, y and z) each with 1 as initial value and three variables (a, b and c).

        P1:

        (1.1) wait(x);
        (1.2) a = a + 1;
        (1.3) wait(y);
        (1.4) b = b - a;
        (1.5) wait(z);
        (1.6) c = a + 2*b -c;
        (1.7) signal(z);
        (1.8) signal(y);
        (1.9) signal(x)


        Code for P2:

        (2.1) wait(y);
        (2.2) b = b*2;
        (2.3) wait(z);
        (2.4) c = c - b;
        (2.5) signal(y);
        (2.6) wait(x);
        (2.7) a = a + c;
        (2.8) signal(x);
        (2.9) signal(z)

        Code for P3:

        (3.1) wait(y);
        (3.2) b = b*2;
        (3.3) wait(z);
        (3.4) c = c - b;
        (3.5) signal(z);
        (3.6) signal(y);
        (3.7) wait(x);
        (3.8) a = a / 10;
        (3.9) signal(x)

    A. If P1 and P2 run concurrently on a computer with only a single CPU, is it possible for these two processes to get into a deadlock? If so, show one execution sequence of the code that results in the deadlock, and show how to revise P2 only (P1 is not changed) to prevent deadlock.

    B. If P1 and P3 are run concurrently on a computer with only a single CPU, is it possible for these two processes to get into a deadlock? If so, show one execution sequence of the code that results in the deadlock, and show how to revise P3 only (P1 is not changed) to prevent deadlock.

    The changes you make should not violate the mutual exclusion requirement on shared variable access.

A) デッドロックに陥ったときの例が何を意味するのかわかりませんか? 私には、1.3行目でyが-1になり、P2の2.5までロックが解除されないため、yがデッドロックを引き起こすように見えます。

これを解決するには、1.3 を 1.5 より下に移動する必要があります。これは、P2 で y がリリースされたときだからです。x を使用しても他の競合が発生するようですが、P2 を変更せずにこれを解決するために P1 を再配置する良い方法が何であるかはわかりません。

B) ここでは、1.3 (wait(y)) が 3.6 まで通知されないため、再び問題を引き起こしているようです。解決策は、それを1.6以降に移動することですか?

この演習を行うために、デッドロックとセマフォ プログラミングに関する Wiki のページを使用しようとしています。

4

1 に答える 1

1

ええと、例として最初のケースでは。

    Sequence                       Holds lock on
    (1.1) wait(x);                 P1 x,  P2 -
    (1.2) a = a + 1;               P1 x,  P2 -
    (2.1) wait(y);                 P1 x,  P2 y
    (2.2) b = b*2;                 P1 x,  P2 y
    (2.3) wait(z);                 P1 x,  P2 yz
    (2.4) c = c - b;               P1 x,  P2 yz
    (2.5) signal(y);               P1 x,  P2 z
    (2.6) wait(x);                 P1 x,  P2 z   - P2 locks waiting for x
    (1.3) wait(y);                 P1 xy, P2 z
    (1.4) b = b - a;               P1 xy, P2 z
    (1.5) wait(z);                 P1 xy, P2 z   - P1 locks waiting for z

たとえば、P1 と同じ順序 (y、z、x ではなく x、y、z) で P2 をロックすることで修正できます。相互排除のために本当に必要になる前に x をロックする必要があることを意味するかもしれませんが、デッドロックを防ぐことができます。

私が見る限り、P1 と P3 は相互にデッドロックすることはできません。なぜなら、P3 はシーケンス y、z (x、y、z シーケンスに従い、x のロックをスキップするだけ) でロックされてから、ロックを解放し、 x のみをロック/ロック解除します。

于 2013-10-24T19:06:38.053 に答える