How to test progress and bounded waiting in Peterson's algorithm?

[shivajikobardan]

Homework Statement

How to test progress and bounded waiting in Peterson's algorithm?

Relevant Equations

How to test progress and bounded waiting in Peterson's algorithm?

This is Petersons's solution for critical section problem. I want to test mutual exclusion, progress and bounded waiting for it. Of course, it satisfied all three.

Process0

while(true)
{
intendToEnter0=true;
turn=1;
while(intendToEnter1==T && turn==1);
critical section
intendToEnter0=false;
non-critical section
}Process1while(true)
{
intendToEnter1=true;
turn=0;
while(intendToEnter0==T && turn==0);
critical section
intendToEnter1=false;
non-critical section
}

1) Mutual Exclusion

Definition:

No two cooperating processes can enter into their critical section at the same time. For example, if a process P1 is executing in its critical section, no other cooperating process can enter in the critical section until P1 finishes with it.

Test:

Say P1 is in its critical section.
That means turn=0 & intendToEnter1=true.

Now, P0 attempts to enter its critical section.
That means it sets intendToEnter0=true & turn=1.

In AND condition if any condition is false, the output is false. Both condition are true here, so it waits.So, mutual exclusion is achieved.2) Progress

Definition:

If no process is in its CS and there are one or more processes that wish to enter their CS, this selection cannot be postponed indefinitely.

No process in remainder section can participate in this decision.

How to test?

3) Bounded Waiting

Definition:

After a prcess P has made a request to enter its CS, there is a limit on the number of times that the other processes are allowed to enter their CS, before P's request is granted.
How to test?

How to test?

 

[jim mcnamara]

Here is a discussion on the nuances of implementing a critical section, with multiple examples.
https://rosettacode.org/wiki/Events

It is not merely a single "flavor" which may be why you are confused.

 

[.Scott]

At the design level, this type of code would normally be tested by exhaustive inspection. At the atomic operation level, each place in the code where shared memory is either set of read is identified. Then all possible combinations of preemption at those points is considered and it is demonstrate by argument that none will allow execution of both critical sections at the same time - while also allowing for eventual execution after proper waiting. Of course, in this case, the design is well known and well documented. So that kind of testing is done.

At the implementation level, I would suggest a couple of shared variables RunningProcess0CS and RunningProcess1CS. I'll leave it to you exactly how you would use and check those variables. Hopefully the OS you are working with has some king of "yield" to prompt context switching. This can sometime be done by "waiting 0 seconds".

Right away, I will tell you that all shared variables (turn, intentToEnter*, RunningProcess*CS) must be declared volatile. Also, you must be running in a system where preemption is possible and that each of the two process while loops has the potential of being preempted by the other process.