Solution to Critical State Problem: Progress Requirement

[prashantgolu]

i read this as a solution to critical state problem in galwin

repeat
while turn!= i do no-op;
critical section
turn := j;
remainder section
until false;


now this algo does not meet the "progress" conditiion...
the book states the reason as...this requires strict alteration of processed in execution of their critical state
for ex...if turn =0 and p1 is ready to enter its critical section,it cannot do so...even though p0 maybe in its remainder section...

how can p1 be in its remainder section and turn still be 0...

how does this algo not meet the reqirement of progress?

 

[Mark44]

i read this as a solution to critical state problem in galwin

repeat
while turn!= i do no-op;
critical section
turn := j;
remainder section
until false;

As stated here, this doesn't make much sense. Is this just a part of an algorithm and you haven't shown us the rest? We don't know the value of i, so can't tell whether turn != i is true or false.

now this algo does not meet the "progress" conditiion...
the book states the reason as...this requires strict alteration of processed in execution of their critical state
for ex...if turn =0 and p1 is ready to enter its critical section,it cannot do so...even though p0 maybe in its remainder section...

how can p1 be in its remainder section and turn still be 0...

how does this algo not meet the reqirement of progress?

What are p0 and p1? They aren't mentioned in the algorithm you showed.

 

[prashantgolu]

sorry...my fault...turn=0 initaially...and p0 and p1 are two processes...this algorithm is for 2 processes only...so turn can be 0 or 1...

 

[amit88]

Ya, it is true that the algorithm does not satisfy the condition of progress...

Imagine a case when p1 has entered its critical section. After executing, it turns the value of turn to 0 and exits. But the process p0 does not want to enter its critical section. So the value of turn would be set to 0 for ever. Even though if process p1 wants to enter its critical section again, it cannot do so, until process p0 wishes to enter its critical section.
Hence the condition of progress is not satisfied.

I hope I was able to explain you. Do let me know...

 

[prashantgolu]

thanks a lot :)

 

[rcgldr]

Without an atomic operation, you'll need a flag variable in addition to the turn variable:

http://en.wikipedia.org/wiki/Dekker's_algorithm

http://en.wikipedia.org/wiki/Peterson's_algorithm

Operating systems will generally have mutexes and/or semaphores impemented as atomic operations to allow multi-threaded programs to wait for and share common resources.

http://en.wikipedia.org/wiki/Mutex

http://en.wikipedia.org/wiki/Semaphore_(programming)