La seguente soluzione sincronizza correttamente i filosofi. Eseguendola più volte è possibile osservare che due filosofi possono mangiare contemporaneamente. Per forzare lo stallo è sufficiente decommentare la sleep tra la raccolta delle due bacchette (linea 29):
public class Filosofi implements Runnable {
static final int NTHREAD=5; // numero di filosofi
final int index; // indice locale del filosofo
Tavola t; // monitor condiviso
// il filosofo memorizza il proprio indice e il monitor condiviso
Filosofi(int i, Tavola t) {
index = i;
this.t = t; // memorizza il monitor condiviso
}
// il thread esegue il codiceFilosofo a meno di interruzioni
public void run() {
try {
codiceFilosofo(index);
} catch (InterruptedException e) {
System.out.println("Il filosofo "+index+" e' stato interrotto");
}
}
// il filosofo pensa e mangia come al solito
void codiceFilosofo(int index) throws InterruptedException {
while(true) {
// PENSA
System.out.println("Filosofo " + index +" pensa");
Thread.sleep(1000);
t.raccogli_sx(index); // raccoglie la bacchetta sinistra
// Decommentare per forzare lo stallo
// Thread.sleep(1000);
t.raccogli_dx(index); // raccoglie la bacchetta destra
//MANGIA
System.out.println("Filosofo " + index +" mangia");
Thread.sleep(1000);
t.deposita_sx(index); // deposita la bacchetta sinistra
t.deposita_dx(index); // deposita la bacchetta destra
}
}
public static void main(String args[]) throws InterruptedException {
int i;
Thread thread[] = new Thread[NTHREAD];
Tavola t= new Tavola(NTHREAD); // crea il monitor
// crea NTHREAD filosofi e li esegue
for(i=0;i<NTHREAD;i++) {
thread[i] = new Thread(new Filosofi(i,t));
thread[i].start();
}
// esce lasciando i filosofi al loro destino
}
}
/* monitor Tavola per la gestione delle bacchette */
class Tavola {
private boolean b[]; // le bacchette
private final int NFIL; // il numero di filosofi
// crea le NFIL bacchette e le inizializza a true (presenti)
// NOTA: non serve sincronizzarlo e' prima della creazione dei filosofi
Tavola(int i) {
int j;
NFIL=i; // memorizza il numero dei filosofi
b = new boolean[NFIL]; // crea le bacchette
for (j=0;j<NFIL;j++) // inizializza le bacchette a true
b[j] = true;
}
// raccoglie la bacchetta sinistra
synchronized void raccogli_sx(int i) throws InterruptedException {
while (!b[i]) // finche' non e' disponibile attende
wait();
// raccoglie la bacchetta
b[i]=false;
}
// raccoglie la bacchetta destra
synchronized void raccogli_dx(int i) throws InterruptedException {
raccogli_sx((i+1)%NFIL); // la dx e' sx del filosofo successivo
}
// deposita la bacchetta sinistra e notifica TUTTI i filosofi
synchronized void deposita_sx(int i) {
b[i]=true; // raccoglie la bacchetta
notifyAll(); // notifica tutti
}
// deposita la bacchetta destra e notifica TUTTI i filosofi
synchronized void deposita_dx(int i) {
deposita_sx((i+1)%NFIL); // la dx e' sx del filosofo successivo
}
}
Esercizio 2: filosofi con raccolta “atomica”
I monitor rendono semplice la realizzazione di soluzioni in cui le condizioni di bloccaggio sono complesse e non realizzabili tramite un semplice contatore (come nel caso dei semafori). Implementare i filosofi a cena con la raccolta delle bacchette atomiche. Utilizzare il seguente codice per i filosofi:
void codiceFilosofo(int index) throws InterruptedException {
while(true) {
// PENSA
System.out.println("Filosofo " + index +" pensa");
Thread.sleep(1000);
t.raccogli(index); // raccoglie atomicamente le bacchette
//MANGIA
System.out.println("Filosofo " + index +" mangia");
Thread.sleep(1000);
t.deposita(index); // deposita le bacchette
}
}
Provare a ridurre il numero dei filosofi in modo da osservare la starvation di un filosofo.
La seguente soluzione sincronizza correttamente i filosofi con la raccolta atomica delle bacchette.
Eseguendola più volte è possibile osservare che due filosofi possono mangiare contemporaneamente.
Per osservare la starvation è sufficiente ridurre il numero di filosofi NTHREAD a 4 (linea 2) e decommentare la linea 45 in modo da “sfasare” il primo filosofo rispetto ai successivi. In questo modo si osserveranno solo due filosofi (0 e 2) che mangiano e gli altri due (1 e 3) che “muoiono di fame” (to starve), letteralmente. Con 5 filosofi è più difficile che si formi starvation perché quando 0 o 2 rilasciano le bacchette potrebbero iniziare a mangiare, rispettivamente, 3 e 4, rompendo l’alternanza stretta tra 0 e 2.
public class FilosofiAtomico implements Runnable {
static final int NTHREAD=5; // numero di filosofi
final int index; // indice locale del filosofo
TavolaAtomica t; // monitor condiviso
// il filosofo memorizza il proprio indice e il monitor
FilosofiAtomico(int i, TavolaAtomica t) {
index = i;
this.t = t;
}
// il thread esegue il codiceFilosofo a meno di interruzioni
public void run() {
try {
codiceFilosofo(index);
} catch (InterruptedException e) {
System.out.println("Il filosofo "+index+" e' stato interrotto");
}
}
// il filosofo pensa e mangia come al solito
void codiceFilosofo(int index) throws InterruptedException {
while(true) {
// PENSA
System.out.println("Filosofo " + index +" pensa");
Thread.sleep(1000);
t.raccogli(index); // raccoglie atomicamente le bacchette
//MANGIA
System.out.println("Filosofo " + index +" mangia");
Thread.sleep(3000);
t.deposita(index); // deposita le bacchette
}
}
public static void main(String args[]) throws InterruptedException {
int i;
Thread thread[] = new Thread[NTHREAD];
TavolaAtomica t= new TavolaAtomica(NTHREAD); // monitor condiviso
// crea NTHREAD filosofi e li esegue
for(i=0;i<NTHREAD;i++) {
thread[i] = new Thread(new FilosofiAtomico(i,t));
thread[i].start();
/* Decommentare la linea seguente per sfasare il
* filosofo 0 rispetto ai successivi per e
* osservare la starvation
* Ridurre anche NTHREAD a 4
*/
// if (i==0) Thread.sleep(2000);
}
// esce lasciando i filosofi al loro destino
}
}
/* monitor TavolaAtomica per la gestione atomica delle bacchette */
class TavolaAtomica {
private boolean b[]; // le bacchette
private final int NFIL; // il numero di filosofi
// crea le NFIL bacchette e le inizializza a true (presenti)
// NOTA: non serve sincronizzarlo e' prima della creazione dei filosofi
TavolaAtomica(int i) {
int j;
NFIL=i; // memorizza il numero dei filosofi
b = new boolean[NFIL]; // crea le bacchette
for (j=0;j<NFIL;j++) // inizializza le bacchette a true
b[j] = true;
}
// raccoglie le bacchette in modo atomico
synchronized void raccogli(int i) throws InterruptedException {
// finche' non ci sono le due bacchette attende
while (!(b[i] && b[(i+1)%NFIL]))
wait();
// raccoglie entrambe le bacchette
b[i]=false; // deposita la bacchetta sx
b[(i+1)%NFIL] = false; // deposita la bacchetta dx
}
// deposita entrambe le bacchette e notifichiamo TUTTI i filosofi
synchronized void deposita(int i) {
b[i]=true; // deposita la bacchetta sx
b[(i+1)%NFIL] = true; // deposita la bacchetta dx
notifyAll(); // notifica tutti i filosofi
}
}
Esercizio 3: filosofi con coda esplicita
Evitare la starvation della soluzione precedente introducendo una coda in Java che implementi una politica First Come First Served (FCFS o FIFO). L’idea è che prima di un blocco while-wait il thread si accodi. Nella condizione del while controlliamo in primo luogo se il thread non è il primo della coda, e in tal caso lo blocchiamo di nuovo indipendentemente dalla condizione di attesa. Quando il thread supera il blocco while lo rimuoviamo dalla coda.
La seguente soluzione aggiunge una coda esplicita di interi private LinkedList<Integer> coda nel monitor che viene utilizzata per preservare l’ordine di arrivo ed evitare la starvation. La coda viene usata nel metodo raccogli: il filosofo viene aggiunto alla coda e attende finché non è il suo turno o non ci sono le bacchette. Appena supera il ciclo while si toglie dalla coda e procede normalmente. Quando il filosofo entra notifica tutti gli altri in modo che il primo della coda, se può, raccolga le bacchette. Le linee modificate sono evidenziate nel codice.
import java.util.LinkedList;
public class FilosofiAtomicoCoda implements Runnable {
static final int NTHREAD=4; // numero di filosofi
final int index; // indice locale del filosofo
TavolaAtomicaCoda t; // monitor condiviso
// il filosofo memorizza il proprio indice e il monitor condiviso
FilosofiAtomicoCoda(int i, TavolaAtomicaCoda t) {
index = i;
this.t = t;
}
// il thread esegue il codiceFilosofo a meno di interruzioni
public void run() {
try {
codiceFilosofo(index);
} catch (InterruptedException e) {
System.out.println("Il filosofo "+index+" e' stato interrotto");
}
}
// il filosofo pensa e mangia come al solito
void codiceFilosofo(int index) throws InterruptedException {
while(true) {
// PENSA
System.out.println("Filosofo " + index +" pensa");
Thread.sleep(1000);
t.raccogli(index); // raccoglie atomicamente le bacchette
//MANGIA
System.out.println("Filosofo " + index +" mangia");
Thread.sleep(3000);
t.deposita(index); // deposita le bacchette
}
}
public static void main(String args[]) throws InterruptedException {
int i;
Thread thread[] = new Thread[NTHREAD];
TavolaAtomicaCoda t= new TavolaAtomicaCoda(NTHREAD);
// crea NTHREAD filosofi e li esegue
for(i=0;i<NTHREAD;i++) {
thread[i] = new Thread(new FilosofiAtomicoCoda(i,t));
thread[i].start();
/* Decommentare la linea seguente per sfasare il
* filosofo 0 rispetto ai successivi per e
* osservare la starvation
* Ridurre anche NTHREAD a 4
*/
if (i==0) Thread.sleep(2000);
}
// esce lasciando i filosofi al loro destino
}
}
/* monitor TavolaAtomicaCoda per la gestione atomica delle bacchette */
class TavolaAtomicaCoda {
private boolean b[]; // le bacchette
private final int NFIL; // il numero di filosofi
private LinkedList<Integer> coda;// coda esplicita
// crea le NFIL bacchette e le inizializza a true (presenti)
// NOTA: non serve sincronizzarlo e' prima della creazione dei filosofi
TavolaAtomicaCoda(int i) {
int j;
NFIL=i; // memorizza il numero dei filosofi
b = new boolean[NFIL]; // crea le bacchette
for (j=0;j<NFIL;j++) // inizializza le bacchette a true
b[j] = true;
coda = new LinkedList<Integer>(); // crea la coda esplicita
}
// raccoglie le bacchette in modo atomico
synchronized void raccogli(int i) throws InterruptedException {
// accoda il filosofo
coda.add(i);
// finche' non è il primo della coda o non ci sono le due bacchette o attende
while (i != coda.peek() || !(b[i] && b[(i+1)%NFIL]))
wait();
// toglie il filosofo dalla coda
coda.remove();
// raccoglie entrambe le bacchette
b[i]=false; // deposita la bacchetta sx
b[(i+1)%NFIL] = false; // deposita la bacchetta dx
notifyAll(); // notifica eventuali filosofi che
// potrebbero mangiare ma non erano i primi
// della coda
}
// deposita entrambe le bacchette e notifichiamo TUTTI i filosofi
synchronized void deposita(int i) {
b[i]=true; // deposita la bacchetta sx
b[(i+1)%NFIL] = true; // deposita la bacchetta dx
notifyAll(); // notifica tutti i filosofi
}
}