Algoritmo di Dekker
Da Wikipedia, l'enciclopedia libera.
L'algoritmo di Dekker costituisce, come pure l'algoritmo di Peterson, una soluzione completa al problema della mutua esclusione nella coordinazione decentrata di processi (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:
// dichiarazione delle variabili globali comuni
boolean flag0 = false, flag1 = false;
int turno = 0; // oppure: int turno = 1;
// processo #0
// ...
P: flag0 = true;
while (flag1) { // busy waiting
if (turno == 1) {
flag0 = false;
goto P;
}
}
// <sezione critica>
flag0 = false;
turno = 1;
// ...
// processo #1
// ...
P: flag1 = true;
while (flag0) { // busy waiting
if (turno == 0) {
flag1 = false;
goto P;
}
}
// <sezione critica>
flag1 = false;
turno = 0;
// ...
[modifica] Funzionamento
L'algoritmo di Dekker per due processi richiede tre variabili condivise: 2 flag e una variabile turno. Per ciascun processo esiste esattamente un flag. Un flag impostato (flag = true) segnala che il processo corrispondente potrebbe trovarsi in esecuzione della sezione critica. La variabile turno funziona come una specie di segnalino di turno. La condizione d'ingresso per la iterazione è il flag dell'altro processo: se è impostato, allora l'altro processo si trova in esecuzione della sezione critica, oppure della propria iterazione. in quest'ultimo caso è lo stato di turno che stabilisce l'ulteriore procedere. Se turno contiene il numero dell'altro processo, il flag viene cancellato e l'esecuzione riprende da principio. In questo modo, l'altro processo ottiene la possibilità di abbandonare l'iterazione (in caso vi ci si trovava) e di accedere alla sezione critica. Dopo la sezione critica il flag viene cancellato.
[modifica] Esempio
- turno è inizializzato a 0.
- processo #0 in esecuzione: flag0 = true
- processo #1 in esecuzione: flag1 = true
- processo #0 in esecuzione: ingresso nell'iterazione
- processo #1 in esecuzione: ingresso nell'iterazione
- processo #0 in esecuzione: la condizione turno == 1 non è soddisfatta
- processo #1 in esecuzione: la condizione turno == 0 è soddisfatta
- processo #0 in esecuzione: nuovo ingresso nell'iterazione (flag1 è impostato)
- processo #1 in esecuzione: flag1 = false
- processo #0 in esecuzione: la condizione turno == 1 non è soddisfatta
- processo #1 in esecuzione: salto all'indietro a P
- processo #0 in esecuzione: ingresso nella sezione critica (flag1 non è impostato)
- processo #1 in esecuzione: flag1 = true
- processo #0 in esecuzione: sezione critica
- processo #1 in esecuzione: ingresso nell'iterazione
- processo #0 in esecuzione: flag0 = false
- processo #1 in esecuzione: la condizione turno == 0 è soddisfatta
- processo #0 in esecuzione: turno = 1; fine
- processo #1 in esecuzione: flag1 = false
- processo #1 in esecuzione: salto all'indietro a P
- processo #1 in esecuzione: flag1 = true
- processo #1 in esecuzione: ingresso nella sezione critica (flag0 non è impostato)
- processo #1 in esecuzione: sezione critica
- processo #1 in esecuzione: flag1 = false
- processo #1 in esecuzione: turno = 0
[modifica] Considerazioni
A differenza da altre soluzioni di coordinazione decentrata, l'algoritmo di Dekker funziona correttamente anche quando lo scheduling dei due processi si alterna imprevedibilmente. Una variante più semplice ma anche correttamente funzionante è rappresentata dal già citato algoritmo di Peterson. Il principale inconveniente della coordinazione decentrata sussiste tuttavia: i processi in attesa non rilasciano il controllo del processore, ma continuano ad utilizzarlo attraverso cicli di attesa attiva.
