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.

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