GATE IT 2005 | Question: 42

Question

Two concurrent processes $P1$ and $P2$ use four shared resources $R1, R2, R3$ and $R4$, as shown below.
$$\begin{array}{|l|l|}\hline \textbf{P1}  &  \textbf{P2}  \\  \text{Compute: } & \text{Compute;} \\ \text{Use R1;  } & \text{Use R1;} \\  \text{Use R2; } & \text{Use R2;}\\  \text{Use R3;   } & \text{Use R3;} \\  \text{Use R4;  } & \text{Use R4;} \\\hline \end{array}$$
Both processes are started at the same time, and each resource can be accessed by only one process at a time The following scheduling constraints exist between the access of resources by the processes:

• $P2$ must complete use of $R1$ before $P1$ gets access to $R1$.
• $P1$ must complete use of $R2$ before $P2$ gets access to $R2$.
• $P2$ must complete use of $R3$ before $P1$ gets access to $R3$.
• $P1$ must complete use of $R4$ before $P2$ gets access to $R4$.

There are no other scheduling constraints between the processes. If only binary semaphores are used to enforce the above scheduling constraints, what is the minimum number of binary semaphores needed?

• A. $1$
• B. $2$
• C. $3$
• D. $4$

Comments

https://www.geeksforgeeks.org/gate-gate-it-2005-question-42/

nice explanation

---

Use of resources is serial execution.

---

Inspired by best answer

 

Try to visualise

 

Answer 1

Here x1 and x2 are two semaphores and initialized to 0.

Process P1{                                                                                 Process P2{

p(x1)   // P1 cannot access resource R1                                  v(x1)  // up operation always success.

R1     //P1 access R1 after P2                                                   R1        // process P2 access R1.

v(x2)    // it allows everytime                                                     p(x2)    // again process P2 is blocked 

R2        // it access resource R2                                                 R2

p(x1)                                                                                            v(x1)

R3                                                                                                 R3

v(x2)                                                                                             p(x2)

R4                                                                                                 R4

}                                                                                                 }

Here first resource is accessed by Process P2 so P1 should be blocked by using semaphore.i.e) p(x1) and x1 =0.

whenever 2nd resource is first accessed by Process P1 so P2 should be blocked using semaphore.i.e) p(x2) and x2=0.

Repeat the same procedure for 'n' number of resources.

Here only two processes are present and they access the resources alternatively so 2 semaphore variables are sufficient .

Comments

what if after P2 incremented x1, after this P1 acquires  x1, both are in the critical section isn't it and also P1 can access R1 before P2 this answer needs modification

Answer 2

Lets take two semaphores A = 0 & B = 1.

Then the process execution flow would look something like this,

Now in the above flowchart both processes are running concurrently. All the lines have the following meaning:

Line1 ) wait() is implemented on both A and B. But since A=0 therefore the process P1 will be stuck & the control will reach to process P2 until A is not released. Now value of B = 0.

Line2 ) Since P2 is running therefore it will use the resource R1. P1 is still stuck at Line1.

Line3 ) Now P2 releases A and hence P1 also starts to run right from Line1. Value of A = 0.

Line4 ) Both processes are running simultaneously but P2 gets stuck at wait(B) since B = 0 (Just like P1 got stuck  at Line1). Till then P1 uses R1 & R2 and finally releases B. Value of B = 0 again.

Line5 ) P1 again gets stuck for A = 0 and P2 takes control and moves forward to use R2.

Line6 ) P2 is only running and using R3.

Line7 ) P2 releases A and hence P1 starts executing right from Line5. Value of A = 0 once again.

Line8 ) P1 finishes using R3 & R4 and P2 gets stuck at B since its value was 0. But at Line8 P1 releases B after which P2 moves ahead with execution. Value of B = 0.

Line9 ) P2 uses R4 and hence all resources get properly used by both the processes.

Line10 ) Since the value of B = 0, P2 ups the value of semaphore B to what it was before. Now value of A = 0, Value of B = 1.

Hence two semaphores got used.

 

Although I'm still trying to understand whether the use of exactly TWO semaphores would come to my mind intuitively in the exam or is it just a matter of practice.

 

Ref.https://www.geeksforgeeks.org/gate-gate-it-2005-question-42/

Answer 3

S=0,Q=0

P1                                                                        P2

V(S)	P(S)
P(Q)	R1
R1	V(Q)
R2	P(S)
V(S)	R2
P(Q)	R3
R3	V(Q)
R4	P(S)
V(S)	R4

ANSWER IS 2

Answer 4

I think it can be done by 1 semaphore . Let semaphore s=0 initially.

      P1               P2

Wait(S);

Use(R1) ;         Use(R1) ;

                        Signal(S);

                        Wait(S);

Use(R2);           Use(R2);

Signal(S);       

Wait(S);    

Use(R3);             Use(R3);

                         Signal(S);

                        Wait(S);

Use(R4);            Use(R4);

Signal(R4)          Signal(R4);

Comments

One problem is there:

P2:
Signal(S);
Wait(S);

P1:
Wait(S);

When P2 does signal, we can't be sure whether the waiting P1's wait succeed or the wait of the P2 succeed. 

---

Whoever starts the execution doesn't matter because S is initially 0 . So P1 at line 1 will be spin locked.  then when at line 3 after Signal(S) by P2 , P1 gets the access imidiately .

---

For that to happen there must be a condition that after each instruction by P2, P1 will try for the lock release and vice-verse. But that condition is not satisfied.

---

P2 use R1 and then give Signal and then preempt
P1 will use  R1,R2 and perform Signal which will make S=1 and then it continues to execute and performs Wait on S (making S=0) Use R3, Use R4 ... So the sequence is broken ..therefore we need atleast two semaphores!