Esercizio - Distributore di aranciata, moduli di borsa di studio e attuatori (eserciziario, esercizi 10, 15, 47 e 85)

In questa pagina 5

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD). Quattro problemi di sincronizzazione con semafori, tutti con un rifornitore che riempie una risorsa e dei consumatori che la svuotano. Teoria: Semafori, monitor e problemi classici di sincronizzazione.

Esercizio 85. Un distributore di aranciata, un fornitore e $N = 20$ consumatori. Il distributore ha due operazioni: carica (il fornitore lo rifornisce con $M = 10$ aranciate) e preleva (un consumatore ne prende una). Il fornitore inizialmente carica la macchinetta, poi si sospende in attesa di essere chiamato a rifornirla quando è vuota. Il primo consumatore che trova la macchinetta scarica deve chiamare il fornitore e attendere; finché è vuota i consumatori si sospendono. Scrivere carica e preleva con: type A = array[1..10] of orange; var pieno: semaphore(initial 1); vuoto: semaphore(initial 0); mutex: semaphore(initial 1); index: 1..10; aranciate: A.
Esercizio 15. Studenti in coda davanti alla segreteria per ritirare un modulo di richiesta di borsa di studio. Inizialmente su un tavolo c'è una pila di 50 moduli. Uno studente alla testa della fila controlla se ci sono moduli; in caso contrario suona un campanello per segnalare il problema al personale. Un impiegato arriva, depone sul tavolo una nuova pila di 50 moduli e se ne va. Variabili condivise: semaphore fila = 1, campanello = 0, disp_moduli = 0; int moduli = 50;. Scrivere le procedure di studente e impiegato.
Esercizio 47. In una mensa universitaria gli studenti, dopo aver mangiato, depongono i vassoi in $M$ contenitori (solo uno studente alla volta può usare un contenitore), ognuno con $K$ ripiani. Periodicamente un addetto sceglie un contenitore tra quelli con i ripiani pieni, lo svuota, lava i piatti e lo riporta in sala. Implementare i processi cameriere e studente in modo che, se uno studente sceglie il contenitore che l'addetto sta liberando e lavando, aspetti (col vassoio in mano) che l'addetto lo riporti in sala.
Esercizio 10. Quattro processi: tre "attuatori" che eseguono una stessa azione e un "fornitore" di risorse. Ogni attuatore ha bisogno di tre risorse distinte ma ne possiede una sola: l'attuatore 1 possiede la risorsa 1 e gli servono 2 e 3; l'attuatore 2 possiede la 2 e gli servono 1 e 3; l'attuatore 3 possiede la 3 e gli servono 1 e 2. Il fornitore mette a disposizione due risorse (di disponibilità infinita) scelte a caso, e il processo che possiede la terza è in grado di portare a termine l'azione. Sincronizzare con semafori l'esecuzione dei quattro processi.

Esercizio 85: distributore

Idea. pieno = "il distributore è vuoto, il fornitore può caricare" (nome fuorviante: significa "da riempire"; inizialmente 1 perché la macchinetta parte da caricare); vuoto = "ci sono aranciate da prelevare" (inizialmente 0); mutex fa prelevare un consumatore alla volta. index conta le aranciate rimaste.

carica(x: A):                               preleva(var y: orange):
    wait(pieno);                                wait(mutex);
    aranciate := x;                             wait(vuoto);
    index := 10;                                y := aranciate[index];
    signal(vuoto);                              index := index - 1;
                                                if index = 0 then signal(pieno)
                                                             else signal(vuoto);
                                                signal(mutex);

Passo per passo: il fornitore ripete carica; la prima volta pieno = 1 passa; carica, index = 10, signal(vuoto). Un consumatore prende mutex, wait(vuoto) passa, prende l'aranciata in cima, decrementa; se resta qualcosa fa signal(vuoto) (lascia passare il prossimo), se ha preso l'ultima fa signal(pieno) che sveglia il fornitore (la chiamata). Il consumatore successivo prende mutex e si ferma su wait(vuoto) tenendo mutex: gli altri aspettano su mutex, ma il fornitore non ne ha bisogno, quindi non c'è deadlock: carica, signal(vuoto), e il consumatore bloccato riparte.

Programma C con 4 consumatori da 5 aranciate ciascuno (20 in tutto) e fornitore che carica 2 volte da 10:

aranciata.cc

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

#define M 10                    /* aranciate per caricamento */
#define CONSUMATORI 4
#define PER_CONSUMATORE 5       /* 4 * 5 = 20 aranciate */
#define CARICHE 2               /* 2 * 10 = 20 aranciate */

static int aranciate[M];
static int index_;              /* numero di aranciate presenti */
static sem_t pieno, vuoto, mutex;

static void carica(int primo)
{
    sem_wait(&pieno);                     /* aspetta che il distributore sia vuoto */
    for (int i = 0; i < M; i++)
        aranciate[i] = primo + i;
    index_ = M;
    sem_post(&vuoto);
}

static int preleva(void)
{
    sem_wait(&mutex);                     /* un consumatore alla volta */
    sem_wait(&vuoto);                     /* aspetta che ci sia qualcosa */
    int y = aranciate[--index_];
    if (index_ == 0)
        sem_post(&pieno);                 /* ultima: chiama il fornitore */
    else
        sem_post(&vuoto);
    sem_post(&mutex);
    return y;
}

static void *fornitore(void *arg)
{
    (void)arg;
    for (int k = 0; k < CARICHE; k++)
        carica(k * M);
    return NULL;
}

static void *consumatore(void *arg)
{
    long id = (long)arg;
    for (int k = 0; k < PER_CONSUMATORE; k++)
        printf("consumatore %ld ha preso l'aranciata %d\n", id, preleva());
    return NULL;
}

int main(void)
{
    pthread_t f, c[CONSUMATORI];
    sem_init(&pieno, 0, 1);
    sem_init(&vuoto, 0, 0);
    sem_init(&mutex, 0, 1);
    pthread_create(&f, NULL, fornitore, NULL);
    for (long i = 0; i < CONSUMATORI; i++)
        pthread_create(&c[i], NULL, consumatore, (void *)i);
    pthread_join(f, NULL);
    for (int i = 0; i < CONSUMATORI; i++)
        pthread_join(c[i], NULL);
    return 0;
}

Esercizio 15: moduli alla segreteria

fila serve per far gestire uno studente alla volta (quello alla testa): così al più uno solo suona il campanello. L'impiegato aspetta il campanello, rimette i moduli e segnala che sono disponibili.

studente():                                  impiegato():
    wait(fila);                                  while (true) {
    if (moduli == 0) {                               wait(campanello);
        signal(campanello);                          moduli = 50;
        wait(disp_moduli);                           signal(disp_moduli);
    }                                            }
    moduli--;
    signal(fila);

Lo studente che trova la pila vuota suona e aspetta tenendo fila: gli altri non possono superarlo (è giusto, la fila è ordinata). Quando i moduli arrivano riparte, ne prende uno e lascia passare il successivo.

moduli.cc

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

#define MODULI_PILA 3           /* pila piccola (invece di 50) per vedere i rifornimenti */
#define STUDENTI 7
#define RIFORNIMENTI 2          /* 7 studenti, 3 moduli per pila: servono 2 rifornimenti */

static sem_t fila, campanello, disp_moduli;
static int moduli = MODULI_PILA;

static void *studente(void *arg)
{
    long id = (long)arg;
    sem_wait(&fila);
    if (moduli == 0) {
        printf("studente %ld: pila vuota, suono il campanello\n", id);
        sem_post(&campanello);
        sem_wait(&disp_moduli);
    }
    moduli--;
    printf("studente %ld ritira un modulo (restano %d)\n", id, moduli);
    sem_post(&fila);
    return NULL;
}

static void *impiegato(void *arg)
{
    (void)arg;
    for (int k = 0; k < RIFORNIMENTI; k++) {
        sem_wait(&campanello);
        moduli = MODULI_PILA;
        sem_post(&disp_moduli);
    }
    return NULL;
}

int main(void)
{
    pthread_t s[STUDENTI], imp;
    sem_init(&fila, 0, 1);
    sem_init(&campanello, 0, 0);
    sem_init(&disp_moduli, 0, 0);
    pthread_create(&imp, NULL, impiegato, NULL);
    for (long i = 0; i < STUDENTI; i++)
        pthread_create(&s[i], NULL, studente, (void *)i);
    for (int i = 0; i < STUDENTI; i++)
        pthread_join(s[i], NULL);
    pthread_join(imp, NULL);
    return 0;
}

Esercizio 47: contenitori della mensa

Un semaforo cont[i] (inizio 1) per ogni contenitore: mutua esclusione sul contenitore $i$ per studenti e addetto; un array condiviso liberi[i] (inizio $K$ ) conta i ripiani liberi. Lo studente prova i contenitori a rotazione; l'addetto li passa in rassegna e ripulisce quelli pieni:

cameriere():                               studente():
    i = -1;                                    i = -1; fatto = no;
    while (1) {                                while (fatto == no) {
        i = (i + 1) % M;                           i = (i + 1) % M;
        wait(cont[i]);                             wait(cont[i]);
        if (liberi[i] == 0) {                      if (liberi[i] > 0) {
            liberi[i] = K;                             liberi[i] = liberi[i] - 1;
            lava();                                    posa();
        }                                              fatto = si;
        signal(cont[i]);                           }
    }                                              signal(cont[i]);
                                               }

Lo studente che arriva al contenitore mentre l'addetto lo sta lavando resta fermo su wait(cont[i]) (col vassoio in mano) finché l'addetto non fa signal(cont[i]): è il comportamento richiesto. Il lava() si fa dentro la sezione critica proprio per questo.

mensa.cc

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

#define M 3                     /* contenitori */
#define K 2                     /* ripiani per contenitore */
#define STUDENTI 8

static sem_t cont[M];
static int liberi[M];
static atomic_int finiti;

static void *cameriere(void *arg)
{
    (void)arg;
    int i = -1;
    while (atomic_load(&finiti) < STUDENTI) {
        i = (i + 1) % M;
        sem_wait(&cont[i]);
        if (liberi[i] == 0) {
            printf("cameriere: svuota e lava il contenitore %d\n", i);
            usleep(500);                  /* lava() */
            liberi[i] = K;
        }
        sem_post(&cont[i]);
        usleep(100);
    }
    return NULL;
}

static void *studente(void *arg)
{
    long id = (long)arg;
    int i = -1, fatto = 0;
    while (!fatto) {
        i = (i + 1) % M;
        sem_wait(&cont[i]);
        if (liberi[i] > 0) {
            liberi[i]--;
            printf("studente %ld posa il vassoio nel contenitore %d\n", id, i);
            fatto = 1;
        }
        sem_post(&cont[i]);
        if (!fatto)
            usleep(100);
    }
    atomic_fetch_add(&finiti, 1);
    return NULL;
}

int main(void)
{
    pthread_t c, s[STUDENTI];
    for (int i = 0; i < M; i++) {
        sem_init(&cont[i], 0, 1);
        liberi[i] = K;
    }
    pthread_create(&c, NULL, cameriere, NULL);
    for (long i = 0; i < STUDENTI; i++)
        pthread_create(&s[i], NULL, studente, (void *)i);
    for (int i = 0; i < STUDENTI; i++)
        pthread_join(s[i], NULL);
    pthread_join(c, NULL);
    return 0;
}

Con $M \cdot K = 6$ posti e 8 studenti, almeno due studenti dovranno aspettare che l'addetto svuoti un contenitore.

Esercizio 10: gli attuatori (problema dei fumatori)

È il problema classico dei fumatori di sigarette. Il fornitore sceglie a caso un attuatore $i$ e mette sul tavolo le altre due risorse; sveglia proprio l'attuatore $i$ (che possiede la terza), il quale le prende, avvisa il fornitore che può mettere altre risorse e agisce. Semafori: attuatore[i] (0, uno per attuatore), agent (1, il fornitore può mettere nuove risorse solo dopo che quelle precedenti sono state prese), lock (1, mutua esclusione sul tavolo). Soluzione del corso:

Fornitore:                                  Attuatore_i:
  do forever {                                do forever {
      wait(agent);                                wait(attuatore_i);      // dorme finché non è il suo turno
      scegli a caso r in {1,2,3};                 wait(lock);
      metti le due risorse diverse da r;          prendi le altre due risorse;
      signal(attuatore_r);                        signal(lock);
  }                                               signal(agent);          // il fornitore può proseguire
                                                  agisci();
                                              }

(Nella soluzione del corso wait(agent) è l'ultima istruzione del ciclo, equivalente a questa con agent inizializzato a 1.) Il fornitore sa quali due risorse ha messo e quindi quale attuatore le può usare: non serve che gli attuatori guardino il tavolo. Il pericolo da evitare è che un attuatore prenda una sola delle due risorse e lasci l'altro bloccato: qui le due risorse sono prese insieme, e il semaforo attuatore[i] identifica l'unico processo che può proseguire.

attuatori.cc

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

#define ROUND 9                          /* quante volte il fornitore mette risorse */

static sem_t attuatore[3], agent, lock;
static int tavolo = -1;                  /* indice dell'attuatore che puo' agire, -1 = tavolo vuoto */

static void *fornitore(void *arg)
{
    (void)arg;
    srand(42);
    for (int k = 0; k < ROUND; k++) {
        sem_wait(&agent);                /* il tavolo e' vuoto: si puo' mettere */
        int r = rand() % 3;              /* l'attuatore che possiede la terza risorsa */
        sem_wait(&lock);
        tavolo = r;                      /* sul tavolo ci sono le due risorse diverse dalla r+1 */
        sem_post(&lock);
        printf("fornitore mette le risorse diverse dalla %d\n", r + 1);
        sem_post(&attuatore[r]);
    }
    for (int i = 0; i < 3; i++)
        sem_post(&attuatore[i]);         /* risveglio finale: gli attuatori usciranno */
    return NULL;
}

static void *attuatore_run(void *arg)
{
    long i = (long)arg;
    for (;;) {
        sem_wait(&attuatore[i]);
        sem_wait(&lock);
        int mio = (tavolo == i);         /* e' davvero il mio turno? */
        if (mio)
            tavolo = -1;                 /* prende le due risorse */
        sem_post(&lock);
        if (!mio)
            return NULL;                 /* risveglio finale */
        sem_post(&agent);                /* il fornitore puo' mettere altre risorse */
        printf("attuatore %ld ha le tre risorse e agisce\n", i + 1);
        usleep(100);
    }
}

int main(void)
{
    pthread_t f, a[3];
    sem_init(&agent, 0, 1);
    sem_init(&lock, 0, 1);
    for (int i = 0; i < 3; i++)
        sem_init(&attuatore[i], 0, 0);
    pthread_create(&f, NULL, fornitore, NULL);
    for (long i = 0; i < 3; i++)
        pthread_create(&a[i], NULL, attuatore_run, (void *)i);
    pthread_join(f, NULL);
    for (int i = 0; i < 3; i++)
        pthread_join(a[i], NULL);
    return 0;
}

Il campo tavolo dice quale attuatore può agire e permette di distinguere un risveglio vero da quello finale (usato solo per terminare il programma): un attuatore che si risveglia e non trova il proprio indice sul tavolo esce. Il programma è stato compilato senza avvisi (non eseguito qui).

Domande d'esame

Perché nel distributore il consumatore prende mutex prima di wait(vuoto) senza creare deadlock? Traccia. Il consumatore bloccato su vuoto tiene mutex, ma il fornitore, che è l'unico che può fare signal(vuoto), non ha mai bisogno di mutex: non c'è attesa circolare.

Versione ripasso

85 (distributore): pieno=1 (da caricare), vuoto=0, mutex=1, index. carica: wait(pieno); riempi; index=10; signal(vuoto). preleva: wait(mutex); wait(vuoto); prendi aranciate[index]; index--; se index==0 signal(pieno) altrimenti signal(vuoto); signal(mutex). Nessun deadlock: il fornitore non usa mutex. Teoria: Semafori, monitor e problemi classici di sincronizzazione.
15 (moduli): fila=1, campanello=0, disp_moduli=0, moduli=50. Studente: wait(fila); se moduli==0 {signal(campanello); wait(disp_moduli)}; moduli--; signal(fila). Impiegato: wait(campanello); moduli=50; signal(disp_moduli).
47 (mensa): un cont[i] (1) per contenitore, liberi[i]=K. Cameriere: scorre, wait(cont[i]), se liberi[i]==0 {liberi[i]=K; lava()}, signal. Studente: scorre, wait(cont[i]), se liberi[i]>0 {liberi[i]--; posa(); fatto}, signal. Lo studente aspetta sul semaforo mentre si lava.
10 (attuatori = fumatori): attuatore[i]=0, agent=1, lock=1; il fornitore sceglie $r$ , mette le altre due, signal(attuatore_r); l'attuatore prende, signal(agent), agisce.
Schema comune: un rifornitore riempie, i consumatori svuotano; il semaforo "da riempire" sveglia il rifornitore quando la risorsa finisce, il semaforo "da consumare" sveglia i consumatori dopo il rifornimento. Un consumatore che aspetta tenendo un mutex non crea deadlock se il rifornitore non ha mai bisogno di quel mutex.
85, traccia: $f$ : carica (pieno=1 passa, index=10, vuoto=1); $c_1$ : mutex, vuoto passa, prende, index=9, signal(vuoto), rilascia; ... il 10° consumatore porta index a 0 e fa signal(pieno) (chiama il fornitore); l'11° resta su wait(vuoto) tenendo mutex finché il fornitore non ha ricaricato.
15, perché fila: uno solo alla testa controlla moduli, quindi al più un signal(campanello) per volta; lo studente aspetta disp_moduli tenendo fila: la coda resta ordinata. Valori iniziali: fila=1, campanello=0, disp_moduli=0.
47, punti chiave: liberi[i] e cont[i] per ogni contenitore; il lavaggio è dentro la sezione critica (così lo studente aspetta con il vassoio in mano); il cameriere lava solo se liberi[i]==0.
10, fumatori: semafori attuatore[0..2]=0, agent=1, lock=1; il fornitore sceglie $r$ a caso, mette le due risorse diverse da $r$ , signal(attuatore_r); l'attuatore $r$ prende le due risorse, signal(agent), agisce. In C si distingue il risveglio finale con un campo tavolo (indice dell'attuatore abilitato, $-1$ se vuoto).
Pseudocodice 85:

carica(x):  wait(pieno); aranciate = x; index = 10; signal(vuoto);
preleva(y): wait(mutex); wait(vuoto); y = aranciate[index]; index--;
            if (index == 0) signal(pieno); else signal(vuoto); signal(mutex);

Pseudocodice 15 e 47:

studente:  wait(fila); if (moduli == 0) { signal(campanello); wait(disp_moduli); } moduli--; signal(fila);
impiegato: while (1) { wait(campanello); moduli = 50; signal(disp_moduli); }
cameriere: i = (i+1)%M; wait(cont[i]); if (liberi[i] == 0) { liberi[i] = K; lava(); } signal(cont[i]);
studente:  i = (i+1)%M; wait(cont[i]); if (liberi[i] > 0) { liberi[i]--; posa(); fatto; } signal(cont[i]);

Pseudocodice 10: fornitore wait(agent); r = random; tavolo = r; signal(attuatore_r); attuatore $i$ : wait(attuatore_i); se tavolo == i { tavolo = -1; signal(agent); agisci; }.
C compilato: aranciata.c (4 consumatori $\times$ 5, 2 caricamenti da 10), moduli.c, mensa.c, attuatori.c: zig cc -Wall -Wextra -Wpedantic senza avvisi, non eseguiti.
Errori tipici: invertire il significato di pieno/vuoto; signal(campanello) da più studenti insieme (serve fila); lavare fuori dalla sezione critica.

Teoria collegata

Semafori, monitor e problemi classici di sincronizzazione