Sincronizzazione - sezione critica, race condition e mutex

In questa pagina 6

Processi e thread concorrenti (Processi - stati, PCB, creazione con fork ed exec, Thread e concorrenza - modelli, Pthreads e goroutine) possono essere interrotti in qualunque momento, anche a metà di un'operazione. Se condividono dati, un'interruzione nel posto sbagliato lascia i dati incoerenti. Questa nota presenta il problema (race condition e sezione critica), le soluzioni via software (Peterson) e via hardware (test_and_set, compare_and_swap), e il primo strumento da usare in pratica, il mutex. I semafori, i monitor e i problemi classici sono nella nota successiva (Semafori, monitor e problemi classici di sincronizzazione); quando si bloccano a vicenda i processi sorge lo stallo (Deadlock - condizioni, prevenzione, evitamento e rilevamento).

Race condition

Definizione (race condition). Si ha una race condition (corsa critica) quando più processi o thread accedono agli stessi dati e il risultato dipende dall'ordine in cui le operazioni si intrecciano (interleaving).

Esempio 1: il produttore-consumatore con un contatore counter degli elementi nel buffer (v. Processi - stati, PCB, creazione con fork ed exec). Il produttore esegue counter++, il consumatore counter--. In linguaggio macchina ognuna è un'operazione di lettura, modifica, scrittura su un registro:

counter++ :  registro1 = counter           counter-- :  registro2 = counter
             registro1 = registro1 + 1                  registro2 = registro2 - 1
             counter = registro1                        counter = registro2

Con counter = 5 un possibile intreccio è:

t	chi	istruzione	registro	`counter`
0	produttore	`reg1 = counter`	reg1 = 5	5
1	produttore	`reg1 = reg1 + 1`	reg1 = 6	5
2	consumatore	`reg2 = counter`	reg2 = 5	5
3	consumatore	`reg2 = reg2 - 1`	reg2 = 4	5
4	produttore	`counter = reg1`		6
5	consumatore	`counter = reg2`		4

Un'incrementata e una decrementata dovrebbero lasciare 5, invece resta 4 (con t4 e t5 scambiati si avrebbe 6). Il codice è corretto "in sequenza", ma non sotto concorrenza.

Esempio 2: due processi $P_0$ e $P_1$ chiamano fork; il kernel assegna il pid con la variabile next_available_pid. Senza un meccanismo che impedisca l'accesso contemporaneo, lo stesso pid potrebbe essere dato a due processi.

Una race condition è un errore intermittente: il programma funziona per migliaia di esecuzioni e poi sbaglia. Il laboratorio 3 la fa vedere con due thread che incrementano e decrementano sum (Esercizio - Thread, race condition e parallelismo sui dati (laboratorio 3)).

Il problema della sezione critica

Si considera un sistema di $n$ processi $\{P_0, \dots, P_{n-1}\}$ ; ognuno ha un segmento di codice, la sezione critica (critical section), in cui modifica dati comuni (variabili, tabelle, file). Quando un processo è nella sua sezione critica gli altri non devono essere nelle loro. La struttura di ogni processo:

while (true) {
    entry section        // chiede il permesso di entrare
        sezione critica
    exit section         // segnala che ha finito
    remainder section    // il resto del codice
}

Una soluzione deve soddisfare tre requisiti:

requisito	significato
mutua esclusione (mutual exclusion)	se $P_i$ è nella sua sezione critica, nessun altro è nella propria
progresso (progress)	la decisione di chi entra non dipende dai processi nella remainder section e non può essere rimandata all'infinito
attesa limitata (bounded waiting)	dopo che un processo ha chiesto di entrare, il numero di volte che gli altri entrano prima di lui è limitato

Primo tentativo: disabilitare gli interrupt

Entry: disabilita gli interrupt; exit: li riabilita. Su un monoprocessore il codice in esecuzione non può essere interrotto. Ma: e se la sezione critica dura un'ora? Un processo può causare starvation agli altri? E con due o più CPU bisogna disabilitare gli interrupt di tutte? Non scala e dà troppo potere ai programmi utente.

Secondo tentativo: alternanza stretta

Due processi condividono int turn, che indica a chi spetta entrare. Si assume che load e store siano atomiche.

/* P0 */                         /* P1 */
while (true) {                   while (true) {
    while (turn == 1) ;              while (turn == 0) ;
    sezione critica                  sezione critica
    turn = 1;                        turn = 0;
    remainder                        remainder
}                                }

Mutua esclusione: sì, turn non può valere contemporaneamente 0 e 1.
Progresso: no. I due processi devono alternarsi: se $P_1$ è lento (resta nella sua remainder section), $P_0$ ha finito il turno e non può rientrare anche se la sezione critica è libera.
Attesa limitata: sì (prima o poi ogni processo entra).

La soluzione di Peterson

Definizione (soluzione di Peterson, due processi). I processi condividono boolean flag[2] e int turn. flag[i] = true significa « $P_i$ vuole entrare»; turn dice a chi spetta se entrambi vogliono.

/* processo P_i, con j = l'altro */
while (true) {
    flag[i] = true;                    // voglio entrare
    turn = j;                          // ma cedo il turno all'altro
    while (flag[j] && turn == j) ;     // aspetto solo se l'altro vuole entrare ED è il suo turno
        sezione critica
    flag[i] = false;                   // ho finito
    remainder
}

Perché funziona:

Mutua esclusione: $P_i$ entra solo se flag[j] == false oppure turn == i. Se entrambi fossero dentro, avremmo flag[0] = flag[1] = true, e ognuno sarebbe entrato perché turn è il proprio indice: ma turn non vale 0 e 1 insieme. Chi ha scritto turn per ultimo ha ceduto il turno all'altro, che quindi passa.
Progresso: se $P_j$ non vuole entrare (flag[j] == false) $P_i$ non aspetta mai.
Attesa limitata: dopo aver sbloccato, $P_j$ rimette flag[j] = true e turn = i: lascia passare $P_i$ , che aspetta al più un'entrata dell'altro.

Punto debole. Anche con load e store atomiche, la soluzione non è garantita sulle architetture moderne: per migliorare le prestazioni processori e compilatori possono riordinare istruzioni senza dipendenze tra loro. Per un solo thread va bene, per più thread no. Esempio: due thread condividono boolean flag = false; int x = 0;. Il thread 1 esegue while (!flag) ; print x; e il thread 2 x = 100; flag = true;. Ci si aspetta 100, ma se il thread 2 viene riordinato in flag = true; x = 100; si può stampare 0. In Peterson, il riordino di flag[i] = true e turn = j o delle letture può far entrare entrambi nella sezione critica.

Barriere di memoria

I modelli di memoria possono essere fortemente ordinati (strongly ordered: la modifica di un processore è subito visibile agli altri) o debolmente ordinati (weakly ordered: può non esserlo). Una barriera di memoria (memory barrier) è un'istruzione che costringe a completare, e a rendere visibili agli altri processori, tutte le letture e scritture precedenti prima di ogni successiva. Nell'esempio: thread 2 esegue x = 100; memory_barrier(); flag = true; e thread 1 while (!flag) memory_barrier(); print x;, così x viene scritto prima di flag e letto dopo.

In C11 le variabili atomiche con ordinamento sequenziale (memory_order_seq_cst, il default di <stdatomic.h>) mettono le barriere necessarie. Peterson corretto per due thread:

peterson_c11.cc

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>
#include <stdlib.h>

#define ITER 100000

static atomic_bool flag[2];
static atomic_int turn;
static long contatore;                    /* dato condiviso protetto da Peterson */

static void entra(int i)
{
    int j = 1 - i;
    atomic_store(&flag[i], 1);            /* voglio entrare */
    atomic_store(&turn, j);               /* cedo il turno */
    while (atomic_load(&flag[j]) && atomic_load(&turn) == j)
        ;                                 /* attesa attiva */
}

static void esci(int i)
{
    atomic_store(&flag[i], 0);
}

static void *lavora(void *arg)
{
    int i = (int)(long)arg;               /* 0 oppure 1 */
    for (int k = 0; k < ITER; k++) {
        entra(i);
        contatore += (i == 0) ? 1 : -1;   /* sezione critica */
        esci(i);
    }
    return NULL;
}

int main(void)
{
    pthread_t t0, t1;
    pthread_create(&t0, NULL, lavora, (void *)0L);
    pthread_create(&t1, NULL, lavora, (void *)1L);
    pthread_join(t0, NULL);
    pthread_join(t1, NULL);
    printf("contatore = %ld (atteso 0)\n", contatore);
    return 0;
}

La soluzione di Peterson resta però lenta (attesa attiva) e limitata a due processi: in pratica si usano gli strumenti sotto.

Supporto hardware

Su un monoprocessore si potrebbero disabilitare gli interrupt, ma su un multiprocessore è inefficiente. Molti sistemi offrono istruzioni speciali che leggono e modificano atomicamente (cioè senza interruzione) una parola, o ne scambiano due.

test_and_set: ritorna il vecchio valore di *target e lo imposta a true, in modo atomico. Con lock condiviso inizializzato a false:

do {
    while (test_and_set(&lock)) ;     // finché il vecchio valore è true, qualcuno è dentro
        sezione critica
    lock = false;
    remainder
} while (true);

Il primo processo trova false (e imposta true), entra; gli altri leggono true e aspettano. Soddisfa la mutua esclusione ma non l'attesa limitata: un processo veloce può riprendere sempre il lock e far soffrire gli altri (starvation).

compare_and_swap (CAS): ritorna il valore originale di *value e lo sostituisce con new_value solo se *value == expected:

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected) *value = new_value;
    return temp;
}
// lock condiviso, inizializzato a 0
while (compare_and_swap(&lock, 0, 1) != 0) ;     // entra quando riesce a passare da 0 a 1
    sezione critica
lock = 0;

Stesso limite sull'attesa limitata, ma è la base di strumenti più flessibili: le variabili atomiche (aggiornamenti non interrompibili su interi e booleani) e i semafori. Per esempio increment(&sequence) si può realizzare con un ciclo di CAS: leggere il valore, calcolare il nuovo, riprovare finché CAS riesce (se *v cambia prima, ripete). Non risolvono tutti i problemi (per esempio quando una variabile è controllata da più processi).

Un lock realizzato con il vero test_and_set del C11 (atomic_flag):

spinlock_tas.cc

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>

#define ITER 200000

static atomic_flag lock = ATOMIC_FLAG_INIT;
static long contatore;

static void acquire(void)
{
    while (atomic_flag_test_and_set(&lock))   /* imposta a true e ritorna il vecchio valore */
        ;                                     /* spinlock: attesa attiva */
}

static void release(void)
{
    atomic_flag_clear(&lock);
}

static void *lavora(void *arg)
{
    (void)arg;
    for (int k = 0; k < ITER; k++) {
        acquire();
        contatore++;
        release();
    }
    return NULL;
}

int main(void)
{
    pthread_t a, b;
    pthread_create(&a, NULL, lavora, NULL);
    pthread_create(&b, NULL, lavora, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("contatore = %ld (atteso %d)\n", contatore, 2 * ITER);
    return 0;
}

Mutex lock

Le soluzioni precedenti sono complicate e inaccessibili al programmatore applicativo. Il sistema operativo offre quindi il mutex lock (mutual exclusion lock): un booleano che dice se il lock è disponibile; si protegge la sezione critica con acquire() prima e release() dopo. Le due operazioni devono essere atomiche (di solito realizzate con compare_and_swap).

Definizione (spinlock). Un mutex che aspetta con un ciclo (busy waiting, attesa attiva) è detto spinlock: il thread resta in esecuzione senza fare lavoro utile. Pregio: leggero e adatto quando l'attesa prevista è molto breve (niente cambio di contesto). Difetto: spreca CPU se l'attesa è lunga.

I mutex di sistema (come pthread_mutex_t) invece sospendono il thread che non ottiene il lock, mettendolo in una coda d'attesa. In POSIX:

funzione	uso
`pthread_mutex_init(&m, NULL)`	inizializza (o `PTHREAD_MUTEX_INITIALIZER`)
`pthread_mutex_lock(&m)`	blocca; se è già bloccato da un altro thread sospende il chiamante
`pthread_mutex_trylock(&m)`	come `lock` ma non blocca: se è occupato ritorna subito `EBUSY`
`pthread_mutex_unlock(&m)`	sblocca (deve essere chiamata dal thread proprietario)
`pthread_mutex_destroy(&m)`	libera le risorse (il mutex deve essere sbloccato)
`pthread_spinlock_t`	alternativa con attesa attiva (spreca CPU)

Il mutex ha due stati, libero o posseduto da un thread: non può mai essere posseduto da due thread insieme. Attenzione: per default un thread che chiama pthread_mutex_lock due volte sullo stesso mutex senza sbloccare lo blocca per sempre (deadlock con se stesso). Su Linux il mutex bloccato da un thread può essere sbloccato da un altro, ma non è lo standard POSIX e il comportamento è indefinito.

Il programma del laboratorio 3 corretto con un mutex: due thread incrementano e decrementano la stessa variabile sum.

somma_mutex.cc

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

static long sum;                                   /* dato condiviso */
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void *incrementa(void *param)
{
    long upper = atol(param);
    for (long i = 1; i <= upper; i++) {
        pthread_mutex_lock(&lock);                 /* entry section */
        sum++;                                     /* sezione critica */
        pthread_mutex_unlock(&lock);               /* exit section */
    }
    return NULL;
}

static void *decrementa(void *param)
{
    long upper = atol(param);
    for (long i = 1; i <= upper; i++) {
        pthread_mutex_lock(&lock);
        sum--;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main(int argc, char *argv[])
{
    if (argc != 2) {
        fprintf(stderr, "uso: %s N\n", argv[0]);
        return 1;
    }
    pthread_t t1, t2;
    pthread_create(&t1, NULL, incrementa, argv[1]);
    pthread_create(&t2, NULL, decrementa, argv[1]);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("sum = %ld\n", sum);                    /* sempre 0 */
    return 0;
}

Il risultato è sempre 0; senza mutex, per $N$ grande, sum è un valore diverso a ogni esecuzione (con -O0: l'ottimizzatore potrebbe altrimenti fondere le $N$ iterazioni e nascondere il problema). Si osserva anche che il mutex è molto più semplice e veloce della soluzione di Peterson con usleep.

Esercizi collegati

Domande d'esame

1. Elencare i tre requisiti della sezione critica e dire quali sono violati dall'alternanza stretta con la variabile turn. Traccia. Mutua esclusione, progresso, attesa limitata. L'alternanza stretta garantisce la mutua esclusione e l'attesa limitata, ma viola il progresso: un processo veloce non può rientrare se l'altro, lento, non ha ancora cambiato turn, anche con la sezione critica libera.

2. Perché la soluzione di Peterson può fallire su un processore moderno e come si ripara? Traccia. Compilatore e processore possono riordinare le istruzioni senza dipendenze (per esempio flag[i] = true e turn = j), facendo entrare insieme i due processi. Si ripara con barriere di memoria o variabili atomiche con ordinamento sequenziale.

3. Differenza tra spinlock e mutex con sospensione: quando si preferisce l'uno o l'altro? Traccia. Lo spinlock attende in un ciclo (busy waiting): nessun cambio di contesto, conviene per attese molto brevi su multiprocessore. Il mutex sospende il thread in una coda: non spreca CPU, conviene per attese lunghe o con un solo processore.

Versione ripasso

Race condition: più processi/thread sugli stessi dati, risultato dipendente dall'ordine degli accessi. counter++ e counter-- sono load, modifica, store; con counter=5 si ottiene 4, 5 o 6. Errore intermittente. Altro esempio: next_available_pid in fork.
Sezione critica: entry section, sezione critica, exit section, remainder section. Requisiti: mutua esclusione, progresso, attesa limitata.
Disabilitare gli interrupt: non scala (multiprocessori, sezioni lunghe, starvation). Alternanza con turn: mutua esclusione e attesa limitata sì, progresso no.
Peterson (2 processi): flag[2] + turn; flag[i]=true; turn=j; while(flag[j] && turn==j); ... flag[i]=false. Soddisfa i 3 requisiti, ma il riordino di istruzioni (compilatore/CPU) lo rompe: servono barriere di memoria o variabili atomiche C11 (seq_cst). Esempio: x=100; flag=true; riordinato -> si stampa 0.
Hardware: test_and_set (ritorna il vecchio valore e imposta true) e compare_and_swap (cambia solo se *value==expected), atomiche; soddisfano la mutua esclusione ma non l'attesa limitata. Variabili atomiche costruite con CAS (ciclo di retry).
Mutex lock: acquire/release atomici. Spinlock = attesa attiva (breve, nessun cambio di contesto); mutex di sistema = sospensione. POSIX: pthread_mutex_init/lock/trylock/unlock/destroy; trylock ritorna EBUSY; lock doppio = deadlock; unlock dal proprietario.
Test: sum++/sum-- senza mutex dà valori diversi; con mutex sempre 0 (compilare con -O0 per vedere l'errore). Rimandi: Semafori, monitor e problemi classici di sincronizzazione, Deadlock - condizioni, prevenzione, evitamento e rilevamento.
Tabella dell'intreccio (counter=5): prod reg1=counter (5), prod reg1=reg1+1 (6), cons reg2=counter (5), cons reg2=reg2-1 (4), prod counter=reg1 $\to$ 6, cons counter=reg2 $\to$ 4. Con le ultime due scambiate: 6. Il valore giusto, 5, esce solo se i due blocchi non si intrecciano.
Peterson, perché funziona: (1) mutua esclusione: $P_i$ entra solo se flag[j]==false o turn==i, e turn non vale 0 e 1 insieme; (2) progresso: se $P_j$ non vuole entrare, $P_i$ non aspetta; (3) attesa limitata: dopo l'uscita $P_j$ rimette turn=i e lascia passare $P_i$ al più dopo una sua entrata. Alternanza con turn: viola il progresso (il processo veloce attende quello lento anche a sezione libera).
Riordino, esempio: x=100; flag=true; riordinato in flag=true; x=100; $\to$ il lettore può stampare 0. Barriera di memoria: completa e rende visibili a tutti i processori letture e scritture precedenti prima delle successive; C11: atomic_* con memory_order_seq_cst.
Hardware: test_and_set(&lock): ritorna il vecchio valore e mette true; compare_and_swap(&v, expected, new): ritorna il vecchio valore e scrive new solo se *v==expected. Entrambi atomici, mutua esclusione ma non attesa limitata (starvation). Variabile atomica: increment come ciclo di CAS (rilegge e riprova se il valore è cambiato).

while (atomic_flag_test_and_set(&lock)) ;   /* acquire: spinlock */
contatore++;                                /* sezione critica */
atomic_flag_clear(&lock);                   /* release */

Mutex POSIX: pthread_mutex_init/lock/trylock/unlock/destroy; trylock non blocca (EBUSY); unlock va fatta dal thread proprietario; lock doppio dello stesso thread $\to$ blocco per sempre (mutex non ricorsivo). Spinlock (pthread_spinlock_t, attesa attiva): conviene per attese brevissime su multiprocessore, perché evita il cambio di contesto; il mutex di sistema sospende il thread.
Verifica pratica: sum++/sum-- con due thread: per $N$ piccolo spesso 0, per $N$ grande valori diversi a ogni esecuzione; con mutex sempre 0; compilare con -O0 per vedere l'errore (l'ottimizzatore può fondere il ciclo).
Requisiti, in una riga: mutua esclusione = al più uno dentro; progresso = chi decide non dipende dai processi nella remainder section e non rimanda per sempre; attesa limitata = un tetto alle entrate degli altri dopo la richiesta. Disabilitare gli interrupt: non scala (multiprocessori, sezioni lunghe, starvation).
Errori tipici: credere che counter++ sia atomico; Peterson senza barriere; pthread_mutex_lock due volte; unlock senza lock; dimenticare join; proteggere la scrittura ma non la lettura; mutex diversi per lo stesso dato.