Algoritmo di Peterson
Da Wikipedia, l'enciclopedia libera.
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).
Indice |
[modifica] Schema
Quella che segue è una descrizione schematica dell'algoritmo in pseudocodice C, per 2 e per n processi:
[modifica] 2 processi
// dichiarazione delle variabili globali comuni
boolean in1 = false, in2 = false;
int last;
// processo #1
Process CS1 {
for(;;) {
in1 = true;
last = 1;
while (in2 && last == 1);
<sezione critica>
in1 = false;
<sezione non critica>
}
}
// processo #2
Process CS2 {
for(;;) {
in2 = true;
last = 2;
while (in1 && last == 2);
<sezione critica>
in2 = false;
<sezione non critica>
}
}
[modifica] Funzionamento
Se il processo #1 viene eseguito per primo, in1 viene impostato a true prima di impostare last a 1. 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 last a 0. 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à last a 1, 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 last 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.
[modifica] n processi
// dichiarazione delle variabili globali comuni
int in[1:n] = ([n] 0); // array di lunghezza n con tutti i valori a 0
int last[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
last[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] & last[j] == i);
}
}
<sezione critica>
in[i]=0;
<sezione non critica>
}
}
[modifica] 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 last[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.
[modifica] 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.
