Esercizio - Peterson, mutex e lettori-scrittori con i thread (laboratorio 4)

Testo (laboratorio 4 del corso di Sistemi Operativi, Ing. Informatica UniPD).

• Task 1. Riprendere threads.c del laboratorio 3 (due thread che fanno sum++ e sum--) e risolvere la race condition con la soluzione di Peterson; salvare threads_peterson.c. Si può aggiungere una piccola pausa (usleep(n)) nel ciclo di attesa per non restare bloccati in attesa attiva.
• Task 2. simple_mutex.c: due thread fanno ciascuno una sezione critica protetta da un pthread_mutex_t. C'è race condition? Provare a togliere lock/unlock. Poi rimettere i due e aggiungere una seconda pthread_mutex_lock(&lock): cosa succede? perché?
• Task 3. Risolvere lo stesso problema di threads.c con un mutex; salvare threads_mutex.c. Confronto con Peterson.
• Task 4. multithreads.c: tre thread, uno scrittore e due lettori, condividono una variabile book. In ogni istante il libro deve essere scritto da uno scrittore oppure letto da uno o più lettori (anche insieme). Modificare il programma (provando con un mutex) in modo che book sia solo scritto o solo letto; salvare multithreads_new.c.

Teoria: 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 →. Compilazione: gcc file.c -o file -lpthread.

Task 1: Peterson per due thread

Condivisi: flag[2] e turn. Il thread $i$ (con $j$ l'altro) esegue prima di ogni sezione critica: flag[i] = true; turn = j; while (flag[j] && turn == j) ; e dopo flag[i] = false;. La soluzione del corso li scrive come variabili normali con usleep(1) nell'attesa; funziona su molte macchine ma non è garantita: il compilatore può tenere flag e turn in registri (il ciclo diventerebbe infinito) e il processore può riordinare scritture e letture (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 →). La versione corretta usa variabili atomiche C11 (che comprendono le barriere di memoria):

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

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

static void entra(int i)
{
    int j = 1 - i;
    atomic_store(&flag[i], 1);                 /* voglio entrare */
    atomic_store(&turn, j);                    /* ma cedo il turno all'altro */
    while (atomic_load(&flag[j]) && atomic_load(&turn) == j)
        usleep(1);                             /* attesa (con una piccola pausa) */
}

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

static void *runner(void *param)
{
    long *p = param;                            /* p[0] = N, p[1] = indice del thread */
    int i = (int)p[1];
    for (long k = 1; k <= p[0]; k++) {
        entra(i);
        sum += (i == 0) ? 1 : -1;               /* sezione critica */
        esci(i);
    }
    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]);
    long a0[2] = {n, 0}, a1[2] = {n, 1};
    pthread_t t0, t1;
    pthread_create(&t0, NULL, runner, a0);
    pthread_create(&t1, NULL, runner, a1);
    pthread_join(t0, NULL);
    pthread_join(t1, NULL);
    printf("sum = %ld\n", sum);                 /* sempre 0 */
    return 0;
}

Risultato: sum = 0 per ogni $N$ (anche se per $N$ grande il programma è molto lento: ogni iterazione richiede un'attesa attiva e una pausa).

Task 2: simple_mutex

Due thread eseguono runner: pthread_mutex_lock(&lock), stampano START critical section of Thread <id>, un ciclo di 1000 usleep(10), stampano END ..., pthread_mutex_unlock(&lock).

• Con il mutex: non c'è race condition. L'output è sempre START T1, END T1, START T2, END T2 (o con i thread scambiati): le due sezioni critiche non si intrecciano, perché il secondo thread aspetta (sospeso) che il primo faccia unlock.
• Senza lock/unlock: gli output si mescolano: START T1, START T2, END T1, END T2: entrambi sono "dentro" insieme.
• Con una seconda pthread_mutex_lock(&lock) consecutiva: il programma si blocca per sempre. Il mutex di default non è ricorsivo: il thread che lo possiede e lo richiede di nuovo si mette in attesa di se stesso (deadlock con se stesso), e anche l'altro thread resta bloccato. Si vedrebbe START di un solo thread e nessun END. (Esiste il tipo PTHREAD_MUTEX_RECURSIVE che lo permette.)

Task 3: soluzione con mutex

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

static long sum;
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);
        sum++;
        pthread_mutex_unlock(&lock);
    }
    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);
    return 0;
}

Confronto. Il risultato è sempre 0 come con Peterson, ma il codice è molto più semplice, più veloce (il thread bloccato dorme invece di girare a vuoto) e vale per un numero qualunque di thread (Peterson è definito per due). Nota del corso: su Linux un mutex preso da un thread può essere rilasciato da un altro, ma lo standard POSIX non lo garantisce: il comportamento è indefinito.

Task 4: lo scrittore e due lettori

multithreads.c ha tre thread: writer (incrementa book, stampa written) e due reader (copiano book in page, stampano read), ciascuno in un ciclo infinito. Senza protezione un lettore può leggere mentre lo scrittore sta modificando.

Con un mutex (soluzione semplice): il mutex protegge sia la scrittura sia la lettura. Ne risulta mutua esclusione completa: o scrive lo scrittore o legge un lettore. È corretta ma troppo restrittiva: i lettori non possono leggere insieme (e il testo permette più lettori contemporanei).

Con un lock lettori-scrittori (pthread_rwlock_t): più lettori insieme, lo scrittore da solo. È lo schema dei lettori-scrittori (Semafori, monitor e problemi classici di sincronizzazioneUn semaforo è un intero accessibile solo con due operazioni atomiche, wait (P: aspetta finché S > 0 e decrementa) e signal (V, in POSIX sem_post: incrementa); il semaforo contatore ha valori illimitati, quello binario vale 0 o 1; con valore iniziale 1 realizza la mutua esclusione, con valore iniziale 0 impone un ordine di esecuzione (S1 prima di S2); senza attesa attiva ogni semaforo ha una coda di processi sospesi (sleep e wakeup); i semafori si usano male con facilità (ordine sbagliato, omissioni); il monitor è un tipo di dato astratto in cui un solo processo alla volta è attivo e le variabili condizione x.wait()/x.signal() sospendono e risvegliano (in POSIX mutex più pthread_cond_t); le anomalie di liveness sono deadlock, starvation e inversione di priorità; i problemi classici sono produttore-consumatore a buffer limitato (mutex, vuote = n, piene = 0; l'ordine delle wait è importante), lettori-scrittori (rw_mutex, mutex, read_count; i lettori possono far morire di fame gli scrittori) e filosofi a cena (la soluzione ingenua con un semaforo per bacchetta va in deadlock; si evita limitando a n-1 filosofi, rompendo la simmetria o ordinando le risorse), con soluzioni in C (POSIX) e in Go (canali e sync).Semafori, monitor e problemi classici di sincronizzazione →). Versione limitata a 5 giri per poter terminare:

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

#define GIRI 5

static unsigned char book = 'a';
static pthread_rwlock_t rw = PTHREAD_RWLOCK_INITIALIZER;

static void *writer(void *arg)
{
    (void)arg;
    for (int i = 0; i < GIRI; i++) {
        pthread_rwlock_wrlock(&rw);            /* accesso esclusivo */
        book++;
        printf("written: %c\n", book);
        pthread_rwlock_unlock(&rw);
        usleep(1000);
    }
    return NULL;
}

static void *reader(void *arg)
{
    (void)arg;
    for (int i = 0; i < GIRI; i++) {
        pthread_rwlock_rdlock(&rw);            /* piu' lettori insieme */
        unsigned char page = book;
        printf("read: %c\n", page);
        pthread_rwlock_unlock(&rw);
        usleep(1000);
    }
    return NULL;
}

int main(void)
{
    pthread_t w, r1, r2;
    pthread_create(&w, NULL, writer, NULL);
    pthread_create(&r1, NULL, reader, NULL);
    pthread_create(&r2, NULL, reader, NULL);
    pthread_join(w, NULL);
    pthread_join(r1, NULL);
    pthread_join(r2, NULL);
    return 0;
}

Per usare un semplice mutex basta sostituire rdlock/wrlock con pthread_mutex_lock (e unlock con pthread_mutex_unlock): le tre righe di lettura e di scrittura diventano sezioni critiche esclusive. La versione con i semafori (Task 4 del laboratorio 5, multithreads_sem.c) è nell'Esercizio - Semafori POSIX, thread e processi (laboratorio 5).

Tutti i programmi sono compilati con zig cc -Wall -Wextra -Wpedantic per Linux senza avvisi; non sono eseguiti qui.

Domande d'esame

Perché la soluzione di Peterson scritta con variabili ordinarie può non funzionare oggi? Traccia. Riordino delle istruzioni da parte di compilatore e processore e cache non coerenti: servono variabili atomiche o barriere di memoria.

Cosa succede con due pthread_mutex_lock consecutive sullo stesso mutex dello stesso thread? Traccia. Deadlock con se stesso: il mutex di default non è ricorsivo.