Sincronizzazione: sezione critica, Peterson, semafori e monitor

Quando più thread o processi accedono agli stessi dati, il risultato può dipendere dall’ordine, imprevedibile, in cui le loro istruzioni si alternano. Sono gli errori più difficili da trovare: compaiono una volta su un milione, spariscono quando si aggiunge una stampa di prova. In questa lezione vediamo la condizione di gara, i requisiti di una sezione critica, l’algoritmo di Peterson con la dimostrazione della mutua esclusione, le istruzioni atomiche, i semafori con il problema del produttore e del consumatore, e i monitor.

La condizione di gara

L’istruzione C contatore++ sembra indivisibile, ma il processore la esegue in tre passi: legge il valore dalla memoria in un registro, lo incrementa, lo riscrive. Se due thread la eseguono insieme partendo da 5:

Due incrementi, ma il contatore vale 6: uno è andato perso. È una condizione di gara (race condition). Due thread che eseguono un milione di incrementi ciascuno su un multicore finiscono quasi sempre con meno di due milioni, e con un valore diverso a ogni esecuzione.

La sezione critica

Il codice che accede ai dati condivisi è una sezione critica. Una soluzione corretta deve garantire:

1. mutua esclusione: al più un thread alla volta nella sezione critica;
2. progresso: se nessuno è nella sezione critica e qualcuno vuole entrare, la decisione non può essere rinviata all’infinito;
3. attesa limitata: un thread che chiede di entrare ci riesce dopo un numero limitato di ingressi degli altri.

L’algoritmo di Peterson

Per due thread, 0 e 1, bastano due variabili condivise: flag[i] vale vero quando il thread i vuole entrare, turn indica chi deve cedere il passo.

/* codice del thread i; j = 1 - i è l'altro */
flag[i] = true;          /* voglio entrare */
turn = j;                /* ma cedo il passo all'altro */
while (flag[j] && turn == j)
    ;                    /* attendo */
/* sezione critica */
flag[i] = false;         /* esco */

Teorema. L’algoritmo di Peterson garantisce la mutua esclusione.

Dimostrazione. Supponiamo per assurdo che entrambi i thread siano nella sezione critica. Allora flag[0] e flag[1] valgono entrambi vero, perché ciascuno l’ha messo a vero prima di entrare e lo rimette a falso solo uscendo. Consideriamo l’ultimo thread che ha scritto turn, per esempio il thread 1, che ha scritto turn = 0. Da quel momento turn vale 0 e flag[0] vale vero, quindi la condizione del ciclo del thread 1, flag[0] && turn == 0, è vera: il thread 1 non può aver superato il ciclo dopo la sua scrittura. Ma il ciclo viene dopo la scrittura nel suo codice: contraddizione. Lo stesso vale scambiando i ruoli. ∎

Si dimostrano anche il progresso e l’attesa limitata. Sui processori moderni però l’algoritmo funziona solo con barriere di memoria, perché il processore e il compilatore possono riordinare letture e scritture a indirizzi diversi (lezione sui sistemi multicore): è un’idea didattica, non uno strumento pratico.

Le istruzioni atomiche

I processori offrono istruzioni che leggono e modificano una parola di memoria in modo indivisibile:

• test-and-set: scrive vero e restituisce il valore precedente;
• compare-and-swap (CAS): scrive un nuovo valore solo se quello attuale è uguale a un valore atteso, e dice se ci è riuscita.

Con queste si costruisce un spinlock: un thread ripete test-and-set finché non ottiene il valore falso. Va bene per sezioni critiche brevissime su multicore; altrimenti spreca CPU, ed è meglio che il thread si blocchi e ceda il processore.

I semafori

Un semaforo (Dijkstra, 1965) è un intero con due operazioni atomiche:

• wait (o P): se il valore è positivo lo decrementa, altrimenti blocca il thread finché non lo diventa;
• signal (o V): incrementa il valore e sveglia un thread in attesa, se c’è.

Un semaforo inizializzato a 1 è un mutex: wait prima della sezione critica, signal dopo. Un semaforo inizializzato a conta risorse disponibili.

Produttore e consumatore. Un produttore deposita elementi in un buffer circolare di posti, un consumatore li preleva. Servono tre semafori: e conta i posti vuoti (inizialmente ), f i posti pieni (inizialmente 0), m protegge gli indici (inizialmente 1).

/* produttore */                 /* consumatore */
wait(e);                         wait(f);
wait(m);                         wait(m);
buf[i] = x; i = (i+1) % N;       y = buf[j]; j = (j+1) % N;
signal(m);                       signal(m);
signal(f);                       signal(e);

Il produttore si blocca su e quando il buffer è pieno, il consumatore su f quando è vuoto. L’ordine delle wait conta: se il produttore facesse wait(m) prima di wait(e) e trovasse il buffer pieno, si bloccherebbe tenendo m, e il consumatore non potrebbe più entrare a liberare un posto. È uno stallo (lezione sullo stallo).

I monitor

I semafori sono potenti ma facili da sbagliare: una wait dimenticata o invertita rompe tutto. I linguaggi moderni offrono costrutti di livello più alto. Un monitor raggruppa dati condivisi e procedure, con la garanzia che un solo thread alla volta esegua una procedura; per attendere una condizione dentro il monitor si usano le variabili di condizione, con le operazioni wait (che rilascia il monitor mentre si aspetta) e signal. In Java ogni oggetto è un monitor (synchronized, wait, notify); in C e C++ si usano mutex e variabili di condizione della libreria dei thread.

Un’alternativa è evitare la condivisione: strutture dati senza lock basate su compare-and-swap, oppure thread che non condividono nulla e comunicano solo con messaggi, come nei linguaggi Go ed Erlang.