Algoritmo del biglietto
Da Wikipedia, l'enciclopedia libera.
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, abbiamo un display nel quale viene 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(number[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.
