Esercizio - Spogliatoi e cesti della piscina (eserciziario, esercizio 9)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 9). Problema della sincronizzazione degli arrivi e partenze dei nuotatori in una piscina. Ci sono due classi di risorse, entrambe in numero limitato: $n$ spogliatoi (cabine) e $k$ cesti in cui depositare gli abiti (in genere $n < k$). La procedura per ogni utente:

1. trovare uno spogliatoio libero;
2. reperire un cesto per la biancheria;
3. riporre i propri abiti;
4. lasciare lo spogliatoio e depositare il cesto al personale;
5. nuotare (la piscina ha ricettività illimitata);
6. recuperare il proprio cesto dalla biancheria;
7. trovare uno spogliatoio libero;
8. rivestirsi (e lasciare lo spogliatoio, riconsegnando il cesto).

Si descriva una soluzione che garantisca la mutua esclusione per l'accesso alle risorse; si verifichi la presenza di stallo nella soluzione proposta e si evidenzi se e come può avvenire. Suggerimento: usare due semafori contatori, opportunamente inizializzati, per l'accesso alle risorse. Teoria: 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 →, 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 →.

Soluzione del corso (con deadlock)

Due semafori contatori: cab = n (cabine libere) e bas = k (cesti liberi).

wait(cab);        // 1) trova una cabina
   cambiarsi;
wait(bas);        // 2) prende un cesto
   riempire il cesto;
signal(cab);      // 4) lascia la cabina
   nuotare;
wait(cab);        // 7) trova una cabina
   svuotare il cesto;
signal(bas);      // restituisce il cesto
   rivestirsi;
signal(cab);

Il deadlock è possibile. Un nuovo arrivato occupa una cabina ma deve aspettare un cesto libero. Se tutti i $k$ cesti sono in mano a nuotatori in acqua e $n$ nuovi arrivati occupano tutte le cabine aspettando un cesto, nessuno di questi può proseguire; i nuotatori vogliono rientrare ma non trovano una cabina in cui rivestirsi (tutte occupate) e quindi non restituiscono mai i cesti: attesa circolare tra cabine (tenute dagli arrivati che aspettano un cesto) e cesti (tenuti dai nuotatori che aspettano una cabina). Valgono tutte e quattro le condizioni di Coffman.

Soluzione senza deadlock

Si nega l'hold and wait per i nuovi arrivati: un arrivato prende prima il cesto e poi la cabina, così chi occupa una cabina ha già tutto quello che gli serve per finire il turno nella cabina e non aspetta più nulla. È anche un ordinamento totale delle risorse (cesto prima, poi cabina), seguito da tutti: i nuotatori che rientrano tengono già il cesto e chiedono la cabina.

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

#define N_CABINE 2
#define K_CESTI  4
#define UTENTI   8

static sem_t cab, bas;

static void *utente(void *arg)
{
    long id = (long)arg;
    sem_wait(&bas);                       /* prima il cesto: chi e' in cabina non aspetta piu' nulla */
    sem_wait(&cab);                       /* cabina per cambiarsi */
    printf("utente %ld: si cambia, riempie il cesto\n", id);
    usleep(1000);
    sem_post(&cab);                       /* lascia la cabina (tiene il cesto) */

    usleep(3000);                         /* nuota */

    sem_wait(&cab);                       /* cabina per rivestirsi: il cesto e' gia' suo */
    printf("utente %ld: si riveste\n", id);
    usleep(1000);
    sem_post(&cab);
    sem_post(&bas);                       /* riconsegna il cesto */
    return NULL;
}

int main(void)
{
    pthread_t t[UTENTI];
    sem_init(&cab, 0, N_CABINE);
    sem_init(&bas, 0, K_CESTI);
    for (long i = 0; i < UTENTI; i++)
        pthread_create(&t[i], NULL, utente, (void *)i);
    for (int i = 0; i < UTENTI; i++)
        pthread_join(t[i], NULL);
    printf("tutti usciti\n");
    return 0;
}

Perché non si blocca. Al più $k$ utenti sono "dentro" (tengono un cesto), perché gli altri aspettano il cesto senza tenere una cabina. Chi tiene una cabina ha già il cesto, e l'unica cosa che fa è cambiarsi e lasciarla: quindi le cabine vengono sempre liberate, e chi aspetta una cabina (arrivati o nuotatori che rientrano) prima o poi la ottiene. Non c'è nessuna attesa circolare. Dopo l'uso del cesto, il processo lo restituisce, svegliando un arrivato in attesa. Il programma è stato compilato senza avvisi (non eseguito qui).

Alternativa. Mantenere l'ordine originale ma riservare una cabina ai nuotatori che escono con un semaforo aggiuntivo (le cabine disponibili per gli arrivati sono al più $n - 1$): evita il deadlock ma riduce l'uso delle cabine.

Domande d'esame

Qual è la condizione di deadlock nella soluzione ingenua e come si previene? Traccia. Hold and wait: gli arrivati tengono una cabina mentre aspettano un cesto, e i nuotatori che tengono i cesti aspettano una cabina. Si previene chiedendo prima il cesto e poi la cabina, oppure riservando una cabina alle uscite.