The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+26 votes

Consider the methods used by processes $P1$ and $P2$ for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables $S1$ and $S2$ are randomly assigned.

$$\begin{array}{|l|l|}\hline \textbf{Method used by P1} & \textbf{Method used by P2} \\ \hline \text{while (S1==S2);} & \text{while (S1!=S2);} \\ \text{Critical Section} & \text{Critical Section} \\ \text{S1=S2;} & \text{S2 = not(S1)} \\\hline \end{array}$$

Method used by P1 | Method used by P2 |
---|---|

while (S1==S2); Critical Section S1=S2; |
while (S1!=S2); Critical Section S2 = not(S1) |

Which one of the following statements describes the properties achieved?

- Mutual excusion but not progress
- Progress but not mutual exclusion
- Neither mutual exclusion nor progress
- Both mutual exclusion and progress

+52 votes

Best answer

Answer is (**A**)**.** In this mutual exclusion is satisfied,only one process can access the critical section at particular time but here progress will not satisfied because suppose when $s1=1$ and $s2=0$ and process p1 is not interested to enter into critical section but $p2$ want to enter critical section. $P2$ is not able to enter critical section in this as only when $p1$ finishes execution, then only $p2$ can enter (then only $s1 = s2$ condition be satisfied).

Progress will not be satisfied when any process which is not interested to enter into the critical section will not allow other interested process to enter into the critical section. When P1 wants to enter the critical section it might need to wait till P2 enters and leaves the critical section (or vice verse) which might never happen and hence progress condition is violated.

+5

Yes. When P1 wants to enter the critical section it might need to wait till P2 enters and leaves the critical section (or vice verse) which might never happen and hence progress condition is violated.

+2

So this means that if progress condition is satisfied between two processes p1 and p2_{, } and if p1 does not want to enter its critical section, and p2 want to enter its critical section every time , then p2 can enter the critical section infinite number of times... ryt ?

+8

"infinite" is not a good word here. P2 should be able to enter the critical section as many times as it wants as long as P1 is not interested to enter the critical section.

0

I don't think this answer is correct. Lets remove unnecessary use of word 'Interested'

P1: Enter when both are not equal

CS

Set both of them equal

P2: Enter when both are equal

CS

Set both not equal.

**When S1=1 & S2=0 **

here P1 will enter CS and By no way P2 can stop P1 from entering CS.

Hence Answer should be D

+12 votes

S1 | S2 | Chance to get into CS |
---|---|---|

1 | 1 | P-2 can enter the CS |

1 | 0 | P-1 can enter the CS |

0 | 1 | P-1 can enter the CS |

0 | 0 | P-2 can enter the CS |

When S-1=1 S-2 =1 then it is p-2 turn to get into CS but if it is busy in doing some other work outside the CS and if P-1 want to get into CS which is also outside the CS then P-2 going to stop P-1 getting into CS because it is P-2 Turns This is what the Definition of the Progress Which is not Guaranteed here .

Answer (A)

It can be easily observed that the Mutual Exclusion requirement is satisfied by the above solution, P1 can enter critical section only if S1 is not equal to S2, and P2 can enter critical section only if S1 is equal to S2.

Progress Requirement is not satisfied. Let us first see definition of Progress Requirement.
*Progress Requirement:* If no process is executing in its critical section and there exist some processes that wishes to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.

If P1 or P2 want to re-enter the critical section, then they cannot even if there is other process running in critical section.

+2 votes

Answer (a)

Explanation:

its the solution of strict alternation, in which execution will be either: P1P2P1P2...... or P2P1P2P1......

so

> Mutual exclusion is satisfied (As any instance only one process will be in C.S.)

> Progress not satisfied (beacuse alternation is used initially if S1=1, S2=0 and P1 do not want to enter in CS and P2 wants then also it have to wait)

> Bounded waiting satisfied as both process getting chance equally to enter into its C.S.)

so option a is correct match.

Explanation:

its the solution of strict alternation, in which execution will be either: P1P2P1P2...... or P2P1P2P1......

so

> Mutual exclusion is satisfied (As any instance only one process will be in C.S.)

> Progress not satisfied (beacuse alternation is used initially if S1=1, S2=0 and P1 do not want to enter in CS and P2 wants then also it have to wait)

> Bounded waiting satisfied as both process getting chance equally to enter into its C.S.)

so option a is correct match.

+1 vote

@Arjun sir , Can you please verify answer

I don't think this answer given by neha is correct. Lets remove unnecessary use of word 'Interested'

P1: Enter when both are not equal

CS

Set both of them equal

P2: Enter when both are equal

CS

Set both not equal.

**When S1=1 & S2=0 **

here P1 will enter CS and By no way P2 can stop P1 from entering CS.

Hence Answer should be D

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 584
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,109 questions

53,222 answers

184,631 comments

70,463 users