Esercizio - Thread, race condition e parallelismo sui dati (laboratorio 3)

Testo (laboratorio 3 del corso di Sistemi Operativi, Ing. Informatica UniPD). Per gli esercizi di scheduling la macchina virtuale va configurata con una sola CPU (lscpu mostra il numero di CPU). Programmi C con POSIX Threads, compilati con -lpthread:

• Task 1 (threads.c): due thread incrementano e decrementano N volte una variabile condivisa sum (runner1: sum++, runner2: sum--). Provare con N = 100, 1000, 10000, 100000, ... Qual è l'output? Cambia? Perché?
• Task 2: risolvere la race condition senza mutex né semafori; scrivere threads_new.c e riprovare.
• Task 3: scrivere threads_data.c: parallelismo sui dati. Creare un array di $N$ interi e assegnare a ogni elemento $i$ il valore $i \cdot i$; l'assegnazione va fatta in parallelo da $M$ thread, ognuno responsabile di $N/M$ elementi.
• Task 4 (posix-scope.c): scope della contesa dei thread; che cosa stampa?

Teoria: Thread e concorrenza - modelli, Pthreads e goroutineUn thread è un flusso di esecuzione dentro un processo: ha program counter, registri e stack propri ma condivide codice, dati, heap e file aperti del processo, quindi costa meno di un processo (creazione e commutazione) e comunica più facilmente, ma i dati condivisi producono race condition; concorrenza (più compiti che avanzano, anche su un solo core) non è parallelismo (più compiti eseguiti nello stesso istante, serve più di un core); si distinguono parallelismo sui dati e sui compiti e la legge di Amdahl dà lo speedup massimo 1/(S+(1-S)/N) con S frazione seriale; i thread utente sono gestiti da una libreria, quelli kernel dal sistema, e i modelli many-to-one, one-to-one (Linux, Windows) e many-to-many li collegano; in C si usa Pthreads (pthread_create, pthread_join, pthread_exit), in Go le goroutine (parola chiave go, sync.WaitGroup, canali); questioni aperte: fork/exec con i thread, segnali, cancellazione (asincrona o differita), thread-local storage, contention scope (PCS e SCS).Thread e concorrenza - modelli, Pthreads e goroutine →, Sincronizzazione - sezione critica, race condition e mutexQuando più processi o thread accedono agli stessi dati e il risultato dipende dall'ordine degli accessi si ha una race condition (esempio: counter++ e counter-- sono tre istruzioni macchina ciascuna, e interleaving diversi danno 4, 5 o 6 partendo da 5); il problema della sezione critica chiede un protocollo (entry section, sezione critica, exit section, remainder section) che garantisca mutua esclusione, progresso e attesa limitata; disabilitare gli interrupt non scala sui multiprocessori, l'alternanza stretta con turn viola il progresso, la soluzione di Peterson (flag[2] e turn) soddisfa i tre requisiti ma può fallire su hardware moderno per il riordino delle istruzioni, per cui servono barriere di memoria; l'hardware offre test_and_set e compare_and_swap (atomiche) e variabili atomiche; il mutex lock (acquire/release, in POSIX pthread_mutex_t) è lo strumento di alto livello, con attesa attiva se è uno spinlock oppure con sospensione del thread se è un mutex di sistema; bloccare due volte lo stesso mutex senza sbloccarlo causa deadlock.Sincronizzazione - sezione critica, race condition e mutex →.

Task 1: la race condition

Il programma del corso (con la correzione di %ld per un long: il corso stampa con %d, formato errato per un long che stampa solo i 32 bit bassi):

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

static long sum;                               /* dato condiviso dai due thread */

static void *runner1(void *param)
{
    long upper = atol(param);
    for (long i = 1; i <= upper; i++)
        sum++;                                 /* lettura, somma, scrittura: NON atomico */
    pthread_exit(0);
}

static void *runner2(void *param)
{
    long upper = atol(param);
    for (long i = 1; i <= upper; i++)
        sum--;
    pthread_exit(0);
}

int main(int argc, char *argv[])
{
    if (argc != 2) {
        fprintf(stderr, "uso: %s N\n", argv[0]);
        return 1;
    }
    pthread_t tid1, tid2;
    pthread_create(&tid1, NULL, runner1, argv[1]);
    pthread_create(&tid2, NULL, runner2, argv[1]);
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    printf("sum = %ld\n", sum);
    return 0;
}

Risultati attesi (dipendono dalla macchina, dal compilatore e dal numero di core):

Perché. Se un thread finisce prima che parta l'altro (con $N$ piccolo la creazione di un thread impiega più tempo dei 100 giri del ciclo), non c'è sovrapposizione e il risultato è 0. Con $N$ grande i due thread girano insieme (su più core, o alternati dallo scheduler): sum++ e sum-- sono ciascuno tre istruzioni macchina (lettura, modifica, scrittura, Sincronizzazione - sezione critica, race condition e mutexQuando più processi o thread accedono agli stessi dati e il risultato dipende dall'ordine degli accessi si ha una race condition (esempio: counter++ e counter-- sono tre istruzioni macchina ciascuna, e interleaving diversi danno 4, 5 o 6 partendo da 5); il problema della sezione critica chiede un protocollo (entry section, sezione critica, exit section, remainder section) che garantisca mutua esclusione, progresso e attesa limitata; disabilitare gli interrupt non scala sui multiprocessori, l'alternanza stretta con turn viola il progresso, la soluzione di Peterson (flag[2] e turn) soddisfa i tre requisiti ma può fallire su hardware moderno per il riordino delle istruzioni, per cui servono barriere di memoria; l'hardware offre test_and_set e compare_and_swap (atomiche) e variabili atomiche; il mutex lock (acquire/release, in POSIX pthread_mutex_t) è lo strumento di alto livello, con attesa attiva se è uno spinlock oppure con sospensione del thread se è un mutex di sistema; bloccare due volte lo stesso mutex senza sbloccarlo causa deadlock.Sincronizzazione - sezione critica, race condition e mutex →) e gli aggiornamenti si perdono: un thread scrive un valore calcolato su una lettura vecchia. Il risultato è imprevedibile e cambia da esecuzione a esecuzione. Attenzione: compilando con ottimizzazione (-O2) il compilatore può tenere sum in un registro e fondere il ciclo (sum += N), nascondendo l'errore: per vederlo si compila con -O0.

Task 2: senza mutex né semafori

Due soluzioni, entrambe senza strumenti di sistema.

(a) Nessun dato condiviso modificato in concorrenza. Ogni thread accumula in una variabile propria e il main combina i risultati dopo i join:

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

static long parziale[2];                        /* un elemento per thread: nessuno scrive lo stesso */

struct arg { long upper; int segno; long *out; };

static void *lavora(void *p)
{
    struct arg *a = p;
    long locale = 0;                            /* variabile locale (sullo stack del thread) */
    for (long i = 1; i <= a->upper; i++)
        locale += a->segno;
    *a->out = locale;
    return NULL;
}

int main(int argc, char *argv[])
{
    if (argc != 2) {
        fprintf(stderr, "uso: %s N\n", argv[0]);
        return 1;
    }
    long n = atol(argv[1]);
    struct arg a1 = {n, +1, &parziale[0]}, a2 = {n, -1, &parziale[1]};
    pthread_t t1, t2;
    pthread_create(&t1, NULL, lavora, &a1);
    pthread_create(&t2, NULL, lavora, &a2);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("sum = %ld\n", parziale[0] + parziale[1]);   /* sempre 0 */
    return 0;
}

Risultato sempre 0, qualunque $N$, perché le uniche scritture concorrenti sono su elementi diversi di un array e il main legge dopo i join.

(b) Alternanza stretta con una variabile turn (attesa attiva, v. soluzione di Peterson in Esercizio - Peterson, mutex e lettori-scrittori con i thread (laboratorio 4)): il thread $i$ modifica sum solo quando turn == i. È corretta ma lenta (i due thread devono alternarsi a ogni iterazione) e viola il requisito di progresso; la soluzione di Peterson la migliora.

Task 3: parallelismo sui dati

Si divide l'array in $M$ intervalli contigui; ogni thread riceve (come argomento) il proprio intervallo semiaperto $[\text{da}, \text{a})$ e scrive solo i propri elementi: nessuna race condition, perché i thread non toccano mai lo stesso elemento.

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

#define N 100                           /* elementi dell'array */
#define M 4                             /* thread */

static int array[N];                    /* dato condiviso: ogni thread scrive solo la sua parte */

struct intervallo { int da, a; };       /* [da, a) */

static void *runner(void *param)
{
    const struct intervallo *r = param;
    for (int i = r->da; i < r->a; i++)  /* a esclusivo! */
        array[i] = i * i;
    return NULL;
}

int main(void)
{
    pthread_t tid[M];
    struct intervallo r[M];             /* un argomento per thread, che vive finche' i thread girano */
    int base = N / M, resto = N % M, inizio = 0;

    for (int k = 0; k < M; k++) {
        int len = base + (k < resto ? 1 : 0);        /* distribuisce anche il resto */
        r[k].da = inizio;
        r[k].a = inizio + len;
        inizio += len;
        pthread_create(&tid[k], NULL, runner, &r[k]);
    }
    for (int k = 0; k < M; k++)
        pthread_join(tid[k], NULL);

    for (int i = 0; i < N; i++)
        if (array[i] != i * i) {
            printf("errore in posizione %d\n", i);
            return 1;
        }
    printf("array verificato: array[5] = %d, array[%d] = %d\n", array[5], N - 1, array[N - 1]);
    return 0;
}

Errore nella soluzione del corso. La soluzione del corso (threads_data.c) usa due intervalli {0, ARRAY_SIZE/2} e {ARRAY_SIZE/2, ARRAY_SIZE} ma il ciclo è for (i = range[0]; i <= range[1]; i++) (<=): il secondo thread arriva fino a array[ARRAY_SIZE], cioè una posizione oltre la fine dell'array (scrittura fuori dai limiti, comportamento indefinito), e l'elemento 50 è scritto da entrambi i thread (stesso valore, quindi innocuo). Con intervalli semiaperti i < range[1] il problema scompare. Inoltre, gli argomenti passati ai thread devono vivere finché i thread girano: qui r[M] sta nel main, che aspetta con i join.

Task 4: scope della contesa

posix-scope.c chiede con pthread_attr_getscope lo scope di default degli attributi e stampa PTHREAD_SCOPE_PROCESS o PTHREAD_SCOPE_SYSTEM; poi lo imposta a PTHREAD_SCOPE_SYSTEM e crea 5 thread. Su Linux l'output è PTHREAD_SCOPE_SYSTEM: Linux (e macOS) supportano solo lo scope di sistema (system-contention scope, i thread kernel competono con tutti i thread del sistema); richiedere PTHREAD_SCOPE_PROCESS con pthread_attr_setscope fallirebbe con ENOTSUP. È il modello one-to-one (Thread e concorrenza - modelli, Pthreads e goroutineUn thread è un flusso di esecuzione dentro un processo: ha program counter, registri e stack propri ma condivide codice, dati, heap e file aperti del processo, quindi costa meno di un processo (creazione e commutazione) e comunica più facilmente, ma i dati condivisi producono race condition; concorrenza (più compiti che avanzano, anche su un solo core) non è parallelismo (più compiti eseguiti nello stesso istante, serve più di un core); si distinguono parallelismo sui dati e sui compiti e la legge di Amdahl dà lo speedup massimo 1/(S+(1-S)/N) con S frazione seriale; i thread utente sono gestiti da una libreria, quelli kernel dal sistema, e i modelli many-to-one, one-to-one (Linux, Windows) e many-to-many li collegano; in C si usa Pthreads (pthread_create, pthread_join, pthread_exit), in Go le goroutine (parola chiave go, sync.WaitGroup, canali); questioni aperte: fork/exec con i thread, segnali, cancellazione (asincrona o differita), thread-local storage, contention scope (PCS e SCS).Thread e concorrenza - modelli, Pthreads e goroutine →).

Compilati con zig cc -Wall -Wextra -Wpedantic per Linux senza avvisi (il threads.c originale del corso ha l'avviso sul formato %d); non eseguiti qui (binari Linux).

Domande d'esame

Perché con $N = 100$ il programma sembra corretto e con $N = 10^6$ no? Traccia. Con $N$ piccolo un thread può finire prima che l'altro cominci: nessuna sovrapposizione. Con $N$ grande si sovrappongono e sum++/sum--, non atomiche, perdono aggiornamenti. Il bug esiste sempre, ma è intermittente.