GATE CSE 2015 | Set 3 | Question: 10

Question

Two processes $X$ and $Y$ need to access a critical section. Consider the following synchronization construct used by both the processes$$\begin{array}{|l|l|}\hline \text{Process X}  &  \text{Process Y}  \\ \hline  \text{/* other code for process X*/} & \text{/* other code for process Y */} \\  \text{while (true)} & \text{while (true)} \\ 
\text{\{} & \text{\{} \\
\quad\text{varP = true;} & \quad \text{varQ = true;} \\
\quad\text{while (varQ == true)} &\quad \text{while (varP == true)}\\ 
\quad\text{\{} & \quad\text{\{}  \\ 
\quad\quad\text{/* Critical Section */} & \quad\quad\text{/* Critical Section */} \\ 
\quad\quad\text{varP = false;} &\quad\quad \text{varQ = false;} \\
\quad\text{\}} & \quad\text{\}} \\
\text{\}} & \text{\}} \\
\text{/* other code for process X */} & \text{/* other code for process Y */}\\
\\ \hline  \end{array}$$

Here varP and varQ are shared variables and both are initialized to false. Which one of the following statements is true?

• A. The proposed solution prevents deadlock but fails to guarantee mutual exclusion
• B. The proposed solution guarantees mutual exclusion but fails to prevent deadlock
• C. The proposed solution guarantees mutual exclusion and prevents deadlock
• D. The proposed solution fails to prevent deadlock and fails to guarantee mutual exclusion

Comments

Assuming ; after while costs you a lot :(

---

All questions related to critical section & solution requirements(ME, Progress, Bounded waiting)

Operating System: GATE CSE 1987 | Question: 1-xvi

Operating System: GATE CSE 1996 | Question: 1.19, ISRO2008-61

Operating System: GATE CSE 2007 | Question: 58

Operating System: GATE CSE 2010 | Question: 23

Operating System: GATE CSE 2015 Set 3 | Question: 10

Operating System: GATE CSE 2016 Set 2 | Question: 48

Operating System: GATE IT 2007 | Question: 10

---

\[
\begin{array}{c|c}
\textbf{Process X} & \textbf{Process Y} \\ \hline
\begin{array}{l}
\texttt{/* other code for process X */}\\
\texttt{while (true)}\\
\texttt{\{}\\
\quad \texttt{varP = true;}\\
\quad \texttt{while (varQ == true);}\\
\quad \texttt{\{}\\
\qquad \texttt{/* Critical Section */}\\
\qquad \texttt{varP = false;}\\
\quad \texttt{\}}\\
\texttt{\}}\\
\texttt{/* other code for process X */}
\end{array}
&
\begin{array}{l}
\texttt{/* other code for process Y */}\\
\texttt{while (true)}\\
\texttt{\{}\\
\quad \texttt{varQ = true;}\\
\quad \texttt{while (varP == true);}\\
\quad \texttt{\{}\\
\qquad \texttt{/* Critical Section */}\\
\qquad \texttt{varQ = false;}\\
\quad \texttt{\}}\\
\texttt{\}}\\
\texttt{/* other code for process Y */}
\end{array}
\end{array}
\]

$\underline{option \ B:}$

would have been correct if this was the question instead, (i.e, while loops are busy waiting mechanism here)

Answer 1

When both processes try to enter critical section simultaneously, both are allowed to do so since both shared variables varP and varQ are true. So, clearly there is NO mutual exclusion. Also, deadlock is prevented because mutual exclusion is one of the necessary condition for deadlock to happen. Hence, answer is (A).

Comments

yes. You're right. In that case mutual exclusion is satisfied but there can be deadlock.

---

(;) AFTER THE WHILE MEANS----IT WILL GO TO INFINITE LOOP UNDER TRUE CONDITION

---

Last line :  "Also, deadlock is prevented because mutual exclusion is one of the conditions for deadlock to happen."

This statement seems to be wrong for me, For deadlock to happen we should have mutually exlusive resources, not any code like this.
It is like- if P1 holding some resource, and P2 wants them. then we can not share that resource with both of them at same time, here resource should be mutually exclusive (Non sharable).

I am intentinally making a Bad implementation for Critical Section-
See-

i=1; While(j==1); i=0; CS

j=1; While(i==1); j=0; CS

Here mutual exclusion is not gauranteed, if P1 executes entry section and resides in CS, now P2 can also enter into CS.
Still  processes may fall into deadlock, as value of i and j can be 1 at same time.

If in an implementation(code), you are allowing process to access simultaneously (No mutual excluaion) that doesnt mean they cant fall in deadlock.

---

in the first case the processes won't enter their respective loops .In the initial condition both the variables are false. and for the process to enter it's loop both the variables should be true.

consider process x for example. let's say it runs first . makes varp=true and then checks whether varQ is true or not.

varQ will become true only if process q runs and gets prempted before entering it's critial section.  because if process q runs . it makes the value of process q false on it's way out.

so in order for prcess p to run it needs process q to run and vice versa. thus both wait for each other to run . leading to deadlock.

about mutual exclusion both can be in their critial section if one is prempted before checking the condition of while loop.

---

@sachin in the above question suppose if mutual exclusive is satisfied then hm deadlock ko kaise check kr sakte h in jaise question m  plz tell me . is it any relation of deadlock with progress ??  i m in doubt

---

Sachin is right.

Because in deadlock prevention

to break mutual exclusion condition

we make resources shareable.

So, for deadlock, we need to have mutually exclusive resources and not code condition

---

If process P and Q both are getting 1 and cannot enter  in CS same time, So both are going for infinite wait. So, isnot it a cause to be deadlock in the system?

@Arjun Sir @Bikram Sir

---

@ srestha

There are 4 conditions for a system to be in deadlock, the first condition is Mutual exclusion. If one of them not hold then there is no deadlock.

So here clearly ME is not satisfied hence deadlock also not satisfied.

And If process P and Q both are getting 1 so both are keep looping then this is livelock where both P and Q are keep executing and wasting CPU cycle.

But see the code cnippet, there is no semicolon after while loop so that means P and Q are not looping indefinite times..so here is no deadlock.

---

yes, that I understood.

But I simply try to run the code to see there is any deadlock or not,

yes in while loop there is no ';' , if that is the issue, then we can say varP and varQ can go inside while loop together. that is why no ME, rt?

but is that portion code is correct? Because as per any algo we read , while must be with a semicolon so that varP or varQ can execute in a order.

If there is no semicolon , there is no order, how the code can execute. rt?

---

in while loop there is no ';' , if that is the issue, then we can say varP and varQ can go inside while loop together. that is why no ME, rt?

yes, right. varP and varQ can go inside CS at a same time.hence no ME .

generally if u see correct implementation of  peterson algo or dekker's algo, there is No semicolon after while() loop. see here https://en.wikipedia.org/wiki/Peterson%27s_algorithm  and here https://cs.stackexchange.com/questions/12621/contrasting-peterson-s-and-dekker-s-algorithms

see after while() loop there is NO semicolon exists.

---

if there is a "semicolon" after while() then ME is satisfied..

semicolon means order..it ensure no 2 process can enter into CS at same time ..

---

These are simple while loops executing their codes. Internal while loop if condition is true then executes else it will not.So it is not doing any kind of wait.So there is no chance of deadlock.

---

@Arjun sir for the same question you have made another answer 

https://gateoverflow.in/8405/gate2015-3_10

---

@Sireesha baggu

You gave the link to current question only?

---

In very sorry this is the link

https://gateoverflow.in/1256/gate2007-58

---

In the link you gave,there is a semicolon after inner while.So it will wait.Here its a simple while loop.There is no waiting

---

Bunded waiting:  After setting $VarQ$=$True$ by process $Y$ ,Process $X$ can run indefinite time without giving a chance to process $Y$, So bounded waiting is not satisfied.and here also process $Y$ can starve..so Starvation also possible

@ rahul sharma 5 ,what say ye?

---

Bounded waiting means there is a bound on number of processes. 

Here just two processes are given.Process X will get a chance after one process i.e Process Y and similar for process Y.

---

BW means there is Bound on number of times other processes (not needs to be distinct ) can enter their CS.

according to this Bounded waiting shuld not be satisfied here in this code.

---

Is it number of times or number of processes.Can you share source of your definition?

---

you can check "galvin chap-7"

Bounded waiting: there exists a bound on the number of times that othere processes are allowed to enter their critical section after a process has made a request to enter its critical section and before that request is granted

---

you are right!!! thanks

---

@VS, If VarQ==true && VarP==true ---> Process Y can also run

yes ,process Y can run but do you know after how many iteration of process X ,process Y will get a chance? No

if process X is running on  the CPU then without relinquishing on the CPU process X may wish to execute as many times as wants.may be 10 times and may be after 100 or 1000 no bound right?

so I think bounded waiting is not satisfied here.

---

@reena_kandari

I think you are considering in terms of CPU and all , but we talk about Entering critical section and not to which process CPU is allocated.

And why are you assuming we have just one Processing core , we could have a Multiprocessor system.

And if I think they way you are doing then we cannot even conclude that we have NO Mutual exclusion here because --> There is one CPU--->Only one process running-->Only one enters its CS-->ME

---

no @VS,I am considering all cases. single or multicore both.

here if process X can can continuously enter in CS every time even if process X shows interest to enter then bounded waiting is not satisfied.

---

@reena_kandari

What you want to say is not clear , can you please elaborate a bit.

---

@VS

bounded waiting is not satisfied here,

bounded waiting says-> "after one process say X requested its critical section by making some signal(for this qsn, making VarP=1), there should be bound on other process Y, executing its critical section and before process X get its critical section"

but see, in above qsn although process X has made request to enter CS by making VarP=1, despite of this process Y can execute its critical section unbounded no. of times, before allowing X to enter its CS.

and thus bounded waiting is not satisfied here.

---

@joshi_nitish

But, as soon as Process Y enters its critical section ,

VarQ==true && VarP==true ---> Process X can also enter its CS

---

@VS,

it doesn't matter whether X can enter its CS or not.

what matters is Y should not execute its CS unbounded no. of times at any cost after X has made request to enter its CS.

---

@joshi_nitish

I think you are right !

But, then what about starvation and progress ?

---

the above definition of bounded waiting also highly support,

"deadlock does not imply no bounded waiting"

see in presence of deadlock none of the two process(say X and Y) will ever get a chance to execute their CS, but then also bounded waiting might be satisfied according to its standard definition because,

if process X has requested its CS then process Y can execute its CS only bounded no. of times(say 2 or 3, because after it, process X and Y both will get struck in deadlock and Y can not further execute its CS)

---

@joshi_nitish

Yes , that's true, and this  "deadlock does not imply no bounded waiting" is more evident in one of the gate2016 questions, where there is deadlock and still bounded waiting is satisfied ! :)

But, then what about starvation and progress  in this question?

---

progression is not satisfied,

starvation is also possible.

---

@joshi_nitish

Why starvation is possible ?

---

One process here can execute long duration without giving chance to other.So starvation is possible here.

---

@joshi_nitish

Can you explain Why progress is not satisfied?

---

@DS maurya progress is not satisfied because even though critical section is empty and anyone of process wants to enter but it cant enter...as it need other process var variable to be intialized to true.. than only other process can enter.

For exmple: P wants to enter CS it needs varQ to be true..so you can say progress not satisfied.

Progress means no process should hinder any other process when it wants to enter and also when CS is empty and process wants to enter than it should enter freely.

---

lets assume both the process try to enter CS. initially varP=F, varQ=F

if both the process wants to enter CS, X sets varP=T and Y sets varQ=T

now both of them can't proceed as one waits for the other(trap condition is satisfied). hence deadlock occurs

how can option A be correct when deadlock can occur?

---

@aditi19

check this https://gateoverflow.in/243994/doubt-synchronization

---

oh i didn't notice the semi-colon

---

So finally conclusion is

(1)Mutual Exclusion is NOT satisfied

(2)Progress is not satisfied.: How

Consider first process X comes sets varP=true and gets preempted.

Process Y comes sets varQ=true, finds varP true, enters into loop and executes CS and sets varQ=false and preempted.

Process X resumes, finds while condition false and while loop is exited, now X preempted.

Process Y resumes, continues to execute while loop and varQ set to false, thereby process X never given a chance to enter into CS from the moment it's request was placed.

For more elaboration on definition of progress, please refer

https://stackoverflow.com/questions/33143779/what-is-progress-and-bounded-waiting-in-critical-section

(3)Starvation is PRESENT because process X never gets a chance to enter CS.(There is a possibility).

(4)Bounded waiting is not satisfied because between the time the process's X request is placed for CS and this request for CS is granted,there exists no finite number c such that $f(N)=c$, means you can say that after a constant number of processes execute CS, this process X's request for CS will be finally granted.

---

read the third comment from beginning written by @ sachin mittal

is that code contain deadlock or live lock?

---

@ Sachin Mittal 1 as described by you for deadlock we need shared resources. When deadlock occurs all processes are in blocked state and none of them with CPU. Here according to your code snippet it is a live lock where each process will get CPU but it will waste it(busy waiting). So yes if there is no ME, no chance of deadlock.

---

Can u derive how livelock is satisfying?

and also what is difference between livelock and bounded waiting in this question

---

@srestha not in question, the code which he has mentioned in his comment.

---

i m confused little bit  about the line given both are initalized to false  so we take varp and varq = false???   correct me if m i wrong

---

@Bikram sir. Thanks for the beautiful explanation!

---

Correct me if I am wrong .

Mutual Exclusion NOT Satisfied ==> No Deadlock Possible

Is the above statement always true ?

---

sir i think there is spin lock in this synchronization , but no deadlock . correct me if i im wrong . as when both variables are true and when x enters into cs then y cannot enter into cs and also now x will go in infinite loop.

---

@kashyaprparmer

Mutual Exclusion is one of the necessary conditions to occur deadlock. So if atleast one of the necessary conditions is not satisfied then there’ll be no deadlock.

---

@Sachin Mittal 1 sir i think bounded waiting is satisfied here bcz 

Bounded waiting: there exists a bound on the number of times that other processes are allowed to enter their critical section after a process has made a request to enter its critical section and before that request is granted.

Initially, varP and varQ are false. Let’s Process Y wants to enter the CS. So it makes varQ true. Preemption has occurred and Process X has been scheduled.  Process X wants to enter the CS and make varP true. Process Y has been scheduled. It also enter the CS. So, there exist a bound.

---

@samarpita

Initially, varP and varQ are false. Let’s Say Process Y wants to enter the CS. So it makes varQ =true and Suppose it gets preempted. X starts – goes in CS as Q = true – makes varP = false – Exits – again X tries to execute ( assume Y is  still preempted after making varQ = true) – makes varP = true – pass the while Condition – enters critical section again.

This can goes on infinite time, So No Bound on how many times X can execute after Y gets preempted at varQ = True. X can Request CPU infinite time and it will get the CPU always.

Therefore Bounded Waiting Not Satisfied.

But I’m not sure about Y getting preempted Indefinitely. @Arjun Sir, Is it possible that Y just being preempted indefinitely

---

@Harish Hatmode

yes correct unbounded waiting is there. 
My approach was if $X$ wants to enter in CS but the while condition is false and the process ends. We don't even execute $Y$ still its not letting $X$ to enter in CS.

Answer 2

the answer is A.. the main thing here to watch in question is that there is no semicolon after while loop. and so When both processes try to enter critical section simultaneously,both are allowed to do so since both shared variables varP and varQ are true. So, clearly there is NO mutual exclusion. Also,deadlock is prevented because mutual exclusion is one of the conditions for deadlock to happen. 

Comments

Nice !!!

I was considering semi-colon and got (B).I was shocked seeing A to be the correct one.

---

Select this as Best answer.

---

best answer..

---

For people Like me

 

Answer 3

With having context switch at every instance, we can see that at one time, both X and Y are in Critical section, and after one such iteration of the while loop either of X or Y depending on the order of context switches, one of them, will move out from The Critical section.

And only one of them will be there forever.

This clearly shows that initially, there was no mutual exclusion as we got one case where both P and Q were in the critical section.

 

There is essentially no deadlock

But there is no progress and no bounded waiting.

Answer 4

There will be dead lock, but mutual exclusion is satisfied.

suppose X executes and sets p to true then preempts,  now Y executes and sets q to true, now when Y goes to while statement it will loop forever, same happens with X.

Most answers are misinterpreting the definition of deadlock and misunderstanding the mutual exclusion condition of Deadlock characteristics with mutual exclusion of critical section.

The definition of Deadlock is :Deadlock - Wikipedia

Also if we find even a single case in which deadlock occurs then the solution is said to not prevent deadlock. 

Mutual exclusion in synchronization means only one process should enter cs, while mutual exclusion of deadlock characteristics is about a resource being owned by only a single process. Take printer for example, only one computer can use it at a time, so this ME can not always be dissatisfied. which now brings me to another point:

ME of synchronization is property that must be enforced by a solution, while ME of deadlock characteristics is a property that should be removed to prevent deadlock. Do you see the difference? in one case we need ME to be present while in another case we need it to go away.

Students are confusing Mutual exclusion in both cases, when working with semaphore mutual exclusion doesn’t have anything to do with deadlock, both are different. 

So answer is B

Comments

there is no ; after the while loop so both the process wont loop forever both will execute the cs hence there is no deadlock

Answer 5

There will be dead lock, but mutual exclusion is satisfied.

suppose X executes and sets p to true then preempts,  now Y executes and sets q to true, now when Y goes to while statement it will loop forever, same happens with X.

Most answers are misinterpreting the definition of deadlock and misunderstanding the mutual exclusion condition of Deadlock characteristics with mutual exclusion of critical section.

The definition of Deadlock is :Deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock.

Also if we find even a single case in which deadlock occurs then the solution is said to not prevent deadlock. 

Mutual exclusion in synchronization means only one process should enter cs, while mutual exclusion of deadlock characteristics is about a resouurce being owned by only a single process. Take printer for example, only one computer can use it at a time, so this ME can not alwasy be dissatisfied. which now brings me to another point:

ME of synchronization is property that must be enforced by a solution, while ME of deadlock characteristics is a property that should be removed to prevent deadlock. Do you see the difference? in one case we need ME to be present while in another case we need it to go away.

Students are confusing Mutual exclusion in both cases, when working with semaphore mutual exclusion doesn’t have anything to do with deadlock, both are different. 

So answer is B

Answer 6

pplease refer to this solutions