Algoritmo de Peterson

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

  bandera[0] = false
  bandera[1] = false
  turno      = 0 
  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] = 1, y ocurre que bandera[1] = 0, 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[editar]

// 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[k] == i)] do; 
}
<sección crítica>
bandera[i] = -1;

Véase también[editar]

Referencias[editar]

  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).