+1 vote
282 views
Process P0:-                                                                                          Process P1

while(1)                                                                                                  while(1)

{                                                                                                             {

int[0]=True;                                                                                              int[1]=True;

while(int[1]==True);                                                                                 while(int[0]=True);

//CS//                                                                                                       //CS//

int[0]=False;                                                                                            int[1]=False;

}                                                                                                              }

Initially, int[0]=int[1]=false;

Will this algorithm satisfy bounded wait? According to me it should not.
bounded waiting is not satisfied here,

P0 can initially take control, and runs it code again again freely without giving P1 any chance to enter its code.
True, didn't think about this case is also possible ..@joshi_nitish that means P0 will always preempt p1 before statement  "  int[1]=True; " right ?
yes..
Bounded waiting condition says, a process should be able to enter a CS after REQUESTING FOR CS in a finite number of times.

In your case, you are considering that P1 is not at all requesting and P0 keeps on executing. You should consider P1 request also.
@Xylene

but here there is no bounded waiting..
Yes, there is no bounded waiting. But the reason is different and the not the one you said I guess.

@Xylene

bounded waiting is not satisfied if the same process can run again and again if it get chance to run again and again...

Here Bounded Waiting is not satisfied.

Only Mutual Exclusion is satisfied.

Progress also not satisfied and here is livelock exists.

A livelock is a special type of deadlock, where the affected processes are consuming (wasting) CPU cycles by looping forever.

Consider the following trace:

1. P0 sets state[0] to interested
2. A context-switch occurs
3. P1 sets state[1] to interested
4. P1 loops in while
5. A context-switch occurs
6. P0 loops in while

Both P0 and P1 loop forever. This is the livelock.

This scenario is happening here..

+1 vote

Consider process P0 .

Process P0:-
while(1)

{

int[0]=True;                      //   "I want to enter."

while(int[1]==True);         //   "If you want to enter and if it's your turn I don't want to enter any more."

//CS//                               //   Enter CS!

int[0]=False;                    //  "I don't want to enter any more."

}

so , this is the scenario. This  guarantee mutual exclusion .

And here is no deadlock here is Livelock . By looping again and again either p0 or p1 cause livelock here.

This satisfy Bounded waiting , as it is 2 process critical section problem so for process p0 , it enter into it's CS one time after that p1 enter , p1 request to enter in it's CS and before that request granted p0 enter one time hence BW =1 .

answered by Veteran (62.3k points) 14 142 566
edited by
True ! But livelock is a special type of deadlock
Yes, live lock is a kind of deadlock where  2 or more process wasting CPU cycles by looping forever and ever....
This is "deadlock" -- not livelock. And does a deadlock imply no bounded waiting? If we follow the definition of Galvin, NO.

Please check Algorithm number #3 here , both are same algorithm .

And does a deadlock imply no bounded waiting?

Deadlock is Not related with Bounded waiting.

Busywait is taken as livelock in it -- but anyway that is deadlock also.

Boundedwait is also given w.r.t time and as per that whenever there is a deadlock, BW won't be satisfied.

BW w.r.t time is not satisfied for this question.

BW e.r.t no. of processes entering CS is satisfied (Galvin defn).

@Arjun , please check my comment here http://gateoverflow.in/1256/gate2007-58?show=144861#c144860 . Even with respect to Galvin's definition bounded waiting is not satisfied.

BW w.r.t time is not satisfied for this question.

BW e.r.t no. of processes entering CS is satisfied (Galvin defn).

yes, I agree with you totally in this 2 lines.

Busywait is taken as livelock in it -- but anyway that is deadlock also.

yes, correct . Livelock is kind of deadlock . It is like busywait .. i agree completely.

But , definition of BW is given there in Galvin is  like this : " Bounded waiting says that a bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted".

--- This is your second statement and same given in this question..so if we follow Galvin definition there is NO Bounded wait .

Why there is no bounded wait here? Which processes are entering CS?

@Arjun

Please see, in this question , lets say for process P0 :

while(int[1]==True);   // see the semicolon after while loop()

This means when int[1]== true it will go infinite because the condition will always result true.

so that means P0 is enter into CS,  and looping again again  without giving P1 any chance to enter its code.

It is possible ..

same thing also can be happen with P1.

so that means there is NO bounded waiting ( in terms of Galvin definition ).

No, CS is from the next line after the loop for getting the lock. No process is getting to CS in the case of deadlock here.

No process is getting to CS in the case of deadlock here.

yes..the same i am also saying..if p1 not getting into CS and looping forever then how Bounded waiting is satisfied here ?

it is looping again and again in busywait ( or livelock, what ever you say both means same) so then how it ensure that for process P1 number of times P1 can enter into CS ? from definition of BW it just says there exists some bounds to enter in it's CS when a process apply so here after P1 apply if it looping forever then how that bounds satisfy here ?

We say bounded waiting is violate, when some process has requested for critical section and its waiting for its turn, now if this process is preempted by every other process (i.e there is no bound how many process will preempt, before our requested process will get its chance ), then bounded waiting is not satisfied.
In above code when deadlock happen, no process is preempting other and gets into critical section, infact no process is in critical section. So bounded waiting is satisfied.
Also i think bounded waiting is with respect to process not with time.

first of all BW says there is a bound ( means a specific number of times you can enter into your CS after apply and before grant ur application) [ Galvin definition ]

so here when P1 willing to enter into CS  by  making (int[0]=True;  )  and loop indefinitely ( due to "; " after while() loop ) then how many times it can enter into it's CS again before P2 enter into it's own(P2's)  CS ?

Here is the definition from Galvin, its says there should be bound on "Other Processes".

"means a specific number of times you can enter into your CS after apply and before grant ur application"

No it means there should be bound on other process, like this many number of process can enter before my application is granted.

Lets take a real life example, you have applied for passport, you reach to passport office next day and standing in queue, what you observe that other people are ignoring your presence and move ahead and do there work, this is the case where bounded waiting is not satisfied. Since you are waiting for you turn and never get your chance.

Now to solve this problem what people at passport office did is they issue a token number i.e before you this many people are allowed to get their work done. Suppose you got number 30, so you know that after 29 people you will definitely going to get your turn. i.e office people have put a bound with respect to other people, Here bounded waiting is satisfied.

Last case happen suppose you reach passport office, you have done your registration online and got token number as 30, you reach passport office you realize due to some reason office is close, here we say progress is not satisfied, but here bound still exist that before you only 29 other people are going to get chance.

In above case only 2 process are there, and the way code is implemented either none of the process will get a chance (deadlock situation) or there is boundation of 1 process before you get a chance.
And i believe in 2 process solution bounded waiting always satisfies

First of all the difference between livelock and deadlock is that: -

In Livelock, process state changes continuously which is in this case. Suppose, process P0 is in critical section, then process P1 will try to enter into critical section, but it will continuously executing the while loop.

when P0 context is switched to P1 then P0 states changes from Running to Ready (so, that it will come next time and execute the remainging work in the critical section when it gets the CPU). Now, P1 turn is came, and P1's states changed from Ready to Running, and in running state it is continously executing the while loop, now the P1's context switched to P0, P0's state changes from ready to running and P1's states changes from running to ready.

And this will continue untill P0 gets out of the critical section.

In Deadlock, process state not changes, if a process in block state then it will be in the block state only untill it brought into ready queue. Eg Semaphore, In semaphore if a process execute a wait operation on semaphore variable having value already 0. then its state changes from running to block state and remain block state. Until it is wake up.

Now Second thing, is that I think bound wait is satisfied here, because if P0 in critical section then after that P1 will definetly get chance when P0 execute int[0]=False;.

Because, if this is not the case the answer for http://gateoverflow.in/1256/gate2007-58?show=144861#c144860 should be (B).

It is a 2 process turn based solution, Here bounded waiting is satisfied.
The purpose of bounded waiting is that every process should get a chance to enter into critical section, such that no process should starve forever.
Suppose P1 wants to get into critical section, it will make int[1] = true, at this time it get preempted by P0 and P0 make int[0] = true, now both process stuck in while loop and deadlock will happen so progress will not satisfied.
However, Here we know one thing for sure, if deadlock never happen, both process will get chance  to use critical section, so here bounded waiting is satisfied.
answered by Boss (6.4k points) 3 12 32
reshown by
Consider a scenario where suppose P1 sets int[1]=true and enters the CS. Now it is preempted by P0.

Now, P0 wants to enter CS, so it sets int[0]=true and is preempted by P1.

Now P1 exits CS and sets int[1]=false. Again, P1 tries to enter CS and sets int[1]=true.

Now P0 can't enter in bounded amount of time. So it doesn't satisfy bounded wait I guess.
when P1 done executing the code,then two case happen
a) P0 will get a chance to execute, it will do while loop and enter into critical section.
b) P0 will get preempted again, and P1 make int[1] = true, now remember before preempting P0 made int[0] = true, so P1 will not pass while loop and so P0 will not pass while loop, so system will get into deadlock

now if (a) happen there is no problem, but if (b) happen then there is problem i.e System is in deadlock, This says progress is not satisfied.
What happen in case of bounded waiting is, suppose some process P0 want to enter into critical section, but some other process always preempt the process P0, so process P0 end up waiting all the time, this is the condition which we are intended to avoid in bounded waiting i.e there must be some bound before a process can get into critical section. Its done process level.
When you talk about deadlock, its happen at system level, here Process P0 cannot get into critical section, infact none of the process can get into critical section,because whole system is in deadlock, not because some other process continuously preempt P0 or some other process.
Therefore in case of deadlock, bounded waiting may satisfy, but progress cannot be satisfied.
edited my comment, read once if you get any doubt let me know.
I understand that deadlock doesnt always imply bounded waiting. Did you read my comment ? In that case P0 will not get access to critical after P1 enters 2nd time(or bounded) and ends up waiting indefinitely.
"Now, P0 wants to enter CS, so it sets int[0]=true and is preempted by P1.
Now P1 exits CS and sets int[1]=false. Again, P1 tries to enter CS and sets int[1]=true.
Now P0 can't enter in bounded amount of time. So it doesn't satisfy bounded wait I guess. "

When P1 tries to enter into critical section 2nd time, it will end up in deadlock. Since value of int[0] = true and value of int[1] = true, both get stuck at while loop. Here P1 is not preempting P0 every time and get a chance to enter into critical section.
Ya, deadlock happens and bounded waiting fails here in this case. If you see petersons solution, this doesn't happen.

There is No relation between deadlock and Bounded waiting.

While in deadlock BW is possible.

We consider deadlock for a system but BW is for a process.

Deadlock means no progress . There is no relation between progress and BW so there is no relation between BW and deadlock too.

@stblue is correct

It is a 2 process turn based solution, Here bounded waiting is satisfied.

Where you see turn  in this given code snippet ? It is not given here right ?

In Peterson's solution turn is used only . And this code is NOT Peterson's solution to critical section problem.. rather it is an incorrect solution !

The purpose of bounded waiting is that every process should get a chance to enter into critical section, such that no process should starve forever.

There is no relation between starvation and Bounded waiting .

BW +progress = no starvation

1) It is a 2 process turn based solution, Here bounded waiting is satisfied.

suppose process P0 wants to get into critical section, and it request for it, that means it certainly executed entry section code, in entry section we have only one statement i.e

int[0]=True;

and process P0, get stuck into while loop, when P1 completed its execution and it will make  int[1]=False, then P0 will defiantly get its turn to enter into critical section. Same goes for P1.
Also in above code we have remove the restriction that process should enter alternatively, any process who wants to enter can do so. Here we give freedom to process to decide for them self they want to enter into critical section.
But sir you are right, I should  not have written its 2 process turn based solution, it does give a wrong meaning that process are entering alternatively, which was not my intention while i was writing the answer.

2) The purpose of bounded waiting is that every process should get a chance to enter into critical section, such that no process should starve forever.

Suppose a system with n processes, and process p0 wants to enter into critical section, so he made a request, now every other process always preempt p0 and get into critical section, this happen because there is no bound for process p0, that before p0 how many process will enter into critical section or how much time it need to wait before it get his turn. That's why bounded waiting is not satisfied in this case, Since P0 is starving forever.

But in above case only 2 process are there, so here either they will get a chance to enter into critical section or they stuck with deadlock, which dissatisfy progress but not bounded waiting, Since here we have put a  bound that only 1 process can get into critical section, before our requested process get a chance to enter into critical section.

Sir correct me if i have made any mistake here.

yes here BW is satisfied . Thanks for your explanation..

I request if possible make your answer more concrete , although it is correct .

once you wrote

deadlock will happen so progress will not satisfied.

again you wrote

However, Here we know one thing for sure, if deadlock never happen, both process will get chance  to use critical section, so here bounded waiting is satisfied.

once u said deadlock happen again in next line u say deadlock is never happen ?

@Bikram Sir

is it not same as previous one?

Logically is there any difference between these two?

So, can we not say , that BW is satisfied here too and bound is 1.

@xylene

yes, when we follow Galvin definition of Bounded waiting, it satisfy BW in this question .

And that CMU link i gave , they refer BW based on time ( means no process should wait for a resource for infinite amount of time.)

But as in GATE like exam we follow standard books only we should go with Galvin definition ( means how many other process enter into CS before a particular process request to enter into it's CS and that request is granted ).

Also BW does not depends upon deadlock , not depends on progress, BW just says there is some bound exists .. so here in this question BW is satisfied as when p1 willing to enter it's CS by making

int[1]=True;  before that p0 enter into CS one time and after that p1 enter.

hence number of time a process enter into CS is 1 for requesting process p1.

+1 vote