MokaByte Numero 20 - Giugno 1998
		Introduzione alla  programmazione concorrente in Java
	di  Massimo Carli	L

Delle due puntate precedenti abbiamo introdotto i concetti fondamentali di programmazione concorrente e risolto il problema del "piatto di spaghetti" utilizzando il costrutto dei semafori binari.
Questo mese affronteremo il classico problema dei "cinque filosofi pensanti" che ci permetterà di venire a contatto per la prima volta con problemi di blocco critico ed individuale.
La risoluzione di questo classico problema di programmazione concorrente, permetterà inoltre di introdurre il costrutto di Monitor. L'articolo si concluderà con l'applicazione dei risultati ottenuti al problema di cucinare, nel modo più efficiente possibile, il maggior numero di spaghetti al sugo contemporaneamente.

Il problema dei cinque filosofi
Il problema dei cinque filosofi è un classico problema di condivisione delle risorse tipico di un sistema operativo in cui esistono più processi che in continuazione, acquisiscono usano e rilasciano un insieme di risorse condivise, quali possono essere una stampante, una particolare locazione di memoria o il disco in scrittura.
Quando si ha a che fare con l'acquisizione di risorse esclusive (il cui uso, in un determinato momento, può essere fatto solamente da un singolo thread) si può incorrere in una situazione di stallo che si indica con il termine di blocco critico. Si parla di blocco critico quando si verifica una situazione tale per cui nessun thread è in grado di proseguire; questo si verifica, per esempio, se si hanno due thread ciascuno dei quali possiede la risorsa che è necessaria all'altro e non è stata adottata una politica di rilascio della risorsa da parte di uno dei due thread. Per blocco critico individuale intendiamo, invece, il caso in cui un particolare processo non riesca mai ad ottenere le risorse di cui ha bisogno e quindi non riesca mai a progredire.

Vediamo meglio di cosa si tratta.
Nell'antica Cina esistevano cinque filosofi che non facevano altro che pensare e mangiare. I cinque filosofi sono sempre seduti attorno ad un tavolo rotondo nel cui centro vi è un piatto di riso, sempre colmo e caldo (risorsa illimitata). Ogni filosofo passa il suo tempo a pensare e, quando per lo sforzo profuso gli viene fame, inizia a mangiare. Per mangiare ha bisogno di due bastoncini. Sul tavolo esistono cinque bastoncini che si alternano ai filosofi in modo che ogni filosofo abbia un bastoncino alla sua destra ed uno alla sua sinistra.
È evidente che per poter mangiare, un filosofo si deve impossessare di entrambi i bastoncini e che mai più di due filosofi mangeranno contemporaneamente. Ogni filosofo rappresenta un thread che esegue all'infinito le operazioni relative a mangiare e pensare. In questo caso creeremo una classe astratta in quanto modificheremo il metodo gestione_risorse() in modo relativo alla tecnica che sceglieremo per l'acquisizione delle risorse: i bastoncini (Listato 1).
Abbiamo detto che ogni filosofo si deve impossessare di entrambi i bastoncini per mangiare e che, ovviamente, un bastoncino non può essere contemporaneamente di due filosofi che quindi se lo contendono (risorsa condivisa). Dovremo trovare un meccanismo tale per cui se il bastoncino non è libero, il filosofo che lo pretendeva dovrà aspettare. Questo è il tipico problema di sincronizzazione che si può risolvere, almeno in parte, con lo strumento visto il mese scorso: il semaforo binario.

Risoluzione con semaforo binario
Proviamo ad associare a ciascuna risorsa, cioè a ciascun bastoncino, un semaforo. In questo modo per acquisire il bastoncino basterà eseguire una P() sul semaforo associato. Se esso è disponibile, acquisiremo il bastoncino, in caso contrario attenderemo che esso si renda disponibile (ovvero che il filosofo che se ne è impossessato, lo rilasci).

Le azioni che il filosofo dovrà fare, che definiremo nel metodo gestione_risorse(), saranno quindi le seguenti:
 

1. Il filosofo pensa
2. Il filosofo prende il bastoncino a destra
3. Il filosofo prende il bastoncino a sinistra
4. Il filosofo mangia
5. Il filosofo rilascia il bastoncino destro
6. Il filosofo rilascia il bastoncino sinistro

Notiamo come le risorse (i bastoncini) siano state rappresentate da un array di 5 semafori binari (oggetti Semaforo del mese scorso). Se un filosofo è nella posizione n il bastoncino alla sua sinistra sarà quello nella posizione n mentre quello alla sua destra sarò quello nella posizione (n+1) mod 5 in quanto dobbiamo gestire il fatto che il tavolo è rotondo.

Notiamo poi come sia stata introdotta una certa casualità nei periodi in cui il filosofo pensa e mangia attraverso le istruzioni:

try{
   Thread.sleep(1000);
}
catch(InterruptedException ie){}

Queste poche righe sono spesso utilizzate per regolare la velocità con cui sono visualizzati i frame di una animazione. Non ci resta che verificarne il comportamento attraverso la semplice applicazione ProvaFilosofoSemaforo (Listato 3). Eseguendo l'applicazione si nota un buon funzionamento ma cosa succederebbe se tutti e cinque i filosofi prendessero il bastoncino alla loro destra e cercassero di impossessarsi di quello alla sinistra?
La politica di gestione utilizzata non permette, infatti, il rilascio di un bastoncino da parte di un filosofo per cui si verificherebbe una situazione di stallo. Il sistema, in pratica, si blocca.

Cerchiamo un'altra soluzione...
È allora evidente che, la soluzione data nel paragrafo precedente, non è la migliore.
Bisognerebbe, infatti, fare in modo che ciascun filosofo disponesse di una unica azione di acquisizione bastoncini, nella quale verificare la disponibilità di entrambi i bastoncini e solo allora impossessarsene.
Si parla di un criterio di allocazione globale delle risorse. Possiamo allora decidere di delegare l'assegnazione dei bastoncini ad un gestore che metterà a disposizione di ciascun filosofo, due metodi per l'acquisizione ed il rilascio delle risorse durante l'esecuzione dei quali l'accesso alle risorse stesse è esclusivo. Bisogna evitare, infatti, che la disponibilità dei bastoncini vari nel tempo che passa dall'istante della verifica a quello dell'acquisizione: un altro processo potrebbe, infatti, "rubarle". Per ottenere lo scopo, possiamo utilizzare quello che si chiama Monitor. Esso è un costrutto sintattico che associa un insieme di procedure con una struttura dati comune (i bastoncini) a più processi (i filosofi), consentendo al compilatore di verificare che esse siano le sole operazioni permesse su quella struttura ed assicurando la loro mutua esclusione (solo un processo alla volta può accedere ad una azione del monitor). Nel contesto Java, un monitor è semplicemente una classe in cui tutti i metodi sono synchronized.
Il fatto che le azioni descritte dai metodi di tale classe siano le uniche azioni possibili sulla struttura dati dipende, ovviamente, dalla implementazione della classe. Nel caso del problema dei cinque filosofi il gestore sarà quindi quello della classe GestoreBastoncini (Listato 4).
Il primo passo consiste nella creazione di un array che contiene la situazione relativa a ciascun filosofo, ovvero il numero di bastoncini di cui potrebbe disporre. La mutua esclusione nella esecuzione di ciascun metodo è assicurata dall'utilizzo del modificatore synchronized. Il metodo acquisizione_bastoncini() consisterà nella verifica della disponibilità di entrambe le risorse.
Nel caso in cui i bastoncini non siano entrambi disponibili, il filosofo si metterà in attesa.
Nella fase di rilascio, invece, non si farà altro che modificare il numero di bastoncini disponibili e chiamare la notifyAll().
Questa volta utilizziamo la notifyAll() in quanto il rilascio da parte di un filosofo di entrambi i bastoncini potrebbe essere un evento favorevole a più processi (in questo caso al massimo due).
In conseguenza di ciò, abbiamo aggiunto un ciclo while di attesa per la condizione richiesta (la presenza di entrambi i bastoncini).
Verificando anche questa soluzione  si nota che il problema di stallo non esiste più, in quanto non si verificherà mai che un filosofo acquisisca un solo bastoncino.
Quella utilizzata è una tecnica di allocazione globale delle risorse la quale evita il blocco critico ma non quello individuale.
Potrebbe, infatti, capitare che a mangiare siano sempre gli stessi filosofi mentre gli altri non riescano mai ad impossessarsi delle risorse necessarie.
Per ovviare a questo nuovo problema si renderebbero necessarie particolari tecniche legate alla natura delle risorse.
Si potrebbe, per esempio, fare in modo che un filosofo che ha mangiato, sia escluso per un particolare lasso di tempo. Un'altra soluzione potrebbe essere una accurata gestione delle priorità da gestire in un oggetto simile al nostro gestore.

Torniamo agli spaghetti
Ci chiediamo allora se, nella soluzione data il mese scorso al problema della cottura dei piatti di spaghetti, esiste il pericolo di un blocco critico. Sicuramente non si avrà mai una situazione di stallo di tutti i processi, però non è detto che non si avrà blocco individuale.
Vediamo il perché facendo un confronto con il problema dei cinque filosofi. Lo stallo del sistema ottenuto per i filosofi è figlio di una certa simmetria del sistema.
Abbiamo cinque filosofi uguali, che pretendono risorse uguali necessarie a tutti; non esiste una sequenza nel tipo di risorse necessarie ovvero servono due bastoncini ma sono uguali. Nel caso dei cuochi le risorse sono diverse e l'acquisizione avviene in sequenza; tutti provano ad acquisire il tegamino, un cuoco se ne impossesserà e gli altri ne aspetteranno il rilascio.
Nella nostra implementazione, nessun cuoco acquisirà prima la pentola del tegamino. Ma il fatto fondamentale che assicura che non si verifichi mai stallo è che l'azione di cottura del piatto di spaghetti è stata scomposta in tre azioni per ciascuna delle quali è necessaria una unica risorsa. Supponiamo infatti di scomporre la cottura del piatto di spaghetti in due fasi:

Cuocere gli spaghetti al sugo;
Mettere il tutto nel piatto.

1. Si tornerebbe ad avere il problema iniziale di ottimizzazione della cottura dei piatti di spaghetti; avremmo un piatto alla volta. Questo sarebbe esatto da un punto di vista di programmazione in quanto otteniamo una serie di piatti di spaghetti, ma se siamo in compagnia di un amico sarebbe bene mangiarli contemporaneamente.
2. Non abbiamo uno sfruttamento adeguato delle risorse in quanto non abbiamo la necessità di usarle contemporaneamente. È importante sottolineare che la definizione di Monitor non è per niente vincolata alla allocazione globale delle risorse che ne rappresenta semplicemente un esempio. La caratteristica fondamentale di Monitor è quella di avere accesso esclusivo alla gestione di un certo numero di risorse, qualunque essa sia.

Conclusioni
Questo mese abbiamo visto i problemi di stallo che si possono verificare quando si devono gestire più risorse esclusive.
Abbiamo visto che cosa si intende per blocco critico e per blocco individuale. Il classico problema dei cinque filosofi cinesi ci ha permesso di verificare tali problemi e di studiarne alcune soluzioni. Una prima soluzione al blocco critico è sicuramente l'assegnazione globale delle risorse.
Questa è stata ottenuta attraverso un nuovo costrutto detto Monitor che funge da gestore. Esso fornisce le risorse ad un processo solamente se tutte queste risorse sono effettivamente disponibili. L'utilizzazione di un Monitor permette anche di gestire una eventuale politica di assegnazione delle risorse in modo da evitare, attraverso una opportuna gestione, anche lo stallo individuale. Il confronto tra il problema classico dei cinque filosofi ed il nostro, mette in evidenza quali siano le problematiche che si incontrano quando si devono implementare programmi multithreading. Non esiste, infatti, una regola sempre valida.
Il prossimo mese vedremo la gestione delle priorità ed implementeremo un Monitor che permette di risolvere anche l'eventuale problema di blocco individuale per i cuochi.

Bibliografia
[1] "Principi e tecniche di programmazione concorrente", ed. UTET Paolo Ancillotti, Maurelio Boari.
[2] "Introduzione al multiprocessing ed al multithreading", Dev 36 Dicembre 96, Salvatore Antonio Bello.
[3] "Concurrent Programming in Java-Design and Pattern", Doug Lea, Addison Wedsley.
[4] "Java in a NutShell", 2nd Edition D.Flanagan, O'Reilly.
[5] "Java Restaurant", F.Tisato, L.Nigro, Apogeo.
[6] "Java Threads", Scott Oaks, Henry Wong, O'Reilly.
[7] "Il problema dei cinque filosofi", Computer Programming N° 65, Gennaio 1998, Ed. Infomedia.

MokaByte Web  1998 - www.mokabyte.it  MokaByte ricerca nuovi collaboratori. Chi volesse mettersi in contatto con noi può farlo scrivendo a mokainfo@mokabyte.it