Algoritmo del biglietto

In informatica, l'algoritmo del biglietto (in inglese ticket lock) è un meccanismo di sincronizzazione tra processi per verificare quale thread in esecuzione ha i permessi di accesso ad una sezione critica del sistema, ovvero una risorsa condivisa tra più processi.

Descrizione

Il ticket lock è un sistema di code basato sul principio "first in, first out" (FIFO). Esso introduce il vantaggio della correttezza nell'acquisizione del blocco, resa possibile attraverso l'inizializzazione di due variabili interi al valore zero. Il primo rappresenta il biglietto di coda (in inglese queue ticket), mentre il secondo il biglietto di uscita (in inglese, dequeue ticket).

Quando un nuovo thread viene creato, il sistema operativo assegna un nuovo biglietto numerato al thread ed incrementa il ticket della coda atomicamente. L'atomicità di questa operazione è necessaria per evitare che due thread ottengano due biglietti differenti con lo stesso valore di accesso.^[1] Successivamente, confronterà il valore del suo biglietto con quello del biglietto di fine coda, prima dell'incremento. Se i due sono uguali, il thread può accedere nella sezione critica. In caso contrario, un altro thread è già nella sezione critica e questo thread deve attendere o cedere il biglietto. Quando un thread lascia la sezione critica controllata dal lock, incrementa atomicamente il ticket di dequeue. Questo consente al thread immediatamente successivo, ovvero quello con il numero di ticket sequenziale successivo, di accedere alla risorsa.^[2]

Implementazione dell'algoritmo

In un sistema con architettura di memoria non uniforme (NUMA), è essenziale avere un'implementazione dell'algoritmo del biglietto che garantisca un certo grado di equità nella sua implementazione. L'algoritmo del biglietto è un'implementazione di spinlock che aggiunge questo attributo desiderato.^[3][4] Il seguente pseudocodice mostra le operazioni di inizializzazione, acquisizione e rilascio del blocco. In esso, una chiamata di sistema a inizializza_biglietto precede la sezione critica del codice e rilascia_biglietto la segue. Ogni processore tiene traccia del proprio turno attraverso il valore di il_mio_biglietto.^[2][5]

inizializza_biglietto(int *biglietto_successivo, int *biglietto_attuale)
{
    *biglietto_attuale = *biglietto_successivo = 0;
}

rilascia_biglietto(int *biglietto_successivo, int *biglietto_attuale)
{
    il_mio_biglietto = fetch_and_inc(biglietto_successivo);
    while (*biglietto_attuale != il_mio_biglietto) {}
}

rilascia_biglietto(int *biglietto_attuale)
{
    ++*biglietto_attuale;
}

All'interno di essa, l'istruzione CPU fetch_and_inc (abbreviato con FAA in informatica^[6]) incrementa atomicamente il contenuto di una locazione di memoria di un valore specificato.^[7]

La mutua esclusione è garantita dal fatto che il_mio_biglietto è univoco per ogni processo e quindi la condizione di fetch_and_inc può essere verificata per un solo processo alla volta. L'univocità di il_mio_biglietto garantisce l'assenza di deadlock perché un solo processo alla volta può entrare in sezione critica.

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]=fetch_and_inc(number,1);
        while(turn[i]!=next){}
        CS;
        next++;
        nonCS;
     }
  }