Algoritmo di Dekker

Disambiguazione – Se stai cercando l'algoritmo di Dijkstra per la ricerca dei cammini minimi, vedi algoritmo di Dijkstra.

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^[1].

Schema[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

• 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[modifica | modifica wikitesto]

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.

Note[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

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

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica