Algoritmo di Peterson

L'algoritmo di Peterson o algoritmo tie-breaker è un algoritmo sviluppato nella teoria del controllo della concorrenza per coordinare due o più processi o thread che hanno una sezione critica in cui deve esservi mutua esclusione. L'algoritmo assicura la corretta sincronizzazione, impedendo lo stallo (deadlock) ed assicurando che soltanto un processo alla volta possa eseguire una sezione critica (serializzazione). A causa del modo in cui i moderni elaboratori eseguono le istruzioni elementari del linguaggio macchina come load e store, non è affatto certo che l'algoritmo di Peterson funzioni correttamente su tali sistemi.

Schema

Quella che segue è una descrizione schematica dell'algoritmo in pseudocodice C, per 2 e per n processi:

2 processi

 //'' dichiarazione delle variabili globali comuni''
 boolean in1 = false, in2 = false;
 int turno;
 
 // processo #1
 Process CS1 {
     while(1) {
         in1 = true;
         turno = 2;
         while (in2 && turno == 2)
            ; // finché è il turno del processo #2, il processo #1 rimane all'interno del while
         <sezione critica 1>
         in1 = false;
         <sezione non critica 1>
     }
 }
 
 // processo #2
 Process CS2 {
     while(1) {
         in2 = true;
         turno = 1;
         while (in1 && turno == 1)
            ; // finché è il turno del processo #1, il processo #2 rimane all'interno del while
         <sezione critica 2>
         in2 = false;
         <sezione non critica 2>
      }
 }

Funzionamento

Se il processo #1 viene eseguito per primo, in1 viene impostato a true prima di impostare turno a 2. Dal momento che in2 è stato inizializzato a false, la condizione dell'iterazione while non è soddisfatta e il processo #1 accede alla sezione critica.

Se nel frattempo viene avviato il processo #2, questo imposterà in2 a true e turno a 1. in1 è già stato impostato a true dal processo #1, perciò la condizione dell'iterazione while del processo #2 è soddisfatta, così che questo deve aspettare. Solo dopo che il processo #1 ha abbandonato la sezione critica in1 diventa false, e il processo #2 può accedere alla sua sezione critica.

Se il processo #1 viene nel frattempo riavviato, imposterà turno a 2, e dovrà aspettare che il processo #2 abbia abbandonato la sua sezione critica.

• La mutua esclusione è garantita dal fatto che il controllo di in e di turno viene fatto in modo atomico.
• L'assenza di deadlock viene garantita dal fatto che solamente una delle due condizioni while può essere vera nello stesso momento.
• Il progresso dell'elaborazione è garantito dal fatto che se uno dei due processi tenta di entrare e l'altro non è in sezione critica può tranquillamente entrare.
• L'attesa di un processo è limitata in quanto, se i due processi tentano di entrare in sezione critica, entrano alternamente.

n processi

 //'' dichiarazione delle variabili globali comuni''
 int in[1:n] = ([n] 0);    //'' array di lunghezza n con tutti i valori a 0''
 int turno[1:n] = ([n] 0);  //'' array di lunghezza n con tutti i valori a 0''
 
 Process CS[i = 1 to n] {
     for(;;) {
         for[j = 1 to n] { //'' protocollo di ingresso per la sezione critica''
             turno[j] = i;
             in[i] = j;
             for[k = 1 to n st i != k] {
                 //'' aspetta se il processo k ha il numero di in più grande''
                 while(in[k] >= in[i] & turno[j] == i);
             }
         }
         <sezione critica>
         in[i]=0;
         <sezione non critica>  
     }
 }

Funzionamento

La generalizzazione che è stata fatta dell'algoritmo per n processi è piuttosto complessa. Il protocollo di ingresso, per ciascuno degli n processi, consiste in un ciclo for che itera in n-1 fasi. Il valore di turno[j] indica quale sia l'ultimo processo che è arrivato nella fase j; mentre il valore di in[i] rappresenta la fase in cui il processo i si trova.

Considerazioni

L'algoritmo di Peterson è più semplice dell'algoritmo di Dekker, che pure risolve il problema della mutua esclusione. Esso tuttavia eredita il principale problema della coordinazione decentrata: i processi in attesa non rilasciano il controllo del processore, ma continuano ad utilizzarlo attraverso cicli di attesa attiva.