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) 我不确定他们何时会陷入僵局的例子是什么意思？对我来说，似乎 y 会导致死锁，因为第 1.3 行将导致 y 变为 -1，直到 P2 的 2.5 才会解锁。

为了解决这个问题，应该将 1.3 移到 1.5 以下，因为那是在 P2 中释放 y 的时候。看起来虽然与 x 会有其他冲突，但我不知道在不更改 P2 的情况下重新排列 P1 的好方法是什么。

B) 这里似乎 1.3 (wait(y)) 再次导致问题，因为它直到 3.6 才发出信号。那么解决方案是将其移至 1.6 之后？

我正在尝试使用 Wiki 的 Deadlock 和 Semaphore Programming 页面来做这个练习。

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 相同的顺序（x、y、z 而不是 y、z、x）锁定 P2 来修复。这可能意味着您必须在真正需要互斥之前锁定 x，但这会防止死锁。

据我所知，P1 和 P3 不能相互死锁，因为 P3 被锁定在 y,z 序列中（它遵循 x,y,z 序列，只是跳过 x 上的锁），然后释放锁并仅锁定/解锁 x。

于 2013-10-24T19:06:38.053 回答