Verifica semafori

La verifica (link) è una variante del classico problema dei filosofi a cena con l’aggiunta dei camerieri.

Ci sono N_FILOSOFI al ristorante che, come al solito, pensano e mangiano a una tavola circolare, condividendo le bacchette con i vicini. Inizialmente ci sono N_FILOSOFI bacchette e i filosofi prelevano la bacchetta sinistra e poi quella destra per mangiare. Quando un filosofo finisce di mangiare butta via le proprie bacchette e un cameriere le sostituisce con bacchette pulite, in modo che due filosofi non mangino mai con la stessa bacchetta usata.

Lo schema del filosofo id è il seguente:

while(1) {
    raccogli_sx(id); // raccoglie la bacchetta sinistra
    raccogli_dx(id); // raccoglie la bacchetta destra

    // mangia

    alzati(id); // Si alza da tavola portandosi via le bacchette

    // pensa
}

Lo schema del cameriere id (uno per filosofo) è il seguente:

while(1) {
    prepara_coperto(id); // prepara il coperto in posizione id
}

Il cameriere deve attendere che il filosofo si alzi prima di sostituire il coperto, quindi la chiamata a prepara_coperto(id) deve sincronizzarsi con alzati(id).

Soluzione

Una possibile soluzione commentata della verifica è la seguente:

/*
 * La verifica consiste nell'implementazione di una variante del classico
 * problema dei filosofi a cena. In questa variante sono presenti tanti
 * camerieri quanti sono i filosofi: dopo aver finito di mangiare, un
 * filosofo non deposita le bacchette sul tavolo (come nella versione
 * classica), ma è il cameriere associato al filosofo che deve occuparsi
 * di posizionare sul tavolo delle bacchette nuove.
 *
 * È dunque necessario realizzare:
 * - la sincronizzazione tra il filosofo e il corrispondente cameriere per
 *   la disposizione delle bacchette sulla tavola quando il primo ha finito
 *   di mangiare;
 * - la sincronizzazione tra i filosofi nella raccolta delle bacchette,
 *   impedendo il verificarsi di situazioni di stallo.
 * 
 * Per la gestione delle bacchette utilizziamo il vettore di semafori chiamato
 * 'bacchette': il semaforo i-esimo vale 1 se la bacchetta i-esima è depositata
 * sul tavolo, 0 altrimenti.
 *
 * Per la sincronizzazione tra camerieri e filosofi utilizziamo il vettore di
 * semafori 'cambio_coperto': il semaforo i-esimo vale 1 se il filosofo si è
 * alzato ed il cameriere deve posizionare le nuove bacchette, 0 altrimenti.
 *
 * Per la risoluzione del problema dello stallo è possibile adottare varie
 * tecniche spiegate a lezione, quali il filosofo mancino o la limitazione
 * del numero dei posti a tavola. È preferibile evitare la raccolta atomica
 * delle bacchette poiché "sincronizza troppo" i filosofi, come spiegato
 * nella lezione 'Programmazione con i semafori'.
 * Nella soluzione proposta limitiamo il numero di filosofi che possono
 * contemporaneamente competere nella raccolta delle bacchette a 'N_FILOSOFI-1':
 * dal momento che le bacchette disponibili sono 'N_FILOSOFI', almeno uno
 * riuscirà a raccogliere entrambe le bacchette e mangiare. Il semaforo 'posti'
 * viene utilizzato proprio a questo scopo.
 */

#define N_FILOSOFI 5

sem_t cambio_coperto[N_FILOSOFI];
sem_t bacchette[N_FILOSOFI];
sem_t posti;

/* Inizializzazione dei semafori. */
void init_sem() {
  /* Come descritto sopra, limitiamo il numero di posti a tavola a
   * 'N_FILOSOFI-1'. */
  sem_init(&posti, 0, N_FILOSOFI-1);
  for (int i = 0; i < N_FILOSOFI; i++) {
    /* Inizialmente le bacchette sono già posizionate sul tavolo, dunque i
     * camerieri devono rimanere in attesa. */
    sem_init(cambio_coperto+i, 0, 0);
    sem_init(bacchette+i, 0, 1);
  }
}

/* Rimozione dei semafori. */
void destroy_sem() {
  sem_destroy(&posti);
  for (int i = 0; i < N_FILOSOFI; i++) {
    sem_destroy(cambio_coperto+i);
    sem_destroy(bacchette+i);
  }
}

void prepara_coperto(int id) {
  /* Attendi che il filosofo si alzi dal tavolo. */
  sem_wait(cambio_coperto+id);
  /* Riposiziona sul tavolo le bacchette usate dal filosofo. */
  sem_post(bacchette+id);
  sem_post(bacchette + (id+1) % N_FILOSOFI);
}

void alzati(int id) {
  /* Notifica al cameriere che deve preparare il coperto. */
  sem_post(cambio_coperto+id);
  /* Libera il posto a tavola per altri filosofi. */
  sem_post(&posti);
}

void raccogli_sx(int id) {
  /* Attendi che si liberi un posto a tavola. */
  sem_wait(&posti);
  /* Raccogli la bacchetta sinistra: attendi se è già in uso dal filosofo
   * seduto a sinistra. */
  sem_wait(bacchette+id);
}

void raccogli_dx(int id) {
  /* Raccogli la bacchetta destra: attendi se è già in uso dal filosofo
   * seduto a destra. */
  sem_wait(bacchette + (id+1) % N_FILOSOFI);
}