Process Synchronization: Dekker's algorithm

Question

This Screenshot is taken from William Stalling's Operating Systems book. My doubt is that Bounded wait is not satisfied by this solution. Though Book claims that is satisifes all three required conditions.

For example: P0 and P1 both want to enter critical section and set their flags to true.

flag[0] = true

flag[ 1] = true

Both p0 and p1 enter while loop, p0 wins the race process P1 sets its flag to false

now flag[ 1]= false

Process P0 goes into Critical Section, comes out, sets turn = 1 and flag[0]=false.

Now actual problem starts from here:

Process P1 comes out of infinite while loop and before it could set flag[ 1] to True from False, it gets preempted.

Now Process P0 can go any number of times in Critical section because Flag[ 1] is False.

Conclusion: Process P1 tried to get access to critical section but because of bad solution it did set its flag to False to give path to Po and now stuck for infinite time.

hence B.W is not satisfied!

Comments

@ manu00x

Read this thread , specially 2 nd answer.

https://cs.stackexchange.com/questions/60235/is-bounded-waiting-ensured-in-given-version-of-dekkers-solution-for-critical-se

In one line we can say , it all depends how we define BW.

1. If BW is defined based on number of other process enter into CS then it is satisfied here.
2. If BW is defined based on infinite waiting time then it is Not satisfied here ( it seems Stallings follow this definition ..so livelock can exists here  which leads to dis satisfy BW)

But if we follow Galvin definition then BW satisfied in Dekker's algo.

---

@Sachin Mittal 1  sir, given solution is incorrect.. how bounded waiting will be satisfied in following scenario:

consider P0 is inside critical section, 

in this case flag[0] = 1, turn = 0;

now P1 wants to go inside the critical section hence

flag[1] = 1 , now it will go inside while loop and checks for if condition and it evaluates to true now it sets its own flag i.e flag[1] = 0 and stuck on while loop.

now suppose P0 exits from critical section, then flag[0] = 1, turn = 1

suppose P0 again wants to go inside critical section, it can go since flag[1] = 0;

and it can do it for indefinite time..

now say how bounded waiting is satisfied ?

---

Galvin defn of BW

Focus on the line”made a request to enter its CS”, this will be referred afterwards
Here, flag[i]=0 means the process is not requesting to enter CS(as per Dekker code, flag[0]=1, means P0 is requesting to enter CS ,flag[1]=1, means P1 is requesting to enter CS), so first need to figure out which variable a process uses to request to enter CS 

—in all the problems, we most did in lecs, Pyqs
for checking bounded wait, what we did was while P0 is executing, P1 had to try to enter CS, and if it can't ,it was stuck in the loop(and for evry such qstn we did in lecs, Pyqs it also meant P1 has requested to enter CS too, cuz in none of those prblms P1 retracted it's request, even before it requested for CS, so  imo Dekker coded his algo in  a bit different way)
But for Dekker algo,P1 before getting CS set it's flag[1]=0 which effectively meant p1 is not even requesting for CS<P1 retracting the request >( this corresponds to the code written beside "I don't want to enter any more" statement in the fig)  before getting stuck

so for the prblms in lecs, Pyqs, we never had a need to explicitly focus on "requesting CS" part, cuz being stuck in loop already meant the process had requested for CS here, but it is NOT the case for dekker algo

Answer 1

Though Book claims that is satisifes all three required conditions.

Yes, in Stallings , it defined BW based on infinite waiting time .. ( the definition says : no process should wait for a resource for infinite amount of time . )

For this case , you can see deadlock is there so BW is not satisfy as there is indefinite waiting.

But there are another way we can define BW ( The Galvin definition ), in terms of number of other process in CS ( what we need to follow  )

And here BW is satisfied if we consider this definition ... when u check BW satisfied or not just check before our requesting process how many other process can go to CS or how many times other process can go to CS ! thats it.

So you see there are 2 way we can define BW, in one case BW not satisfy and in other case BW does satisfy .

For 2nd case we just need to check for each process before it enter how many other process can enter into CS ( this is rather more simple way to check , here we don't consider that the system is in deadlock or no progress possible ..etc , we just check when a process request and before that request granted how many other process enter into CS ) .

When there are 2 process and there is strict alternation ( means after p1 , p2 must come) BW never get dissatisfied.

--------

Read this thread once :

• https://cs.stackexchange.com/questions/60235/is-bounded-waiting-ensured-in-given-version-of-dekkers-solution-for-critical-se

Comments

p1 p1 p1 p1 p2 p2 p1 p2 , is a strict alternation indeed.

---

1. Deadlock is not possible
2. Progress is not satisfied,

How possible ?

deadlock means no progress .. due to ; after while in your code , deadlock also posible ( specifically it should be busy waiting or livelock )..

In your code, there is no deadlock possibility but progress is satisfied.

---

I don't think that is strict alternation, strict alternation means p1 then p2 then only p1...if processes are allowed to go in any order then what is strict alternation after all?