Esercizio - Bagno condiviso e piazza dei tifosi con due categorie (eserciziario, esercizi 12 e 18)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizi 12 e 18).

Esercizio 12. Nella Facoltà di Ingegneria c'è un solo locale destinato ai servizi igienici. Il locale è condiviso da tutti gli studenti, uomini e donne, con la regola che in ogni istante l'intero locale può essere utilizzato esclusivamente da persone dello stesso sesso (ma con capacità illimitata!). Utilizzando semafori, simulare un protocollo di accesso (ingresso/uscita) per sincronizzare i possibili utenti del locale (si cerchi di evitare la starvation).

Esercizio 18. Dopo la finale del Campionato del Mondo di Calcio del 2006 (Italia-Francia), la polizia tedesca deve dirigere i tifosi alle stazioni ferroviarie evitando che gruppi di nazioni diverse vengano a contatto. Ogni volta che i gruppi di tifosi devono attraversare una piazza, il capo della polizia decide che:

• se la piazza è libera, può essere attraversata da qualunque tifoso;
• se nella piazza c'è almeno un tifoso italiano, nessun tifoso francese può attraversarla;
• se nella piazza c'è almeno un tifoso francese, nessun tifoso italiano può attraversarla.

Si implementi una soluzione mediante semafori (in pseudo-codice) per i processi italiano e francese. Suggerimento: tre semafori per una soluzione simmetrica.

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 →. Sono lo stesso schema: due categorie di processi che non possono stare insieme nella stessa risorsa, ma più processi della stessa categoria sì (come i lettori, con due categorie "lettori").

Schema: l'interruttore di categoria (lightswitch)

La soluzione 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 →) generalizza a due categorie simmetriche. Per ogni categoria un contatore e un mutex: il primo della categoria che entra prende la risorsa stanza; l'ultimo che esce la rilascia.

Esercizio 18: soluzione del corso

Variabili: int ita = 0, fra = 0; semaphore mutex1 = 1, mutex2 = 1, piazza = 1;

italiano():                               francese():
    wait(mutex1);                             wait(mutex2);
    ita++;                                    fra++;
    if (ita == 1) wait(piazza);               if (fra == 1) wait(piazza);
    signal(mutex1);                           signal(mutex2);
    attraversa();                             attraversa();
    wait(mutex1);                             wait(mutex2);
    ita--;                                    fra--;
    if (ita == 0) signal(piazza);             if (fra == 0) signal(piazza);
    signal(mutex1);                           signal(mutex2);

Il primo italiano blocca la piazza ai francesi; gli italiani successivi entrano senza aspettare (ita > 1); l'ultimo italiano a uscire riapre la piazza. Mutua esclusione tra categorie garantita da piazza; i contatori sono protetti da mutex1 e mutex2. Come per i lettori, c'è starvation possibile: se arrivano italiani senza sosta, la piazza non si libera mai per i francesi.

Esercizio 12: bagno senza starvation

Si usa lo stesso schema per uomini e donne, con in più un tornello (semaforo tornello = 1) che impone un minimo di equità. Ogni persona fa wait(tornello) prima di entrare e signal(tornello) dopo aver "registrato" il suo ingresso:

entra(categoria c):
    wait(tornello);              // un solo "richiedente" alla volta supera questo punto
    wait(mutex[c]);
    n[c]++;
    if (n[c] == 1) wait(bagno);  // il primo della categoria prende il bagno
    signal(mutex[c]);
    signal(tornello);
    ...usa il bagno...
    wait(mutex[c]);
    n[c]--;
    if (n[c] == 0) signal(bagno);
    signal(mutex[c]);

Perché evita la starvation: se un uomo arriva mentre il bagno è occupato da donne, resta bloccato dentro wait(bagno) tenendo il tornello; di conseguenza anche le donne che arrivano dopo si fermano al tornello e non possono entrare. Le donne già dentro escono, n[donne] torna a 0, bagno viene rilasciato, entra l'uomo (e dopo di lui gli uomini accodati al tornello); poi il turno passa alle donne in attesa. Nessuna categoria può essere esclusa per sempre da un flusso continuo dell'altra. Semafori con coda FIFO garantiscono l'ordine di sblocco.

Programma C completo e compilabile (con una breve simulazione di 6 persone di categorie diverse):

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

#define PERSONE 8

static sem_t tornello, bagno, mutex[2];
static int n[2];                          /* contatore dei richiedenti per categoria (protetto da mutex[c]) */
static atomic_int dentro[2];              /* persone che sono davvero nel bagno (solo per la verifica) */

static void entra(int c)
{
    sem_wait(&tornello);
    sem_wait(&mutex[c]);
    if (++n[c] == 1)
        sem_wait(&bagno);                 /* il primo della categoria blocca l'altra */
    sem_post(&mutex[c]);
    sem_post(&tornello);
}

static void esci(int c)
{
    sem_wait(&mutex[c]);
    if (--n[c] == 0)
        sem_post(&bagno);                 /* l'ultimo riapre il bagno */
    sem_post(&mutex[c]);
}

static void *persona(void *arg)
{
    long id = (long)arg;
    int c = (int)(id % 2);                /* 0 = uomo, 1 = donna */
    usleep((useconds_t)(id * 300));
    entra(c);
    atomic_fetch_add(&dentro[c], 1);
    printf("%s %ld dentro (uomini %d, donne %d)\n", c ? "donna" : "uomo", id,
           atomic_load(&dentro[0]), atomic_load(&dentro[1]));
    if (atomic_load(&dentro[1 - c]) != 0)
        printf("ERRORE: categorie miste\n");
    usleep(2000);
    atomic_fetch_sub(&dentro[c], 1);
    esci(c);
    return NULL;
}

int main(void)
{
    pthread_t t[PERSONE];
    sem_init(&tornello, 0, 1);
    sem_init(&bagno, 0, 1);
    sem_init(&mutex[0], 0, 1);
    sem_init(&mutex[1], 0, 1);
    for (long i = 0; i < PERSONE; i++)
        pthread_create(&t[i], NULL, persona, (void *)i);
    for (int i = 0; i < PERSONE; i++)
        pthread_join(t[i], NULL);
    return 0;
}

Il contatore n[c] conta anche chi è in attesa del bagno (è già incrementato quando il primo della categoria aspetta bagno): per verificare la regola si usa quindi un secondo contatore atomico, dentro[c], incrementato solo dopo che entra è ritornata. Il codice è stato compilato senza avvisi con zig cc -Wall -Wextra -Wpedantic per Linux; non è stato eseguito qui.

Per l'esercizio 18 basta lo stesso programma con le due categorie "italiano" e "francese" (la piazza è bagno): la soluzione del corso senza il tornello è quella giusta se non si chiede equità.

Domande d'esame

Perché serve il tornello per evitare la starvation? Traccia. Senza tornello, un flusso continuo di persone di una categoria mantiene n[c] > 0 e l'altra categoria non entra mai. Con il tornello chi aspetta la categoria opposta blocca i nuovi arrivi, così il gruppo attuale si esaurisce e il turno passa.