MokaByteNumero 16 - Febbraio 1998
Foto
Java e il problema
dei 5 filosofi
di 
Massimo Carli 
 Java è un linguaggio orientato al multithreading dotato di costrutti come semafori e monitor che consentono di risolvere gran parte dei problemi di gestione di risorse condivise   


 
 

La conoscenza delle tecniche relative alla programmazione concorrente non è più caratteristica dei soli programmatori di sistemi operativi, ma è divenuto bagaglio indispensabile di ogni professionista del settore. La concorrenza spinge alla creazione di programmi sempre più efficienti che sfruttano appieno le potenzialità del linguaggio utilizzato. Se poi il linguaggio è multithreaded come Java, è quasi impossibile non essere a conoscenza delle tecniche di creazione di thread e di interazione tra essi. In questo articolo utilizzeremo il tradizionale problema dei cinque filosofi pensanti come pretesto per la descrizione dei concetti fondamentali di programmazione multithreading applicati a Java.

Concetti base

Prima di passare alla descrizione del problema specifico, vediamo alcuni concetti alla base della programmazione concorrente. La prima osservazione è relativa alla distinzione tra i concetti di algoritmo e programma.
Un algoritmo consiste in un procedimento logico atto alla risoluzione di un problema attraverso un determinato sistema d'elaborazione, mentre un programma si riferisce alla descrizione dell'algoritmo attraverso un opportuno formalismo: il linguaggio di programmazione [1]. Uno stesso algoritmo può portare alla realizzazione di programmi diversi. Il processo, invece, rappresenta il procedimento di esecuzione di un programma. In un ambiente multitasking possiamo avere più processi per uno stesso programma: ad esempio più finestre dello stesso text editor nel desktop. Ogni processo dispone della propria memoria e delle proprie risorse che vengono gestite dal sistema operativo.

Il concetto di thread è molto simile e deriva dalla considerazione secondo cui se in un sistema operativo possono coesistere più processi, non si vede perché uno stesso processo non possa essere scomposto a sua volta in sottoprocessi che, questa volta, condividono lo stesso spazio di memoria e le stesse risorse.

Questi sottoprocessi prendono il nome di thread. L'esigenza di un insieme di strumenti e di tecniche per la programmazione multithreading nasce proprio dal fatto che più sottoprocessi possono disporre delle stesse risorse per cui è necessario poterne regolare l'interazione. Ecco che nascono problemi di sincronizzazione (le azioni devono essere eseguite in un particolare ordine), e di condivisione delle risorse che non portino a situazioni di deadlock (blocco irreversibile del processo). Il problema dei cinque filosofi si presenta come un buon esempio per esporre le principali tecniche utilizzate nel contesto descritto e per proporre le soluzioni più adatte.

Il problema dei cinque filosofi
Si tratta di 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.

Ovviamente si vogliono evitare situazioni di blocco critico o individuale. Per blocco critico individuale si intende la situazione per cui un particolare processo non riesce mai ad ottenere le risorse di cui ha bisogno e quindi a proseguire.

Nell'antica Cina esistevano cinque filosofi che non facevano altro che pensare e mangiare. I cinque filosofi sono sempre seduti attorno a 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 e uno alla sua sinistra. Per poter mangiare un filosofo deve impossessarsi di entrambi i bastoncini. Mai più di due filosofi mangeranno contemporaneamente.

Rappresentazione del problema

Ogni filosofo rappresenta un thread che esegue all'infinito le operazioni relative a mangiare e pensare. Una possibile rappresentazione di ciò è una classe astratta con un metodo da specializzare ad ogni istanziazione come nel codice riportato qui di seguito


 
 

Per creare un thread è sufficiente estendere la classe java.lang.Thread e definire il metodo run() come corpo del thread stesso. Java permette solamente l'ereditarietà singola, per cui nel caso in cui una classe sia già l'estensione di un'altra, sarà sufficiente implementare l'interfaccia java.lang.Runnable, che richiede la definizione del solo metodo run() e utilizzare il costruttore della classe Thread appropriato. Si è detto che ogni filosofo deve impossessarsi di entrambi i bastoncini per mangiare e ovviamente un bastoncino non può essere contemporaneamente di due filosofi (risorsa condivisa). Dovremo trovare un meccanismo per cui se il bastoncino non è libero, il filosofo che lo reclama dovrà aspettare. Questo particolare strumento si chiama semaforo binario.

Sincronizzazione in Java
Nello sviluppo di applicazioni concorrenti capita spesso che un thread, che dispone di una certa risorsa, si blocchi in attesa di particolari condizioni, per esempio che siano disponibili dati su uno stream. Per il raggiungimento di tali condizioni, è possibile che divenga indispensabile il rilascio della risorsa utilizzata fino a quel momento. Sarà poi un altro thread a risvegliare il thread bloccato. Quando un thread si impossessa di una particolare risorsa in modo esclusivo ed agisce su di essa, si dice che il thread opera in una regione critica.

La regione critica è costituita, quindi, dall'insieme delle istruzioni che sono eseguite in modo esclusivo su una particolare risorsa: un solo thread le potrà eseguire in un particolare momento. È chiaro allora che la possibilità di fermarsi in attesa di particolari condizioni debba avvenire all'interno di una regione critica. Analogamente il thread che verifica la condizione dovrà essere in una regione critica relativa alla stessa risorsa del thread che dovrà eventualmente "svegliare". Lo strumento che si utilizza in questi casi si dice semaforo binario. Supponiamo che un thread si trovi in una regione critica e che per proseguire debba attendere il verificarsi di una particolare condizione.

A tale condizione assoceremo un semaforo binario. Per indicare che il thread è in attesa su quel semaforo chiamiamo un particolare metodo che, per motivi storici, indichiamo con P() (noto anche come wait). A questo punto il thread si fermerà in corrispondenza del metodo e libererà la regione critica, ovvero la risorsa associata. Un altro thread potrà verificare la condizione attesa dal primo e, nel caso si verificasse, lo potrà risvegliare richiamando il metodo V() (noto anche come signal).

L'esecuzione di questi metodi deve essere indivisibile. Java permette di ottenere un funzionamento analogo attraverso il costrutto synchronized ed i metodi wait() e notify(). La parola chiave synchronized permette, infatti, di individuare una regione critica relativamente ad una particolare risorsa. Per esempio, nel caso di una risorsa object si ha:
 

La parola chiave synchronized si può utilizzare anche come modificatore nel caso in cui si volesse ottenere l'esecuzione di un metodo in modo esclusivo:
public synchronized void metodo(){
    // REGIONE CRITICA
}

è equivalente a

public void metodo(){
    syncronized(this){
        // REGIONE CRITICA
    }
}

in quanto il metodo deve essere eseguito in modo esclusivo relativamente all'oggetto considerato (this).
Ovviamente l'esclusività si riferisce ad una stessa istanza della classe in cui il metodo è definito. All'interno di un blocco synchronized possiamo utilizzare i metodi wait() e notify() che sono propri di ogni oggetto in quanto appartenenti alla classe java.lang.Object.
Il metodo wait() permette di bloccare un thread in attesa di una qualche condizione, mentre notify() permette di segnalare il verificarsi della stessa.
Nel caso in cui più thread eseguano la wait() su una stessa risorsa, e venga poi eseguita una notify(), le specifiche Java non definiscono quale thread venga effettivamente svegliato.
Questo dipende dall'implementazione della Java Virtual Machine e dalle tecniche di scheduling e di temporizzazione utilizzate. Va segnalato anche il metodo notifyAll() il quale risveglia tutti i thread che hanno eseguito una wait() sulla stessa risorsa. Come vedremo in seguito la notifyAll() permetterà di scegliere il criterio di risveglio attraverso opportuni test.

Un semaforo binario in Java
Caratteristica fondamentale delle operazioni V e P è l'atomicità o indivisibilità. Esse devono essere eseguite come se fossero primitive dell'ambiente. In Java ciò significa che devono essere eseguite in modo esclusivo e quindi utilizzeremo la parola chiave synchronized
 
 
 
 


 
 
 

Per rappresentare lo stato del semaforo, utilizziamo una variabile intera. Se essa è a 0 significa che il semaforo è rosso e quindi se un thread esegue una P() su di esso, si bloccherà. Se il valore di stato è 1 allora il semaforo è verde per cui uno dei thread bloccati (che aveva eseguito una P), potrà proseguire. Ovviamente, più thread si possono bloccare sullo stesso semaforo. A tale scopo utilizzeremo una variabile intera, num_attesa, che memorizza il numero di processi in attesa sul semaforo rosso (vedi listato 2). Inizialmente il valore dello stato è 1 ed il numero di thread in attesa è 0. Se facciamo una P sul semaforo, esso è verde (stato=1) per cui possiamo proseguire. Da questo momento in poi il semaforo, però, diventa rosso (stato=0). Se un altro thread esegue la P sullo stesso semaforo rimarrà bloccato. Affinché uno dei thread in attesa possa proseguire è necessario che venga chiamata la funzione V sul semaforo. Al suo interno avviene l'esecuzione del metodo notify() che permette il risveglio di un thread in attesa (se ne esistono).

Una prima soluzione al problema
Nel paragrafo precedente abbiamo definito e costruito un semaforo binario che vogliamo ora utilizzare per risolvere il problema iniziale. 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 è disponibile acquisiremo il bastoncino, altrimenti attenderemo che 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:

L'acquisizione corrisponde a una P sul semaforo associato mentre il rilascio corrisponde alla V. Le risorse (i bastoncini) sono state rappresentate da un array di 5 semafori binari. 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 (bisogna 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. A questo punto non resta che verificare quanto accade con il programma ProvaFilosofoSemaforo, visibile nel listato qui di seguito
 

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.

Un'altra soluzione

La soluzione suggerita, quindi, 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 se ne impossessasse. Possiamo allora decidere di delegare l'assegnazione dei bastoncini ad un gestore che metterà a disposizione di ciascun filosofo, due metodi per l'acquisizione e 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 5).


 

Implementare un costrutto monitor

Il primo passo consiste nella creazione di un array che contenga la situazione relativa a ciascun filosofo, ovvero il numero di bastoncini di cui potrebbe disporre. La mutua esclusione nell'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() (listato 6).
 

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 più 2). In conseguenza di ciò, abbiamo aggiunto un ciclo while di attesa per la condizione richiesta (la presenza di entrambi i bastoncini).
Verifichiamo anche questa soluzione, e notiamo che il problema di stallo non esiste più, visto che non sarà più possibile che un filosofo acquisisca un solo bastoncino.
 

Quella utilizzata è una tecnica di allocazione globale delle risorse che evita il blocco critico ma non quello individuale. Potrebbe, infatti, capitare che a mangiare siano sempre gli stessi filosofi mentre gli altri non riescono 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 un'accurata gestione delle priorità da stabilire in un oggetto simile al nostro gestore.

Conclusioni

Il classico problema dei cinque filosofi ha permesso di introdurre quelli che sono gli strumenti (semafori e monitor) più importanti nella gestione dei thread e di applicarli ad un particolare linguaggio: Java.
È stato anche evidenziato il fatto di come una particolare tecnica, giudicata buona sotto certi aspetti (evita il blocco critico), si possa rivelare carente sotto altri (blocco individuale).
Purtroppo la determinazione della possibilità di blocco critico ed individuale è cosa molto più complicata e necessita di algoritmi molto complessi, la cui trattazione esula dagli scopi di questo articolo.

Bibliografia

[1] Paolo Ancillotti, Maurelio Boari, "Principi e tecniche di programmazione concorrente", UTET.
[2] Salvatore Antonio Bello, "Introduzione al multiprocessing ed al multithreading", DEV, Dicembre 96.
[3] Doug Lea, "Cuncurrent Programming in Java-Design and Pattern", Addison Wesley.
[4] David Flanagan, "Java in a Nutshell", II edizione, O'Reilly.
[5] F.Tisato, L.Nigro, "Java Restaurant", Apogeo.
 
 
 

MokaByte Web  1998 - www.mokabyte.it

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