GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
165 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.
asked in Operating System by Active (1.8k points)   | 165 views
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...

 

@Bikram sir please help here.

stblue

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

2 Answers

+1 vote
Best answer

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 (39.3k points)  
edited ago by

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 ?

@Arjun please see this ..

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.

 stblue 

I have a question, please answer this ..

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.

ref :- https://en.wikibooks.org/wiki/Operating_System_Design/Concurrency/Livelock

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).

+1 vote
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 Active (2k points)  
reshown ago by

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. 

 

 

stblue

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

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

stblue

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 ?

i don't get what you want to say from your answers...

@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.



Top Users Aug 2017
  1. ABKUNDAN

    4670 Points

  2. Bikram

    4556 Points

  3. akash.dinkar12

    3420 Points

  4. rahul sharma 5

    3118 Points

  5. manu00x

    2864 Points

  6. makhdoom ghaya

    2450 Points

  7. just_bhavana

    2136 Points

  8. Tesla!

    2042 Points

  9. stblue

    1930 Points

  10. joshi_nitish

    1686 Points


24,969 questions
32,072 answers
74,565 comments
30,147 users