The Gateway to Computer Science Excellence
+29 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
in Operating System by Veteran (105k points)
edited by | 5.1k views
In "method used by P2", the last line is S2 = not(S1). Please rectify.
Thanks for the correction :)
Is it an example of LIVELOCKed processes (where bounded waiting is satisfied but progress is not satisfied) ?
But here it is says that  process P1 and P2 for accessing their critical section 'whenever needed' doesn't that means P1 or P2 can function concurrently

3 Answers

+63 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.

by Active (4.1k points)
edited by
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.

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 ?

"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.
thanks !!!
@ arjun sir, what about bounded waiting?? will it be satisfied??

@ sushmita

Yes as there is strict alteration! so bounded wait is satisfied.

See this

yes, after completion of p1 there is no way other than p2 and vice-versa

@Arjun sir

if both the codes are placed in infinite loops,then progress is satisfied right?




how progress could be satisfied?

See, For this code, why progress not satisfied?

Because, Say P1 wants to enter CS and P2 doesnot want to enter CS.Now, say S1=0 and S2=1. So, P1 can enter CS, but at last line of code, S1=S2. That means P2 have to enter CS, though it is not interested. And P1 cannot enter CS before P2, though it is interested for CS. So, progress  not satisfied.

ME $\checkmark$

Progress $\times $

BW $\checkmark$ (1-Bounded)

Deadlock $\times$

Starvation $\times$
+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.

by Boss (45.4k points)
edited by
+2 votes
Answer (a)


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


> 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.
by Active (1.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,356 answers
105,250 users