Algoritmo del biglietto

L'algoritmo del biglietto (in inglese ticket algorithm) serve per coordinare i processi che vogliono eseguire una sezione critica.

L'algoritmo può essere spiegato nel seguente modo: ogni processo che vuole eseguire la sezione critica prende un biglietto con un numero. In un display è segnalato il numero del processo che in quel dato istante è in sezione critica; quando un processo si accorge che il numero sul display è uguale a quello presente sul suo biglietto, esso entra in sezione critica.

L'algoritmo può essere scritto nel seguente modo:

int number = 1;   //rappresenta il prossimo numero che un processo può prendere
int next = 1;   //rappresenta il numero del biglietto del processo che dovrà andare in CS
int turn[1:n]=([n] 0);   //è un array di lunghezza n con tutti i valori settati a 0

  Process CS[i=1 to n] {
   while(true) {
    <turn[i]=number;
      number=number+1;>  //l'assegnazione del numero ed il successivo incremento viene effettuato atomicamente
       <await(turn[i]==next);>   //il processo resta in attesa sino a quando non è verificata la condizione di await
     CS;
       <next=next+1;>   //incremento della variabile next in modo atomico
         nonCS;
      }
      }

La mutua esclusione è garantita dal fatto che number è univoco per ogni processo e quindi la condizione di await può essere verificata per un solo processo alla volta. L'assenza di deadlock è garantita dal fatto che un solo processo alla volta può entrare in sezione critica grazie all'unicità di turn. Il progresso è garantito dal fatto che se non c'è nessuno in sezione critica un processo entra. L'attesa limitata è garantita se lo scheduler è di tipo weakly fair.

L'algoritmo può essere appena raffinato sostituendo alle righe di pseudo-codice delle sezioni critiche, comandi di programmazione.

  int number = 1;
  int next = 1;
  int turn[1:n]=([n] 0);

  Process CS[i=1 to n] {
     while(true) {
        turn[i]=FA(number,1);
        while(turn[i]!=next){}
        CS;
        next++;
        nonCS;
     }
  }

Viene utilizzato il comando FA (fetch-and-add) che incrementa la variabile number di 1 e restituisce il valore della variabile number prima dell'incremento.