edited by
17,629 views
45 votes
45 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}$$
Which one of the following statements describes the properties achieved?

  1. Mutual exclusion but not progress
  2. Progress but not mutual exclusion
  3. Neither mutual exclusion nor progress
  4. Both mutual exclusion and progress
edited by

5 Answers

Best answer
100 votes
100 votes

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.

edited by
14 votes
14 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.

edited by
3 votes
3 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.
Answer:

Related questions

61 votes
61 votes
6 answers
1
go_editor asked Sep 30, 2014
25,753 views
The following program consists of $3$ concurrent processes and $3$ binary semaphores. The semaphores are initialized as $S0=1, S1=0$ and $S2=0.$$$\begin{array}{|l|l|}\hli...
23 votes
23 votes
2 answers
3
41 votes
41 votes
2 answers
4