0
$\begingroup$

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
}


Process1


while(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.

  1. 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?

  1. 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?

$\endgroup$
2
  • $\begingroup$ When you say "test" are referring to "prove"? It seems to me you provided a proof sketch for what concerns mutual exclusion. $\endgroup$
    – Chaos
    Commented Jul 30, 2023 at 13:40
  • $\begingroup$ Yes. That's what I mean! $\endgroup$ Commented Jul 31, 2023 at 14:18

1 Answer 1

0
$\begingroup$

We note that a process P i can be prevented from entering the critical section only if it is stuck in the while loop with the condition flag[j] == true and turn == j ; this loop is the only one possible. If P j is not ready to enter the critical section, then flag[j] == false , and P i can enter its critical section. If P j has set flag[j] to true and is also executing in its while statement, then either turn == i or turn == j . If turn == i , then P i will enter the critical section. If turn == j , then P j will enter the critical section. However, once P j exits its critical section, it will reset flag[j] to false , allowing P i to enter its critical section. If P j resets flag[j] to true , it must also set turn to i . Thus, since P i does not change the value of the variable turn while executing the while statement, P i will enter the critical section (progress) after at most one entry by P j (bounded waiting).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.