CSC/ECE 506 Spring 2011/ch7 jp

Peterson's Algorithm

Peterson’s algorithm, also known as Peterson’s solution, is an algorithm that addresses the critical section problem by meeting the 3 criteria of the problem: mutual exclusion, progress, and bounded waiting.

int turn;  // turn for execution
int interested[2];   // the processors interested
void enter_region(int process) 
{ 
  int otherProcess; 
  otherProcess = 1 - process;    
  interested[process]=1;  
  turn = process;         
  while(turn == process && interested[otherProcess] == 1)
     {
 	// busy wait
     }
} 
void leave_region(int process) 
{ 
  interested[process] = 0; 
}

The algorithm uses two variables as seen above, interested and turn. If a flag value for interested is set to 1, it indicates the process wants to enter the critical section. The variable turn is a placeholder for the process whose turn will be next allowed to enter the critical section. As seen above, Process1 has been given priority over P0.

To ensure mutual exclusion, the variable interested and turn are set to ensure only 1 can enter the critical section at a time. To ensure Progress, once a processor has left the critical section the other processors can determine which processor is allowed into the critical section next. To ensure bounded waiting, as seen with the above code, a process will wait no longer than 1 turn to enter the critical section as the variable turn=1 will be enabled.