Si deve gestire la sincronizzazione di una versione multithreaded del classico robots UNIX.
Ci sono N_ROBOTS thread robots che cercano di catturare il giocatore. Il giocatore si muove su una board condivisa usando i tasti e,r,t,d,f,g,c,v,b per muoversi nelle varie direzioni. Il tasto ‘f’ è il ‘teletrasporto’. Quando il giocatore si muove tutti i robot si muovono verso di lui. I robot si distruggono quando urtano uno con l’altro (lasciando garbage ‘#’ sulla board). Lo scopo è di sopravvivere e distruggere tutti i robot facendoli urtare tra loro o contro garbage esistente.
I robot seguono il seguente schema di esecuzione:
while(1) {
robot_attendi_mossa(id);
/***************** computa la mossa ********************/
inizia_mossa();
/**** esegue la mossa modificando la board condivisa ***/
fine_mossa();
/* se la mossa fallisce il robot si 'inibisce' comportandosi come segue */
while(1) {
robot_mossa_effettuata(id);
robot_attendi_mossa(id);
}
/************** altrimenti il robot prosegue ***********/
robot_mossa_effettuata(id);
}
Il giocatore segue il seguente schema:
while(1) {
player_attendi_mossa();
/***** stampa il board e legge il comando ************/
inizia_mossa();
/**** esegue la mossa modificando la board condivisa ***/
fine_mossa();
/****** se la mossa fallisce il giocatore termina *******/
player_mossa_effettuata();
}
Si devono implementare le seguenti funzioni di sincronizzazione:
/* inizializza semafori e variabili */
inizializza() {}
/* viene invocata prima di ogni mossa */
inizia_mossa() {}
/* viene invocata dopo ogni mossa */
fine_mossa() {}
/* il robot id attende che il giocatore si muova */
robot_attendi_mossa(int id) {}
/* il robot id si è mosso, il giocatore può fare la mossa successiva */
robot_mossa_effettuata(int id) {}
/* il giocatore attende che i robot si muovano tutti */
player_attendi_mossa() {}
/* il giocatore si è mosso, possono muoversi i robots */
player_mossa_effettuata() {}
/* elimina i semafori */
chiudi() {}
Fare attenzione che
Le mosse dei robot e del giocatore modificano la board condivisa (una matrice condivisa tra tutti i thread)
Ogni mossa del giocatore causa una mossa di tutti i robot. Il giocatore non può muoversi finché tutti i robots non hanno completato la loro mossa.
Per chi finisce presto c’è una variante che viene abilitata compilando con -D EXTRA in cui i robot effettivamente terminano l’esecuzione invocando una funzione aggiuntiva robot_termina(id). Se volete realizzare questa variante aggiungete codice usando #ifdef EXTRA in modo che il codice in più venga attivato quando si compila con -D extra.
[sourcecode lang=”C”]
/******* PARTE DA CONSEGNARE ********
*
* La soluzione proposta si basa su un semaforo mutex, per proteggere
* l’accesso condiviso alla board, e su due array di semafori per
* gestire l’attesa dei robot e quella del player. L’utilizzo
* del mutex e’ quello standard per la protezione della sezione
* critica: prima di fare una mossa si acquisisce il mutex e dopo
* aver effettuato una mossa si rilascia.
*
* La sincronizzazione tra robot e player e’, di fatto, un problema
* produttore-consumatore 1-a-molti e molti-a-1: Il player deve
* attendere tutti i robot e deve poi notificarli (1-a-molti); i
* robot devono tutti attendede il player e poi notificarlo
* (molti-a-1).
*
* Utilizziamo quindi 2 array di semafori: robot_wait per i robot
* che attendono il player e player_wait per il player che attende
* i robot. Inizialmente si muove il player quindi robot_wait saranno
* rossi (0) mentre player_wait saranno verdi (1).
*
* Tutte le volte che il player si deve muovere fa la sem_wait su
* tutti i semafori player_wait, in modo da attendere che tutti i
* robot si siano mossi. Dopo aver effettuato la mossa fa una
* sem_post su tutti i semafori robot_wait in modo da sbloccare
* tutti i robot.
*
* Tutte le volte che un robot id si deve muovere fa la sem_wait sul
* proprio semaforo robot_wait[id], in modo da attendede che il
* player si sia mosso. Dopo aver effettuato la mossa fa una
* sem_post sul proprio semaforo player_wait[id] in modo da
* sbloccare il player.
*/
sem_t mutex; // mutex per proteggere la board condivisa
// array di semafori per l’attesa dei robot
sem_t robot_wait[N_ROBOTS];
// array di semafori per l’attesa del giocatore
sem_t player_wait[N_ROBOTS];
// array che indica la terminazione dei robot
#ifdef EXTRA
int terminato[N_ROBOTS];
#endif
/* inizializza semafori e variabili */
void inizializza() {
int i;
sem_init(&mutex,0,1); // mutex ininzializzato a 1
for (i=0;i<N_ROBOTS;i++) {
// inizialmente i robot attendono (semafori rossi)
sem_init(&robot_wait[i],0,0);
// inizialmente il giocatore può moversi (smeafori verdi)
sem_init(&player_wait[i],0,1);
}
#ifdef EXTRA
for (i=0;i<N_ROBOTS;i++)
// i robot devono tutti terminare
terminato[i] = 0; // false
#endif
}
/* viene invocata prima di ogni mossa */
void inizia_mossa() {
sem_wait(&mutex); // entra in sezione critica
}
/* viene invocata dopo ogni mossa */
void fine_mossa() {
sem_post(&mutex); // esce dalla sezione critica
}
#ifdef EXTRA
void robot_termina(int id) {
// il robot id termina, ne teniamo traccia
// non serve sezione critica perché ogni robot
// aggiorna la propra variabile terminato[id]
terminato[id] = 1;
}
#endif
/* il robot id attende che il giocatore si muova */
void robot_attendi_mossa(int id) {
// attende sul proprio semaforo robot_wait[id]
sem_wait(&robot_wait[id]);
}
/* il robot id si è mosso, il giocatore può fare la mossa successiva */
void robot_mossa_effettuata(int id) {
// notifica di essersi mosso sul proprio semaforo
// player_wait[id]
sem_post(&player_wait[id]);
}
/* il giocatore attende che i robot si muovano tutti */
void player_attendi_mossa() {
int i;
// attende che tutti i robot si siano mossi
for (i=0;i<N_ROBOTS;i++)
#ifdef EXTRA
// se il robot è ancora attivo …
if (!terminato[i])
#endif
// il giocatore attende che il robot i si sia mosso
sem_wait(&player_wait[i]);
}
/* il giocatore si e’ mosso, possono muoversi i robots */
void player_mossa_effettuata() {
int i;
// concede a tutti i robot di muoversi
for (i=0;i<N_ROBOTS;i++)
// sblocca il robot i-esimo
sem_post(&robot_wait[i]);
}
/* elimina i semafori */
void chiudi() {
int i;
// elimina il mutex
sem_destroy(&mutex);
// elimina robot_wait e player_wait
for (i=0;i<N_ROBOTS;i++) {
sem_destroy(&robot_wait[i]);
sem_destroy(&player_wait[i]);
}
}
/******** FINE PARTE DA CONSEGNARE ********/
