MokaByte Numero 18 - Aprile 1998
		Introduzione alla  programmazione concorrente in Java
	di Massimo Carli

Introduzione e concetti fondamentali

Prima di giungere alla definizione di programmazione concorrente, è bene stabilire un linguaggio comune attraverso qualche definizione.
Quando un programmatore deve risolvere un determinato problema con l'ausilio di un calcolatore, solitamente procede secondo le seguenti fasi:

1. Determina quale ruolo ha il sistema nella risoluzione del problema specificando quali sono i dati da considerare d'ingresso e quali d'uscita;
2. Determina un algoritmo che il calcolatore deve eseguire affinché dai dati d'ingresso si ottengano i dati d'uscita voluti;
3. Traduce l'algoritmo creato in un determinato linguaggio di programmazione comprensibile all'elaboratore.

int dim=array.length();
max=array[0];
for (int i=1; i<dim;i++){
    if (array[i]>max)
        max=array[i];
}// fine for

    array = {3, 4 ,8, 1 };

la storia del processo è data dal seguente grafo (Figura 1). Nell'esempio il dato d'ingresso è costituito dall'array e quello di uscita dal valore della variabile interna max.

L'algoritmo consiste nelle seguenti azioni:

1. Memorizza in dim la lunghezza dell'array.
2. Metti in max il valore contenuto nella prima posizione dell'array che per ora è anche il massimo.
3. Si inizializza un indice i di un ciclo for e si verifica che non soddisfi la condizione di fine ciclo (esaminato l'intero array).
4. Se il dato indicato dall'indice i è maggiore di quello in max allora lo si memorizza della variabile max.
5. Si incrementa i di 1 e se i< dim si ritorna al punto 4.

Il grafo di precedenza ad ordinamento totale è chiamato così perché esiste una sequenzialità obbligata tra le varie istruzioni.

In certi casi l'ordinamento totale è implicito nel problema da risolvere; molto più spesso è un'imposizione che deriva dalla natura sequenziale dell'elaboratore. Possiamo anche dire che esistono molti esempi reali di applicazioni che potrebbero, per loro natura, essere rappresentate da processi (detti processi non sequenziali) fra le cui istruzioni non esiste un ordinamento totale ma solamente parziale.

Questa volta cambiamo genere e facciamo un esempio culinario: supponiamo di avere il compilatore per un linguaggio di programmazione che dispone delle istruzioni che servono per preparare dei semplici... spaghetti al sugo.

I dati d'ingresso consistono negli ingredienti: spaghetti, acqua, sale, pomodoro, salvia. Il risultato dell'algoritmo dovrà essere un appetitoso piatto di spaghetti al sugo di pomodoro. Supponiamo di disporre di strumenti quali una pentola, un tegamino, un fornello, un piatto ed uno scolapasta. L'algoritmo sarà dato dalle seguenti azioni:

1. Mettere l'acqua nella pentola;
2. Accendere il fuoco;
3. Mettere la pentola sul fuoco;
4. Preparare il sugo;
5. Mettere il sale nell'acqua;
6. Inserire gli spaghetti nella pentola;
7. Versare il contenuto della pentola nello scolapasta;
8. Versare il contenuto dello scolapasta nel piatto;
9. Versare il sugo nel piatto.

Dal grafo risulta che certe operazioni del processo (dette talvolta eventi del processo) sono fra loro scorrelate da qualunque relazione di precedenza temporale; il che significa che il risultato dell'operazione, nel nostro caso un buon piatto di spaghetti al pomodoro, è indipendente dall'ordine con cui, alcune di esse, vengono eseguite.

Come detto il vincolo è dato dall'elaboratore che è in grado di compiere solamente una operazione alla volta. L'esecuzione di processi di calcolo non sequenziali, cioè rappresentate da un grafo di precedenza ad ordinamento parziale, richiede quindi la disponibilità di un elaboratore non sequenziale, in grado cioè di eseguire non un'operazione alla volta, ma un numero arbitrario di operazioni contemporaneamente.

I vantaggi ottenibili dall'uso di un tale elaboratore sarebbero molteplici; in particolare una maggiore efficienza di calcolo legata al grado di parallelismo ed una più naturale soluzione di tutta una gamma di problemi. Un esempio banale potrebbe essere quello del calcolo di una semplice operazione matematica del tipo:

    ris= ((a*b)+(c*d))*e

in cui il calcolo delle moltiplicazioni (a*b) e (c*d) non è legato da vincoli di precedenza, a differenza della loro somma e del prodotto per e.

Elaboratori non  sequenziali

Nel paragrafo precedente abbiamo parlato di elaboratori non sequenziali come di elaboratori in grado di eseguire processi diversi contemporaneamente. Un primo modo, il più semplice, per raggiungere lo scopo, è l'uso di un numero di processori fisici uguale al massimo numero di processi che vogliamo eseguire.

In questo modo otterremmo un elevato grado di parallelismo (tutti gli eventuali processi che richiedessero di essere eseguiti, lo sarebbero immediatamente) ma un basso sfruttamento delle risorse (negli altri istanti alcuni processori rimarrebbero inutilizzati).

Si cercano allora, sia per ovvi motivi di costi sia per ottenere un alto sfruttamento delle risorse, altre tecniche che permettano l'esecuzione parallela (almeno apparentemente) di più processi con un numero minore di processori fisici, spesso uno solo: queste tecniche si dicono di scheduling [2].

Se disponiamo di un solo processore bisognerà stabilire un criterio per scegliere quale processo eseguire e quale eventualmente interrompere; questo è compito del sistema operativo che stabilisce per ogni processo tre particolari stati:

Stato di esecuzione. Il processo dispone del processore ed è quindi in esecuzione.

Stato di pronto. Il processo non dispone del processore ma di tutte le altre risorse di cui ha bisogno, per cui attende che gli venga assegnato.

Stato di attesa. Il processo non dispone del processore ed è in attesa che si verifichino determinate condizioni (per esempio la presenza di dati su uno stream) per passare nello stato di pronto.

Quindi, una politica di schedulazione (scheduling) è il criterio che il sistema operativo adotta per scegliere il processo da promuovere nello stato di esecuzione ed eventualmente per decidere il tempo CPU da dedicare allo stesso.

Esistono diverse tecniche di scheduling che qui solo accenniamo:

Gestione in ordine di arrivo.

Quando un processo richiede al sistema operativo di essere eseguito, viene messo in una coda FIFO (First In First Out) dei processi pronti. Quando un processo termina la sua esecuzione, il processore passa allo stato di esecuzione il processo che lo seguiva nella coda. Questo tipo di scheduling non è molto efficiente in quanto vengono penalizzati i processi di breve esecuzione.

Gestione a priorità.
Esiste anche qui una coda dei processi pronti la quale viene però ordinata in modo da favorire i processi a priorità maggiore. In questa tecnica di scheduling è previsto il prerilascio del processore in quanto il processo in esecuzione deve avere priorità sempre maggiore di tutti quelli in coda; se arriva la richiesta di un processo a priorità maggiore, il precedente processo in esecuzione passa allo stato di pronto e viene inserito nella coda mentre quello nuovo viene passato nello stato di esecuzione. Questa tecnica ha il problema che eventuali processi a bassa priorità potrebbero non essere mai eseguiti. A questo problema si può ovviare aumentando, ad ogni esecuzione di un processo, la priorità dei processi in attesa nella coda.

Gestione a quanti di tempo.
Questa tecnica prevede che ad ogni processo venga assegnato un certo quanto di tempo di CPU. Essa permette l'esecuzione di tutti i processi in attesa, ma causa dei tempi persi per la commutazione di processo (la fase di passaggio dalla esecuzione di un processo a quella di un altro) e può avere un basso sfruttamento del processore.

Gestione a quanti di tempo ed a priorità.
Questa tecnica è la fusione delle precedenti due e rappresenta una possibile soluzione al problema accennato al punto precedente.

Indipendentemente dalla tecnica utilizzata dal sistema operativo per la schedulazione del processo, a noi interessa che più processi possano essere eseguiti parallelamente.

Il multithreading

Sappiamo che la gestione dei processi è delegata al sistema operativo che, secondo la politica di scheduling adottata, manda nello stato di esecuzione il processo più adatto in quel momento. In questo caso le tecniche di scheduling si riferiscono a processi che rappresentano solitamente l'esecuzione di programmi diversi.

Le stesse tecniche potrebbero essere utilizzate anche scomponendo l'esecuzione di uno stesso programma in più sottoprocessi, dotando il linguaggio utilizzato di particolari strumenti che permettano di regolarne le interazioni.

In questo nuovo contesto i sottoprocessi si chiamano thread e si parla di multithreading.

Il vantaggio principale deriva dalla possibilità di utilizzare il parallelismo all'interno di uno stesso programma semplicemente suddividendolo in due o più sottoprogrammi che, a differenza del multiprocessing, condividono lo stesso spazio di indirizzamento e delle risorse.

La differenza tra un thread ed un processo è quindi molto sottile in quanto entrambi rappresentano l'esecuzione sequenziale di istruzioni, con la differenza che i primi si riferiscono ad uno stesso programma e ne condividono le risorse.

Nell'esempio culinario possiamo suddividere il programma in tre parti:

1. Preparare il sugo
2. Cuocere gli spaghetti
3. Mettere il tutto nel piatto

Programmazione  Concorrente

Nel paragrafo precedente abbiamo scomposto la preparazione del nostro piatto di spaghetti in tre parti, in cui le prime due possono essere eseguite parallelamente mentre la terza deve attendere la conclusione delle precedenti.
Se così non fosse rischieremmo di rimanere con la fame in quanto potrebbe capitare di far bollire anche il sugo o di mettere nel piatto gli spaghetti crudi.
Da qui l'esigenza di strumenti che permettano di regolare l'interazione tra i thread; nel caso specifico fare in modo che il terzo thread attenda la conclusione degli altri due prima di diventare attivo.
Si ha quindi un problema di sincronizzazione. Supponiamo poi di dover cucinare due piatti di spaghetti e di dover eseguire due volte il programma ovvero creare due processi. Oltre ai precedenti problemi se ne aggiungerebbero di nuovi, dovuti al fatto che disponiamo di una sola pentola per cucinare gli spaghetti.
Si presenta allora un problema di condivisione delle risorse.  Il thread relativo alla cottura degli spaghetti dovrà verificare se è disponibile la pentola e quindi utilizzarla. Se la pentola non è disponibile bisognerà attendere.
Analoga cosa potrebbe capitare nel caso della preparazione del sugo disponendo di un solo tegamino. Un attento lettore potrebbe allora pensare di eseguire completamente il programma una volta di seguito all'altra in modo da evitare tutti questi problemi. Ciò è vero, anche se non si raggiungerebbe un buon risultato nel caso in cui vi fossero due amici che volessero mangiare gli spaghetti insieme.
È per questo che la visione classica secondo cui un elaboratore è essenzialmente un esecutore di algoritmi, e l'attività di sviluppo di sistemi software è quindi riconducibile alla definizione ed implementazione di algoritmi sequenziali corretti ed efficienti, mostra i suoi limiti nel momento in cui l'elaboratore non è utilizzato come un puro strumento di calcolo, ma deve interagire con l'ambiente esterno [5].
Non sempre il risultato è rappresentato dai soli dati finali ma spesso conta il momento in cui questi si rendono disponibili.
Il fatto che il sistema di elaborazione debba adeguarsi al comportamento dell'ambiente esterno ha, oltre alla necessità di sincronizzazione accennata, un'altra implicazione rilevante: la necessità di svolgere in parallelo diverse attività, rappresentate ciascuna da un algoritmo sequenziale.
Si parla allora di attività concorrenti e quindi di programmazione concorrente [3].
L'esigenza di strumenti e tecniche di questo tipo nasce dalla necessità di sincronizzare e far interagire tra loro processi la cui esecuzione si può considerare paradossalmente casuale.
Il concetto diventa più chiaro se pensiamo al problema della cottura di N piatti di spaghetti secondo l'algoritmo descritto. Il fatto di possedere un limitato numero di risorse (la pentola, il fornello, ecc.) complica moltissimo il nostro problema se interpretato in ottica non concorrente: il lettore può verificarlo provando a scrivere un algoritmo che permetta la cottura "parallela" di N piatti con gli usuali strumenti: otterremmo un algoritmo pieno di test e di cicli in cui non sapremo più raccapezzarci.
Questo succede quando si cerca di risolvere in modo deterministico un problema che deterministico non è, in quanto deve adattarsi a vincoli temporali imposti dall'ambiente; tali vincoli, nella maggior parte dei casi, sono incontrollabili e, entro certi limiti, imprevedibili.
Nel prossimo articolo introdurremo gli strumenti che permetteranno di risolvere il problema, in maniera semplice ed intuitiva.

Perché utilizzare Java?

La programmazione concorrente era inizialmente riservata ai programmatori di sistemi operativi che dovevano implementare i suddetti criteri di scheduling per la gestione dei processi.
Ora, con l'affermarsi di applicazioni client-server per Internet, diventa difficile pensare ad un linguaggio privo degli strumenti per la gestione dei Thread.
Java è un linguaggio multithreading molto semplice e fornisce gli strumenti base, come vedremo nei successivi articoli, per la programmazione concorrente.
La sua semplicità si nota immediatamente, per esempio, nella procedura di creazione di un Thread; è sufficiente estendere la classe java.lang.Thread nel seguente modo:
 

public class MioThread extends Thread {
    public MioThread(){
        super("nuovo thread");
            ...
    }// fine costruttore

    public void run(){
        // corpo del thread
    }

}// fine thread

MioThread miothread= new MioThread();
miothread.start();
...
miothread.stop();

Conclusioni
In questo primo articolo abbiamo introdotto i concetti fondamentali legati alla programmazione concorrente (algoritmo, programma e processo) e abbiamo visto come sia possibile simulare un ambiente multiprocessing attraverso una opportuna tecnica di scheduling.
Abbiamo poi visto che l'utilizzo di tecniche di programmazione concorrente si rendono necessarie quando il risultato della elaborazione di un programma, non consiste nella semplice disponibilità dei dati calcolati, ma anche nel modo e tempi con cui essi si rendono disponibili.
Nel prossimo articolo vedremo quali sono gli strumenti offerti da Java utilizzandoli per cucinare qualche piatto di spaghetti in più e meglio.

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] "Cuncurrent 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.

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