The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
3.3k views

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.

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?

  1. Mutual excusion but not progress
  2. Progress but not mutual exclusion
  3. Neither mutual exclusion nor progress
  4. Both mutual exclusion and progress
asked in Operating System by Veteran (101k points)
edited by | 3.3k views
+2
In "method used by P2", the last line is S2 = not(S1). Please rectify.
0
Thanks for the correction :)
0
Is it an example of LIVELOCKed processes (where bounded waiting is satisfied but progress is not satisfied) ?
0
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

4 Answers

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

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

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

@ sushmita

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

See this https://gateoverflow.in/39600/gate-2016-2-48

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

This might help ...

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 

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

answered by Boss (45.2k points)
edited by
+1 vote
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.
answered by Junior (803 points)
0 votes

@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 

answered by Active (1.8k points)
0
you are wrong here the definition of progress is when one process p wants to enter the critical section then no other process will stop p. Here in this case p1 doesn't want to execute critical section but p2 wants then tell me how can p2 get the chance? So that's why progress is not satisfied.
Answer:

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

39,530 questions
46,674 answers
139,829 comments
57,598 users