La verifica consiste nell’implementazione di un monitor CodaPoste per la sincronizzazione di un certo numero di thread Persone. I thread Persone rappresentano gli utenti di un ufficio postale con N_SPORTELLI sportelli. La coda di attesa agli sportelli è unica: le persone si mettono in fila e quando è il loro turno vanno al primo sportello libero.
Un thread Persona si comporta come segue:
Thread Persona {
while( in coda ) {
// si muove in coda
p.move(x, y, newx, newy); // si muove da x,y a newx,newy
}
// attendi il primo sportello libero e lo occupa
sportello = p.attendiSportello();
while( non hai raggiunto lo sportello ) {
p.move(x, y, newx, newy); // si muove da x,y a newx,newy
}
// attendi di essere servito (sleep)
// libera lo sportello
p.liberaSportello(sportello);
// esce dall'ufficio postale
p.libera(x, y);
}
I metodi del monitor che dovete implementare sono i seguenti:
// si muove da x,y a nx,ny. Se nx,ny è occupato attende altrimenti
// occupa nx,ny e libera x,y.
public synchronized void move(int x, int y, int nx, int ny) throws InterruptedException {
}
// libera la posizione x,y (invocata quando l'utente esce dall'ufficio)
public synchronized void libera(int x, int y) {
}
// La persona è la prossima ad essere servita e attende che si liberi uno sportello.
// Nel caso ci sia almeno uno sportello libero, occupa il primo disponibile e ne
// ritorna l'indice.
public synchronized int attendiSportello() throws InterruptedException {
return 0; // da modificare opportunamente
}
// La persona ha raggiunto lo sportello, ha fruito del servizio e ora lo libera
public synchronized void liberaSportello(int id) {
}
Scaricate la verifica da qui e modificate il file CodaPoste.java. Per compilare ed eseguire il programma, usate i seguenti comandi:
> javac Poste.java
> java Poste
NOTA BENE
Consegnate solo il file CodaPoste.java;
Commentate in maniera appropriata il vostro programma: in particolare, inserite un commento iniziale in cui spiegate l’idea risolutiva. Soluzioni non commentate NON saranno valutate.
/*
* COMMENTO GENERALE (necessario per la sufficienza!):
*
* - Come si è arrivati a scegliere le strutture dati utilizzate per la
* sincronizzazione
*
* Per la sincronizzazione utilizziamo:
*
* 1. una matrice 'persona' di dimensione X, Y per gestire la mutua esclusione sulla
* posizione fisica nell'ufficio (di fatto è una matrice di mutex). La matrice
* è inizializzata a false per indicare che le posizioni sono sono tutte libere;
*
* 2. un array 'occupato' di dimensione N_SPORTELLI che tiene traccia dello stato di
* occupazione degli sportelli. L'array è inizializzato a false per indicare
* che gli sportelli sono tutti liberi.
*
* - Come funziona, intuitivamente, la sincronizzazione
*
* La funzione 'move' è bloccante se la posizione nx,ny da raggiungere è occupata
* ovvero se persona[nx][ny] è true. Se la posizione è libera viene occupata
* ponendo persona[nx][ny] a true e liberando la precedente x,y tramite la funzione
* libera(x,y).
*
* la funzione 'attendiSportello' è bloccante se non ci sono sportelli liberi,
* ovvero se occupato[x] è false per ogni sportello x. Questo test viene fatto
* dalla funzione accessoria 'nlibero' che ritorna l'indice del primo sportello
* libero o ritorna -1 se gli sportelli sono tutti occupati. Lo sportello libero
* l viene occupato ponendo a true occupato[l] e viene poi liberato nella funzione
* 'liberaSportello'.
*
* - Come sono state utilizzate le wait e le notify / notifyAll
*
* Le wait vengono usate in 'move' e 'attendiSportello' nel caso che,
* rispettivamente, la posizione nx,ny sia occupata ( persona[nx][ny] ) e
* gli sportelli siano tutti occupati ( nlibero() == -1 ). Poiché
* abbiamo diverse situazioni di bloccaggio, utilizziamo la notifyAll per
* sbloccare i thread, nelle funzioni 'libera' e 'liberaSportello'.
* Tali funzioni liberano, rispettivamente, una posizione o uno
* sportello. Le wait sono racchiuse in un while in modo da riverificare
* la condizione di bloccaggio. Se venisse sbloccato erroneamente un thread
* questo non sarebbe un problema perché si ribloccherebbe autonomamente.
*
*/
public class CodaPoste {
private int X, Y; // dimensioni dell'ufficio
private int N_SPORTELLI; // numero di sportelli
private boolean[][] persona; // mutex per le persone che si muovono nell'ufficio
private boolean[] occupato; // sportello occupato
public CodaPoste(int x, int y, int sportelli) {
this.X = x;
this.Y = y;
this.N_SPORTELLI = sportelli;
// inizialmente non ci sono persone (false)
persona = new boolean[X][Y];
// inizialmente gli sportelli sono liberi (false)
occupato = new boolean[N_SPORTELLI];
}
// si muove da x,y a nx,ny. Se nx,ny è occupato attende altrimenti
// occupa nx,ny e libera x,y.
public synchronized void move(int x, int y, int nx, int ny)
throws InterruptedException {
while (persona[nx][ny])
wait(); // attende se c'è una persona in nx,ny
// acquisisce la nuova posizione nell'ufficio postale
persona[nx][ny] = true;
// libera la posizione vecchia
libera(x,y);
}
// libera la posizione x,y (invocata quando l'utente esce dall'ufficio)
public synchronized void libera(int x, int y) {
// rilascia la posizione vecchia
persona[x][y] = false;
// notifica eventuali thread in attesa della posizione x,y
notifyAll();
}
// funzione accessoria privata. Ritorna l'indice del primo sportello libero.
// Ritorna -1 se tutti occupati.
synchronized int nlibero() {
int i;
for(i=0;i<N_SPORTELLI;i++) {
if (!occupato[i]) return i; // lo sportello i è libero
}
return -1; // nessuno sportello libero, ritorna -1
}
// La persona è la prossima ad essere servita e attende che si liberi
// uno sportello. Nel caso ci sia almeno uno sportello libero, occupa
// il primo disponibile e ne ritorna l'indice.
public synchronized int attendiSportello() throws InterruptedException {
int l;
while( (l=nlibero()) == -1)
wait(); // attende se gli sportelli sono tutti occupati
occupato[l]=true; // occupa lo sportello
return l; // ritorna lo sportello appena occupato
}
// La persona ha raggiunto lo sportello, ha fruito del servizio e ora
// lo libera
public synchronized void liberaSportello(int id) {
// libera lo sportello
occupato[id]=false;
// notifica eventuali thread in attesa degli sportelli
notifyAll();
}
}
