# Designing solution to critical section problem with two semaphores vs single semaphore

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);    |
| }                     | }                     |
+-----------------------+-----------------------+


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.

• 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?
– anir
Jul 17 '19 at 13:30
• Correct. You said it. I have said it, too. Jul 17 '19 at 18:25
• 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?
– anir
Jul 18 '19 at 19:56