[semafori] Multi-snake

La verifica consiste nella sincronizzazione di N_SNAKES thread, dove ciascun thread è uno snake rappresentato da un identificatore numerico tra 0 e N_SNAKES-1. Ogni snake implementa il seguente comportamento:

  • Inizialmente è fermo e rimane in attesa di una sequenza di caratteri.
  • Mano a mano che riceve i caratteri, il corpo dello snake si trasforma nella stringa ricevuta.
  • Quando la trasformazione è completa, lo snake si muove finché non incontra un altro snake al quale invia la stringa, un carattere alla volta.
  • Trasmettendo i caratteri, lo snake ritorna nella sua forma iniziale e si rimette in attesa.

Essenzialmente lo schema di uno snake è il seguente:

snake(id) {
    while(1) {
        for (i=0; i < SNAKE_LENGTH; i++) {
            body[i] = leggi_char(id); // legge il char
            fatta_lettura(id); // segnala che la lettura è avvenuta
        }

        // lo snake si muove finché possibile

        if (bloccato dallo snake s)
            for (i=0; i < SNAKE_LENGTH; i++) {
                invia_char(s,body[i]); // invia il char
                attendi_lettura(s); // attende che s abbia letto
            }
    }
}

I sorgenti della verifica sono disponibili qui. Dovete implementare le funzioni presenti nel file soluzione.c che viene incluso dal file multi-snake.c

Esempio

La situazione iniziale è la seguente:

+----------------------------------------+
|                        3333         1  |
|                                     1  |
|                                     1  |
|                                     1  |
|                0000                    |
|         2                              |
|         2                              |
|         2                              |
|         2                              |
|                                        |
|                                        |
|                                        |
|                                        |
|                                        |
|                                        |
|                    4444                |
|                                        |
|                                        |
|                                        |
|                                        |
+----------------------------------------+

Il thread principale invia la stringa LEAD allo snake 2 (scelto in maniera casuale):

+----------------------------------------+
|                        3333         1  |
|                                     1  |
|                                     1  |
|                                     1  |
|                0000                    |
|         L                              |
|         E                              |
|         A                              |
|         D                              |
|                                        |
|                                        |
|                                        |
|                                        |
|                                        |
|                                        |
|                    4444                |
|                                        |
|                                        |
|                                        |
|                                        |
+----------------------------------------+

Lo snake 2 si sposta e colpisce lo snake 4, al quale passa la stringa un carattere alla volta:

+----------------------------------------+
|                        3333         1  |
|                                     1  |
|                                     1  |
|                                     1  |
|                0000                    |
|                                        |
|                                        |
|                                        |
|                                        |
|                                        |
|                                        |
|                     D                  |
|                     A                  |
|                     2                  |
|                     2                  |
|                    LE44                |
|                                        |
|                                        |
|                                        |
|                                        |
+----------------------------------------+

Soluzione

Ecco una possibile soluzione commentata della verifica:

/*
 * La verifica consiste nel sincronizzare "N_SNAKES" thread. Ogni thread è uno 
 * snake il cui corpo è costituito da cifre che rappresentano l'identificatore
 * del serpente. Lo schema che si vuole realizzare è il seguente:
 * - ogni snake è in attesa di una sequenza di caratteri che, quando ricevuti,
 *   modificano gradualmente il corpo del serpente;
 * - ricevuta la stringa, lo snake inzia a muoversi nello schema fino a che non
 *   si scontra con un altro serpente, al quale invia a sua volta la stringa;
 * - trasmessa la stringa, il serpente ritorna in attesa.
 * All'avvio del programma tutti i serpenti sono fermi e la stringa viene
 * inviata dal thread principale ad un serpente scelto in modo casuale.
 *
 * La soluzione realizzata utilizza i seguenti semafori:
 * - un vettore di semafori "wr" di dimensione "N_SNAKES" utilizzato dai vari
 *   serpenti per attendere che venga inviato loro un carattere. In particolare,
 *   il semaforo "wr[id]" è verde se per lo snake di indice "id" è disponibile
 *   un carattere da leggere, rosso altrimenti.
 * - un mutex "rd" usato dal serpente che ha inviato il carattere per attendere
 *   che questo sia letto dal serpente con cui si è scontrato. Il semaforo è
 *   verde se lo snake "tamponato" ha letto il carattere ricevuto, rosso
 *   altrimenti.
 * Notare che è possibile usare solo un mutex per implementare l'attesa della
 * lettura del carattere inviato dal momento che, in un certo istante di tempo,
 * vi sarà al più un thread che esegue "attendi_lettura" (lo snake in movimento)
 * ed uno che esegue "fatta_lettura" (lo snake che è stato colpito).
 * Infine viene usata la variabile "ch" in cui viene scritto il carattere che
 * si sta spostando da un serpente all'altro.
 */

char ch;
sem_t wr[N_SNAKES], rd;

void init_sem() {
    /* I semafori del vettore "wr" sono inizializzati a 0. Nessun carattere è
     * inizialmente disponibile per nessuno degli snake. */
    for (int i = 0; i < N_SNAKES; i++) {
        sem_init(wr+i, 0, 0);   
    }
    /* Il semaforo "rd" è inizializzato a 0 dal momento che nessun carattere
     * è stato inviato da un serpente ad un altro. */
    sem_init(&rd, 0, 0);
}

void destroy_sem() {
    /* Distruggi i vari semafori. */
    for (int i = 0; i < N_SNAKES; i++) {
        sem_destroy(wr+i);
    }
    sem_destroy(&rd);
}

void invia_char(int id, char c) {
    /* Salva il carattere da inviare. */
    ch = c;
    /* Notifica allo snake "id" che è disponibile un carattere da leggere. */
    sem_post(wr+id);
}

char leggi_char(int id) {
    /* Attendi che sia disponibile un carattere per lo snake "id". */
    sem_wait(wr+id);
    /* Restituisci il carattere ricevuto. */
    return ch;
}

void attendi_lettura(int id) {
    /* Attendi che lo snake "id" con cui ci si è scontrati legga il
     * carattere inviato. */
    sem_wait(&rd);
}

void fatta_lettura(int id) {
    /* Notifica l'avvenuta lettura allo snake con cui ci si è scontrati. */
    sem_post(&rd);
}