Programmazione Concorrente

		MokaByte Numero 21 - Luglio 1998

		Programmazione Concorrente
	`di` `Massimo Carli`	parte IV

Questo mese vediamo qual è la tecnica di scheduling dei processi in Java e come si possono gestire le priorità

Il mese scorso abbiamo introdotto i problemi principali che si incontrano nella realizzazione di programmi concorrenti. Abbiamo quindi definito il blocco critico ed il blocco individuale sottolineando come l'individuazione e prevenzione di tali situazioni sia piuttosto difficile e troppo legata alla specifica applicazione. Abbiamo descritto l'allocazione globale delle risorse come una possibile soluzione al blocco critico, ma non abbiamo dato soluzioni al blocco individuale.

Questo mese vedremo nel dettaglio come sia possibile assegnare a ciascun processo una priorità diversa e come la JVM (Java Virtual Machine) gestisca tali processi. Concluderemo con l'applicazione dei concetti visti all'ormai famoso problema del piatto di spaghetti.

Lo scheduling dei processi nella JVM
Una delle soluzioni date il mese scorso al problema dei cinque filosofi, consisteva nell'allocazione globale delle risorse (quella con il Monitor per intenderci). Una volta che una coppia di bastoncini veniva rilasciata, veniva eseguita una notifyAll() che sbloccava tutti thread in attesa dei bastoncini. Non veniva data, però, nessuna regola che permettesse di stabilire in modo univoco quale dei thread in attesa potesse acquisire le risorse e proseguire nell'esecuzione. Avevamo anticipato come il tutto dipendesse dalla implementazione della JVM; ora vediamo su cosa si basa effettivamente questa dipendenza.

Diciamo subito che, nelle versioni ad oggi disponibili, la JVM non prevede l'esecuzione di processi diversi su processori diversi. Ogni thread Java viene eseguito su uno stesso processore che quindi diventa risorsa condivisa e contesa. In base all'utilizzo che un thread fa del processore possiamo fare la seguente classificazione:

CPU Intensive: sono quei processi che richiedono un elevato uso della CPU per completare le azioni a loro assegnate. Essi utilizzano la CPU per calcoli ed elaborazioni matematiche che richiedono molto tempo ma non necessitano di nessuna interazione con l'utente.

I/O Intensive: sono quei processi che attendono per lunghi periodi il completamento di determinate operazioni di I/O come la lettura o scrittura su un file, la lettura di dati da socket o la comunicazione tra processi diversi.

Interactive: sono quei processi che fanno elaborazioni in risposta ad azioni dell'utente attraverso l'interfaccia grafica. Quando l'utente esegue una particolare azione, il thread entra in una situazione di CPU o I/O Intensive prima di ritornare all'attesa del comando successivo.

Un singolo programma può attraversare tutte e tre le situazioni descritte, ma lo scheduling dei processi deve essere tale da considerare maggiormente i processi CPU Intensive su un lungo periodo di tempo. Un esempio di processo CPU Intensive in Java è quello costituito dal caricamento di una immagine (anche se viene fatto per passi successivi [8]).

Java ed il multithreading
Per descrivere la gestione di default dei thread Java facciamo un piccolo esempio. Creiamo una classe (MioThread), che estende la classe java.lang.Thread, e che rappresenta dei processi che eseguono dieci volte una particolare operazione che supponiamo CPU Intensive (in questo caso stampiamo semplicemente il nome del thread ad ogni passo del ciclo). A questo punto, nel main() dell'applicazione, creiamo tre oggetti MioThread e li eseguiamo uno di seguito all'altro. Eseguendo l'applicazione non si avrà altro che una successione di righe relative a ciascun ciclo di ciascun thread. La cosa importante è però l'ordine con cui vengono stampate. Ci si aspetterebbe un ordine casuale del tipo

...
Thread 1
Thread 2
Thread 2
Thread 3
Thread 1
Thread 2
Thread 3
Thread 3
...

ed invece si ottengono semplicemente dieci righe con Thread1, poi di seguito dieci righe con Thread2 terminando con le dieci di Thread3. Questo comportamento, nel caso di processi che utilizzano in modo intensivo la CPU, non è sicuramente vantaggioso in quanto si ha pura sequenzialità nelle esecuzioni. Per comprendere cosa sia successo, è necessario esaminare qualche aspetto interno relativo alla gestione dei thread in Java. Ogni thread nella JVM può assumere uno dei seguenti quattro stati:

Initial: un thread Java sarà in questo stato negli istanti tra la sua creazione e la chiamata al metodo start().

Runnable: una volta che il metodo start() è stato chiamato, un thread Java si trova in questo stato. Esistono vari modi con cui un thread può lasciare questo stato che si può considerare comunque di default ovvero ogni metodo che non è in nessun altro stato è nello stato di Runnable

Blocked: un processo è in questo stato quando non può proseguire perché in attesa di un qualche evento che lo possa sbloccare. Caso tipico è quello relativo alla lettura di dati da un socket.

Exiting: un processo è in questo stato una volta che il suo metodo run() ha finito la sua esecuzione oppure quando è stato chiamato il suo metodo stop().

Nonostante la JVM permetta ad un solo thread di progredire in un determinato istante, nulla impedisce che più thread siano nello stato di Runnable. Quando questo accade, la JVM seleziona un processo Runnable e lo promuove facendolo diventare il thread corrente.

Tutti gli altri thread rimarranno nello stato di Runnable in attesa del loro momento. Dobbiamo però descrivere come avviene tale scelta. Java implementa uno scheduling dei processi di tipo pre-emptive basato sulle priorità. Ad ogni processo è assegnata una priorità (vedremo in seguito come) ovvero un valore intero positivo che varia tra due valori static della classe Thread: MIN_PRIORITY e MAX_PRIORITY. Quando un thread viene creato, come nell'esempio precedente, la sua priorità è pari a NORM_PRIORITY. È importante sottolineare che la priorità di un processo non sarà mai modificata dalla JVM, ma potrà essere cambiata solamente dal programmatore. Inoltre il valore della priorità è indipendente dallo stato del processo.

Questo significa che, per esempio, se un thread ha massima priorità e passa dallo stato Runnable nello stato di Blocked, nonostante non sia più il thread corrente, mantiene la sua priorità. Il valore di priorità di un processo è fondamentale in quanto la JVM assicura che in ogni istante il thread corrente sia uno dei thread nello stato di Runnable con priorità massima (in quanto scheduling basato sulle priorità). Il fatto di essere pre-emptive significa che, se in un determinato istante esiste un thread nello stato Runnable che ha priorità maggiore di quello corrente, esso viene promosso (pre-empted) sostituendo il precedente che, pur rimanendo nello stato di Runnable, non avanzerà nella esecuzione. Proviamo allora ad applicare questi concetti all'esempio precedente. Supponiamo di cambiare la priorità dei vari processi.

/**

* Questa applicazione permette di vedere come

* avviene la schedulazione di default

* dei thread java

*/

public class MioThread extends Thread {

public MioThread(String nome_thread){

super(nome_thread);

}

public void run(){

for (int i=0; i<10;i++)

System.out.println(getName());

}

public static void main(String[] str){

MioThread thread1 = new MioThread("Thread1");

thread1.start();

MioThread thread2 = new MioThread("Thread2");

thread2.setPriority(Thread.MAX_PRIORITY);

thread2.start();

MioThread thread3 = new MioThread("Thread3");

thread3.setPriority(Thread.MIN_PRIORITY);

thread3.start();

}

}

Listato 2
Esempio di utilizzo delle priorità

Notiamo come questo avvenga attraverso il metodo setPriority(int priority) della classe java.lang.Thread. L'output dell'esempio è questa volta il seguente:

Thread1
Thread2
Thread2
...

Thread2
Thread1
Thread1
...
Thread1
Thread3
Thread3
...

Infatti accade che thread1 viene creato con la priorità di default NORM_PRIORITY e viene fatto partire con il metodo start(). Di seguito viene creato thread2 a cui viene assegnata la massima priorità. Esso diviene quindi il thread corrente. Di seguito viene creato e fatto partire thread3 che, avendo la minima priorità, dovrà aspettare. Quando il thread2 termina la sua esecuzione, restano gli altri due thread nello stato Runnable. Ad avanzare sarà però thread1 che ha la priorità più alta. Il thread3 avanzerà solamente quando gli altri termineranno la loro esecuzione.

La gestione di thread di uguale priorità
Fino a qui sembrerebbe che la decisione di quale thread far avanzare da parte della JVM sia di tipo deterministico. Questo è vero se non ci sono più thread con la stessa priorità. I livelli di priorità sono dieci per cui nel caso di un numero maggiore di processi, questa situazione non è da scartare. Vediamo allora quale è il criterio di scelta da parte della JVM nel caso di thread di uguale priorità arrivando alla descrizione dei motivi per cui questo criterio possa essere differente nelle varie implementazioni della JVM in sistemi operativi diversi. La JVM memorizza al suo interno i riferimenti ai thread attraverso 13 liste concatenate. Esiste una lista dei processi nello stato Initial, una relativa allo stato Blocked, una relativa allo stato Exiting, ed altre dieci relative ad ogni priorità dei thread nello stato Runnable (Figura 1).

Figura 1 L'organizzazione in liste concatenate dei thread java nella JVM

Abbiamo già visto come la JVM promuova (pre-empt) il processo nello stato Runnable con priorità maggiore. Abbiamo però visto un solo criterio secondo cui un processo viene promosso a processo corrente: il caso in cui abbia priorità maggiore. Nel caso di processi di uguale priorità sembrerebbe che, come nel nostro esempio, l'unica possibilità sia l'attesa del cambio di stato da parte del processo stesso. Ecco che entrano in gioco le caratteristiche proprie di ciascun sistema operativo. Possiamo elencare le cause (eventi) per cui un thread nello stato di Runnable perda il privilegio di essere il thread corrente:

Quando il processo stesso perde lo stato di Runnable perché in attesa di una particolare condizione o semplicemente perché ha terminato il suo compito. In questo caso la JVM selezionerà il thread in testa alla lista dei thread nello stato Runnable di priorità maggiore.
Quando un processo di priorità più elevata entra nello stato di Runnable. È il caso dell'esempio precedente. Infatti tale thread diventa quello nello stato Runnable di priorità maggiore per cui, in base alla tecnica pre-emptive basata sulle priorità della JVM deve essere promosso.
Termine del tempo che la CPU dedica al thread. Ad ogni thread è assegnato un tempo massimo di utilizzo della CPU oltre il quale dovrà lasciare la CPU stessa ad altri thread.
L'ultimo evento è il responsabile delle possibili differenze di comportamento nelle varie implementazioni della JVM.
In molti sistemi operativi UNIX, questo tipo di evento non esiste per cui la schedulazione si può considerare deterministica come accennato in precedenza in quanto basata sui primi due tipi di eventi.
Nelle implementazioni della JVM in Window95 o NT gli eventi del terzo tipo esistono.
Provate, infatti, ad eseguire l'esempio del Listato 3.

/**

* Questa applicazione permette di vedere come

* avviene la schedulazione di default

* dei thread java

*/

public class MioThreadWIN extends Thread {

public MioThreadWIN(String nome_thread){

super(nome_thread);

}

public void run(){

for (int i=0; i<1000000;i++)

System.out.println(getName());

}

public static void main(String[] str){

MioThreadWIN thread1 = new

MioThreadWIN("Thread1");

thread1.start();

MioThreadWIN thread2 = new

MioThreadWIN("Thread2");

thread2.setPriority(Thread.MAX_PRIORITY);

thread2.start();

}

}

Listato 3
Presenza di eventi di scheduling di termine tempo di CPU in ambiente Windows

Esso è molto semplice e consiste nel creare due processi di uguale priorità che contano fino a 1000000 (nel primo esempio il conteggio fino a 10 poteva essere completato in un unico passo di utilizzo della CPU). Vedrete che talvolta il thread corrente è thread1 ed altre volte thread2 proprio a causa degli eventi di scheduling del terzo tipo descritto. La stessa applicazione in un ambiente UNIX porterebbe al termine l'esecuzione di thread1 e poi passerebbe a thread2. Se invece diamo una diversa priorità ai processi il funzionamento sarà lo stesso nei due sistemi operativi.

Il caso degli spaghetti
I concetti descritti nei paragrafi precedenti permettono di fare alcune considerazioni relative all'esempio della cottura di piatti di spaghetti al sugo. La prima osservazione riguarda il fatto che il blocco individuale non si verificherà mai (o è almeno molto improbabile) in un sistema operativo Windows 95 o NT in quanto la casualità degli eventi di termine del tempo di CPU fanno sì che prima o poi, tutti i thread riescano a progredire. Possiamo dire la stessa cosa anche in sistemi operativi in cui non esistano eventi di quel tipo. Questo per il modo con cui sono organizzate le liste dei processi Runnable. Quando un processo (cuoco) acquisisce una risorsa passa dallo stato Blocked allo stato di Runnable tornando poi allo stato di Blocked quando è in attesa della risorsa successiva. Quando questo accade, sarà promosso il thread in cima alla lista corrispondente alla priorità NORM_PRIORITY.

Il thread che ha concluso il suo passo, verrà poi messo in coda alla stessa lista. Possiamo quindi dire che, come per il blocco critico, anche il blocco individuale non riguarda il problema.

Conclusioni
Dopo aver descritto nei dettagli come avviene la gestione dei thread in Java, abbiamo visto che le soluzioni al problema degli spaghetti sono abbastanza buone relativamente alla possibilità di blocco critico ed individuale.

Abbiamo visto quali sono le possibili differenze nella gestione dei thread di analoga priorità nelle varie implementazioni della JVM. Il prossimo mese, concluderemo il corso con qualcosa di più pratico elencando vari esempi di utilizzo dei thread nelle applicazioni ed applet Java.

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 David 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 Ed. Infomedia.
[8] "Corso di elaborazione delle immagini in java", M. Carli, Mokabyte 2 e successivi http://www.mokabyte.it.
(c) 1998 Edizioni Infomedia srl

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