Algoritme de Peterson

L'algoritme de Peterson, també conegut com a solució de Peterson, és un algoritme de programació concurrent per a exclusió mútua, que permet a dos o més processos o fils d'eixecució compartir un recurs sense conflictes, utilisant només memòria compartida per a la comunicació.

Gary L. Peterson va desenrollar en 1981 l'algoritme bàsic per a dos processos, com una simplificació del algoritme de Dekker. L'algoritme bàsic pot generalisar-se fàcilment a un número arbitrari de processos.

Algoritme per a dos processos

  bandera[0] = false
  bandera[1] = false
  tanda      // No és necessari assignar una tanda
  p0: bandera[0] = true                      p1: bandera[1] = true
      tanda = 1                                 tanda = 0
      while( bandera[1] && tanda == 1 );        while( bandera[0] && tanda == 0 );
      //{ no fa res; espera. }               //{ no fa res; espera. }
      // secció crítica                        // secció crítica
                                           
      // fi de la secció crítica              // fi de la secció crítica
      bandera[0] = false                        bandera[1] = false

Els processos p0 i p1 no poden estar en la secció crítica al mateix temps: si p0 està en la secció crítica, llavors bandera[0] = true, i ocorre que bandera[1] = false, en lo que p1 ha terminat la secció crítica, o que la variable compartida tanda = 0, en lo que p1 està esperant per a entrar a la secció crítica. En abdós casos, p1 no pot estar en la secció crítica.

Algoritme per a N processos

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

// Protocol per a Pi ( i=0,...,N-1 )
j:0..N-2; /* variable local indicant l'etapa */
for j = 0 to N-2
{
   bandera[i] = j;
   tanda[j] = i;
   while [(∃ k ≠ i : bandera[k] ≥ j) ∧ (tanda[j] == i)] do; 
}
<secció crítica>
bandera[i] = -1;

Vore també

• Algoritme del forn de Lamport