edited by
12,409 views
61 votes
61 votes

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?

  1. $1$
  2. $2$
  3. $3$
  4. $4$
edited by

8 Answers

0 votes
0 votes

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 .

0 votes
0 votes

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/

0 votes
0 votes

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

–3 votes
–3 votes

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

Answer:

Related questions

75 votes
75 votes
11 answers
1