[monitor] Pedaggio in autostrada

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

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;
    }
}