How is "bounded waiting" achieved in here?

[shivajikobardan]

Homework Statement

How's bounded waiting achieved in here?

Relevant Equations

How's bounded waiting achieved in here?

I understand how mutual exclusion is achieved here. But not sure how bounded waiting is achieved here.

P_i:
do
{
 while(turn!=i);
 critical section
 turn=j;
 remainder section
 while(1);
}

This question has also been answered here but not properly imo. So, I'm asking this again here.

https://stackoverflow.com/questions/41590276/how-does-this-code-section-maintain-bounded-waiting

 

[Filip Larsen]

Have you taken a look at https://en.wikipedia.org/wiki/Peterson's_algorithm

 

[shivajikobardan]

View attachment 329509
http://cc.ee.ntu.edu.tw/~farn/courses/OS/slides/ch06.pdf

How do I write a backward refutation tree for proving mutual exclusion or anything for that matter?

 

[Filip Larsen]

You first ask about understanding bounded waiting and now you ask how to prove mutual exclusion. Does this mean you now understand why bounded waiting is obtained?

Proving stuff (depending on the formal framework you use) can be much more difficult and nitpicking than understanding, rather similar to math stuff. And, by the way, your code snippet is messed up, so please refer to the snippet in the wiki link I gave or something similar valid.

 

[jedishrfu]

In the interests of sanity, let's try to answer the bounded waiting question only.

Your example is not quite correct, here is a better one although it too is not the way it would really be done.

P_i:
do {
     while(turn!=i);

     ## start of critical section

         turn=(i+1) mod n;

         ## where i is the proc-id and n is the # of processes wanting the resource

         ## do your critical code here

     ## end of critical section

     ## remainder section

 } while(1);

Bounded waiting means no consumer of a resource will be starved out of using shared resources by other consumers.

It’s like folks at a gun range where they all want to shoot but the range master designates who can make the next shot and ensures that each person gets a chance to shoot.

The people are the processes waiting on the resource, the range master is the algorithm that handles bounded waiting and the gun range is the shared resource.