Algoritmo del fornaio

L'algoritmo del fornaio è uno dei metodi di mutua esclusione che trovano applicazione pratica nella programmazione parallela per serializzare l'esecuzione delle sezioni critiche da parte di più processi o thread concorrenti.

L'algoritmo deve il nome al suo inventore Leslie Lamport, che propose l'analogia con il modello reale di una frequentata panetteria, dove i clienti strappano un numero prima di mettersi in fila ad aspettare il proprio turno. I clienti del fornaio rappresentano i task in attesa del proprio turno per eseguire la sezione critica.

Schema

Quella che segue è una descrizione schematica dell'algoritmo in pseudocodice C++:

// dichiarazione delle variabili globali comuni
bool sceglie[N] = {false}; // N costante
int numero[N] = {0};

int i; // indice del thread in esecuzione
// ...
for (;;) {
    sceglie[i] = true;
    numero[i] = 1 + max(numero[0], numero[1], ..., numero[N - 1]);
    sceglie[i] = false;
    for (j = 0; j < N; ++j) {
        while (sceglie[j]);
        while (
            (numero[j] != 0) &&
            (
             (numero[j] < numero[i]) ||
             ((numero[j] == numero[i]) && (j < i))
            )
        );
    }
    // <sezione critica>
    numero[i] = 0;
    // <sezione non critica>
}

Funzionamento

Al di là di ogni affinità con le situazioni reali, è possibile che più thread ricevano lo stesso numero di turno. Per ovviare a questa circostanza si introduce l'indice del thread come secondo argomento di confronto. Se più thread ricevono lo stesso numero di turno, si conviene di assegnare la precedenza al thread con l'indice più basso. Va notato che l'indice di ciascun thread deve essere unico: esso può venire assegnato al momento della creazione o passato come parametro. Nell'esempio schematico riportato sopra, la costante N rappresenta il numero massimo di thread concorrenti. Dopo aver ricevuto il suo indice unico, ogni thread scrive solo nelle sue slot (sceglie[i] e numero[i]). La serializzazione è assicurata dalle due iterazioni while consecutive. Questi cicli vengono ripetuti da ogni thread per tutti i thread, incluso quello in esecuzione e i thread non attivi. Solo quando non ci sono più altri thread con priorità più alta è possibile l'accesso alla sezione critica.

Considerazioni

L'algoritmo del fornaio garantisce che un solo thread alla volta possa accedere alla sezione critica, indipendentemente dall'ordine delle commutazioni di contesto e dagli altri dettagli dello scheduling. Sussiste tuttavia il principale inconveniente che è proprio di tutti gli algoritmi di coordinazione decentrata, cioè non coordinata dallo scheduler: i task in attesa continuano ad utilizzare il processore in un ciclo di attesa attiva detto busy waiting, rallentando così gli altri thread nel sistema.

Bibliografia

Leslie Lamport, A New Solution of Dijkstra's Concurrent Programming Problem, Communications of the ACM 17, 8 (August 1974), 453-455
Pagina in cui Lamport descrive l'algoritmo, su research.microsoft.com.