La verifica consiste nell’implementazione di un monitor Pedaggio per la sincronizzazione di un certo numero di thread Auto e Casello. I thread Auto rappresentano delle automobili in uscita dall’autostrada e i thread Casello rappresentano dei dispositivi di pagamento automatico presso i quali pagare il pedaggio autostradale.
Un casello è identificato da un id intero compreso tra 0 e NTOLLS-1 (dove NTOLLS è il numero totale di caselli presenti nell’autostrada). Ciascun thread Casello si comporta secondo il seguente schema, dove p è l’istanza del monitor Pedaggio e FEE è una costante che rappresenta la somma da pagare al casello:
Thread Casello(id) {
while(true) {
// attende che tutta la quota sia pagata e poi dà il via libera
p.incassa(id, FEE);
}
}
Un auto si comporta come segue:
Thread Auto {
scegli casualmente il casello da raggiungere (con id idCasello)
while( non hai raggiunto il casello ) {
p.move(x, y, newx, newy); // si muove da x,y a newx,newy
}
int pagato = 0;
while (pagato < FEE) {
scegli la moneta con cui pagare (numero intero)
p.paga(idCasello, moneta);
pagato += moneta;
}
p.attendiOK(idCasello); // attende il via libera
while( non sei uscito dall'autostrada ) {
p.move(x, y, newx, newy); // si muove da x,y a newx,newy
}
p.libera(x, y);
}
I metodi del monitor da implementare sono i seguenti:
// si muove dalla posizione x,y a nx,ny. Se nx,ny è occupato attende altrimenti
// occupa nx,ny e libera x,y.
void move(int x, int y, int nx, int ny) {}
// libera la posizione x,y sulla strada (invocata quando l'auto esce definitivamente)
void libera(int x, int y) {}
// paga a idCasello un valore parziale che si accumula ai pagamenti precedenti:
// corrisponde a inserire una moneta o banconota nella macchinetta.
// Viene invocato tante volte, fino a raggiungimento della cifra corretta.
void paga(int idCasello, int parziale) {}
// Il casello 'idCasello' attende che il pagamento del totale sia avvenuto. Accumula i vari
// pagamenti parziali e esce solamente quando il totale è stato raggiunto.
// Viene invocato una volta sola e esce solo quando il totale è stato raggiunto.
// Quando il pagamento è effettuato da' il via libera all'auto.
void incassa(int idCasello, int totale) {}
// Attende l'OK dell'avenuto pagamento prima di superare il casello.
// Quando ha il via libera procede.
void attendiOK(int idCasello) {}
Scaricate il codice da qui e modificate il file Pedaggio.java. Per compilare ed eseguire il programma, usate i seguenti comandi:
> javac Casello.java > java Casello
Visualizza la soluzione
Soluzione
Una possibile soluzione commentata della verifica è la seguente:
/*
* La verifica consiste nell'implementazione di un monitor Pedaggio che deve
* occuparsi di:
* - sincronizzare il movimento delle auto in maniera tale che non si
* verifichino incidenti
* - sincronizzare caselli e automobili in maniera tale che un auto non
* possa superare un casello fino a quando non ha pagato per intero il
* pedaggio e la sbarra del casello non è stata sollevata in modo da
* permettere il passaggio dell'auto.
*
* Per implementare questo schema utilizziamo le seguenti variabili:
* - 'occupato': matrice di booleani di dimensione pari alla dimensione
* dello schermo. Viene usata per tenere traccia della posizione delle
* automobili nella strada. La variabile 'occupato[x][y]' è true se la
* posizione (x, y) è occupata da un'automobile, false altrimenti.
* - 'pedaggi': vettore di interi di dimensione pari al numero di caselli
* presenti nell'autostrada. Viene usato per tenere traccia dei pagamenti
* parziali effettuati dalle automobili ai caselli.
* - 'viaLibera': vettore di booleani di dimensione pari al numero di caselli
* presenti nell'autostrada. Viene usato per gestire l'attesa del via
* libera da parte del casello per il passaggio delle auto. La variabile
* 'viaLibera[id]' è true se la sbarra del casello id è alzata (quindi
* l'auto in attesa presso quel casello può passare), false altrimenti.
*/
public class Pedaggio {
private boolean occupato[][];
private int pedaggi[];
private boolean viaLibera[];
public Pedaggio(int x, int y, int ntolls) {
/* NB: in mancanza di inizializzazione esplicita, Java inizializza di
* default le variabili booleane a true e quelle intere a 0. */
/* Tutte le posizioni della strada sono inizialmente libere, quindi
* la matrice è inizializzata a false. */
occupato = new boolean[x][y];
/* Inizialmente non è stato effettuato alcun pagamento, quindi tutti
* i pedaggi parziali sono pari a 0. */
pedaggi = new int[ntolls];
/* Nessun pagamento è stato effettuato, pertanto tutte le sbarre dei
* caselli sono abbassate. */
viaLibera = new boolean[ntolls];
}
public synchronized void move(int x, int y, int nx, int ny) throws InterruptedException {
/* Attendi se la posizione in cui ci si vuole spostare è occupata. */
while (occupato[nx][ny]) {
wait();
}
/* La posizione (nx, ny) ora è occupata. */
occupato[nx][ny] = true;
/* Libera la posizione in cui si trovava l'auto in precedenza. */
libera(x, y);
}
public synchronized void libera(int x, int y) {
/* Segnala che la posizione (x, y) è libera. */
occupato[x][y] = false;
/* Notifica agli altri thread che la posizione (x, y) è libera.
* In questo modo, eventuali auto in attesa di questa posizione
* possono provare ad occuparla. */
notifyAll();
}
public synchronized void paga(int idCasello, int parziale) {
/* Incrementa il pedaggio pagato finora. Per efficienza, non facciamo
* alcuna 'notifyAll' in questo punto dal momento che non siamo
* sicuri che l'intero pedaggio sia stato pagato, bensì lo facciamo
* all'inizio della funzione 'attendiOK'. */
pedaggi[idCasello] += parziale;
}
public synchronized void incassa(int idCasello, int totale) throws InterruptedException {
/* Attendi che il pedaggio sia completamente pagato. */
while (pedaggi[idCasello] < totale) {
wait();
}
/* Azzera il pedaggio per poter processare correttamente la prossima
* macchina in coda. */
pedaggi[idCasello] = 0;
/* Alza la sbarra per permettere il passaggio alla macchina
* attualmente al casello. */
viaLibera[idCasello] = true;
/* Notifica all'automobile che la sbarra si è alzata e che dunque
* può uscire dal casello. */
notifyAll();
}
public synchronized void attendiOK(int idCasello) throws InterruptedException {
/* Notifica al casello che l'intero pedaggio è stato pagato (vedi
* commento nel metodo 'paga'). */
notifyAll();
/* Attendi che la sbarra del casello sia sollevata. */
while (!viaLibera[idCasello]) {
wait();
}
/* La sbarra si chiude immediatamente. In questo modo siamo sicuri
* di permettere il passaggio ad una macchina alla volta. */
viaLibera[idCasello] = false;
}
}