11,730 views
11 votes
11 votes

Dekkers Algorithm

flag[0]=true;
while(flag[1]==true)
{
    if(turn!=0)
    {
        flag[0]=false;
        while(turn!=0);
        flag[0]=true;
    }
}

// CS

turn=1;
flag[0]=false;

Peterson Algorithm
 

flag[0]=true;
turn=1;
while(flag[1]==true&&turn==1);
// CS
flag[0]=false

Account on the

  • Mutual Exclusion
  • Bound Waiting
  • Deadlock and Starvation
  • Progress

1 Answer

Best answer
4 votes
4 votes

Both Dekker's and Peterson's algo Account on the all 4 cases :

Mutual Exclusion is satisfied and progress is there that means freedom from deadlock .

Bounded waiting  is satisfied , both are starvation free and there is no deadlock . 

Consider a scenario where there are 2 person wants to enter in a cave . We start from person 1, he is giving the first try .

Dekker's Algorithm :

flag[0]=true;         // "I want to enter."  Here progress is satisfied .

while(flag[1]==true)  // "If you want to enter and "

{

if(turn!=0)          // "if it's your turn,"

   {

flag[0]=false;      // " I don't want to enter any more."   Here it ensure No Starvation

while(turn!=0) {}  //  "If it's your turn I'll wait."     Here Bounded waiting is satisfied 

flag[0]=true;     //  "I want to enter."

   }

}

 // CS      //  "Enter into the Cave "                    Here Mutual Exclusion is satisfied 

turn=1;     //  "You can enter next."   

flag[0]=false;  //  "I don't want to enter any more."  Ensure No Deadlock 

Hence Dekker's Algorithm satisfy all four conditions .

selected by

Related questions

0 votes
0 votes
0 answers
2
Raj Singh 1 asked Jan 1, 2019
1,383 views
Many problems on gateoverflow asks whether the given code satisfies progress requirement of the solution for the critical section problem. Most of these code contain mult...