Algoritmo di Dekker

L'algoritmo di Dekker, noto anche come algoritmo di proiezione di Dijkstra, costituisce 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). Tale algoritmo è attribuito al matematico olandese Th. J. Dekker da Edsger W. Dijkstra nel suo manoscritto sui processi cooperanti sequenziali.

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;
           while(turno == 1) ; // busy waiting
           goto P;
        }
     }
     // <sezione critica>
     flag0 = false;
     turno = 1;
// ...

// processo #1
// ...
P:   flag1 = true;     
     while (flag0) { // busy waiting
        if (turno == 0) {
           flag1 = false;
           while(turno == 0) ; // busy waiting
           goto P;
        }
     } 
     // <sezione critica>
     flag1 = false;
     turno = 0;  
// ...

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 nella 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 a true, allora l'altro processo si trova in esecuzione nella sezione critica, oppure nella 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.

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

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.

Bibliografia

• E. W. Dijkstra - Solution of a Problem in Concurrent Programming Control - Communications of the ACM - September 1965 - page 569