Algoritmo de Peterson

El algoritmo de Peterson, también conocido como solución de Peterson,^[1]​ es un algoritmo de programación concurrente para exclusión mutua, que permite a dos o más procesos o hilos de ejecución compartir un recurso sin conflictos, utilizando sólo memoria compartida para la comunicación.

Gary L. Peterson desarrolló en 1981 el algoritmo básico para dos procesos,^[2]​ como una simplificación del algoritmo de Dekker. El algoritmo básico puede generalizarse fácilmente a un número arbitrario de procesos.^[3]​

Algoritmo para dos procesos

  bandera[0] = false
  bandera[1] = false
  turno      // No es necesario asignar un turno
  p0: bandera[0] = true                      p1: bandera[1] = true
      turno = 1                                 turno = 0
      while( bandera[1] && turno == 1 );        while( bandera[0] && turno == 0 );
      //{ no hace nada; espera. }               //{ no hace nada; espera. }
      // sección crítica                        // sección crítica
                                           
      // fin de la sección crítica              // fin de la sección crítica
      bandera[0] = false                        bandera[1] = false

Los procesos p0 y p1 no pueden estar en la sección crítica al mismo tiempo: si p0 está en la sección crítica, entonces bandera[0] = true, y ocurre que bandera[1] = false, con lo que p1 ha terminado la sección crítica, o que la variable compartida turno = 0, con lo que p1 está esperando para entrar a la sección crítica. En ambos casos, p1 no puede estar en la sección crítica.

Algoritmo para N procesos

// Variables compartidas
bandera: array[0..N-1] of -1..n-2; /* inicializada a –1 */
turno: array[0..N-2] of 0..n-1; /* inicializada a 0 */

// Protocolo para Pi ( i=0,...,N-1 )
j:0..N-2; /* variable local indicando la etapa */
for j = 0 to N-2
{
   bandera[i] = j;
   turno[j] = i;
   while [(∃ k ≠ i : bandera[k] ≥ j) ∧ (turno[j] == i)] do; 
}
<sección crítica>
bandera[i] = -1;

Véase también

• Algoritmo de la panadería de Lamport

Referencias

1. Silberschatz, Abraham (2005). Fundamentos de sistemas operativos (7ª edición). McGraw-Hill Interamericana. pp. 174-175. ISBN 0-471-69466-5. 
2. G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
3. En Operating Systems Review, enero de 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).

• Datos: Q903721