Algoritmo de Peterson , la enciclopedia libre

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

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

Datos: Q903721

[Silberschatz2005-1] Silberschatz, Abraham (2005). Fundamentos de sistemas operativos (7ª edición). McGraw-Hill Interamericana. pp. 174-175. ISBN 0-471-69466-5.

[Peterson1981-2] G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116

[OSR1990-3] En Operating Systems Review, enero de 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).

[1]

[2]

[3]