Esercizio - Il barbiere che dorme con i semafori (eserciziario, esercizio 68)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 68). In un negozio di barbiere ci sono:

una sedia per lavorare (quella del barbiere);
$n$ sedie per far attendere i clienti.

Il barbiere di solito dorme; quando arriva un cliente, questi lo sveglia e si fa servire; se nel frattempo arrivano altri clienti, si accomodano sulle sedie oppure, se sono tutte occupate, se ne vanno. Implementare con semafori usando le variabili:

#define CHAIRS 5                 /* sedie per i clienti in attesa */
typedef int semaphore;
semaphore customers = 0;         /* clienti in attesa di servizio */
semaphore barbers   = 0;         /* barbieri in attesa di clienti (pronti a tagliare) */
semaphore mutex     = 1;         /* mutua esclusione per la variabile waiting */
int waiting = 0;                 /* clienti in attesa (non quelli in servizio) */

Teoria: Semafori, monitor e problemi classici di sincronizzazione.

Soluzione del corso

void barber(void) {                          void customer(void) {
    while (TRUE) {                               wait(&mutex);
        wait(&customers);                        if (waiting < CHAIRS) {
        wait(&mutex);                                waiting = waiting + 1;
        waiting = waiting - 1;                       signal(&customers);
        signal(&barbers);                            signal(&mutex);
        signal(&mutex);                              wait(&barbers);
        cut_hair();                                  get_haircut();
    }                                            } else {
}                                                    signal(&mutex);
                                                 }
                                             }

Come funziona.

customers conta i clienti in attesa: il barbiere fa wait(customers) e dorme se è 0; ogni cliente che si siede fa signal(customers) e quindi lo sveglia.
barbers serve a far incontrare cliente e barbiere: il barbiere fa signal(barbers) quando è pronto a tagliare a uno dei clienti; il cliente fa wait(barbers), e solo allora si fa tagliare i capelli.
waiting è una copia del numero di clienti seduti (i semafori non si possono leggere): serve a decidere se c'è posto. È protetta da mutex.

Perché i controlli e le modifiche sono fatti dentro mutex. Il cliente legge waiting e lo incrementa nella stessa sezione critica: due clienti non possono entrambi vedere "c'è un posto" quando ce n'è uno solo. Il barbiere decrementa waiting quando sceglie un cliente.

Sincronizzazione. Il cliente non tiene mutex mentre aspetta il barbiere (rilascia con signal(mutex) prima di wait(barbers)): altrimenti il barbiere, che deve prendere mutex per decrementare waiting, non potrebbe svegliarlo. Sarebbe un deadlock.

Il programma C seguente simula il negozio con 3 sedie e 8 clienti (arrivati a intervalli diversi); alla fine conta quanti sono stati serviti e quanti se ne sono andati.

barbiere.cc

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

#define CHAIRS 3
#define CLIENTI 8

static sem_t customers, barbers, mutex;
static int waiting;                       /* clienti seduti in attesa */
static int serviti, persi;
static int fine;                          /* tutti i clienti sono passati */

static void *barber(void *arg)
{
    (void)arg;
    for (;;) {
        sem_wait(&customers);             /* dorme se nessuno e' in attesa */
        sem_wait(&mutex);
        if (fine && waiting == 0) {       /* risveglio finale */
            sem_post(&mutex);
            return NULL;
        }
        waiting--;
        sem_post(&barbers);               /* e' pronto per un cliente */
        sem_post(&mutex);
        usleep(2000);                     /* cut_hair() */
    }
}

static void *customer(void *arg)
{
    long id = (long)arg;
    usleep((useconds_t)(id * 500));       /* arrivi a intervalli diversi */
    sem_wait(&mutex);
    if (waiting < CHAIRS) {
        waiting++;
        sem_post(&customers);             /* sveglia il barbiere se dorme */
        sem_post(&mutex);
        sem_wait(&barbers);               /* aspetta il suo turno (senza tenere mutex) */
        sem_wait(&mutex);
        serviti++;
        sem_post(&mutex);
        printf("cliente %ld servito\n", id);
    } else {
        persi++;
        sem_post(&mutex);
        printf("cliente %ld se ne va (sedie piene)\n", id);
    }
    return NULL;
}

int main(void)
{
    pthread_t b, c[CLIENTI];
    sem_init(&customers, 0, 0);
    sem_init(&barbers, 0, 0);
    sem_init(&mutex, 0, 1);
    pthread_create(&b, NULL, barber, NULL);
    for (long i = 0; i < CLIENTI; i++)
        pthread_create(&c[i], NULL, customer, (void *)i);
    for (int i = 0; i < CLIENTI; i++)
        pthread_join(c[i], NULL);
    sem_wait(&mutex);
    fine = 1;
    sem_post(&mutex);
    sem_post(&customers);                 /* sveglia il barbiere per farlo terminare */
    pthread_join(b, NULL);
    printf("serviti %d, persi %d, totale %d\n", serviti, persi, serviti + persi);
    return 0;
}

Controlli: il totale serviti + persi è sempre uguale a CLIENTI (8). Il barbiere esce solo con fine vero e nessuno in attesa; la wait(customers) finale è sbloccata dalla sem_post del main.

Domande d'esame

Cosa succederebbe se il cliente non rilasciasse mutex prima di wait(barbers)? Traccia. Il barbiere, per sceglierlo, deve prendere mutex (per waiting--): ma il cliente lo tiene mentre aspetta barbers, che solo il barbiere può segnalare: attesa circolare, deadlock.

Versione ripasso

Variabili: customers=0 (clienti in attesa), barbers=0 (barbiere pronto), mutex=1, waiting=0, CHAIRS. Teoria: Semafori, monitor e problemi classici di sincronizzazione.
Barbiere: wait(customers) (dorme se nessuno); wait(mutex); waiting--; signal(barbers); signal(mutex); cut_hair().
Cliente: wait(mutex); se waiting < CHAIRS {waiting++; signal(customers); signal(mutex); wait(barbers); get_haircut()} altrimenti {signal(mutex) (se ne va)}.
Punti chiave: waiting è una copia del numero di seduti (i semafori non si leggono) protetta da mutex; il cliente rilascia mutex prima di wait(barbers), altrimenti deadlock.
Ruoli: customers = clienti seduti in attesa (il barbiere dorme a 0, ogni cliente seduto lo sveglia); barbers = incontro cliente-barbiere (il barbiere lo segnala, il cliente lo attende); waiting = copia del numero di seduti, perché i semafori non si leggono; mutex protegge waiting.
In C (3 sedie, 8 clienti): serviti + persi == CLIENTI; fine: fine=1 sotto mutex e sem_post(&customers) per svegliare il barbiere che esce se fine && waiting==0.
In Go: sedie = make(chan int, sedie); cliente select{case attesa<-id: default: se ne va}; barbiere for c := range attesa; close(attesa) a fine arrivi; si veda l'esercizio sulla sincronizzazione in Go.
Errori tipici: wait(barbers) dentro mutex; non decrementare waiting; dimenticare signal(mutex) nel ramo "piene".

Esercizi su questo argomento

Esercizio - Sincronizzazione in Go con canali, mutex e variabili condizione (problemi classici)

Teoria collegata

Semafori, monitor e problemi classici di sincronizzazione