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 | | | | | | | | | +----------------------------------------+
Visualizza la soluzione
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.
*
* Il problema è sostanzialmente una istanza di produttore-consumatore con
* l'unica differenza che il test sulle celle vuote viene fatto dopo aver
* scritto e quindi i semafori "vuoto" sono inizializzati a 0 (vedi la
* descrizione sotto)
* La soluzione realizzata utilizza i seguenti semafori:
* - un array di char "buffer" di dimensione "N_SNAKES" che rappresenta N_SNAKES
* buffer ognuno di dimensione 1 char. buffer[id] viene usato per inviare un
* char allo snake id.
* - un vettore di semafori "pieno" di dimensione "N_SNAKES" utilizzato dai vari
* serpenti per attendere che venga inviato loro un carattere. In particolare,
* il semaforo "pieno[id]" è verde se per lo snake di indice "id" è disponibile
* un carattere da leggere, rosso altrimenti. Il semaforo dice se buffer[id] è
* pieno.
* - un vettore di semafori "vuoto" di dimensione "N_SNAKES" utilizzato dai vari
* serpenti per attendere che il carattere inviato sia stato letto. In
* particolare, il semaforo "vuoto[id]" è verde se lo snake di indice "id" ha
* letto il carattere inviato, rosso altrimenti. Il semaforo dice se buffer[id] è
* vuoto.
* Notare che poiché attendi_lettura viene invocato per la prima volta dopo aver
* inviato il carattere, i semafori vuoto[id] devono essere inizializzati a 0.
*/
// variabili globali e semafori qui
sem_t vuoto[N_SNAKES],pieno[N_SNAKES]; // array di semafori vuoto e pieno
char buffer[N_SNAKES]; // array di char per bufferizzare il carattere
// invocato all'inizio dal thread principale prima di creare gli snake
void init_sem() {
int i;
for (i=0;i<N_SNAKES;i++) {
// i buffer sarebbero vuoti ma il semaforo viene testato solo dopo
// l'invio del carattere quindi lo inizializziamo a 0 in modo che i
// thread attendano correttamente la lettura del carattere
sem_init(&vuoto[i],0,0);
// i buffer sono vuoti quindi inizializziamo i semafori pieno a 0
sem_init(&pieno[i],0,0);
}
}
// invocato dal thread prima della terminazione del programma
void destroy_sem() {
int i;
for (i=0;i<N_SNAKES;i++) {
sem_destroy(&vuoto[i]); // elimina i semafori vuoto
sem_destroy(&pieno[i]); // elimina i semafori pieno
}
}
// invia un carattere al thread id
void invia_char(int id, char c) {
// i buffer sono inizialmente vuoti quindi è OK scriverci
buffer[id] = c; // salva il carattere nel buffer
sem_post(&pieno[id]); // notifica che il buffer è pieno e può essere letto
}
// il thread id legge un carattere (bloccante se il carattere non è stato inviato)
char leggi_char(int id) {
sem_wait(&pieno[id]); // attende che il buffer sia pieno
return buffer[id]; // legge il carattere dal buffer e lo restituisce
}
// attende che il thread id abbia letto
void attendi_lettura(int id) {
// questa wait nel produttore/consumatore viene fatta prima di scrivere.
// In questo caso, invece, la facciamo dopo, di conseguenza il semaforo è stato
// inizializzato a 0
sem_wait(&vuoto[id]); // attende che il buffer sia stato letto (vuoto)
}
// il thread id segnala che la lettura è avvenuta
void fatta_lettura(int id) {
sem_post(&vuoto[id]); // segnala che il buffer è stato letto (vuoto)
}