Esercizio - Deadlock con semafori e thread (laboratorio 6)

Testo (laboratorio 6 del corso di Sistemi Operativi, Ing. Informatica UniPD). Due programmi C con thread e semafori POSIX che si bloccano in deadlock:

• Task 1 (deadlock1.c): due thread e due semafori $S_1, S_2$ (valore 1). Il thread $A$ fa wait(sem1), poi wait(sem2); il thread $B$ fa wait(sem2), poi wait(sem1). Verificare che il programma si blocca e rimuovere il deadlock cambiando l'uso dei semafori.
• Task 2 (deadlock2.c): tre thread e tre semafori che rappresentano risorse: $R_1$ (1 istanza), $R_2$ (2 istanze), $R_3$ (1 istanza). Il grafo di partenza: $T_1$ possiede un'istanza di $R_2$ e richiede $R_1$; $T_2$ possiede $R_1$ e un'istanza di $R_2$ e richiede $R_3$; $T_3$ possiede $R_3$ e richiede $R_2$. Verificare il deadlock e rimuoverlo cambiando l'allocazione iniziale, per esempio in modo che i thread terminino nell'ordine $T_1, T_3, T_2$.
• I Task 3 e 4 (banchiere) sono in Esercizio - Implementare il banchiere e calcolarne la complessità (eserciziario, esercizio 3 e laboratorio 6).

Teoria: Deadlock - condizioni, prevenzione, evitamento e rilevamentoUn deadlock (stallo) è una situazione in cui un insieme di processi attende all'infinito risorse possedute da altri processi dello stesso insieme; può verificarsi solo se valgono insieme quattro condizioni (mutua esclusione, hold and wait, assenza di prelazione, attesa circolare); il grafo di allocazione delle risorse (archi di richiesta P->R e di assegnazione R->P) senza cicli esclude lo stallo, con un ciclo lo implica se ogni risorsa ha una sola istanza, e lo rende solo possibile se ha più istanze; si può prevenire (negare una delle quattro condizioni, per esempio ordinare le risorse per negare l'attesa circolare), evitare (stato sicuro: esiste una sequenza sicura; algoritmo del grafo con archi di rivendicazione per istanza singola, algoritmo del banchiere con Available, Max, Allocation, Need = Max - Allocation e complessità O(m n^2) per istanze multiple), rilevare e ripristinare (grafo wait-for per istanza singola, algoritmo di rilevamento per istanze multiple; terminazione dei processi o prelazione delle risorse con scelta della vittima e rollback), oppure ignorare.Deadlock - condizioni, prevenzione, evitamento e rilevamento →, 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 →. Compilazione: gcc deadlockN.c -o deadlockN -lpthread.

Task 1: attesa circolare tra due semafori

Il codice originale:

void* threadA(void* arg) { sem_wait(&sem1); sleep(1); sem_wait(&sem2); ... sem_post(&sem2); sem_post(&sem1); }
void* threadB(void* arg) { sem_wait(&sem2); sleep(1); sem_wait(&sem1); ... sem_post(&sem1); sem_post(&sem2); }

Perché si blocca: il sleep(1) dà tempo a entrambi di prendere il primo semaforo. Allora $A$ possiede $S_1$ e aspetta $S_2$, $B$ possiede $S_2$ e aspetta $S_1$: valgono tutte e quattro le condizioni di Coffman (mutua esclusione: semafori binari; hold and wait; nessuna prelazione; attesa circolare $A \to S_2 \to B \to S_1 \to A$). Il join nel main non ritorna mai.

Correzione (quella del corso). Si nega l'attesa circolare con un ordine totale sulle risorse: entrambi i thread prendono prima $S_1$ e poi $S_2$. Il codice (con la stessa struttura) è:

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

static sem_t sem1, sem2;

static void *threadA(void *arg)
{
    (void)arg;
    sem_wait(&sem1);                       /* ordine: sempre sem1 prima di sem2 */
    printf("[A] prima sezione critica...\n");
    sleep(1);
    sem_wait(&sem2);
    printf("[A] seconda sezione critica...\n");
    sleep(1);
    sem_post(&sem2);
    sem_post(&sem1);
    return NULL;
}

static void *threadB(void *arg)
{
    (void)arg;
    sem_wait(&sem1);                       /* stesso ordine di A: niente attesa circolare */
    printf("[B] prima sezione critica...\n");
    sleep(1);
    sem_wait(&sem2);
    printf("[B] seconda sezione critica...\n");
    sleep(1);
    sem_post(&sem2);
    sem_post(&sem1);
    return NULL;
}

int main(void)
{
    pthread_t tA, tB;
    sem_init(&sem1, 0, 1);
    sem_init(&sem2, 0, 1);
    pthread_create(&tA, NULL, threadA, NULL);
    pthread_create(&tB, NULL, threadB, NULL);
    pthread_join(tA, NULL);
    pthread_join(tB, NULL);
    sem_destroy(&sem1);
    sem_destroy(&sem2);
    return 0;
}

Ora il thread che arriva per secondo si ferma già alla wait(sem1) senza possedere nulla: non c'è hold and wait che chiuda un ciclo. Il programma stampa le sezioni di $A$ e poi quelle di $B$ (o viceversa) e termina in circa 4 secondi.

Altre soluzioni (nel corso viene citata solo la prima): rilasciare $S_1$ prima di prendere $S_2$ (se la logica lo permette, nega hold and wait); usare sem_trywait sul secondo semaforo e, se fallisce, rilasciare il primo e riprovare (nega l'assenza di prelazione, con rischio di livelock); un unico semaforo che protegge entrambe le sezioni.

Task 2: più istanze, grafo di allocazione

Il programma originale usa tre semafori inizializzati a 1, 2 e 1 come risorse. Ogni thread prende prima le risorse che il grafo dice che possiede, poi (dopo un sleep(1)) chiede la rimanente:

Perché si blocca. Dopo le wait iniziali: $R_1 = 0$ (di $T_2$), $R_2 = 0$ (una istanza a $T_1$, una a $T_2$), $R_3 = 0$ (di $T_3$). Poi $T_1$ chiede $R_1$ (posseduta da $T_2$), $T_2$ chiede $R_3$ (da $T_3$), $T_3$ chiede $R_2$ (finite le istanze, in mano a $T_1$ e $T_2$): ciclo $T_1 \to R_1 \to T_2 \to R_3 \to T_3 \to R_2 \to T_1$ (e $T_2$). Nel grafo con $R_2$ a due istanze è deadlock perché le due istanze di $R_2$ sono possedute da processi del ciclo ($T_1$ e $T_2$).

Il grafo è lo stesso dell'algoritmo del banchiere: Available $= (0,0,0)$, e con Max $=$ Allocation $+$ richiesta: $T_1$: alloc $(0,1,0)$ max $(1,1,0)$; $T_2$: alloc $(1,1,0)$ max $(1,1,1)$; $T_3$: alloc $(0,0,1)$ max $(0,1,1)$. Sono esattamente le matrici del programma banker.c del Task 3, che risulta UNSAFE: nessun processo può finire.

Correzione del corso. Si cambia l'allocazione iniziale: $T_1$ prende $R_2$ e $R_1$ all'inizio (poi non chiede più nulla); $T_2$ prende solo $R_2$ all'inizio e dopo il sleep chiede $R_3$ e $R_1$; $T_3$ resta com'era ($R_3$, poi chiede $R_2$). Stato iniziale: $T_1$ ha $(R_1, R_2)$, $T_2$ ha $R_2$, $T_3$ ha $R_3$; Available $= (0,0,0)$. Evoluzione:

1. $T_1$ non chiede altro: termina e libera $R_2$ e $R_1$;
2. ora $T_3$ può ottenere un'istanza di $R_2$ (una libera): termina e libera $R_2$ e $R_3$;
3. $T_2$ ottiene $R_3$ e $R_1$: termina.

Ordine di terminazione $T_1, T_3, T_2$, come richiesto: sequenza sicura $\langle T_1, T_3, T_2 \rangle$. Il codice:

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

static sem_t R1, R2, R3;

static void *T1_run(void *arg)
{
    (void)arg;
    sem_wait(&R2);                  /* possiede R2 e R1 fin dall'inizio */
    sem_wait(&R1);
    printf("T1 running...\n");
    sleep(1);
    printf("T1 completed.\n");
    sem_post(&R2);
    sem_post(&R1);
    return NULL;
}

static void *T2_run(void *arg)
{
    (void)arg;
    sem_wait(&R2);                  /* all'inizio possiede solo R2 */
    printf("T2 running...\n");
    sleep(1);
    sem_wait(&R3);                  /* poi chiede R3 e R1 */
    sem_wait(&R1);
    printf("T2 completed.\n");
    sem_post(&R3);
    sem_post(&R2);
    sem_post(&R1);
    return NULL;
}

static void *T3_run(void *arg)
{
    (void)arg;
    sem_wait(&R3);                  /* come nel programma originale */
    printf("T3 running...\n");
    sleep(1);
    sem_wait(&R2);
    printf("T3 completed.\n");
    sem_post(&R2);
    sem_post(&R3);
    return NULL;
}

int main(void)
{
    pthread_t T1, T2, T3;
    sem_init(&R1, 0, 1);
    sem_init(&R2, 0, 2);            /* due istanze */
    sem_init(&R3, 0, 1);
    pthread_create(&T1, NULL, T1_run, NULL);
    pthread_create(&T2, NULL, T2_run, NULL);
    pthread_create(&T3, NULL, T3_run, NULL);
    pthread_join(T1, NULL);
    pthread_join(T2, NULL);
    pthread_join(T3, NULL);
    sem_destroy(&R1);
    sem_destroy(&R2);
    sem_destroy(&R3);
    return 0;
}

Verifica esaustiva. I thread non partono in un ordine garantito, quindi la correttezza non può dipendere dalla fortuna. Modellando i tre thread come sequenze di wait e post ed enumerando tutti i possibili intrecci, la versione corretta completa in ognuno dei 601 intrecci possibili senza mai bloccarsi, mentre il programma originale ha intrecci che finiscono in deadlock (ed è quello che succede sempre in pratica, perché lo sleep(1) dà a tutti il tempo di prendere le prime risorse). Per il Task 1 si trova lo stesso: l'originale ha un intreccio bloccante ($A$ prende $S_1$ e $B$ prende $S_2$), la versione con ordine uguale non ne ha.

I due programmi sono stati compilati con zig cc -Wall -Wextra -Wpedantic per Linux senza avvisi; per il resto la correttezza è stata verificata con il banchiere e con l'enumerazione degli intrecci (i binari Linux non vengono eseguiti qui). Il codice originale del corso ha invece 3 avvisi -Wextra per l'argomento arg inutilizzato nelle funzioni dei thread.

Domande d'esame

Come si rimuove il deadlock del Task 1 senza cambiare il numero di semafori? Quale condizione di Coffman si nega? Traccia. Si impone lo stesso ordine di acquisizione ai due thread ($S_1$ poi $S_2$): si nega l'attesa circolare con un ordine totale delle risorse.