What the fuck is Peterson’s algorithm? 

As we all know when two or more processes need to share a single resource, conflict occurs. Remember fighting with your mom for that TV remote back in the days when you watched TV. You still do? ..hah.. what a loser. So, moving on, to solve this conflict we kinda need to use a thing called mutual exclusion which basically means TV serials are your mom’s time and you are not allowed near that TV when she’s watching.

Peterson’s algorithm is a mutual exclusion algorithm that allows two or more processes to share a single-use resource without conflict. 

The algorithm is named after Gary L. Peterson who literally made the algorithm. His original work only focused on two processes (i.e you and your mom because I needed an opportunity to say your mom). But, it can be generalized for more than two processes. So, the algorithm kinda works for two or more than two processes. So, that means you dad and your mom’s boyfriend can join in too if they wish to. 

Note: Dekker also tried to solve the issue between you and your mom but Peterson’s solution is simpler because he knows that you’re a dumbfuck. 

So, how does this algorithm thingy work? 

Here’s a little rote memorization trick for you because you’re too dumb to understand anything. The algorithm used two variables flag and turn. A flag[0]=true indicates that Po wants to enter the critical section. Entrance to critical section is given to P0 if P1 does not want to enter its critical section or P1 has given priority to Po by setting turn to 0

P0:      flag[0] = true;
P0_gate: turn = 1;
         while (flag[1] == true && turn == 1)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[0] = false;
P1:      flag[1] = true;
P1_gate: turn = 0;
         while (flag[0] == true && turn == 0)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[1] = false;

P1 and P0 can never be in the critical section at the same time. If P0 is in its critical section, then flag[0] is true. In addition, either flag[1] is false ( meaning P1 has left its critical section), or turn is 0 (meaning P1 is just now trying to enter the critical section but is waiting, or P1 is at label P1_gate (trying to enter its critical section, after setting flag[1] to true  but before setting turn to 0 and busy waiting). So if both processes are in their critical sections then we conclude that the state must satisfy flag[0] and flag[1]  and turn = 0 and turn = 1. No state can satisfy both turn = 0 and turn = 1, so there can be no state where both processes are in their critical sections. 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *