CODEWITHSUNDEEP
processparallel-processingsemaphore
Heplar
Heplar

Reputation: 65

Sempahores and Deadlocks

This is an exercise that was suggested for my upcoming exam, the bottom is what I have gathered thus-far. All constructive input will be appreciated.

   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) I'm not sure what it means by an example of when they would get into a deadlock? To me, it appears that y will cause a deadlock because line 1.3 will cause y to become -1 an would not be unlocked until 2.5 of P2.

To resolve this, 1.3 should be moved below 1.5 because that is when y is released in P2. It looks like there will be other conflicts though with x, but I don't know what a good way to rearrange P1 would be to resolve this without changing P2.

B) Here it appears 1.3 (wait(y)) causes a problem again since it is not signaled until 3.6. The resolution would then be to move it to after 1.6?

I'm trying to use Wiki's pages on Deadlock and Semaphore Programming to do this exercise.

Upvotes: 0

Views: 162

Answers (1)

Joachim Isaksson
Joachim Isaksson

Reputation: 180927

Well, in the first case as an example;

    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

It could - for example - be fixed by locking P2 in the order same order as P1 (x, y, z instead of y, z, x). It may mean that you'll have to lock x before you really need to for mutual exclusion, but it will prevent deadlock.

As far as I can see, P1 and P3 can't mutually deadlock, since P3 is locked in the sequence y, z (which follows the x, y, z sequence, just skips the lock on x), then releases the locks and only locks/unlocks x.

Upvotes: 1

Related Questions