The Gateway to Computer Science Excellence

+63 votes

Consider the following proposed solution for the critical section problem. There are $n$ processes : $P_0....P_{n-1}$. In the code, function $\text{pmax}$ returns an integer not smaller than any of its arguments .For all $i,t[i]$ is initialized to zero.

Code for $P_i$;

do { c[i]=1; t[i]= pmax (t[0],....,t[n-1])+1; c[i]=0; for every j != i in {0,....,n-1} { while (c[j]); while (t[j] != 0 && t[j] <=t[i]); } Critical Section; t[i]=0; Remainder Section; } while (true);

Which of the following is TRUE about the above solution?

- At most one process can be in the critical section at any time
- The bounded wait condition is satisfied
- The progress condition is satisfied
- It cannot cause a deadlock

0

I think if we can make $pmax$ a atomic instruction then above code could be used for n process synchronization.

Please correct if i am wrong.

Please correct if i am wrong.

0

Yes its possible that two process can have same t[i] value in that situation tie will be break by process id (value of i)

i.e. lower value of i will be given higher priority.

i.e. lower value of i will be given higher priority.

0

why you are saying BW isn't satisfy?

what is the reason behind it ? post it clearly and post the definition of BW which you followed ?

0

I was confused reading multitude of reasoning over BW. Let me tell my conviction after going through threads sprawling hither and tither. The reason this solution doesn't satisfy BW because for a same process, say $P_1$ to acquire CS again there is no bound. In fact, the process can join the deadlocked system.

@Shaikh

@Shaikh

0

You mean, let P1 enters, now P2 come but it can't enter... Now P1 completes it's execution.. and again want to go into the CS..

Now P1 can enters ===> BW not satisfied

Is this your reason?

Now P1 can enters ===> BW not satisfied

Is this your reason?

0

I mean there exists a process which can't get CS second time is starvation which is reason of not BW.

0

Also it seems to me a process attempting to get CS second time can be surpassed quickly by other processes before c[] making presence of unbounded number of processes before 2nd attempt, which is nothing but starvation. So, no BW. Right?

0

I mean there exists a process which can't get CS second time is starvation which is reason of not BW.

I agree there may be starvation, but how can you conclude it is not BW based on the starvation?

By the way it is satisfied BW., Read the answer given by Arjun sir

0

Suppose there is a series which wont put the system in deadlock, then still for that series starvation won't imply no BW? I think it will imply then, because we say starvation doesn't imply no BW because in a deadlocked system can satisfy BW. In other words,

In absence of deadlock, does starvation imply no Bounded Waiting?

0

Okay, leave it for few days. you put the reply, will restart it after couple of days. Have more points to say...

0

did you read the comments before commenting ?

check the link which is provided in my previous comment !

+59 votes

Best answer

Answer is (**A**).

while (t[j] != 0 && t[j] <=t[i]);

This ensures that when a process $i$ reaches Critical Section, all processes $j$ which started before it must have its $t[j] = 0$. This means no two process can be in critical section at same time as one of them must be started earlier.

returns an integer not smaller

is the issue here for deadlock. This means two processes can have same $t$ value and hence

while (t[j] != 0 && t[j] <=t[i]);

can go to infinite wait. ($t[j] == t[i]$). Starvation is also possible as there is nothing to ensure that a request is granted in a timed manner. But bounded waiting (as defined in Galvin) is guaranteed here as when a process $i$ starts and gets $t[i]$ value, no new process can enter critical section before $i$ (as their $t$ value will be higher) and this ensures that access to critical section is granted only to a finite number of processes (those which started before) before eventually process $i$ gets access.

But in some places bounded waiting is defined as finite waiting (see one here from CMU) and since deadlock is possible here, bounded waiting is not guaranteed as per that definition.

+1

I also agree with Bikram sir.

Starvation does not lead to deadlock and there is no relation between Bounded waiting and Deadlock.

Starvation does not lead to deadlock and there is no relation between Bounded waiting and Deadlock.

0

Sir, we can get t[i] of two process same ONLY IN THE CASE when,

t[i]= pmax (t[0],....,t[n-1])+1

of a process is preempted and

if we modify above statement with

P(s)

t[i]= pmax (t[0],....,t[n-1])+1

V(s)

where s is any binary semaphore with initial value of 1, then we can never have deadlock.

m i right or wrong?

Is there any other case when the two process can have same value for their t[i]??

'

+1

what definition of Bounded wait are we supposed to use in exam? Bound on number of turns or " No process waits forever"??

+2

Bound on number of turns.....i.e. if one process waits infinitely but other process/processes are allowed to enter CS, then its bounded wait voilation.

If all processes wait for a resource infinitely, then it deadlock and not unbounded wait.

If all processes wait for a resource infinitely, then it deadlock and not unbounded wait.

0

@Sushmita

Bounded wait does not have ambiguous meaning ..

it have only one meaning that is " Bound on number of turns ", it means if a process P wants to enter into it's CS then there are some number of turns( **read it as number of Bounds - it have some Upper Bound)** it have to enter into CS.

Here number of turns means Number of times P can enter into it's Critical Section .

Like i can go to Library 5 times in a day, that 5 is my BW to go to Library . If it is 6 then i can not enter into the Library.

Hope it is clear.

No process waits forever is the effect of BW, not the definition itself !!

0

yeah now its clear. Actualy that case of deadlock confused me. But now clear. Thanx again. Well this is such a question. Very conceptual.

0

I think @Sushant Gokhale has given the correct explanation for No Bounded Waiting i.e wrapping up of the integer value.

+3

we say not satisfying bounded waiting means starvation??

No. It does not simple like that .

Bounded-Waiting does not say if a process can actually enter. It only says there is a bound.

For example, all processes are locked up in the enter section (i.e., failure of Progress).

**We need Progress + Bounded-Waiting to imply Starvation-Freedom .**

So , all it means Starvation freedom **does not **satisfy Bounded Waiting .

0

Progress is related to starvation..there is no progress means starvation possible (long waiting == starvation )

Progress and Bounded Waiting are independent means not related to each other .

so we can say BW and starvation is not related .

Hence your assumption " not satisfying bounded waiting means starvation? " is not correct as there is no relation holds between BW and starvation.

+2

Here 2 lines are missing with original bakery algorithm. And that must make some difference in answering this question

Entering[i] = true;//missing in question Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]); Entering[i] = false;//missing in question for (integer j = 1; j <= NUM_THREADS; j++) { while (Entering[j]) { /* nothing */ } while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ } } <Critical Section> Number[i] = 0;

for loop executing one time, then where is wrap around condition here?

+1

@srestha mam

for loop executing one time, has nothing to do with wrap around condition beacuse the wraparound is happening for the array contents of t[] or if we consider the snapshot of bakery algorithm provided by you , in the array Number[]

PS: Keeping in mind the comments of Sushant Gokhale sir.

0

@VS

yes , thank u :)

but still can we assume 2 process could get same id? So, deadlock satisfied?

In question it is given there are n processes P_{0} to P_{n-1}

So, every process should be distinct. rt?

0

@arjun sir @srestha.How is it possible for two process to have same t[i]? Are we assuming that after calling pmax a process is preempted and then some other process can get same pmax?

+3

Deadlock => No progress.

Assume that I have two process P1 and P2.And both gets same t[i] value.(I dont know how they will get.But it is mentioned.May be because after pmax P1 is prempted and P2 comes and get same pmax)

Now both will stuck at while loop.And critical section is free and the two processes are trying to enter but no-one will ever get a chance.So progress not satisfied

In simple, Deadlock => No progress always holds

Assume that I have two process P1 and P2.And both gets same t[i] value.(I dont know how they will get.But it is mentioned.May be because after pmax P1 is prempted and P2 comes and get same pmax)

Now both will stuck at while loop.And critical section is free and the two processes are trying to enter but no-one will ever get a chance.So progress not satisfied

In simple, Deadlock => No progress always holds

0

How to decide atomicity, if an expression is c = a + b would this be atomic or addition and assignment would be considered seperately?

+35 votes

Given question is a wrongly modified version of actual bakery algorithm, used for N-process critical section problem.

Bakery algorithm code goes as follows : (as in William stalling book page 209, 7th edition)

Entering[i] = true; Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]); Entering[i] = false; for (integer j = 1; j <= NUM_THREADS; j++) { // Wait until thread j receives its number: while (Entering[j]) { /* nothing */ } // Wait until all threads with smaller numbers or with the same // number, but with higher priority, finish their work: while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ } } <Critical Section> Number[i] = 0; /*remainder section */

The important point here is that due to lack of atomicity of `max`

function multiple processes may calculate the same `Number.`

In that situation to choose between two processes, we prioritize the lower `process_id.`

`(Number[j], j) < (Number[i], i)) `

this is a tuple comparison and it allows us to correctly select only one process out of `i`

` `

and `j`

.but not both (when `Number[i] = Number[j] `

)

*Progress and Deadlock:*

The testing condition given in the question is `while (t[j] != 0 && t[j] <=t[i]);`

which creates deadlock for both `i`

and `j`

( and possibly more) processes which have calculated their Numbers as the same value. C and D are wrong.

*Bounded waiting :*

If the process `i `

is waiting and looping inside the for loop. Why is it waiting there ? Two reasons,

- Its number value is not yet the minimum positive value.
- Or, its Number value is equal to some other's Number value.

Reason1 does not dissatisfy bounded waiting , because if the process `i `

has the Number value = 5 then all processes having less positive `Number`

will enter CS first and will exit. Then Process `i `

will definitely get a chance to enter into CS.

Reason2 dissatisfy bounded waiting because assume process 3 and 4 are fighting with the equal Number value of 5. whenever one of them (say 4) is scheduled by the short term scheduler to the CPU, it goes on looping on $Number[3] \Leftarrow Number[4]$ .Similarly with process 3 also. But when they are removed from the Running state by the scheduler , other processes may continue normal operation. So for process 3 and 4 although they have requested very early, because of their own reason, other processes are getting a chance of entering into CS. B is wrong.

note : in this all the processes go into deadlock anyway after a while.

*How mutual exclusion is satisfied ?*

Now we assume all processes calculate their Number value as distinct.

And categorize all concurrent N processes into three groups;

- Processes which are now testing the while condition inside the for loop.
- Processes which are now in the reminder section.
- Processes which are now about to calculate its Number values.

In *Category 1, *assume process `i `

wins the testing condition, that means no one else can win the test because `i `

has the lowest positive value among the 1st category of processes.

*Category 3* processes will calculate Number value more than the Number of `i `

using `max`

the function.

Same goes with *Category 2* processes if they ever try to re-enter.

**detail of bakery algorithm** Link1 and Link2 and Link3_page53

0

note : in this all the processes go into deadlock anyway after a while.

That means we do have a **BOUND** rt? I mean there cannot be an unbounded sequnce of processes getting access to CS.

0

Yes sir I deliberately avoided indefinitely word there. Here bounded waiting and deadlock seems to be arising from the same reason.

0

i did nt understand your point of bounded waiting.how is it not satisfied.if possible,can you explain it more??

Thankyou

Thankyou

0

I should not argue on bounded waiting after so much of discussion. You please see others comments and answers. specially of @ArjunSir and @Sushant Gokhale.

+20 votes

1.do { 2. c[i]=1; 3.t[i]= pmax (t[0],....,t[n-1])+1;4. c[i]=0; 5. for every j != i in {0,....,n-1} { 6. while (c[j]); 7. while (t[j] != 0 && t[j] <=t[i]); 8. } 9. Critical Section; 10. t[i]=0; 11. Remainder Section; 12.} while (true);

The above code is N process synchronization solution (Lamport's bakery algorithm)

For detailed information on it , I'd request you to please refer below link and then come to this question.It'd really help you to understand the algorithm in detail and then the below solution would become very trivial.

https://www.youtube.com/watch?v=3pUScfud9Sg

Lines 2-4 can be termed as doorway for getting the token number. Each process which wants to enter into Critical section, gets a token number similar to restaurant system and wait for his token to be announced.

2. c[i]=1; //announce that process Pi is now ready to take it's token number

3. ** t[i]= pmax (t[0],....,t[n-1])+1; //get token number**

This line 3, can be further decomposed as

(a)LOAD R1 MAX[0..N-1] where max[0..n-1] is the same function which returns max of t[0..n-1]

(b) INCR R1

(c) STORE t[i]

4. c[i]=0; //announce that process Pi has taken it's token number.

Now consider a scenario when processes P1, P2 P3 and P4 want to enter critical section

now since in question, there is no way indicated that line 3 is atomic, two or more processes may get same token value.

So when P1, P2 , P3 and P4 want to enter say

below is an instance of array t[i] for the above processes.

P1 | P2 | P3 | P4 |

0 | 1 |
1 |
1 |

As you can see, processes P2, P3 and P4 have got same t[i] value because line 3 was not atomic in nature.

Suppose their respective C[i] values are all zero as of now,

then

Say P2 wanted to enter C.S. so it executed below line

while (t[j] != 0 && t[j] <=t[i]);

Now for J!=i, P2 scans for processes P1,P3 and P4 and checks if one any one of them would have it's timestamp less than or equal to it's own timestamp or token value.

P2 finds this to be true and loops at this condition.

Similarly processes P3, and P4 keep looping at while condition.

Suppose now P1 wants to enter C.S. and now t[i] array is as follows

P1 | P2 | P3 | P4 |

2 |
1 |
1 |
1 |

P1 gets a timestamp value of 2.

Now when P1 gets to execute line number 7

**while (t[j] != 0 && t[j] <=t[i]);**

it finds that all other processes have their timestamp non-zero and have value less than that of token of P1, so P1 also waits.

As, we can see now a deadlock is created. No process will now be able to proceed.

Hence option (d) is ruled out.

**When there is deadlock possibility, progress is definitely not satisfied, because progress states that in a finite amount of time decision must be taken which process will get to execute CS next.**

**When a deadlock is present, bounded waiting may or may not be satisfied.**

Good Read on the above point is : https://cs.stackexchange.com/questions/63730/how-to-satisfy-bounded-waiting-in-case-of-deadlock

Let's examine case of bounded waiting here.

Consider we have 4 processes and they have been assigned timestamp as below

$P_0$ | $P_1$ | $P_2$ | $P_3$ |

1 | 2 | 3 | 3 |

Now, process $P_0$ and $P_1$ will get chance to execute CS, and after they complete the $t[i]$ values are as under:

$P_0$ | $P_1$ | $P_2$ | $P_3$ |

0 | 0 | 3 | 3 |

Now, process $P_2$ and $P_3$ would keep looping in while loop and never get to execute CS.

Now, consider a scenario where we have 7 processes which have been assigned t[i] values as under

$P_0$ | $P_1$ | $P_2$ | $P_3$ | $P_4$ | $P_5$ | $P_5$ |

1 | 2 | 3 | 4 | 5 | 6 | 6 |

Now, processes $P_0,P_1,P_2,P_3,P_4$ will get to execute CS but $P_5,P_6$ won't get a chance to execute CS.

Similarly another scenario can be there where some processes are allowed into CS, who have got distinct t[i] values and the processes with the same t[i] values(say t[i]=k) and the processes having t[i] values greater than the k, won't get a chance to execute CS.

Now I ask you this question. Since this code is a solution for "N" processes, **is your "K" bounded**?

And bounded waiting says that **there exist ****a bound** on the number of times that other processes are allowed entry into CS between the time the process placed its request for CS and the time the request for CS is finally granted.

Does, your code guarantee that under any circumstances, **for a constant k** , after k processes execute finally process $P_i$ would get a chance to get into CS?

The answer is **NO**. K is variable here and not constant.K depends on the moment when two or more processes take the same t[i] value.

So, Bounded waiting is **NOT Satisfied**.

Now let's prove option (a)

Consider that again we have four processes and below is their token value

P1 | P2 | P3 | P4 |

0 | 1 |
0 |
0 |

Suppose only now P2 wants to enter C.S. so, it gets its token value as 1.

When P2, executes line number 7, it succeeds as no other process has t[i] non-zero.

P2 enters into C.S.

Now suppose P2 is executing in C.S. and it is preempted.

P3 now wants to enter C.S. and gets it token

P1 | P2 | P3 | P4 |

0 | 1 |
2 |
0 |

When P3 will execute line number 7, it will find that process P2 has it's token value non-zero and it is less than it's own token value(1<2). So, P3 will now wait.

**Hence, Mutual Exclusion is satisfied.**

**Answer- Option (a)**

0

@Bikram sir

When there is deadlock possibility, bounded waiting and progress cannot be satisfied. Is it always True ?

When there is deadlock possibility, bounded waiting and progress cannot be satisfied. Is it always True ?

0

Now consider a scenario when processes P1, P2 P3 and P4 want to enter critical section

now since in question, there is no way indicated that line 3 is atomic, two or more processes may get same token value.

So when P1, P2 , P3 and P4 want to enter say

below is an instance of array t[i] for the above processes.

P1 P2 P3 P4 0 1 1 1 As you can see, processes P2, P3 and P4 have got same t[i] value because line 3 was not atomic in nature.

**@Ayush Upadhyaya At what line the preemption should happen in order for P2,P3,P4 to get same t[i] value?**

0

@Ayush

good one

Where is it's main difference with original bakery algo?

Can u tell me in code part which is it's main difference with original bakery?

+1

@srestha-

in the line

while (t[j] != 0 && t[j] <=t[i]);

Which should be replaced by

while (t[j] != 0 && (t[j],j)<(t[i],i));

Which compares like this

If two processes, say $P_i$ and $P_j$ have timestamps $t[i]$ and $t[j]$, then

(a)If they have distinct timestamps, the process with the smaller timestamp is allowed to go into CS.

(b)If they have the same timestamp, then the process with the lower process number gets to execute CS.

So, in both case, bounded waiting is ensured in the original bakery algorithm.

I'd recommend you to watch the video(link mentioned in answer), so you'll understand it much much better :)

0

I am taking an example

Say there are 4 processes $P_{0},P_{1},P_{2},P_{3},P_{4}$

Now, check the question. there are $4$ variables according to the question

$t\left [ i \right ],t\left [ j \right ],c\left [ i \right ],c\left [ j \right ]$ [Assume $ t[x]$ means $token[x]$ and $c[x]$ means $choose[x]$ ]

So, we are thinking token and process same for this question, otherwise this question cannot be solved

right?

Now, I am defining each step of program

2.c[i]=1;

Here in this step we take another array $c[i]$ or $choose[i]$

Now say value of choose array will be like this , which just acting as a flag

it just taking arbitrary value

------------------------------------------------------------------------------------------------------------------------------------

Now, say $i=0$

According to 1st line of program make $c[0]=1$

Now 2nd line making the token array

and it adding $1$ to each maximum value of token

array will be like this

Now execute 3rd statement of array ,i.e.

c[i]=0;

means $choose[0]=0$

upto this corrct?

Now, in next comment I am writing next part of code

0

Now, take $i=0,j=0$

for every j != i in {0,....,n-1} {

Here $j!=i$ not satisfying

So, $token[0]$ or $P_{0}$ going inside C.S,

So, $C.S.::$ contains $P_{0}$

------------------------------------------------------------------------------------------------------------------

Now, say $P_{1}$ wants to execute

So, it enters in for loop

then

while (c[j]); while (t[j] != 0 && t[j] <=t[i]);

but it cannot satisfy 1st while loop as $c[1]=0$

So, $P_{1}$ cannot execute

----------------------------------------------------------------------------------

Now, say $P_{3}$ wants to execute

So, go through loop

while (c[j]); while (t[j] != 0 &&);`t[j] <=t[i]`

So, $P_{3}$ cannot execute highlighted part of code.

That is why ME is satisfied

Now here one doubt coming

is there could be any condition where

`t[j] <=t[i]`

this portion of code is satisfied?

when the prev process value will be greater than next process??

0

problem is, more than one process waiting for entering into CS, then it lead to DEADLOCK.

let P0 only want to enter into CS ===> it can enter.

while P0 is in CS, P1 and P2 in the for loop for waiting into the for loop.

P0 out from CS, then P1 and P2 both are strucked in the loop ===> DEADLOCK

let P0 only want to enter into CS ===> it can enter.

while P0 is in CS, P1 and P2 in the for loop for waiting into the for loop.

P0 out from CS, then P1 and P2 both are strucked in the loop ===> DEADLOCK

0

and also P2 ,P3 ... never can go inside CS and can never executed like mutually exclusive manner

right?

right?

0

mam, did you want to check ME, right ?

then give a scenario where you are getting more than one Process enter into CS at a time.

then give a scenario where you are getting more than one Process enter into CS at a time.

0

Very Nice explanation @Ayush Upadhyaya

I am having a doubt in this explanation for bounded waiting ...

And bounded waiting says that

there exista boundon the number of times that other processes are allowed entry into CS between the time the process placed its request for CS and the time the request for CS is finally granted.Does, your code guarantee that under any circumstances,

for a constant k, after k processes execute finally process Pi would get a chance to get into CS?The answer is

NO

I am having a doubt in this explanation for bounded waiting ...

It is quite sure that when a process made a request there is a bound on number of times other processes can enter in CS ...How ?

If processes with lesser token which is already in CS try to enter in CS again after Pi made request already they will get larger token than Pi hence they will restricted to go in CS.

Does, your code guarantee that under any circumstances,

for a constant k, after k processes execute finally process PiPi would get a chance to get into CS?

To satisfy bounded waiting (I am considering galvin def) we must be sure that before request granted till then only finite number of times others should have entered CS ..but it is not that after that finite times Pi should get chance...we don't know when in future Pi will get chance to get in CS ..but we are sure that there will always be bound on number of times others entered before Pi when Pi get chance .

Hence BW is satisfied acc to galvin def, But if we consider BW as finite wait in terms of time it is not satisfied.

Check this ..BW is satisfied though DL is there https://gateoverflow.in/1256/gate2007-58

0

@jatin khachane 1-You have interpreted incorrectly definition of Bounded Waiting.

Take this

SUppose process $P_i$ makes a request to enter CS at time $t=t_0$

Now suppose the request is finally granted at $t=t_k$

Now, between time interval $[t_0,t_k]$ there must be only "**finite or constant**" number of processes who can bypass this process $P_i$ and enter into CS and execute CS and go.

So, this is an expression in terms of a function $f(N)=k$ where N=Number of processes in the system and K is a constant for all processes,this K may not be same for all processes, but this K is surely a constant number and not a variable quantity.

0

@jatin khachane 1-And in that question which you have given, when want1 and want2 both are true, processes are deadlocked.No process is able to byepass the other one and enter CS indefinitely.Hence BW is satisfied in this case with constant function $f(N)=0$

0

In your answer

And bounded waiting says that

there exista bound on the number of times that other processes are allowed entry into CSbetween the time the process placed its request for CS and the time the request for CS is finally granted

In above comment

Now, between time interval [

t0,tk] there must be only "finite or constant" number of processeswho can bypass this processPiand enter into CS and execute CS and go.

second one is wrong it is about number of times other can enter in CS not number of processes..

And for BW in this example we are sure that when process made request and before this request grant other processes can enter only one time in CS that came before

+2 votes

This Question is a little bit wrong modification of bakery algorithm. You can learn about bakery algorithm from this 15 min video of NPTEL.

NPTEL - Bakery Algorithm

–2 votes

do {

1. c[i]=1;

2. t[i]= pmax (t[0],....,t[n-1])+1;

3.c[i]=0;

4. for every j != i in {0,....,n-1} {

5.while (c[j]);

6. while (t[j] != 0 && t[j] <=t[i]);

}

7. Critical Section;

8. t[i]=0;

9 Remainder Section;

} while (true);

i would like to attempt this question :

Line no 1 - > indiacte that process i would like to enter ito into critical section . it shows its intention by setting value of i is equal to 1

line no 2 : t[i]= return the maximum positive integer not less that any of it argument implies : the process would get its turn no . now let see what i mean

suppose at current instant p[1]=2 and p[2]=3 then another process say now p4 would get it turn as max (p[i])+1 here it will be 3+1 = 4

But apart from turn , it would be more approiate to say that the it record the number of times process want to enter into CS

the reason for this why i thought is

Line no 3 :

c[i]=0 : Again reseeting the value of i =0 ( will explain about this statement in the next some lines )

consder a scenario where process p1 , p2 , p3 want to enter into CS

p[1] makes C[1]=1 (assumin p2 and p3 are not in picture now )

t[1]= 1 (sinc currenlt all are 0 so max (0)+1= 1 )

ad then p3 which will get t2;

p[1]=0 ; And suppose if now process p1 premept from here and go back to section where line 1 is present

noe this time p1 and p2enter simultaeously then both process make there c[1]=1 and c[2]=1 (p3 is not presnet here )

since there is no lock on the line 2

both would end up as t[1]=3 and t[2]=3 (neglecting relative speed of process )

so we basically got 2 process whose t[i] is same .

Line n0 4-6 : implies that if any process i who want to enter into critical section , we must check for all the process j , if the t[j] of any process is found to be less than t[i] then then process p[i] would wait .

beacuse the one who comes early will enter into CS first . but this assumption is wrong with statement C[i]=0

continuing the above scenraio

where p[1]=2 =p[2] then in such a case no one would enter into CS , if anyother process say p3 comes whose value t[i] is less than other two then it will enter into Cs but still problem between p1 and p2 remain same so deadlock problem continues--- so this how option d is eleminated . And even from this sceanario i can say that process p3 ( only 1 process can be in CS ) ..option a may be answer ( let us prove other option too )

Now let us see Bounded waiting :

"There exists a bound, or limit, 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. In other words, no process should have to wait forever to enter its critical region."

--- i think this statement is wrong what if a process p1 prempt evertime from c[i]=0 , then go back to line 1 . Inpsite of another process making a request to enter into Cs it is (p1 ) again making infinite number of attempts again and again to enter into Cs so Bw not satisfied

Now let us see Progress :

i dont agree with progress explantion . A progress basically mean if process doenst want to enter into CS then it shouldnt disallow any other process to enter into Cs . SO if any other process say P5 doesnt want to enter into so c[i]=0 so no other issue would arrise

so i think progress is satisfied too a and c both .according to me .

1. c[i]=1;

2. t[i]= pmax (t[0],....,t[n-1])+1;

3.c[i]=0;

4. for every j != i in {0,....,n-1} {

5.while (c[j]);

6. while (t[j] != 0 && t[j] <=t[i]);

}

7. Critical Section;

8. t[i]=0;

9 Remainder Section;

} while (true);

i would like to attempt this question :

Line no 1 - > indiacte that process i would like to enter ito into critical section . it shows its intention by setting value of i is equal to 1

line no 2 : t[i]= return the maximum positive integer not less that any of it argument implies : the process would get its turn no . now let see what i mean

suppose at current instant p[1]=2 and p[2]=3 then another process say now p4 would get it turn as max (p[i])+1 here it will be 3+1 = 4

But apart from turn , it would be more approiate to say that the it record the number of times process want to enter into CS

the reason for this why i thought is

Line no 3 :

c[i]=0 : Again reseeting the value of i =0 ( will explain about this statement in the next some lines )

consder a scenario where process p1 , p2 , p3 want to enter into CS

p[1] makes C[1]=1 (assumin p2 and p3 are not in picture now )

t[1]= 1 (sinc currenlt all are 0 so max (0)+1= 1 )

ad then p3 which will get t2;

p[1]=0 ; And suppose if now process p1 premept from here and go back to section where line 1 is present

noe this time p1 and p2enter simultaeously then both process make there c[1]=1 and c[2]=1 (p3 is not presnet here )

since there is no lock on the line 2

both would end up as t[1]=3 and t[2]=3 (neglecting relative speed of process )

so we basically got 2 process whose t[i] is same .

Line n0 4-6 : implies that if any process i who want to enter into critical section , we must check for all the process j , if the t[j] of any process is found to be less than t[i] then then process p[i] would wait .

beacuse the one who comes early will enter into CS first . but this assumption is wrong with statement C[i]=0

continuing the above scenraio

where p[1]=2 =p[2] then in such a case no one would enter into CS , if anyother process say p3 comes whose value t[i] is less than other two then it will enter into Cs but still problem between p1 and p2 remain same so deadlock problem continues--- so this how option d is eleminated . And even from this sceanario i can say that process p3 ( only 1 process can be in CS ) ..option a may be answer ( let us prove other option too )

Now let us see Bounded waiting :

"There exists a bound, or limit, 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. In other words, no process should have to wait forever to enter its critical region."

--- i think this statement is wrong what if a process p1 prempt evertime from c[i]=0 , then go back to line 1 . Inpsite of another process making a request to enter into Cs it is (p1 ) again making infinite number of attempts again and again to enter into Cs so Bw not satisfied

Now let us see Progress :

i dont agree with progress explantion . A progress basically mean if process doenst want to enter into CS then it shouldnt disallow any other process to enter into Cs . SO if any other process say P5 doesnt want to enter into so c[i]=0 so no other issue would arrise

so i think progress is satisfied too a and c both .according to me .

+1

progress is not satisfied here.

if satisfied then a,c,d would be answer coz progress satisfies==no deadlock

analyse and see only A is correct

if satisfied then a,c,d would be answer coz progress satisfies==no deadlock

analyse and see only A is correct

0

the progress is defined as if any process doent want to enter into CS and if there is another process say Pj then its decison would be taken by the process in remainder section right ?

+1

NOPE!

PROGRESS is defined as that if many process wants to enter critical section then at any point of time at least one process will be in CS! no deadlock.

i.e at least one process should be able to complete critical seection if it wants.

it may be the case that depending on the condition same process enters cs again and again but it is entering... not deadlocked

it is progress

PROGRESS is defined as that if many process wants to enter critical section then at any point of time at least one process will be in CS! no deadlock.

i.e at least one process should be able to complete critical seection if it wants.

it may be the case that depending on the condition same process enters cs again and again but it is entering... not deadlocked

it is progress

0

@priti progress means there should be progress :) You can see Galvin for the exact definition and the last part of it will be saying "this decision cannot wait indefinitely".

+2

@arjun

Progress and bounded wait are more precisely defined over here http://nptel.ac.in/courses/106104025/lecture41/41_3.htm

For a set of processes to satisfy bounded wait, there should be an upper bound on the no of processes that enter into their critical sections before a process can enter into it's critical section

Bounded wait ensures no starvation.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,167 answers

193,840 comments

94,030 users