2
$\begingroup$

I came across following problem:

Let two processes P1 and P2 are there:

+-----------------------+-----------------------+
| P1                    | P2                    |
| while(1)              | while(1)              |
| {                     | {                     |
|    //s1               |    //s3               |
|    //s2               |    //s4               |
|    //critical section |    //critical section |
|    signal(mutex1);    |    signal(mutex1);    |
|    signal(mutex2);    |    signal(mutex2);    |
| }                     | }                     |
+-----------------------+-----------------------+

Lets mutex1 and mutex2 both are initialized to 1. So in order to avoid deadlock s1, s2, s3 and s4 (respectively) will be replaced by
(A) wait(mutex2), wait(mutex1), wait(mutex1), wait(mutex2)
(B) wait(mutex1), wait(mutex2), wait(mutex2), wait(mutex1)
(C) wait(mutex1), wait(mutex2), wait(mutex2), wait(mutex2)
(D) wait(mutex1), wait(mutex2), wait(mutex1), wait(mutex2)

Doubt

Given solution is D, which I understood why. But I am guessing whether having two semaphores mutex1 and mutex2 serve any special purpose in above code? Does below single semaphore based programs achieve same as what is achieved by above code?

+-----------------------+-----------------------+
| P1                    | P2                    |
| while(1)              | while(1)              |
| {                     | {                     |
|    wait(mutex1);      |    wait(mutex1);      |
|    //critical section |    //critical section |
|    signal(mutex1);    |    signal(mutex1);    |
| }                     | }                     |
+-----------------------+-----------------------+
$\endgroup$
1
$\begingroup$

If only one semaphore is used to control the access to the critical section, it is not possible for deadlock to happen. That is why two semaphores are used in the problem statement since the problem is designed to, I assume, showcase deadlock.

A single-semaphore-based program can protect the critical section from concurrent access as well, as demonstrated by your program that uses a single semaphore.

However, some critical sections do require two or more semaphores to protect. Here is an example. There are only one fork and one knife. Each of the two diners must obtain both of them before entering the dining section. So there should one semaphore for the fork and another one for the knife. If the waiting operations of these two semaphores are not arranged in the same order for both diners, deadlock could happen. Note that one semaphore is not enough to deal with this situation correctly.

$\endgroup$
  • $\begingroup$ But that means if the requirement itself changes, then we might need both semaphores. But for given problem, if we select correct option D, then it wont add anything extra over single semaphore version, right? That is given no other explicit requirement, two semaphore version involve redundant semaphore, we can very well manage with single semaphore also, right? $\endgroup$ – anir Jul 17 at 13:30
  • 1
    $\begingroup$ Correct. You said it. I have said it, too. $\endgroup$ – Apass.Jack Jul 17 at 18:25
  • $\begingroup$ You correctly stated that "If the waiting operations of these two semaphores are not arranged in the same order for both diners, deadlock could happen." Just want to confirm possibly stupid thing: no such restriction exist on order of semaphores in which they are signaled, right? Can we come up with any problem that might require specific order of semaphores while signaling? $\endgroup$ – anir Jul 18 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.