Esercizio - Monitor per conto bancario, cannibali e fabbrica (eserciziario, esercizi 16, 17 e 103)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD). Tre problemi da risolvere con i monitor. 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 →.

• Esercizio 16. Un conto bancario è condiviso da più persone. Ciascuna può depositare o prelevare soldi dal conto, ma il saldo non deve mai diventare negativo. Se una persona accreditata vuole fare un prelievo e ci sono soldi a sufficienza, lo fa aggiornando il saldo; altrimenti resta in attesa che il saldo renda possibile il prelievo. Quando una persona deposita, avverte le eventuali altre persone in attesa. Scrivere un monitor con le funzioni prelievo e deposito.
• Esercizio 17. Una tribù di $N$ selvaggi mangia in comune da una pentola che può contenere fino a $M$ porzioni di stufato ($M < N$); quando un selvaggio ha fame controlla la pentola: se non ci sono porzioni, sveglia il cuoco e attende che questo abbia riempito di nuovo la pentola; se la pentola contiene almeno un pasto, si mette in attesa di essere servito. Il cuoco controlla inizialmente che ci siano delle porzioni; se ci si addormenta, altrimenti cuoce $M$ porzioni e le serve ai cannibali in attesa. Si descrivano soluzioni con semafori o monitor (in quest'ultimo caso si descrivono le procedure riempi e servi).
• Esercizio 103. Numerosi operai in una fabbrica preparano un unico prodotto con $nA$ unità del componente $A$ e $nB$ unità del componente $B$. Un fattorino viene chiamato a riempire le quantità di $A$ e $B$ fino a $totA$ e $totB$ ogni volta che le loro quantità residue scendono sotto $nA$ e $nB$. Prima di iniziare a comporre il prodotto, ogni operaio si assicura di avere le quantità necessarie dei due componenti; altrimenti chiama il fattorino e attende che arrivi con la scorta. Terminato il suo compito il fattorino resta in attesa di essere richiamato. Una volta completato un prodotto, ogni operaio ne prepara un altro. Inizialmente le scorte di $A$ e $B$ sono piene e nessun prodotto è stato preparato. Scrivere con i monitor le procedure prepara_prodotto (chiamata da ogni operaio all'infinito) e scorta_ingrediente (chiamata dal fattorino). Dati del monitor: condition operaio, fattorino; int qA, qB; int operai_in_attesa; e costanti nA, nB, totA, totB.

Come si traduce un monitor in C. Un monitor è un mutex (un solo thread dentro) più variabili condizione. In POSIX: pthread_mutex_lock all'ingresso di ogni procedura, pthread_cond_wait(&cond, &m) per x.wait() (rilascia il mutex mentre dorme), pthread_cond_signal per x.signal(). Poiché con signal and continue la condizione può non valere più al risveglio, si rivaluta sempre in un while.

Esercizio 16: conto bancario

Soluzione del corso (monitor cc con saldo, n_sosp e la condizione sosp): prelievo ripete "se saldo > cifra, preleva; altrimenti incrementa n_sosp e fa sosp.wait(); quando si sveglia, se ci sono altri sospesi li risveglia a catena"; deposito somma e sveglia uno dei sospesi. Si può anche svegliarli tutti: più lento ma, in questo esercizio, deposito non fa altro dopo il risveglio.

Il corso usa saldo > cifra: con un saldo esattamente uguale alla cifra il prelievo resta in attesa anche se il saldo non diventerebbe negativo (porterebbe il saldo a 0). Per il testo ("non deve mai diventare negativo") la condizione giusta è saldo >= cifra; qui si usa quella.

Versione C con pthread_cond_broadcast (più semplice: ognuno rivaluta la propria condizione):

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

static int saldo;
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t sosp = PTHREAD_COND_INITIALIZER;

static void prelievo(int cifra)
{
    pthread_mutex_lock(&m);                   /* entra nel monitor */
    while (saldo < cifra)                     /* il saldo non deve diventare negativo */
        pthread_cond_wait(&sosp, &m);         /* sospeso, il monitor e' libero */
    saldo -= cifra;
    pthread_mutex_unlock(&m);
}

static void deposito(int cifra)
{
    pthread_mutex_lock(&m);
    saldo += cifra;
    pthread_cond_broadcast(&sosp);            /* avverte tutti: ognuno ricontrolla */
    pthread_mutex_unlock(&m);
}

static void *prelevatore(void *arg)
{
    (void)arg;
    for (int i = 0; i < 5; i++)
        prelievo(10);
    return NULL;
}

static void *depositante(void *arg)
{
    (void)arg;
    for (int i = 0; i < 10; i++)
        deposito(5);
    return NULL;
}

int main(void)
{
    pthread_t p[2], d[2];
    for (int i = 0; i < 2; i++) {
        pthread_create(&p[i], NULL, prelevatore, NULL);   /* 2 * 5 * 10 = 100 prelevati */
        pthread_create(&d[i], NULL, depositante, NULL);   /* 2 * 10 * 5 = 100 depositati */
    }
    for (int i = 0; i < 2; i++) {
        pthread_join(p[i], NULL);
        pthread_join(d[i], NULL);
    }
    printf("saldo finale = %d (atteso 0)\n", saldo);
    return 0;
}

I prelievi totali (100) uguagliano i depositi (100): tutti i prelevatori terminano e il saldo non è mai negativo; saldo finale 0.

Esercizio 17: selvaggi e cuoco

Con semafori (soluzione del corso): mutex = 1, pieno = 0, vuoto = 0; int porzioni = M; Il selvaggio prende mutex; se la pentola è vuota sveglia il cuoco (signal(vuoto)), aspetta (wait(pieno)) e al risveglio rimette porzioni = M; poi si serve (porzioni--) e rilascia mutex. Il cuoco ripete wait(vuoto), riempie, signal(pieno).

Selvaggio:                                  Cuoco:
    wait(mutex);                                while (1) {
    if (porzioni == 0) {                            wait(vuoto);
        signal(vuoto);                              riempi la pentola;
        wait(pieno);                                signal(pieno);
        porzioni = M;                           }
    }
    porzioni--;
    signal(mutex);
    mangia();

Il selvaggio che trova la pentola vuota tiene mutex mentre aspetta il cuoco: gli altri selvaggi si accodano su mutex, non possono servirsi (la pentola è vuota comunque) e il cuoco non usa mutex: nessun deadlock.

Con un monitor (soluzione del corso, procedure serviti e riempi): serviti(): se pasti == 0 si guarda se il cuoco dorme (vcuoco): in tal caso lo si sveglia (cuoco.signal()), altrimenti il selvaggio si mette in attesa (vcannibale++; cannibale.wait()); poi pasti--. riempi() (chiamata dal cuoco): se ci sono ancora pasti si addormenta (vcuoco = 1; cuoco.wait()), poi pasti = M, e sveglia tutti i cannibali in attesa (while (vcannibale) { vcannibale--; cannibale.signal(); }).

Versione C con semafori e quattro selvaggi (compilata, non eseguita):

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

#define M 3                     /* porzioni nella pentola */
#define N 5                     /* selvaggi */
#define PASTI 3                 /* pasti per selvaggio: 15 in tutto, 5 riempimenti */

static sem_t mutex, pieno, vuoto;
static int porzioni = M;
static int fine;

static void *cuoco(void *arg)
{
    (void)arg;
    for (;;) {
        sem_wait(&vuoto);
        if (fine)
            return NULL;
        printf("il cuoco riempie la pentola\n");
        sem_post(&pieno);
    }
}

static void *selvaggio(void *arg)
{
    long id = (long)arg;
    for (int k = 0; k < PASTI; k++) {
        sem_wait(&mutex);
        if (porzioni == 0) {
            sem_post(&vuoto);                 /* sveglia il cuoco */
            sem_wait(&pieno);                 /* aspetta il riempimento (tenendo mutex) */
            porzioni = M;
        }
        porzioni--;
        printf("selvaggio %ld mangia (restano %d)\n", id, porzioni);
        sem_post(&mutex);
    }
    return NULL;
}

int main(void)
{
    pthread_t c, s[N];
    sem_init(&mutex, 0, 1);
    sem_init(&pieno, 0, 0);
    sem_init(&vuoto, 0, 0);
    pthread_create(&c, NULL, cuoco, NULL);
    for (long i = 0; i < N; i++)
        pthread_create(&s[i], NULL, selvaggio, (void *)i);
    for (int i = 0; i < N; i++)
        pthread_join(s[i], NULL);
    fine = 1;
    sem_post(&vuoto);                         /* sveglia il cuoco per farlo terminare */
    pthread_join(c, NULL);
    return 0;
}

Esercizio 103: fabbrica con operai e fattorino

Nel testo del corso la procedura degli operai controlla qA > nA and qB > nB (disuguaglianza stretta): il testo dice invece che si chiama il fattorino quando le quantità "scendono sotto $nA$ e $nB$", cioè quando una delle due è minore del necessario; la condizione per preparare è $qA \ge nA$ e $qB \ge nB$. La versione stretta funziona ma chiama il fattorino un po' troppo presto. Inoltre, la soluzione del corso usa fattorino.signal() senza un contatore o una flag: se il fattorino non è ancora in attesa nel momento del segnale (per esempio all'avvio, o mentre sta rifornendo), il segnale va perso (le variabili condizione non hanno memoria) e l'operaio rimarrebbe bloccato. Il corso presuppone che il fattorino sia già in fattorino.wait(); il programma sotto rende il protocollo robusto con una flag chiamato.

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

#define nA 2
#define nB 3
#define totA 10
#define totB 12
#define OPERAI 4
#define PRODOTTI 6               /* prodotti per operaio */

static int qA = totA, qB = totB;
static int operai_in_attesa;
static int chiamato;             /* il fattorino e' stato chiamato e non ha ancora rifornito */
static int finito;
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t operaio = PTHREAD_COND_INITIALIZER;
static pthread_cond_t fattorino = PTHREAD_COND_INITIALIZER;

static void prepara_prodotto(void)
{
    pthread_mutex_lock(&m);
    while (!(qA >= nA && qB >= nB)) {          /* scorte insufficienti */
        if (!chiamato) {
            chiamato = 1;                      /* chiama il fattorino (una sola volta) */
            pthread_cond_signal(&fattorino);
        }
        operai_in_attesa++;
        pthread_cond_wait(&operaio, &m);
        operai_in_attesa--;
    }
    qA -= nA;
    qB -= nB;
    pthread_mutex_unlock(&m);
}

static void scorta_ingrediente(void)
{
    pthread_mutex_lock(&m);
    while (!finito) {
        while (!chiamato && !finito)
            pthread_cond_wait(&fattorino, &m);  /* resta in attesa di essere richiamato */
        if (finito)
            break;
        qA = totA;
        qB = totB;
        chiamato = 0;
        printf("fattorino: rifornisce (operai in attesa: %d)\n", operai_in_attesa);
        pthread_cond_broadcast(&operaio);       /* tutti gli operai in attesa riprovano */
    }
    pthread_mutex_unlock(&m);
}

static void *operaio_run(void *arg)
{
    (void)arg;
    for (int k = 0; k < PRODOTTI; k++)
        prepara_prodotto();
    return NULL;
}

static void *fattorino_run(void *arg)
{
    (void)arg;
    scorta_ingrediente();
    return NULL;
}

int main(void)
{
    pthread_t f, o[OPERAI];
    pthread_create(&f, NULL, fattorino_run, NULL);
    for (int i = 0; i < OPERAI; i++)
        pthread_create(&o[i], NULL, operaio_run, NULL);
    for (int i = 0; i < OPERAI; i++)
        pthread_join(o[i], NULL);
    pthread_mutex_lock(&m);
    finito = 1;
    pthread_cond_signal(&fattorino);
    pthread_mutex_unlock(&m);
    pthread_join(f, NULL);
    printf("scorte finali: A = %d, B = %d\n", qA, qB);
    return 0;
}

Controllo dei conti: in tutto si fanno $4 \cdot 6 = 24$ prodotti, che consumano $24 \cdot 2 = 48$ di $A$ e $24 \cdot 3 = 72$ di $B$; la scorta iniziale $(10, 12)$ basta per $\min(10/2, 12/3) = 4$ prodotti (limitato da $B$), poi ogni rifornimento ne permette ancora 4. Non si perde mai un risveglio perché il fattorino è richiamato con la flag chiamato (che resta a 1 finché non rifornisce) e perché dopo il rifornimento tutti gli operai in attesa riprovano (broadcast) e ricontrollano la condizione in un while.

Domande d'esame

Perché un signal di una variabile condizione "vuota" è un problema e come lo si evita? Traccia. Se nessuno sta aspettando, x.signal() non ha alcun effetto e non resta traccia: un operaio che chiama il fattorino prima che questo sia in attesa lo sveglierebbe a vuoto. Si memorizza lo stato in una variabile ordinaria (flag chiamato o contatore) e il ricevente lo controlla in un while prima di aspettare.